시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
우리는 모두 해밍 무게 이진수의. 해밍 가중치는 이진수로 설정된 비트 / 1 초의 수입니다. 이 문제에서 1 비트 수 주어진 해밍 가중치를 찾아야합니다. 번호.
예
숫자 = 3
이진 표현 = 011
해밍 가중치 = 2
숫자 = 4
이진 표현 = 100
해밍 가중치 = 1
몇 가지 이미지 표현이 더 많은 도움이 될 것입니다.
이제 그것을 찾는 방법을 살펴 보겠습니다.
차례
접근 – 1A
브 루트 포스
무차별 대입 접근 방식은
- n % 2를 찾아 해당 위치에서 비트를 제공합니다.
- n = n / 2를 계산하여 다음 비트로 이동
예
숫자 = 5
코드를 살펴 보겠습니다.
JAVA 프로그램
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int ans=0;
while(n!=0)
{
ans=ans+(n%2);
n=n/2;
}
return ans;
}
};
C ++ 프로그램
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;
}
}
시간 복잡도 = O (n)
접근 방식 – 1B
무차별 대입이지만 더 똑똑해!
이제 우리는 간단한 접근 방식을 가지고 있습니다. 비트 조작에 대해 자세히 살펴 보겠습니다.
먼저 몇 가지 스마트 포인트로 게임 강화
- 허용되는 정수는 최대 32 비트 길이가 될 수 있습니다.
- a&1=1 1&0=0
이러한 것들을 유지하면 32 개를 반복하고 AND 연산을 수행하여 설정된 비트를 찾을 수 있습니다.
1 비트 수를위한 JAVA 프로그램
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 비트 수를위한 C ++ 프로그램
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;
}
};
시간 복잡도 = O (n)
지금까지 수집 한 많은 접근 방식은 선형입니다. 우리는 게임을 최적화하기 위해 분명히 한두 가지 똑똑한 것을 우리 고양이에 가져야합니다. 그래서, 나는 금을 발견했습니다.
접근 – 2
Brian Kernighan 알고리즘
모든 지식과 알고리즘을 익히기 전에 프로세스를 설명하겠습니다.
- n-1을 계산합니다.
- 우리와 그것은 n 즉 n & (n-1)
- 따라서 가장 오른쪽 비트 설정 해제
- 0이 될 때까지 위의 단계를 계속 반복하십시오.
number = 5하자
이진 표현 = 101
최적화
- 알고리즘은 설정된 비트 수만큼 반복됩니다.
코드 살펴보기
1 비트 수를위한 Java 프로그램
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 비트 수를위한 C ++ 프로그램
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int ans=0;
while(n!=0)
{
n=n&(n-1);
ans++;
}
return ans;
}
};
시간 복잡성 분석
각 정수에는 log (n) 비트가 있으며 최악의 경우 모든 비트를 통과합니다.
시간 복잡도 = Log (n)
이제 우리는 O (1)을 취하는 접근 방식을 어떻게 놓칠 수 있는지 속도를 높이고 있습니다.
도입
접근 – 3
고급 작업 사용
이진수가 11010011이라고 가정하겠습니다.
여기서는 비트 마스크 즉 0101,0011,00001111,00000000011111111 및 000000000000000001111111111111111을 사용하여 그림에 표시된 절차를 수행합니다.
1 비트 수를위한 JAVA 프로그램
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;
}
}
위의 접근 방식의 시간 복잡도와 공간 복잡도는 모두 O (1)로 끝납니다.
바이너리 이상을 알고 싶습니다. 튜닝!
