剑指Offer

Posted on Edited on In

Prefab

本文记录了我自己在刷剑指offer时的代码。题目顺序根据牛客网，代码没有极致追求高效，但是尽可能使用优雅简明的实现方式，但同时也不会为了简单而使用大量STL自带的方法（若使用，尽可能给出具体实现方式）。

JZ1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int i=array.size()-1;
        int j=0;
        while(i>=0 && j<array[0].size())
        {
            if(array[i][j]>target)    i--;
            else if(array[i][j]<target)    j++;
            else if(array[i][j]==target)   return true;
        }
        return false;
    }
};

JZ2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// using string.replace()
class Solution {
public:
    string replaceSpace(string s) {
        for(int i=0;i<s.size();i++)    if (s[i]==' ')  s.replace(i, 1, "%20");
        return s;
    }
};

// implement it on your own
class Solution {
public:
    string replaceSpace(string s) {
        int n=s.length();
        string s_tmp[n];
        for(int i=0; i<n; i++)    s_tmp[i] = s[i]; // put char to string
        for (int i=0; i<n; i++) 
        {
            if (s_tmp[i] == " ")    s_tmp[i] = "%20";
        }
        string ret;
        for(int i=0; i<n; i++)    ret+=s_tmp[i];
        return ret;
    }
};

JZ3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        auto i = head;
        while(i!=nullptr)
        {
            ans.push_back(i->val);
            i=i->next;
        }
        // vector反转也可以通过vector<int>::reverse_iterator实现(.rbegin()  r.end())
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

JZ4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.size()==0)    return nullptr;
        TreeNode* head = new TreeNode(pre[0]); // create the head node
        int i = 0;
        while(vin[i]!=pre[0])    i++;
        // i is the index of root
        vector<int> left_pre (pre.begin()+1,pre.begin()+i+1);
        vector<int> left_vin (vin.begin(),vin.begin()+i);
        vector<int> right_pre (pre.begin()+i+1,pre.end());
        vector<int> right_vin (vin.begin()+i+1,vin.end());
        
        head->left = reConstructBinaryTree(left_pre, left_vin);
        head->right = reConstructBinaryTree(right_pre, right_vin);
        
        return head; // remember to return
    }
};

JZ5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack1.empty() && stack2.empty())    return 0; // throw error
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                auto node=stack1.top();
                stack2.push(node);
                stack1.pop();
            }
        }
        auto node=stack2.top();
        stack2.pop();
        return node;
        
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

JZ6

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int min=rotateArray[0];
        for(int i:rotateArray)
        {
            if(i>=min)    min=i;
            else return i;
        }
        return rotateArray[0];
    }
};

JZ7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int Fibonacci(int n) {
        // 兼顾了第0项
        if(n<=1)    return n;
        else return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

// 不使用递归--避免大量重复计算
class Solution {
public:
    int Fibonacci(int n) {
        int before = 0, next = 1;
        while(n) {
            before += next;
            // 'next' is 'before' befor changed
            next = before - next;
            n--;
        }
        return before;
    }
};

JZ8

1
2
3
4
5
6
7
class Solution {
public:
    int jumpFloor(int number) {
        if (number<=1)    return 1;
        else return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

JZ9

1
2
3
4
5
6
7
8
9
10
// f(n) = f(n-1)+f(n-2)+...+f(n-n)--对应一次跳1阶，2阶，n阶
// f(n) = f(n-2)+...+f(n-n)
// => f(n)=2*f(n-1)
class Solution {
public:
    int jumpFloorII(int number) {
        if(number<=1)    return number;
        else    return 2*jumpFloorII(number-1);
    }
};

JZ10

1
2
3
4
5
6
7
class Solution {
public:
    int rectCover(int number) {
        if(number<=2)    return number;
        else return rectCover(number-2)+rectCover(number-1);
    }
};

JZ11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 最优解
class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n)
         {
             count++;
             n = n&(n-1);
             // n && n-1 可以保证二进制中的从右往左的第一个1被替换为0，而此左侧的位不受影响
         }
         return count;
     }
};
// 常规思路--让1不断向左按bit移动
class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         int flag=1;
         while(flag)
         {
             if((n&flag)!=0)    count++; // note：这里必须是(n&flag)!=0而不能是n&flag!=0或者(n&flag)==0
             flag=flag<<1;
         }
         return count;
     }
};

JZ12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// O(n)
class Solution {
public:
    double Power(double base, int exponent) {
        if(base==0)    return 0;
        double ans=1;
        bool negative=false;
        if(exponent<0)    negative=true;
        exponent=abs(exponent);
        for(int i=0; i<exponent; i++)
        {
            ans=ans*base;
        }
        if(negative)    ans=1.0/ans;
        return ans;
    }
};

// O(logn)
class Solution {
public:
    double Power(double base, int exponent) {
        if(base==0)    return 0;
        if(exponent==1)    return base;
        if(exponent==0)    return 1;
        
        double ans=1;
        bool negative=false;
        if(exponent<0)    negative=true;
        exponent=abs(exponent);
        
        // exponent is odd
        double half=Power(base, exponent/2);
        if (exponent%2)
        {
            ans=half*half*base;
        }
        // exponent is even
        else    ans=half*half;
        
        if(negative)    ans=1.0/ans;
        return ans;
    }
};

JZ13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        vector<int> odd;
        vector<int> even;
        for (auto i: array)
        {
            if(i%2)    odd.push_back(i);
            else    even.push_back(i);
        }
		// insert可以插入vector的一部分
        odd.insert(odd.end(), even.begin(), even.end());
        return odd;
    }
};

JZ14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        if(pHead==nullptr)    return nullptr;
        ListNode* p1=pHead;
        ListNode* p2=pHead;
        for(int i=0; i<k; i++)
        {
            if(p1==nullptr)    return nullptr; // note: 此语句需在更新p1之前，否则在k=链表长度时会出现问题
            p1=p1->next;
        }
        while(p1!=nullptr)
        {
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
    }
};

JZ15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr)    return nullptr;
        ListNode* p1=pHead;
        ListNode* p2=pHead->next;
        pHead->next=nullptr;
        while(p2!=nullptr)
        {
            ListNode* tmp=p2->next;
            p2->next=p1;
            p1=p2;
            p2=tmp;
        }
        return p1;
    }
};

JZ16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr)    return pHead2;
        if(pHead2==nullptr)    return pHead1;
        // only consider one node at one step
        if(pHead1->val<=pHead2->val)
        {
            pHead1->next=Merge(pHead1->next, pHead2);
            return pHead1;
        }
        else
        {
            pHead2->next=Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};

JZ17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
// note: we want to test whether pRoot2 is a subtree of pRoot1
class Solution {
public:
    bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        // note: we only consider pRoot1==pRoot2 & pRoot1 is subtree of pRoot2
        if(pRoot2==nullptr)    return true;
        else if(pRoot1==nullptr)    return false;
        return pRoot1->val==pRoot2->val && isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot1==nullptr || pRoot2==nullptr)    return false;
        return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
    }
};

JZ18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==nullptr)    return nullptr;
        auto tmp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=tmp;
        Mirror(pRoot->right);
        Mirror(pRoot->left);
        return pRoot;
    }
};

JZ19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> rotateMatrix(vector<vector<int>> matrix)
    {
        // note: you have to consider exception
        if(matrix.empty())    return matrix;
        vector<vector<int>> ans;
        for(int i=0; i<matrix[0].size(); i++)
        {
            vector<int> tmp;
            for(int j=0; j<matrix.size(); j++)
                tmp.push_back(matrix[j][matrix[0].size()-i-1]); // note: the index if not[i][i]
            ans.push_back(tmp);
        }
        return ans;
    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        while(!matrix.empty())
        {
            ans.insert(ans.end(), matrix[0].begin(), matrix[0].end());
            matrix.erase(matrix.begin(), matrix.begin()+1);
            matrix=rotateMatrix(matrix);
        }
        return ans;
    }
};

JZ20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    // 这里非常巧妙的一点在于：假设x>y，如果x先push，那么y push时一定入min_s，pop时也会被从min_s中pop；如果y先push，x没有被push入min_s，但是pop时一定先pop x--保证即使min_s不会没有追踪后push的大的值，但是pop会先pop这些大的值，min_s不需要对其进行追踪。
    stack<int> s;
    stack<int> min_s;
    void push(int value) {
        s.push(value);
        if(min_s.empty())    min_s.push(value);
        else if(min_s.top()>=value)    min_s.push(value);
    }
    void pop() {
        int value=s.top();
        s.pop();
        if(min_s.top()==value)    min_s.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return min_s.top();
    }
};

JZ21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int p1 = 0, p2 = 0;
        stack<int> s;
        while(p1<pushV.size() && p2<popV.size())
        {
            if(s.empty())    s.push(pushV[p1++]);
            else
            {
                if(s.top()==popV[p2])
                {
                    s.pop();
                    p2++;
                }
                else
                {
                    s.push(pushV[p1++]);
                }
            }
        }
        if(p1>=pushV.size() && p2<popV.size())
        {
            while(s.top()==popV[p2])
            {
                s.pop();
                p2++;
                if(p2>=popV.size())    break;
            }
        }
        return s.empty();
    }
};

JZ22

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *p1=head, *p2=head;
        for(int i=0; i<k; i++) p1=p1->next;
        while(p1!=nullptr)
        {
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
    }
};

JZ24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr || head->next==nullptr)  return head;
        ListNode *p1=head, *p2=head->next;
        head->next=nullptr;
        while(p2!=nullptr)
        {
            ListNode *tmp=p2->next;
            p2->next=p1;
            p1=p2;
            p2=tmp;
        }
        return p1;
    }
};

JZ25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(0);
        ListNode *current=head;
        while(l1!=nullptr && l2!=nullptr)
        {
            if(l1->val < l2->val)
            {
                current->next=l1;
                l1=l1->next;
            }
            else
            {
                current->next=l2;
                l2=l2->next;
            }
            current=current->next;
        }
        current->next = l1==nullptr?l2:l1;
        return head->next;
    }
};

JZ26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool hasSubtructure(TreeNode* A, TreeNode* B)
    {
        if(B==nullptr)  return true;
        if(A==nullptr)  return false; 
        if(A->val!=B->val)    return false;
        return hasSubtructure(A->left, B->left) && hasSubtructure(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr)    return false;
        return hasSubtructure(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

JZ27

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr)   return nullptr;
        TreeNode *tmp=root->left;
        root->left=root->right;
        root->right=tmp;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

JZ28

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool symmetricTree(TreeNode* p1, TreeNode* p2)
    {
        if(p1==nullptr && p2==nullptr)  return true;
        if(p1==nullptr || p2==nullptr)  return false;
        return p1->val==p2->val && symmetricTree(p1->right, p2->left) && symmetricTree(p1->left, p2->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)   return true;
        return symmetricTree(root->left, root->right);
    }
};

JZ29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> rotateMatrix(vector<vector<int>>& matrix)
    {
        vector<vector<int>> result;
        int num_row=matrix.size();
        if(num_row==1)  return result;
        int num_col=matrix[0].size();
        for(int i=0; i<num_col; i++)
        {
            vector<int> tmp;
            for(int j=1; j<num_row; j++)
            {
                tmp.push_back(matrix[j][num_col-1-i]);
            }
            result.push_back(tmp);
        }
        return result;
    }
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        vector<vector<int>> m=matrix;
        while(m.size())
        {
            for(int i=0; i<m[0].size(); i++)
            {
                result.push_back(m[0][i]);
            }
            m=rotateMatrix(m);
        }
        return result;
    }
};

JZ30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> store_stack;
    stack<int> min_stack;
    MinStack() {
        min_stack.push(INT_MAX);
    }
    void push(int x) {
        store_stack.push(x);
        if(min_stack.top()>=x)   min_stack.push(x);
    }
    void pop() {
        int tmp=store_stack.top();
        store_stack.pop();
        if(tmp==min_stack.top())    min_stack.pop();
    }
    int top() {
        return store_stack.top();
    }
    int min() {
        return min_stack.top();
    }
};

JZ31

1
2
3
4
```

### JZ32

1
2
3

### JZ33

```