Համարի լրացում Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են խնձոր
Բիթի մանիպուլյացիա Բիթեր Կլյուդերա

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է տասնորդական թիվ: Նպատակը `գտնել այն լրացնում.

Օրինակ

N = 15
0
N = 5
2

Համարի լրացում Leetcode լուծում

Մոտեցում

Մենք կարող ենք ամեն ինչ մատով խփել բիտ 'N' ամբողջ թվով `դրա լրացումը ստանալու համար: Կարևոր մասն այն է, որ մենք չի կարող մատով խփել իր բոլոր 32 բիթերը: Քանի որ դա կհանգեցնի իր երկուական 1-ի լրացմանը: Մեզ անհրաժեշտ է միայն LSB- ից թեքել համարի մեջ սահմանված ամենափոքր ձախ բիթը: Մենք դրան կարող ենք հասնել `տրված թիվը, N- ը բաժանելով 2-ի, մինչև այն զրո դառնա: Եվ յուրաքանչյուր կրկնության ժամանակ մենք կարող ենք համապատասխան բիթը շրջել:

Համարների լրացման լեոդ կոդերի լուծման իրականացում

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 լուծման բարդության վերլուծություն

Timeամանակի բարդություն

O (log2N), որտեղ N = տրված ամբողջ թիվ: Մենք կրկնվում ենք այնքան անգամ, որքան տրված թվի բիթերի քանակը:

Տիեզերական բարդություն 

Ո (1), քանի որ մենք օգտագործում ենք միայն մշտական ​​հիշողություն:

Մոտեցում (օպտիմիզացված)

Օպտիմիզացված մոտեցումն այն է, որ չօգտագործվի որևէ մեկը ճյուղավորելով ծածկագրում: Այսինքն ՝ կոդը լուծել առանց որևէ օղակի, կամ ըստ էության, ճյուղավորման որևէ հրահանգի: Այս մոտեցման մեջ մենք նախ գտնում ենք երկուական դիմակ, որն ունի բոլոր բիթերը դրված են, սկսած «0-րդ» բիթ դեպի ձախից սահմանված բիտը տրված թվով, ապա XOR այն իր հետ: Սա մեզ կտա պահանջվող լրացումը:

N- ի համար պահանջվող երկուական դիմակ գտնելու համար մենք bitwise ԿԱՄ տրված համարը N >> 1, N >> 2, N >> 4,… N >> 16-ով, որտեղ N >> k = աջով տեղափոխում ենք N- ն k տեղերը. Այս մեթոդով մենք բոլոր բիթերը կդնեինք ամենանշանակալից բիտից հետո (ամենաթեժ բիտը) և կտայինք պահանջվող դիմակ:

Համարների լրացման լեոդ կոդերի լուծման իրականացում

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 լուծման բարդության վերլուծություն

Timeամանակի բարդություն

Ո (1), քանի որ բիթային երկուական գործողությունները շատ արագ են, և չնայած գործողությունները տևում են O (log2N), 32-բիթանոց ամբողջ թվերի համար ժամանակի բարդությունը հաստատուն է:

Տիեզերական բարդություն 

Ո (1), քանի որ մենք օգտագործում ենք միայն հիշողության անընդհատ տարածություն: