លេខបំពេញបន្ថែម Leetcode ដំណោះស្រាយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ផ្លែប៉ោម
ការរៀបចំប៊ីត ប៊ីត ក្លូដ្រា។

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានគេផ្តល់លេខគោលដប់។ គោលដៅគឺរកវា បំពេញ.

ឧទាហរណ៍

N = 15
0
N = 5
2

លេខបំពេញបន្ថែម Leetcode ដំណោះស្រាយ

វិធីសាស្រ្ត (ត្រឡប់បន្តិចម្តង ៗ )

យើងអាចត្រឡប់រាល់ beet នៅក្នុងចំនួនគត់ 'N' ដើម្បីទទួលបានការបំពេញបន្ថែមរបស់វា។ ផ្នែកសំខាន់គឺយើង មិនអាច ត្រឡប់ 32 ប៊ីតរបស់វា។ ដូចនោះនឹងមានលទ្ធផលនៅក្នុងការបំពេញគោលពីររបស់វា។ យើងត្រូវត្រឡប់ចាប់ផ្តើមពីអិល។ ប៊ី។ ប៊ី។ ទៅផ្នែកខាងឆ្វេងដែលនៅសេសសល់ក្នុងលេខ។ យើងអាចសម្រេចបានដោយបែងចែកលេខដែលបានផ្តល់ N ដោយ 1 រហូតដល់វាក្លាយជាលេខសូន្យ។ ហើយនៅពេលមានការនិយាយឡើងវិញម្តង ៗ យើងអាចត្រឡប់បន្តិចដែលត្រូវគ្នា។

ការអនុវត្តដំណោះស្រាយលេខឡេឡេលេខកូដ

កម្មវិធី 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;
}

កម្មវិធីចាវ៉ា

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

ការវិភាគភាពស្មុគស្មាញនៃដំណោះស្រាយលេខឡេឡេលេខកូដ

ស្មុគស្មាញពេលវេលា

O (log2N), ដែល N = ចំនួនគត់ដែលបានផ្តល់។ យើងបង្កើនចំនួនដងនៃចំនួនប៊ីតនៅក្នុងចំនួនដែលបានផ្តល់ឱ្យ។

ភាពស្មុគស្មាញនៃលំហ 

ឱ (១)ដូចដែលយើងប្រើតែការចងចាំថេរប៉ុណ្ណោះ។

វិធីសាស្រ្ត (ប្រសើរបំផុត)

វិធីសាស្រ្តដែលប្រសើរបំផុតគឺមិនត្រូវប្រើវាទេ បែក នៅក្នុងកូដ។ នោះគឺដើម្បីដោះស្រាយលេខកូដដោយគ្មានរង្វិលជុំឬមូលដ្ឋានគ្រឹះណាមួយការណែនាំនៃការបញ្ចោញ។ នៅក្នុងវិធីសាស្រ្តនេះដំបូងយើងរកឃើញរបាំងគោលពីរដែលមាន សំណុំប៊ីតទាំងអស់ចាប់ផ្តើមពីឯកសារ '០ ទី' បន្តិច ទៅ​ដល់ សំណុំខាងឆ្វេងបំផុត នៅក្នុងលេខដែលបានផ្តល់ហើយបន្ទាប់មក XOR វាដោយខ្លួនឯង។ នេះនឹងផ្តល់ឱ្យយើងនូវការបំពេញបន្ថែមដែលត្រូវការ។

ដើម្បីរករបាំងគោលពីរដែលត្រូវការសំរាប់អិនយើងអាចតម្រង់ឬលេខដែលមាន 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;
}

កម្មវិធីចាវ៉ា

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

ការវិភាគភាពស្មុគស្មាញនៃដំណោះស្រាយលេខឡេឡេលេខកូដ

ស្មុគស្មាញពេលវេលា

ឱ (១)ដូចជាការធ្វើប្រតិបត្ដិការលេខគោលពីរអញ្ចឹងគឺលឿនណាស់ហើយទោះបីប្រតិបត្តិការយកក៏ដោយ O (log2N), ភាពស្មុគស្មាញពេលវេលាគឺថេរសម្រាប់ចំនួនគត់ ៣២ ប៊ីត។

ភាពស្មុគស្មាញនៃលំហ 

ឱ (១)ដូចដែលយើងប្រើតែទំហំចងចាំថេរប៉ុណ្ណោះ។