Hamımızın haqqında eşitmişik Hamming Çəki ikili ədədin. Hamming çəkisi, ikili ədədə qoyulmuş bit / 1s sayıdır. Bu problemdə 1 bit sayı verilmiş çəkic çəkisini tapmaq məcburiyyətindəyik nömrə.
Nümunələr
Sayı = 3
İkili nümayəndəlik = 011
Hamming çəkisi = 2
Sayı = 4
İkili nümayəndəlik = 100
Hamming çəkisi = 1
Bir neçə şəkil təqdimatı daha çox kömək edəcəkdir
İndi bunu necə öyrənəcəyimizə baxaq
Mündəricat
Yanaşma - 1A
Brute Force
Kobud güc yanaşması olardı
- Bu vəziyyətdə bizə bir az vermək üçün n% 2 tapın
- Növbəti bitə keçmək üçün n = n / 2 hesablayın
misal
Sayı = 5
Kodu nəzərdən keçirək.
JAVA Proqramı
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int ans=0;
while(n!=0)
{
ans=ans+(n%2);
n=n/2;
}
return ans;
}
};
C ++ Proqramı
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
int ans=0;
while(n!=0)
{
ans=ans+(n%2);
n=n/2;
}
return and;
}
}
Zamanın mürəkkəbliyi = O (n)
Yanaşma - 1B
Brute Force AMA Ağıllı!
İndi sadə bir yanaşma olduğumuza görə. Bit-Manipulyasiya baxımından daha çox nəzər salaq
Əvvəlcə oyunumuzu bir neçə ağıllı nöqtə ilə gücləndiririk
- Qəbul olunan bir ədədin maksimum 32 bit uzun ola biləcəyini bilirik
- a&1=1 1&0=0
Bu şeyləri saxlayaraq 32-dən yuxarı döngə edə bilərik və müəyyən edilmiş bitləri tapmaq üçün VƏ əməliyyatı edə bilərik
1 bit sayı üçün JAVA Proqramı
public class Solution
{
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
int ans=0;
for(int i=0;i<32;i++)
{
ans=ans+(n&1);
n=n>>1;
}
return ans;
}
}
1 bit sayı üçün C ++ proqramı
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int ans=0;
for(int i=0;i<32;i++)
{
ans=ans+(n&1);
n=n>>1;
}
return ans;
}
};
Zamanın mürəkkəbliyi = O (n)
İndiyə qədər topladığımız bir çox yanaşma xəttlidir. Pişikçəkdə oyunumuzu optimallaşdırmaq üçün mütləq bir-iki ağıllı şey olmalıdır. Beləliklə, üzümə baxaraq qızıl bir şeyə dəydim.
Yanaşma - 2
Brian Kernighan Alqoritmi
Bütün bilikli və alqoritmi əldə etmədən əvvəl bu prosesi nəzərdən keçirməyimə icazə verin
- N-1 hesablayırıq
- Biz və n ilə yəni n & (n-1) ilə
- Beləliklə, sağ tərəfdəki biti həll edin
- 0 ilə bitənə qədər yuxarıdakı addımları təkrarlayın
Sayı = 5 olsun
İkili nümayəndəlik = 101
Optimallaşdırma
- Alqoritm təyin olunmuş bit qədər təkrarlamadan keçir
Kodu nəzərdən keçirirəm
1 bit sayı üçün Java proqramı
public class Solution
{
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
int ans=0;
while(n!=0)
{
n=n&(n-1);
ans++;
}
return ans;
}
}
1 bit sayı üçün C ++ proqramı
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int ans=0;
while(n!=0)
{
n=n&(n-1);
ans++;
}
return ans;
}
};
Zamanın mürəkkəbliyini təhlil etmək
Hər bir ədədin log (n) biti var və ən pis halda bütün bitlərdən keçirik
Vaxt mürəkkəbliyi = Giriş (n)
İndi sürətləndirdiyimiz üçün O (1) alan bir yanaşmanı necə əldən verə bilərik
Təqdim
Yanaşma - 3
Ətraflı əməliyyatlardan istifadə
= 11010011 ikili sayımız olduğunu düşünək
Şəkildə göstərilən proseduru yerinə yetirmək üçün burada 0101,0011,00001111,00000000011111111 və 000000000000000001111111111111111 bitmasklarını istifadə edirik.
1 bit sayı üçün JAVA Proqramı
public class Solution
{
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
n = (n & 0x55555555) + (n >> 1 & 0x55555555); // put count of each 2 bits into those 2 bits
n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits
n = (n & 0x0F0F0F0F) + (n >> 4 & 0x0F0F0F0F); // put count of each 8 bits into those 8 bits
n = (n & 0x00FF00FF) + (n >> 8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits
n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits
return n;
}
}
Yuxarıda göstərilən yanaşmanın zaman mürəkkəbliyi və kosmik mürəkkəblik hər ikisi O (1) ilə nəticələnir.
Təkcə İkili deyil, daha çox bilmək istəyirəm. Dinlə!
