رقم مكمل Leetcode الحل  


مستوى الصعوبة سهل
كثيرا ما يطلب في أجهزة آبل
خوارزميات معالجة البت بت Cloudera الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions

المشكلة بيان  

في هذه المسألة ، لدينا رقم عشري. الهدف هو العثور عليه تكملة.

مثال

N = 15

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;
}

برنامج جافا

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 صالح

تعقيد الفضاء 

يا (1)، لأننا نستخدم الذاكرة الثابتة فقط.

نهج (محسن)  

الأسلوب الأمثل هو عدم استخدام أي منها المتفرعة في الكود. بمعنى ، حل الكود بدون أي حلقات ، أو أي تعليمات تفريعية بشكل أساسي. في هذا النهج ، نجد أولاً قناعًا ثنائيًا يحتوي على كل مجموعة بتابتداء من بت "0" الى أقصى اليسار مجموعة بت في الرقم المحدد ، ثم XOR بنفسه. هذا سوف يعطينا المكمل المطلوب.

من أجل العثور على القناع الثنائي المطلوب لـ N ، فإننا نحدد البت أو الرقم المعطى مع 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;
    }
}

تحليل التعقيد لحل كود Leetcode المكمّل للأرقام

تعقيد الوقت

يا (1)، حيث أن العمليات الثنائية على مستوى البت تكون سريعة جدًا وعلى الرغم من أن العمليات تستغرق O (log2N)، التعقيد الزمني ثابت للأعداد الصحيحة 32 بت.

انظر أيضا
اللقطات المتاحة لحل Rook Leetcode

تعقيد الفضاء 

يا (1)، لأننا نستخدم مساحة ذاكرة ثابتة فقط.

1