[검지 Offer] 조감 50문제 중 21-30문제.
9354 단어 [검지 Offer]
min 함수를 포함하는 창고
면접 문제
창고의 압축, 팝업 시퀀스
면접 문제
위에서 아래로 두 갈래 나무를 인쇄하다
면접 문제
두 갈래 검색 트리의 뒷차례 반복 시퀀스
면접 문제
두 갈래 트리 중 하나가 되는 경로
면접 문제
복잡한 체인 테이블 복제
면접 문제
두 갈래 검색 트리와 양방향 체인 테이블
면접 문제
문자열 정렬
면접 문제
수조에 나타나는 횟수가 절반을 넘는 숫자
면접 문제 30 가장 작은 K 개수
/****************************************************/
면접문제 21은 min 함수를 포함하는 창고: 창고의 데이터 구조를 정의합니다. 이 유형에서 창고의 최소 요소를 얻을 수 있는 min 함수를 실현하십시오.이 창고에서min,push 및pop를 호출하는 시간의 복잡도는 모두 O(1)
사고방식: 현재 창고의 최소 요소를 저장하기 위해 원래 창고 스택 크기와 같은 창고 tmpStack을 신청합니다.stack은 하나의 원소를 눌러 넣고 tmpStack도 하나의 원소를 눌러 넣는다. 이 원소는 tmpStack과 같다.top를 비교하면 크면 top를 눌러라. 그렇지 않으면 이 요소를 눌러라.출세와 동시에 출세하다.
다음을 수행합니다.
template T;
class Stack
{
public:
Stack();
~Stack();
void pop();
void push(T &value);
T min();
private:
stack m_stack;
stack m_min;
};
void pop()
{
if (m_min.size() <= 0 || m_stack.size() <= 0)
{
return;
}
m_stack.pop();
m_min.pop();
}
void push(T &value)
{
if ( m_min.size() == 0 || value < m_min.top())
{
m_min.push(value);
}
else
{
m_min.push(m_min.top());
}
m_stack.push(value);
}
T min()
{
if (m_min.size() > 0)
{
return m_min.top();
}
}
면접문제 22창고의 압축, 팝업 서열: 두 개의 서열을 입력하고 첫 번째는 창고의 압축 서열입니다. 두 번째 1, 2, 3, 4, 5, 6은 4, 5, 3, 2, 1은 창고의 압축 서열이고 4, 3, 5, 1, 2는 이 압축 서열일 수 없습니다.
생각:
다음을 수행합니다.
bool IsPopOrder(const int *pPush, const int *pPop, int length)
{
const int *pPushNext = pPush;
const int *pPopNext = pPop;
bool result = false;
if (pPush == NULL || pPop == NULL || length <= 0)
{
return false;
}
stack iStack;
while(pPopNext - pPop < length)/* */
{
while(iStack.top() != *pPopNext)
{
if (pPushNext - pPush == length)
{
break;
}
iStack.push(*pPushNext);
pPushNext++;
}
if (iStack.top() != *pPopNext)
{
break;
}
iStack.pop();
pPopNext++;
}
if (iStack.empty() && pPopNext - pPop == length)
{
return true;
}
return false;
} 면접 문제 23 위에서 아래로 인쇄 두 갈래 나무, 두 갈래 나무의 층계 반복
다음을 수행합니다.
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void LevelOrder(BinaryTreeNode *root)
{
BinaryTreeNode *pNode;
if (root == NULL)
{
return;
}
queue iQueue;
iQueue.push(root);
while(!iQueue.empty())
{
pNode = iQueue.front();
if (pNode->lchild != NULL)
{
iQueue.push(pNode->lchild);
}
if (pNode->rchild != NULL)
{
iQueue.push(pNode->rchild);
}
printf("%d",pNode->data);
iQueue.pop();
}
} 면접문제 24 두 갈래 검색 트리의 뒷차례 반복 서열, 한 개의 수조를 제시하여 두 갈래 검색 트리의 뒷차례 반복 서열인지 아닌지를 판단한다
사고방식: 마지막 결점의 값은 왼쪽 나무의 임의 값보다 크고 오른쪽 나무의 임의 값보다 작다
다음을 수행합니다.
int IsSerchTree(int *squeue, int length)
{
int i,j;
if (squeue == NULL || length <= NULL)
{
return false;
}
for (i = 0; i < length; i++)
{
if (squeue[i] > squeue[length-1])
{
break;
}
}
for (j = i, j 면접 문제 25 두 갈래 나무와 어떤 값의 경로
주의:vector와stack과queue의 차이
vector는 머리에서 노드를 삭제하거나 꼬리에서 전체 구조를 훑어볼 수 있습니다
다음을 수행합니다.
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void SumPathTree(BinaryTreeNode *root, int expectSum, vector &iPath, int currentSum)
{
if (root == NULL)
{
return;
}
/* ， */
currentSum += root->data;
iPatch.push_back(root->data);
if ((currentSum == expectSum)
&& (root->lchild == NULL && root->rchild == NULL)
{
for (iterator iter = iPath.begin(); iter < iPath.end(); iter++)
{
printf("%d", *iter);
}
printf("
");
}
if (root->lchild != NULL)
{
SumPathTree(root->lchild,expectSum,iPath,currentSum);
}
if (root->rchild != NULL)
{
SumPathTree(root->rchild,expectSum,iPath,currentSum);
}
/* ， ， */
iPath.pop_back();
currentSum-=root->data;
} 면접문제 26 복잡 체인표 복제
struct ComplexListNode {int data; ComplexListNode *next; ComplexListNode *sibling;/*는 모든 결점을 가리킨다 */};
첫 번째 단계: 각 노드 뒤에 같은 결점을 부여한다
두 번째 단계: 짝수 결점을 훑어보고 새 결점에서sibling 바늘을 가리키는 결점을 가리킨다
세 번째 단계: 체인 시계를 홀수에 따라 짝수로 나누어 두 개의 체인 시계로 나눈다.
면접 문제 27 두 갈래 검색 트리와 쌍방향 체인 테이블, 두 갈래 검색 트리를 입력하여 두 갈래 검색 트리를 정렬된 쌍방향 체인 테이블로 바꿉니다
사고방식: 중간 순서로 두 갈래 나무를 훑어보는 방식으로 매번 귀속해서 지난번에 훑어본 결점을 기록하고 지침으로 다음 귀속으로 전한다
다음을 수행합니다.
struct BinaryTreeNode
{
int data;
BinaryTreeNode *lchild;
BinaryTreeNode *rchild;
};
void ConvertTree(BinaryTreeNode *root, BinaryTreeNode **lastNode)
{
if (root == NULL)
{
return;
}
ConvertTree(root->lchild,lastNode);
root->lchild = lastNode;
if (*lastNode != NULL)
{
(*lastNode)->rchild = root;
}
(*lastNode) = root;
ConvertTree(root->rchild,lastNode);
}
BinaryTreeNode *GetHeadNode(BinaryTreeNode *root)
{
BinaryTreeNode *head;
if (root == NULL)
{
return NULL;
}
head = root;
while (head->lchild)
{
head = head->lchild;
}
return head;
}면접 문제 28 문자열의 배열
예를 들어 abc를 입력하여 abc를 출력하는 6가지 배열 조합 abcbac...
다음을 수행합니다.
#include
void printOrderStr(char *str, int length, int index)
{
char temp;
if (str == NULL || length == 0)
{
return;
}
if (index == length)
{
for (int i = 0; i 확장 문제, 문자열 출력 문자열의 각종 조합을 입력합니다. 예를 들어 abc 출력 a, b, c, ab...abc 입력
다음을 수행합니다.
#include
#include
#include
using namespace std;
#include
void Combination_m(char *string ,int number , vector &result)
{
assert(string != NULL);
if(number == 0)
{
static int num = 1;
printf(" %d \t",num++);
vector::iterator iter = result.begin();
for( ; iter != result.end() ; ++iter)
printf("%c",*iter);
printf("
");
return ;
}
if(*string == '\0')
return ;
result.push_back(*string);
Combination_m(string + 1 , number - 1 , result);
result.pop_back();
Combination_m(string + 1 , number , result);
}
void Combination(char *string)
{
assert(string != NULL);
int i , length = strlen(string);
for(i = 1 ; i <= 3 ; ++i)
{
vector result;
Combination_m(string , i ,result);
}
}
int main(void)
{
char str[] = "abc";
Combination(str);
getchar();
return 0;
}
면접 문제 29 수조 중 출현 횟수가 절반을 넘는 숫자는 한 수조를 정하는데 그 중 한 수조는 그 수가 절반을 초과하여 이 수를 구한다
생각:
가장 간단한 것은 정렬해서 중위수를 구하는 것이다.
하나의 수로 반복 개수를 기록하고 하나의 수로 결과를 기록하는 것은 구체적으로 다음과 같다.
int FindMoreThanHalf(int num[], int length)
{
int times = 0;
int result;
if (num == NULL || length <=0 )
{
return 0;/* */
}
result = num[0];
times++;
for (int i = 1; i < length; i++)
{
if (num[i] == result)
{
times++;
}
if (times == 0)
{
result = num[i];
}
if (num[i] != result && times > 0 )
{
times--;
}
}
return times;
}면접 문제 30 가장 작은 K 개수
#include
#include
/* K */
int partition(int *psArray, int num, int startIndex, int endIndex)
{
int iTemp;
int i = startIndex;
int j = endIndex;
if (psArray == NULL || num <= 0 || startIndex > endIndex || startIndex < 0 || endIndex < 0)
{
return 0;
}
iTemp = psArray[0];
while (i < j)
{
while ((i < j) && (psArray[i] <= psArray[j]))
j--;
if (i < j)
{
iTemp = psArray[i];
psArray[i] = psArray[j];
psArray[j] = iTemp;
}
while((i < j) && (psArray[i] <= psArray[j]))
i++;
if (i < j)
{
iTemp = psArray[i];
psArray[i] = psArray[j];
psArray[j] = iTemp;
}
}
return i;
}
void FindMinKNum(int *psArray, int num, int k)
{
int i;
int j;
if (k > num)
{
return;
}
i = partition(psArray,num,0,num-1);
while (i != k-1)
{
if (i < k-1)
{
i = partition(psArray,num,i+1,num-1);
}
else
{
i = partition(psArray,num,0,i-1);
}
}
for (j = 0; j <= i; j++)
{
printf(" %d", psArray[j]);
}
printf("
");
}
int main()
{
int a[]={3,4,5,1,2};
FindMinKNum(a, 5, 2);
}
O(n*logk)의 시간 복잡도와 O(k)의 공간 복잡도로 실현할 수 있다.
void GetLeastNumbers(int *psArray, int length, int k)
{
if (psArray == NULL || length < 0 || k < 0 || length < k)
{
return;
}
multiset > iMultiset;
multiset >::iterator iSetIterator;
for (int i = 0; i < length; i++)
{
if (i < k)
{
iMultiset.insert(psArray[i]);
}
else
{
if (psArray[i] < *(iMultiset.begin()))
{
iMultiset.erase(iMultiset.begin());
iMultiset.insert(psArray[i]);
}
}
}
for (iSetIterator = iMultiset.begin(); iSetIterator != iMultiset.end(); iSetIterator++ )
{
printf(" %d", *iSetIterator);
}
printf("
");
} 좋은 웹페이지 즐겨찾기
