온라인 펜 문제 요약 4.12

1) Q: 바이너리 표현에서 1의 개수를 출력하는 정수를 입력합니다.그중의 음수는 부호를 보충하여 표시한다.
대답:
코드를 분석해 보자. 이 작은 코드는 매우 교묘하다.
만약 정수가 0이 아니라면, 이 정수는 적어도 한 명은 1이다.만약 우리가 이 정수를 1로 줄이면 원래 정수 맨 오른쪽에 있던 1은 0이 되고 원래 1 뒤에 있던 모든 0은 1이 된다(맨 오른쪽의 1 뒤에 0이 있다면).나머지 모든 비트는 영향을 받지 않을 것이다.
예를 들어 한 이진수 1100, 오른쪽에서 세 번째는 가장 오른쪽에 있는 1이다.1을 빼면 3위는 0이 되고 그 뒤의 두 자리는 0이 1이 되며 앞의 1은 변하지 않기 때문에 얻은 결과는 1011이다.우리는 1을 줄인 결과 맨 오른쪽에 있는 1부터 시작하는 모든 자리를 거꾸로 잡았다는 것을 발견했다.이때 만약에 우리가 원래의 정수와 1을 뺀 결과를 다시 연산한다면 원래의 정수 맨 오른쪽에 있는 1부터 모든 자리가 0이 될 것이다.예를 들어 1100&1011=1000.즉, 하나의 정수를 1에서 빼고 원래의 정수와 연산을 하면 이 정수의 가장 오른쪽에 있는 1을 0으로 변하게 된다.그러면 정수의 이진법이 1이 몇 개면 이런 조작을 몇 번 할 수 있다.

class Solution {
public:
     int  NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
     }
};

2) 물음: 다들 피보나치 수열을 알고 있습니다. 지금 정수 n을 입력해야 합니다. 피보나치 수열의 n항을 출력해 주십시오.
대답:

class Solution {
public:
 int Fibonacci(int n) {
        int* array=new int[n];
        array[0]=1;
        array[1]=1;
        array[2]=2;
        for(int i=3;i<n;i++)
            array[i]=array[i-1]+array[i-2];
        return array[n-1];
    }；
}；

3) 개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.
대답:
n번째 계단은 n-1 또는 n-2의 계단에서만 뛰어오를 수 있기 때문에
F(n) = F(n-1) + F(n-2)
피폴라치 수 서열, 초기 조건
n=1: 한 가지 방법밖에 없어요.
n=2: 두 가지
귀속시키면 돼요.

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 0)
            return 0;
        else if(number == 1)
            return 1;
        else if(number == 2)
            return 2;
        else
            return jumpFloor(number-1) + jumpFloor(number-2);
    }
};

4) 물음: 우리는 2*1의 작은 직사각형을 가로로 하거나 세로로 더 큰 직사각형을 덮을 수 있다.실례지만 n개의 2*1의 작은 직사각형으로 2*n의 큰 직사각형을 중첩 없이 덮어쓰려면 모두 몇 가지 방법이 있습니까?
대답:
여전히 피보나치 수열.
2*n의 큰 직사각형과 n개의 2*1의 작은 직사각형
그중 target*2는 큰 행렬의 크기입니다
다음과 같은 시나리오가 있습니다.
1⃣𐁻target<=0 직사각형은 <=2*0, 직접return1;
2⃣𐁨target=1 큰 직사각형은 2*1이고 단지 한 가지 배치 방법,return1;
3⃣𐁨target=2 큰 직사각형은 2*2로 두 가지 배치 방법이 있는데,return2;
4⃣𐁨 target = n은 두 단계로 나뉘어 고려한다.
첫 번째로 2*1의 작은 행렬을 놓으면 배치 방법은 모두 f(target-1)이고 첫 번째로 1*2의 작은 행렬을 놓으면 배치 방법은 모두 f(target-2)이다.
왜냐하면 1*2의 작은 행렬을 놓고 (√√로 표시), 아래의 1*2에 대응하기 때문이다.××표시) 배치 방법이 확정되어 f(targte-2)
코드:

public:class Solution {
    int rectCover(int number) {
        if(number<=0)return 1;
        else if(number==1)return 1;
        else if(number==2)return 2;
        else return rectCover(number-1)+rectCover(number-2);
    }
};

6) 개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고, 2계단을 올라갈 수도 있다....개구리는 n계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.
대답:
본 문제에 관하여 n계단을 전제하면 n계단의 점프법이 한 번 있을 것이다.분석은 다음과 같습니다.
f(1) = 1
f(2)= f(2-1)+f(2-2)//f(2-2)는 2단계가 한 번에 2단계를 뛰는 횟수를 나타낸다.
f(3) = f(3-1) + f(3-2) + f(3-3) 
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 
 
설명:
1. 여기 f(n)는 n계단이 한 번 하나, 둘...n 단계의 점프수.
2.n = 1시에는 1가지 점프만 있고, f(1)= 1
3. n=2시 점프 방식이 두 가지가 있는데, 한 번에 1 단계 또는 2 단계로 돌아간다. 이것은 문제로 돌아간다(1), f(2)=f(2-1)+f(2-2)
4. n = 3시에는 3 가지 점프 방식이 있습니다. 1 단계, 2 단계, 3 단계,
그럼 첫 번째 1단계 뛰기 뒤에 남은: f(3-1);첫 번째 2 단계 탈출, f (3-2) 남음;첫 번째 3 단계, 그럼 f (3-3) 남음
따라서 결론은 f(3)= f(3-1)+f(3-2)+f(3-3)
5. n = n 시 n 중 점프 방식, 1 단계, 2 단계...n단계, 결론 도출:
    f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) 
6. 위에서 말한 바와 같이 결론을 내렸지만 간단함을 위해 우리는 계속 간소화할 수 있다.
    f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
    f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
다음과 같은 결과를 얻을 수 있습니다.
    f(n) = 2*f(n-1)
7. 최종 결론은 n계단에서 한 번에 1, 2,...n 단계의 점프 방식은 다음과 같습니다.
              | 1       ,(n=0 ) 
f(n) =     | 1       ,(n=1 )
             | 2*f(n-1),(n>=2)
이후에 이런 문제에 부딪히면 유비법열 공식을 쓰면 된다.

class Solution {
public:
    int jumpFloorII(int number) {
        if(number<=0) return -1;
        else if(number==1) return 1;
        else return 2*jumpFloorII(number-1);
    }
};

7) Q: 두 개의 스택으로 하나의 대기열을 구현하고 대기열의 Push와 Pop 작업을 완료합니다.대기열의 요소는 int 형식입니다.
대답:
창고: 테이블 끝에만 삽입 및 삭제 작업을 한정하는 선형 테이블, 창고 꼭대기(top) 창고 밑(bottom)
대기열: 한쪽 끝에만 삽입 작업을 허용하고 다른 한쪽 끝에는 삭제 작업을 허용하는 선형 테이블
입대:원소를 창고 A
출대: 창고 B가 비어 있는지 판단하고 비어 있으면 창고 A의 모든 요소를 pop하고push를 창고 B에 넣고 창고 B를 출고한다.
비어 있지 않으면 스택 B가 스택에서 바로 나옵니다.

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
 
    int pop() {
        int a;
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
    }
 
private:
    stack<int> stack1;
    stack<int> stack2;
};

8) 물음: 어떤 두 갈래 나무의 앞 순서와 중간 순서를 입력한 결과 이 두 갈래 나무를 다시 만드십시오.입력한 앞의 순서와 중간 순서의 결과에 중복된 숫자가 포함되지 않는다고 가정하십시오.예를 들어 전차 역행 서열 {1,2,4,7,3,5,6,8}과 중차 역행 서열 {4,7,2,1,5,3,8,6}을 입력하면 두 갈래 나무를 다시 만들고 되돌려줍니다.
답: 첫 번째 위치는 루트 노드, 중간 루트 노드는 중간 p, p 왼쪽은 노드의 왼쪽 트리의 중간 트리, p 오른쪽은 노드의 오른쪽 트리의 중간 트리입니다.다른 한편, 먼저 순서가 두루 흐르는 두 번째 위치는 p까지이고 노드 왼쪽 트리의 먼저 순서 서브 그룹이다. 나머지 p 오른쪽은 노드의 오른쪽 서브 트리의 먼저 순서 서브 그룹이다.네 개의 수조를 찾아내서 좌우로 나누어 호출하면 된다

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
        int in_size = in.size();
        if(in_size == 0)
            return NULL;
        vector<int> pre_left, pre_right, in_left, in_right;
        int val = pre[0];
        TreeNode* node = new TreeNode(val);//root node is the first element in pre
        int p = 0;
        for(p; p < in.size(); ++p){
            if(in[p] == val) //Find the root position in in 
                break;
        }
        for(int i = 0; i < in.size(); ++i){
            if(i < p){
                in_left.push_back(in[i]);//Construct the left pre and in 
                pre_left.push_back(pre[i+1]);
            }
            else if(i > p){
                in_right.push_back(in[i]);//Construct the right pre and in 
                pre_right.push_back(pre[i]);
            }
        }
        node->left = reConstructBinaryTree(pre_left, in_left);
        node->right = reConstructBinaryTree(pre_right, in_right);
        return node;
    }
};