배열 합
n개 요소를 포함하는 정수 배열 a가 주어지면 a에 있는 모든 요소의 합을 구합니다. 매우 간단하다고 생각할 수도 있지만, 왜 그렇게 말해야 합니까? 첫째, 이 질문에는 한 줄의 코드만 사용하여 재귀를 사용해야 합니다. 둘째, 이것은 내 인생에서 인터뷰를 하면서 처음으로 마주한 질문으로, 특별한 의미를 지닌다.
간단히 말하면 두 가지 상황이 있습니다.
배열 요소의 개수가 0이면 합은 0이 됩니다.
배열의 요소 수가 n인 경우 먼저 처음 n - 1개 요소의 합을 구한 다음 a[n - 1]를 추가합니다.
코드 복사
//Array sum
int sum(int *a, int n)
{
return n == 0 0 : sum(a, n - 1) + a[n - 1]
}
배열의 최대값과 최소값을 찾습니다.
n개의 요소를 포함하는 정수 배열 a가 주어지면 최대값과 최소값을 찾습니다. .
기존 접근 방식은 한 번 순회하여 각각 최대값과 최소값을 찾는 것이지만 여기서 이야기할 것은 분할 정복 방법(Divide and couquer) 배열을 왼쪽으로 나누는 것입니다. 그리고 오른쪽 부분을 찾아서 왼쪽 부분을 먼저 구하고, 그 부분의 최대값과 최소값을 구한 후, 그 부분을 합쳐 전체 최대값과 최소값을 구합니다. 이는 분할 후 왼쪽과 오른쪽 부분에 대해 분할된 간격에 하나 또는 두 개의 요소만 남을 때까지 이 프로세스를 반복합니다.
코드 복사 코드는 다음과 같습니다.
// 배열의 최대값과 최소값을 찾습니다. 반환값은 maxValue와 minValue 사이입니다.
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
{
if(l == r) // l과 r 사이에는 요소가 하나만 있습니다.
{
maxValue = a[l]
minValue = a[l];
return ;
}
if(l + 1 == r) // l과 r 사이에는 두 개의 요소만 있습니다.
{
if (a[l] >= a [r])
{
maxValue = a[l]
minValue = a[r]
}
else
{
maxValue = a[r] ;
minValue = a[l] ;
}
return ;
}
int m = (l + r) / ; / 중간점 찾기
int lmax; // 왼쪽 절반의 최대값
int lmin; // 왼쪽 절반의 최소값
MaxandMin(a, l, m, lmax, lmin) ; // 왼쪽 절반의 재귀 계산
int rmax ; // 오른쪽 절반의 최대값
int rmin ; // 오른쪽 절반의 최소값
MaxandMin(a, m + 1, r, rmax, rmin) ; / / 오른쪽 절반을 재귀적으로 계산
maxValue = max(lmax, rmax); // 총 최대값
minValue = min(lmin, rmin); / 전체 최소값
}
배열의 최대값과 두 번째 최대값을 찾습니다.
n개의 요소를 포함하는 정수 배열이 주어지면 해당 최대값과 두 번째 최대값을 찾습니다.
아이디어는 이전 질문과 유사합니다. 또한 분할 및 정복 방법을 사용합니다. 더 자세한 내용은 없습니다. 코드를 살펴보세요.
코드를 복사하세요.
// 배열의 최대값과 두 번째로 큰 값을 찾습니다. 반환 값은 max와 second입니다.
void MaxandMin(int *a, int left, int right, int &max, int &second)
{
if(왼쪽 == 오른쪽)
{
max = a[왼쪽] ;
두 번째 = a[왼쪽]
}
else if(왼쪽 + 1 = = 오른쪽)
{
max = a[왼쪽] > a[왼쪽] : a[오른쪽]
두 번째 = a[왼쪽] < [왼쪽] : a[오른쪽]
}
else
{
int mid = 왼쪽 + (오른쪽 - 왼쪽) / 2
int leftmax ; leftmin
MaxandMin(a, left, mid, leftmax, leftmin) ;
int rightmax
int rightmin
MaxandMin(a, mid + 1, right, rightmax, rightmin) ;
max = leftmax ? leftmax : rightmax ;
두 번째 = leftmax ? leftmax : rightmax ; 배열에서 절반 이상 나타나는 요소
주어진 a n 정수 요소의 배열 a에서 한 요소가 n / 2 번 이상 나타납니다. 바이두 면접 질문이라고 하네요.
현재 값과 현재 값의 카운터를 설정하고 현재 값을 배열의 첫 번째 요소로 초기화합니다. 카운터 값은 1입니다. 그런 다음 각 요소에 대해 두 번째 요소부터 시작하여 전체 배열을 순회합니다. 통과된 값 a[ i].
a[i]==currentValue인 경우 카운터 값이 1씩 증가합니다.
a[i] != currentValue인 경우 카운터 값은 1씩 감소합니다. 카운터 값이 0보다 작은 경우 현재 값은 a[i]로 업데이트되고 카운터 값은 1로 재설정됩니다.
코드 복사 코드는 다음과 같습니다.
//배열에서 절반 이상 나타나는 요소를 찾습니다
int Find(int* a, int n)
{
int curValue = a[0] ;
int count = 1 ;
for (int i = 1; i
또 다른 방법은 배열을 먼저 정렬한 다음 중간 요소를 가져오는 것입니다. , 요소의 수가 절반보다 크면 배열이 정렬된 후 요소가 배열의 중간 위치를 차지해야 하기 때문입니다.
배열에서 요소의 최단 거리 찾기
n개의 요소를 포함하는 정수 배열이 주어지면, 배열에서 abs(x - y)의 값을 최소화하는 두 개의 요소 x와 y를 찾습니다.
먼저 배열을 정렬한 후 한 번 반복합니다.
코드 복사 코드는 다음과 같습니다.
int Compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b
}
voidMinimumDistance(int* a, int n)
{
// Sort
qsort (a, n, sizeof(int), 비교) ;
int i ; // 숫자 1의 인덱스
int j ; >int minDistance = number_limits< ;int>::max() ;
for (int k = 0; k < n - 1; ++k)
{
if (a[k + 1] - a[k] < minDistance)
{
minDistance = a[k + 1] - a[k]
i = a[k]
j = a[k + 1 ] ;
}
}
"최소 거리: " << minDistance
"i = " << i << " j = " << endl
}
두 개의 순서가 있는 배열을 찾습니다. n개의 정렬된(내림차순) 정수 배열 a와 b 요소를 포함하는 항목은 공통 요소를 찾습니다. 예: a = 0, 1, 2, 3, 4 및 b = 1, 3, 5, 7, 9, 출력 1, 3.
배열의 순서 특성을 최대한 활용하고 두 포인터 i와 j를 사용하여 각각 a와 b를 가리키고 a[i]와 b[j]를 비교하고 비교에 따라 포인터를 이동합니다. 결과적으로 다음과 같은 세 가지 상황이 있습니다. ：
a[i] < b[j], 그러면 i가 1만큼 증가하고 비교가 계속됩니다.
a[i] == b[j] , 그러면 i와 j가 모두 1씩 증가하고 비교가 계속됩니다.
a[i]
i 또는 j가 배열의 끝에 도달할 때까지 위 과정을 반복합니다.
코드 복사 코드는 다음과 같습니다.
// 두 배열의 공통 요소 찾기
void FindCommon(int* a, int* b, int n)
{
int i = 0;
int j = 0; 🎜>++i
else if(a[i] == b[j])
{
cout i] <<
++ i
++j
else// a[i] > 🎜>}
}
이 문제에 대한 다른 해결책이 있습니다. 예를 들어, a에 n개의 요소가 있으므로 b에 있는 요소에 대해 이진 검색을 수행합니다. b에서 이진 검색을 수행하려면 로그인이 필요합니다. 따라서 동일한 요소를 모두 찾는 시간 복잡도는 O(nlogn)입니다.
또한 위 방법의 경우 b가 순서대로라면 a가 순서대로인지는 중요하지 않습니다. 왜냐하면 b에서만 이진 검색을 수행하기 때문입니다. a도 정렬된 경우 위의 방법을 사용하는 것은 약간 느립니다. 왜냐하면 b의 a에 있는 요소의 위치가 k라면 b에 있는 a의 다음 요소의 위치는 k의 오른쪽에 있어야 하기 때문입니다. 따라서 이번에는 전체를 검색하는 대신 마지막 검색 결과를 기준으로 검색 공간을 좁힐 수 있습니다. b. 즉, a와 b가 모두 정렬된 경우 다음과 같이 코드를 수정하면 마지막 검색에서 b에 있는 요소의 위치를 다음 검색의 시작점으로 기록할 수 있습니다.
세 배열의 공통 요소를 찾습니다.
n개의 요소를 포함하는 세 개의 정수 배열 a, b, c가 주어지면 가장 작은 공통 요소를 찾습니다.
세 개의 배열이 모두 정렬된 경우 세 개의 배열의 선두를 가리키도록 세 개의 포인터를 설정한 다음, 세 개의 포인터가 가리키는 값의 비교를 바탕으로 포인터를 다음 위치까지 이동할 수 있습니다. 공통 요소가 발견되었습니다.
코드 복사 코드는 다음과 같습니다.
// 세 배열의 공통 요소 - 가장 작은 배열만 찾습니다.
void FindCommonElements(int a[], int b[], int c[] , int x , int y, int z)
{
for(int i = 0, j = 0, k = 0; i < x && j < y && k < z;)
{
if(a[i] < b[j])
{
i++ ;
}
else // a[i] >= b[j]
{
if(b[j] < c[k])
{
j++
}
else // b[j] >= c[k]
{
if(c[k] < a[i])
{
k++
}
else // c[k] >= a[i]
{
cout
cout
}
}
< " 찾을 수 없습니다!" << endl ; 그리고 c에서 이진 검색을 수행합니다.
코드 복사 코드는 다음과 같습니다.
// 3개의 배열에서 고유한 공통 요소 찾기
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c , int n )
{
// 배열 a 정렬
qsort(a, n, sizeof(int), Compare) // NlogN
// 배열 b 정렬
qsort(b , n, sizeof(int), Compare) ; // NlogN
// 배열 c의 각 요소에 대해 a와 b에서 이진 검색을 수행합니다
// 이는 최대 N*2*logN
for (int i = 0; i < n; i++)
{
if(BinarySearch(a, n, c[i] ) && BinarySearch(b, n, c[i]))
return c[i] ;
return - 1 ; // 찾을 수 없음
}
a를 정렬한 다음 a에서 b와 c의 요소에 대해 이진 검색을 수행할 수도 있습니다.
코드 복사 코드는 다음과 같습니다.
// 3개의 배열에서 고유한 공통 요소 찾기
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c , int n )
{
// 배열 a 정렬
qsort(a, n, sizeof(int), Compare) // NlogN
// 시간 공간
bool *bb = new bool[n] ;
memset(bb, 0, n) ;
bool *bc = new bool[n]
memset(bb, 0, n) ;
// b의 각 요소에 대해 a에서 BS를 수행하고 모든 공통 요소를 표시합니다
for (int i = 0; i < n; i++) // NlogN
{
if (BinarySearch(a, n, b[i]))
bb[i] = true ;
}
// c의 각 요소에 대해 b인 경우에만 BS를 수행합니다. [i]는 참입니다
for (int i = 0; i < n; i++) // NlogN
{
if(b[i] && BinarySearch(a, n, c[i]) )
return c[i] ;
}
return - 1 ; // 찾을 수 없음
}
정렬 및 이진 검색 코드는 다음과 같습니다.
코드 복사 코드는 다음과 같습니다.
// a에 값 k가 포함되어 있는지 확인
bool BinarySearch(int *a, int n, int k)
{
int left = 0; >int right = n - 1;
while (왼쪽 <= 오른쪽)
{
int mid = (왼쪽 + 오른쪽)
if(a[mid] < k )
왼쪽 = mid + 1 ;
if(a[mid] == k)
return true ;
else
right = mid - 1 ; 🎜>return false
}
// qsort의 비교 함수
int Compare(const void* a, const void* b)
{
return *(int*) a - *(int*)b;
}
요약하자면 배열 검색 문제는 다음 두 가지 상황에서 처리할 수 있습니다.
주어진 배열이 정렬된 경우 , 그런 다음 이진 검색을 먼저 생각해야 하며 O(logn)이 필요합니다.
주어진 배열이 정렬되지 않은 경우 먼저 배열 정렬을 생각해야 합니다. 많은 정렬 알고리즘은 O(nlogn) 시간에 배열을 정렬한 다음 이진 검색을 사용할 수 있습니다. 총 시간 복잡도는 여전히 O(nlogn)입니다.
위의 두 가지 사항을 수행할 수 있다면 대부분의 배열 검색 문제는 쉽게 해결될 수 있습니다.
배열에서 유일한 중복 요소 찾기
1-1000 사이의 정수를 저장하는 1001개의 요소가 포함된 배열에서 1개의 정수만 중복됩니다. 이 숫자를 찾으세요.
전체 배열의 합을 구한 후 1~1000의 합을 빼는 코드입니다.
홀수 번 나타나는 요소를 찾습니다.
n개의 요소를 포함하는 정수 배열 a가 주어지고 단 하나의 요소만 홀수 번 나타나는 경우 이 요소를 찾습니다.
임의의 숫자 k에 대해 k ^ k = 0, k ^ 0 = k가 있으므로 a의 모든 요소를 XOR하면 짝수 요소의 XOR은 0이 되어 0만 남습니다. 홀수를 가진 요소.
int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;
for (int i = 1; i
찾기 배열 b의 요소 j에서 주어진 합계를 만족하는 숫자 쌍은 i + j = d를 충족합니다(d는 알려져 있음).
두 포인터 i와 j는 각각 배열의 시작과 끝을 가리킵니다. 그런 다음 두 포인터가 교차할 때까지 양쪽 끝에서 가운데로 동시에 이동합니다.
코드 복사 코드는 다음과 같습니다.
// 주어진 합을 만족하는 숫자 쌍을 찾습니다.
void FixSum(int * a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j >= 0)
{
if (a[i] + b[j] < d)
++ i
else if (a[i] + b[j] == d)
{
cout <
}
else // a[i] + b[j] > d
--j ;
}
}
하위 세그먼트의 최대 합계
정수 배열 a , 가장 큰 연속 하위 세그먼트의 합을 찾습니다. 합이 음수인 경우 1, 2, -5, 6, 8과 같이 0으로 계산되며 출력은 6 + 8 = 14입니다.
프로그래밍에 관한 고전적인 질문입니다.
코드를 복사하세요. 코드는 다음과 같습니다.
// Sub 배열의 최대 합계
int Sum(int* a, int n)
{
int curSum = 0;
int maxSum = 0
for (int i = 0; i < n; i++)
{
if (curSum + a[i] < 0)
curSum = 0;
else
{
curSum += a[i]
maxSum = max(maxSum, curSum); }
}
return maxSum
}
최대 하위 세그먼트 곱
정수 a가 주어지면 1, 2, -8, 12, 7과 같이 가장 큰 연속 하위 세그먼트의 곱을 찾습니다. 출력 12 * 7 = 84.
최대 하위 세그먼트 합계와 유사하며 음수의 경우에 주의하세요.
코드 복사 코드는 다음과 같습니다.
// 하위 배열의 최대 곱
int MaxProduct(int *a, int n)
{
int maxProduct = 1 // max; 현재 위치의 양수 곱
int minProduct = 1; // 현재 위치의 최소 음수 곱
int r = 1; // 결과, 전체 곱셈
for (int i = 0; i < n; i++)
{
if (a[i] > 0)
{
maxProduct *= a[i]
minProduct = min(minProduct * a[i) ], 1)
}
else if (a[i] == 0)
{
maxProduct = 1
minProduct = 1; / a[i ] < 0
{
int temp = maxProduct
maxProduct = max(minProduct * a[i], 1); 🎜>}
r = max(r, maxProduct);
}
return r;
}
배열 순환 이동
배열 변환 n개 요소 포함 배열을 k 비트만큼 오른쪽으로 원형 이동하려면 O(n)의 시간 복잡도가 필요하며 추가 변수는 두 개만 사용할 수 있습니다. 이것은 Microsoft의 Beauty of 프로그래밍에서 본 질문입니다.
예를 들어 배열 1 2 3 4를 1비트 오른쪽으로 회전하면 4 1 2 3이 됩니다. 1 2 3의 순서는 쉬프트 전후로 변하지 않았음을 알 수 있습니다. , 그러나 4의 위치로 바뀌었으므로 동일합니다. 먼저 1 2 3 4를 두 부분으로 나눈 다음 1 2 3 | 4, 그리고 마지막으로 전체 순서를 뒤집어서 4 1 2 3을 얻습니다.
코드 복사 코드는 다음과 같습니다.
// 버퍼의 시작과 끝 사이 요소를 반전합니다.
void Reverse( int buffer[], int start, int end )
{
while( start < end )
{
int temp = buffer[ start ] ;
buffer[ start++ ] = buffer[ end ]
buffer[ end-- ] = temp ; }
}
// n 요소를 포함하는 배열 버퍼를 k 비트만큼 오른쪽으로 이동
void Shift( int buffer[], int n, int k)
{
k %= n
Reverse( 버퍼, 0, n - k - 1)
Reverse( 버퍼, n - k, n - 1 )
Reverse( 버퍼, 0, n - 1 ) ;
}
문자열 역순
n개의 요소를 포함하는 문자 배열 a가 주어지면 이를 제자리에서 뒤집습니다.
어쩌면 이것이 배열에 관한 것이 아니라 문자열에 관한 것이라고 생각할 수도 있습니다. 예. 그러나 질문에는 내부 역순이 필요하다는 점을 잊지 마십시오. 즉, 추가 공간 할당이 허용되지 않으므로 문자열을 수정할 수 없기 때문에 매개변수는 문자 배열 형식이어야 합니다(여기서는 문자열만 있습니다). C/C++의 상수)이므로 배열과 관련이 있지만 정수 배열이 아니라 문자 배열입니다. 두 개의 포인터를 사용하여 문자 배열의 첫 번째 위치를 가리키고 해당 문자를 교환한 다음 두 포인터가 교차할 때까지 배열의 중심을 향해 이동합니다.
코드 복사
// 문자열 역순
void Reverse(char *a, int n)
{
int left = 0
int right = n - 1 ;
while(왼쪽 < 오른쪽)
{
char temp = a[left]
a[left++] = a[right]
a[ right-- ] = temp ;
}
}
조합 문제
n개의 요소를 포함하는 정수 배열 a가 주어지면 그 중에서 m개의 요소를 무작위로 선택하고 모든 조합을 찾습니다. 예를 들어 다음 예는 다음과 같습니다.
a = 1, 2, 3, 4, 5
m = 3
출력:
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5
일반적인 순열 및 조합 문제, 역추적 방법이 선호되며, 문제를 단순화하기 위해 a의 n개 요소 값을 각각 1-n으로 설정합니다.
코드 복사
//n m
int buffer[100]
void PrintArray(int *a, int n)
의 모든 조합을 선택합니다. {
for (int i = 0; i < n; ++i)
cout << a[i] <
cout <
}
bool IsValid(int lastIndex, int value)
{
for (int i = 0; i < lastIndex; i++)
{
if (buffer[ i] > ;= value)
return false;
}
return true
}
void Select(int t, int n, int m)
{
if (t == m)
PrintArray(buffer, m)
else
{
for (int i = 1; i <= n; i++)
{
버퍼 [t] = i
if (IsValid(t, i))
Select(t + 1, n, m)
}
}
}
두 개의 배열 병합
n개의 요소를 포함하는 두 개의 순서가 지정된(내림차순이 아닌) 정수 배열 a와 b가 주어졌습니다. 두 배열의 요소를 정수 배열 c로 병합하여 중복 요소를 제거하고 c를 순서대로(내림차순 아님) 유지합니다. 예는 다음과 같습니다:
a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
병합 정렬의 아이디어를 사용하면 두 포인터 i, j, k가 다음을 가리킵니다. 배열 a와 b를 비교한 다음 두 포인터에 해당하는 요소의 크기를 비교합니다. 세 가지 상황이 있습니다:
a[i]
a[i] == b[j] c[k]는 a[와 같습니다. i] 또는 b[j]가 허용됩니다.
a[i] > b[j]이면 c[k] = b[j]입니다.
i 또는 j가 배열의 끝에 도달할 때까지 위 과정을 반복한 다음 나머지 요소를 배열 c에 직접 복사합니다.
코드 복사 코드는 다음과 같습니다.
// 두 개의 순서 배열 병합
void Merge(int *a, int *b, int *c, int n)
{
int i = 0;
int j = 0;
int k = 0 ; b[j])// a의 요소가 c에 삽입됩니다. [k++] = a[i] ;
++i ;
}
else if (a[i] == b[j])// 요소 a와 b가 동일하면 다음이 가능합니다. 여기에 둘 다 삽입하세요. a
{
c[k++] = a[i ] ;
++i
++j
else // a[i ] > b[j] // b의 요소가 작으면 b의 요소를 c에 삽입합니다.
c[k++] = b[j]
++j ; >}
}
if (i == n) // if a 순회가 완료된 후 b의 나머지 요소를 처리합니다.
{
for (int m = j; m < n; ++m)
c[k++] = b[m] ;
else//j == n, b가 순회되면
의 나머지 요소를 처리합니다. {
for (int m = i; m < n; ++m)
c [k++] = a[m]
}
}
재정렬 문제
0개 요소와 0이 아닌 요소를 포함하여 n개 요소를 포함하는 정수 배열 a가 있는 경우 배열을 정렬하려면 다음과 같은 요구 사항을 충족해야 합니다.
정렬 후 0개 요소가 모두 앞에 오고 0이 아닌 요소는 모두 앞에 옵니다. 는 뒤쪽에 있으며 0이 아닌 요소의 상대 위치는 정렬 전후에 변경되지 않고 유지됩니다.
추가 저장용량을 사용할 수 없습니다.
예제는 다음과 같습니다: 0, 3, 0, 2, 1, 0, 0을 입력하고 0, 0, 0, 0, 3, 2, 1을 출력합니다.
이 정렬은 정렬 전후의 0이 아닌 요소의 상대적 위치가 변경되지 않고 유지되어야 하기 때문에 전통적인 의미의 정렬이 아닙니다. 아마도 정렬이라고 부르는 것이 더 적절할 것입니다. 전체 배열을 뒤에서 앞으로 순회할 수 있습니다. 특정 위치 i의 요소가 0이 아닌 요소일 때 a[k]가 0이면 a[i]가 a[k]에 할당되고 a[ k]에는 값이 0으로 할당됩니다. 실제로 i는 0이 아닌 요소의 첨자이고, k는 0 요소의 첨자입니다.
코드 복사
void Align(int* a, int n)
{
int k = n - 1
for (int i = n - 1; i > = 0; --i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[ k] = a[i] ;
a[i] = 0
}
--k
}
}
}
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
