프로그래머 면접 문제 정선 100 문제: 6 - 10 문제 풀이 보고서

프로그래머 면접 문제 정선 100 문제 (06) - 이원 탐색 트 리 의 뒷 순 서 를 옮 겨 다 니 는 결과 [데이터 구조]  
제목: 정수 배열 을 입력 하여 이 배열 이 특정한 이원 에서 트 리 의 뒤 순 서 를 찾 아 옮 겨 다 니 는 결과 인지 판단 합 니 다.true 로 돌아 가 는 것 이 라면, 그렇지 않 으 면 false 로 돌아 갑 니 다.
예 를 들 어 5, 7, 6, 9, 11, 10, 8 을 입력 하 십시오. 이 정수 서열 은 다음 과 같은 나무의 순서 로 결 과 를 옮 겨 다 니 기 때 문 입 니 다.
         8        /  \       6    10     / \    / \    5   7   9  11
그래서 트 루 로 돌아간다.
7, 4, 6, 5 를 입력 하면 나무의 뒷 순 서 를 옮 겨 다 니 는 결과 가 이 순서 가 없 기 때문에 false 로 돌아 갑 니 다.
분석: 귀속 문제

#include <iostream>

using namespace std;

bool check(int arry[],int beg,int end)
{
    if(beg > end || arry==NULL)
    {
       return false;
    }
    if(beg == end)
        return true;
    int change = end;
    while(true)
    {
       if(change>=beg && arry[change] >= arry[end])
       {
          change--;
       }
       else
           break;
    }
    /*int change = end-1;
    for(;change>=0;--change)
    {
       if(arry[change]<arry[end])
           break;
    }*/
    int left = change;
    while(left>=beg && arry[left]<arry[end])
    {
       left--;
    }
    if(left>=beg)
        return false;
    //recurs
    return check(arry,beg,change) && check(arry,change+1,end-1);
}

int main()
{
    //int arry[] = {5,7,6,9,11,10,8};
    int arry[] = {7,4,6,5};
    bool ispostorder = check(arry,0,sizeof(arry)/sizeof(int)-1);
    if(ispostorder)
        cout << "yes postorder..." << endl;
    else
        cout << "not postorder..." << endl;
    return 0;
}

답:

bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;

      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];

      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }

      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }

      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);

      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);

      return (left && right);
}

왼쪽 에서 오른쪽으로, 여기 for 가 while 보다 좋 은 것 같 아 요. oj 에 AC 가 없어 서 그런 상황 을 고려 하지 않 았 어 요??
=====================================================
프로그래머 면접 문제 정선 100 문제 (07) - 문장 속 단 어 를 뒤 집 는 순서 [알고리즘]  
제목: 영어 문장 을 입력 하고 문장의 단어의 순 서 를 뒤 집 지만 단어 내 문자 의 순 서 는 변 하지 않 습 니 다.문장 중의 단 어 는 빈 칸 으로 구분 된다.간단 한 견 해 를 위해 문장 부 호 는 일반 자모 와 같이 처리한다.
예 를 들 어 'I am astudent.' 를 입력 하면 'student. a am I' 를 출력 합 니 다.
이 문 제 는 문장 을 뒤 집어 야 하기 때문에, 우 리 는 먼저 문장의 모든 문 자 를 뒤 집어 야 한다.이때 문장 속 단어의 순 서 를 뒤 집 었 을 뿐만 아니 라 단어 내 문자 도 뒤 집 혔 다.우 리 는 모든 단어 안의 문 자 를 다시 뒤 집 었 다.단어 안의 문자 가 두 번 뒤 집 히 기 때문에 순 서 는 입력 시의 순서 와 일치 합 니 다.
단어 순 서 를 먼저 뒤 집 은 다음 에 전부 뒤 집 을 수도 있다.
질문
 
========================================================
프로그래머 면접 문제 정선 100 문제 (08) - 구 1 + 2 +... + n [C / C + + / C \ #] 
제목: 1 + 2 +... + n 을 구하 고 곱셈 법, for, while, if, else, switch, case 등 키워드 와 조건 판단 문 (A? B: C) 을 사용 할 수 없습니다.
이것 은 확실히 발산 할 수 있 습 니 다. 클래스 를 정의 합 니 다. 우리 new 는 n 개의 이러한 유형의 요 소 를 포함 한 배열 입 니 다. 그러면 이러한 구조 함 수 는 n 회 호출 될 것 입 니 다.
============================================================
 
프로그래머 면접 문제 정선 100 문제 (09) - 링크 에서 꼴찌 k 번 째 결점 [데이터 구조]  
제목: 단 방향 링크 를 입력 하여 이 링크 의 마지막 k 번 째 노드 를 출력 합 니 다.링크 의 마지막 0 번 째 노드 는 링크 의 꼬리 지침 이다.
분석: 빠 르 고 느 린 지침.
확장: 단 방향 링크 를 입력 하 십시오.만약 이 링크 의 결산 포인트 가 홀수 라면 중간 결산 점 을 출력 합 니 다.링크 의 노드 가 짝수 라면 중간 두 개의 노드 앞 에 있 는 하 나 를 출력 합 니 다.
 
==================================================================
프로그래머 면접 문제 정선 100 문제 (10) - 정렬 배열 과 주어진 값 의 두 숫자 [알고리즘] 
제목: 오름차 순 으로 정렬 된 배열 과 숫자 를 입력 하고 배열 에서 두 개의 수 를 찾 아 입력 한 숫자 와 맞 게 합 니 다.요구 시간 복잡 도 는 O (n) 이다.만약 여러 쌍 의 숫자 와 입력 한 숫자 가 있다 면, 임의의 한 쌍 을 출력 하면 된다.
예 를 들 어 배열 1, 2, 4, 7, 11, 15 와 숫자 15 를 입력 하 십시오.4 + 11 = 15 이기 때문에 4 와 11 을 출력 합 니 다.
분석: 1. 폭력 C (2, n) 복잡 도 O (n ^ 2)
2. 이것 은 질서 있 는 이 조건 을 이용 하지 않 고 두 개의 지침 을 중간 으로 최적화 시 켰 다.복잡 도 O (n)
 
확장:
1. 하나의 배열 을 입력 하여 이 배열 에 세 개의 숫자 i, j, k 가 존재 하 는 지 판단 하고 i + j + k 를 만족 시 키 는 것 은 0 과 같다.
먼저 O (nlogn) 를 정렬 한 다음 에 각 요소 에 대해 상기 알고리즘 을 사용 하여 두 개의 수 와 이 값 이 있 는 지 판단 하고 복잡 도 는 O (n ^ 2) 입 니 다.
 
2. 입력 한 배열 이 정렬 되 지 않 았 지만 안에 있 는 숫자의 범 위 를 알 고 다른 조건 이 변 하지 않 는 다 면 어떻게 O (n) 시간 에 이 두 숫자 를 찾 습 니까?
숫자 범 위 를 알 면 정렬 을 계산 하 세 요. 다른 것 은 O (n) 와 같 습 니 다.
3. 숫자 범 위 를 모른다 면?
이것 은 hash 에 의존 해 야 합 니 다. 먼저 O (n) hash 를 한 다음 에 A 에 대해 hash 가 K - A 가 존재 하 는 지 찾 으 면 존재 하 는 지 찾 을 수 있 습 니 다.복잡 도 O (n)
 
4. 구 글 면접 문제: 무질서 한 배열 에 연속 몇 개의 숫자 와 N 이 있 는 지 여부
분석: 1. 폭력 O (n ^ 3)
2. 다음 f (I, n) = f (I, n - 1) + a [i] [n] 회 O (n) 를 최적화 하고 n 개 i 에 대한 총 복잡 도 는 O (n ^ 2) 이다.
3. 슬 로 우 포인터 I, j.K 보다 작 으 면 j 증가;그렇지 않 으 면 i 가 증가 하고 I = = J 의 상황 에 주의해 야 한다. ij 는 거 슬러 올 라 가지 않 고 최대 2n 걸음 이기 때문에 복잡 도 는 O (n) 이다.