Baza -2 LeetCode Həllinə çevirin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Airbnb Ağır LinkedInBaxılıb 51

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Baza -2 LeetCode Həllinə çevirin - Tam ədəd verilir n, qayıt bazada təmsil olunmasını göstərən ikili sətir -2.

Qeyd geri qaytarılan sətirdə başlanğıc sıfırlar olmamalıdır "0".

Input: n = 2
Output: "110"
Explantion: (-2)2 + (-2)1 = 2

Izahat

Məntiq müsbət əsas məntiqə bənzəyir. Lakin fərq qalıq mənfi olduqda.
Bunun nə üçün əhəmiyyəti var? Əsasən, qalıqlar çıxışda istifadə etdiyimiz rəqəmlər olacaq. Yəni orada mənfi ədədlər ola bilməz, elə deyilmi?

Bəs biz bununla necə məşğul ola bilərik? Məsələn: Üçün num/basebiz var num=base*q+d hara d qalıqdır və q əmsaldır. Əgər d mənfi olarsa, onu aşağıdakı kimi müsbət edə bilərik:
num=base*q-r+(d+r) hara base=-r
num=(q+1)*base+(d+r)

base2 funksiyası bazisin tam əsasıdır.

ilə son rəqəmi yoxlayın N%2 or N&1.
1 olarsa, 1 alırsınız.
0 olarsa, 0 alırsınız.

sağa sürüşdürün N >> 1.
Bu, əslində iki şeyi edir:
2.1 Son rəqəm 1 olarsa, mənfi 1.
2.2 Bölün N 2 tərəfindən.

baza -2 fərqi yoxdur,
bundan başqa bölmək lazımdır N -2 ilə.

Beləliklə, eyni şeyi edirik,
sadəcə bir işarə əlavə edin - bölündükdən sonra.

Baza 2 ədədin genişlənməsini təkrar bölmə ilə tapmaq olar 2, qalıqları qeyd edin və sonuncudan başlayaraq həmin qalıqları birləşdirin. Baza üçün fərq -2 qalıqları mənfi ola bilər. Bu halda bölməni by əlavə edirik 1 və qalanını əlavə edin 2 qalıqların müsbət olması üçün.
Budur izahat:
Qoy d quotient təmsil edir və r onda qalanı təmsil edir
n = d * (-2) + r = d * (-2) + 2 - 2 + r = (d + 1) * (-2) + (r + 2).

Kodu

-2 bazasına çevirmək üçün C++ kodu

class Solution {
public:
     string baseNeg2(int N) {
        string res = "";
        while (N) {
            res = to_string(N & 1) + res;
            N = -(N >> 1);
        }
        return res == "" ? "0" : res;
    }
};

-2 bazaya çevirmək üçün Java kodu

class Solution {
    public String baseNeg2(int N) {
       StringBuilder res = new StringBuilder();
        while (N != 0) {
            res.append(N & 1);
            N = -(N >> 1);
        }
        return res.length() > 0 ? res.reverse().toString() : "0";
    }
}

-2 bazasına çevirmək üçün Python kodu

class Solution:
     def baseNeg2(self, x):
        res = []
        while x:
            res.append(x & 1)
            x = -(x >> 1)
        return "".join(map(str, res[::-1] or [0]))

Baza -2 LeetCode Həllinə çevirmək üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O(Giriş n)

Kosmik Mürəkkəblik

O(Giriş n)

Referans: https://en.wikipedia.org/wiki/Negative_base

Crack Sistemi Dizayn Müsahibələri
Translate »