검지offer--프로그래밍 문제 참고 코드(2)

검지offer의 코드를 계속 공유하면 여러분은 소객망에 가서 긁어보실 수 있습니다. 제가 공유한 것은 모두 통과한 것입니다.여러분은 직접 쓰셔도 됩니다. 최적화해 주세요.이 편은 주로 체인 시계를 조작하는 문제를 몇 개 풀어서 체인 시계에 대한 익숙함을 강화한다. 그 다음은 수조의 문제이다.

9. 체인 테이블을 입력하여 이 체인 테이블의 밑에서 k번째 결점을 출력한다.

/*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
   val(x), next(NULL) {
 }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k==0)
            return NULL;
       ListNode* p_temp = pListHead;  //         k-1   
       ListNode* q = pListHead;
       int i=0;
       while( inext;
           i++ ;
           if(p_temp == NULL)
               return NULL;
       }
        while(p_temp->next!=NULL){
            p_temp = p_temp->next;
            q= q->next;
        }
        return q;
    }
};

10. 조세프 문제(m>n 가능)는 n명(번호 1, 2, 3...n으로 각각 표시)이 원탁 주위에 둘러앉는 것을 알고 있다.번호가 k인 사람부터 번호를 매기고 m까지 센 사람이 줄을 선다.그의 다음 사람은 또 1부터 번호를 매기기 시작했고 m까지 센 사람이 또 줄을 섰다.원탁 주위의 사람들이 모두 나열할 때까지 이 법칙에 따라 반복해라.보통 이런 문제를 해결할 때 우리는 번호를 0~n-1, 마지막[1]의 결과+1을 원문제의 해답으로 한다.

여기 순환 체인 시계 하나 쓸게요.여러분은 체인 테이블을 구축하고 결점을 삽입하는 것을 볼 수 있습니다.그리고 반복해서 결점을 삭제하는 작업 (기본적인 체인 테이블 추가 삭제)

class Solution {
public:
    int LastRemaining_Solution(unsigned int n, unsigned int m)
    {
        if(m==0||n==0)
            return -1;
        struct Lnode{
            int data;
            Lnode* next;
        };
        int len = sizeof(struct Lnode);
        unsigned int i=1;
        struct Lnode* head = (struct Lnode*)malloc(len);
        head->data=0;          //       ，      （       ），     。
        head->next=NULL;
        struct Lnode* cur = head;
        while(idata=i;
        p->next=NULL;
        cur->next = p;
        cur = p ;
        i++;
        }
        cur->next = head;  //      ，     
         
          Lnode* q=head;
          Lnode* pre;        //             
    while(n>1){              //       
         i=0;
        while(i++next;
        }
         pre->next=q->next;
         free(q);
          q=pre->next; 
        --n;
       }
      return (q->data);  
    }
};

11. 두 개의 창고로 하나의 대열을 실현한다.일반적인, 표준 라이브러리 창고, 팀의 조작 함수: 대기열: #include 신청 대기열:queueq;판정대 공백:q.empty();헤더 요소 가져오기: q.front ();입대:q.push();출대:q.pop();창고: #include 신청창고:stacks;입고:s.push();출고: s.pop();스택 상단 요소 가져오기: s.top();창고 비움: s.empty ();

class Solution
{
public:
    void push(int node) {           //  ：      1，   2 ， node  （  ）
        while(!stack2.empty())
            {
              stack1.push(stack2.top());
              stack2.pop();
        }
         stack1.push(node);
    }

    int pop() {
        while(!stack1.empty())  //  ：      2，   1 ，      ，   
            {        
             stack2.push(stack1.top());
             stack1.pop();
        }
        int m=stack2.top();
        stack2.pop();
      return   m;
    }


private:
    stack stack1;
    stack stack2;
};

12. 시계 헤드 결점을 가진 양방향 순환 체인 시계 L이 설치되어 있다. 매 결점마다 4개의 데이터 구성원이 있다. 선구적인 결점을 가리키는 바늘prior, 후계적인 결점을 가리키는 바늘next, 데이터를 저장하는 구성원 데이터와 접근 빈도freq이다.모든 결점의freq는 처음에는 0입니다.체인 테이블에서 L.Locate(x) 조종을 한 번 할 때마다 원소값 x의 결점의 접근 빈도freq를 1로 추가하고 이 결점을 앞으로 이동시켜 현재 방문 빈도가 같은 결점 뒤에 연결시켜 체인 테이블의 모든 결점은 방문 빈도가 점차 줄어드는 순서에 따라 배열하여 빈번한 방문 결점이 항상 테이블 헤더에 접근하도록 한다.

 void Locate(int &x)
 {
 <        >
 *p = first->next;
 while (p != first &&  p->data!=x ) p = p->next;
 if (p != first)
 {
   p->freq++ ;
 <        >
 *current = p;
 current->prior->next = current->next;
 current->next->prior = current->prior;
 p = current->prior;
 while (p != first && p->freq < current->freq  ) p = p->prior;
 current->next = p->next  ;
 current->prior = p;
 p->next->prior = current;
 p->next = current;
 }
 else
 printf(“Sorry. Not find!
”);  \*   *\
 }

//                  

13. 2차원 그룹에서 찾기.하나의 2차원 그룹에서, 모든 줄은 왼쪽에서 오른쪽으로 증가하는 순서에 따라 정렬되고, 모든 열은 위에서 아래로 증가하는 순서에 따라 정렬된다.함수를 완성하고 이러한 2차원 그룹과 정수를 입력하여 그룹에 이 정수가 포함되어 있는지 판단하십시오.

class Solution {
public:
    bool Find(vector > array,int target) {
        int raw=array.size();
        int col=array[0].size();   //     ，  ，  
        int m=raw-1,n=0;
        while(m>=0&&narray[m][n])
                ++n;
            else 
                --m;
        }
         return false;   
    }
};

14. 수조의 순서를 조정하여 홀수가 짝수 앞에 있는 정수 수조를 입력하고 하나의 함수를 실현하여 이 수조의 숫자의 순서를 조정한다. 모든 홀수는 수조의 앞부분에 있고 모든 홀수는 수조의 뒷부분에 있으며 홀수와 홀수는 짝수와 짝수 사이의 상대적인 위치가 변하지 않도록 한다.

class Solution {
public:
    void reOrderArray(vector &array) {
        int m=array.size();
        int i=0,j=m-1,k=0;
       int a[m];
          for(int i=0;i=j;k--)    //          
            array[i++]=a[k];
    }
};