Решение за Leetcode с допълнение към номера  


Ниво на трудност Лесно
Често задавани в ябълка
алгоритми Манипулация на битове Bits Cloudera кодиране Интервю интерпретация LeetCode LeetCodeSolutions

Декларация за проблема  

В този проблем ни се дава десетично число. Целта е да се намери неговото допълнение.

Пример

N = 15

N = 5
2

Решение за Leetcode с допълнение към номера

Подход (обръщане малко по малко)  

Можем да обърнем всеки малко в цялото число 'N', за да получите неговото допълнение. Важната част е, ние не мога обърнете всичките му 32 бита. Тъй като това би довело до неговото двоично допълнение 1. Трябва само да обърнем, започвайки от LSB, до най-левия зададен бит в числото. Можем да постигнем това, като разделим даденото число, N на 2, докато стане нула. И при всяка итерация можем да обърнем съответния бит.

Внедряване на решение за допълване на номера с Leetcode

Програма C ++

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Програма Java

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}

Анализ на сложността на решението за допълнение на номера с Leetcode

Сложност във времето

O (log2N), където N = дадено цяло число. Итерираме толкова пъти, колкото е броят на битовете в дадения брой.

Вижте също
Валидно решение на Palindrome Leetcode

Сложност на пространството 

O (1), тъй като използваме само постоянна памет.

Подход (оптимизиран)  

Оптимизираният подход е да не се използва такъв разклонен в кода. Тоест, за решаване на кода без никакви цикли или някаква основна инструкция за разклоняване. При този подход първо намираме двоична маска, която има всички битове са зададени, започвайки от „0-ти“ бит към най-ляво зададен бит в дадения номер, а след това го XOR със себе си. Това ще ни даде необходимото допълнение.

За да намерим необходимата двоична маска за N, битово ИЛИ даденото число с N >> 1, N >> 2, N >> 4, ... N >> 16, където N >> k = изместване на N на k места. По този метод бихме задали всички битове след най-значимия бит (най-левия бит) и ще създадем необходимата маска.

Внедряване на решение за допълване на номера с Leetcode

Програма C ++

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Програма Java

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}

Анализ на сложността на решението за допълнение на номера с Leetcode

Сложност във времето

O (1), тъй като битовите двоични операции са много бързи и въпреки че операциите отнемат O (log2N), сложността на времето е постоянна за 32-битови цели числа.

Вижте също
Налични снимки за решението на Rook Leetcode

Сложност на пространството 

O (1), тъй като използваме само постоянно пространство в паметта.