Сан Комплект Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган алма
Bit Manipulation Bits Cloudera

Маселени билдирүү

Бул маселеде бизге ондук сан берилет. Максаты - аны табуу толуктап.

мисал

N = 15
0
N = 5
2

Сан Комплект Leetcode Solution

Ыкма (Бир аз-улам жылдыруу)

Биз ар бирин барактай алабыз бит аны толуктап алуу үчүн '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;
    }
}
0

Санды Комплементтин Leetcode Чечиминин Комплекстүүлүгүн Талдоо

Убакыт татаалдыгы

O (log2N), мында N = берилген бүтүн сан. Берилген сандагы биттердин санынан канча эсе көп кайталайбыз.

Космостун татаалдыгы 

O (1), анткени биз туруктуу эс тутумду гана колдонобуз.

Жакындоо (Оптималдаштырылган)

Оптимизацияланган ыкма - бирөөнү колдонбоо бутакташуу коддо. Башкача айтканда, кодду эч кандай циклсиз, же негизинен, кандайдыр бир тармактуу көрсөтмөлөрсүз чечүү. Бул ыкма менен, алгач экилик масканы табабыз бардык биттер коюлган, баштап '0th' бит -га сол жактагы бит берилген санда, андан кийин 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;
    }
}
0

Санды Комплементтин Leetcode Чечиминин Комплекстүүлүгүн Талдоо

Убакыт татаалдыгы

O (1), биттик экилик амалдар тез болгондуктан жана амалдар талап кылынат O (log2N), убакыттын татаалдыгы 32 биттик сандар үчүн туруктуу.

Космостун татаалдыгы 

O (1), анткени биз туруктуу эс тутумун гана колдонобуз.