剑指Offer

Day1

用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

栈A用于存插入的数据，栈B用于出栈

插入函数，直接在A中入栈即可，出队时先看栈B是否为空，不为空直接输出B栈顶

否则看看A是否为空，为空的话说明没有数据

不是上述两种情况，则将A中的数据出栈后插入B中，再取出B的栈顶元素。

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
class CQueue {
    stack<int> A,B;
public:
    CQueue() {
        while(A.size())A.pop();
        while(B.size())B.pop();
    }
    
    void appendTail(int value) {
        A.push(value);
    }
    
    int deleteHead() {
        int x;
        if(B.size()){
            x = B.top();
            B.pop();
        }else if(A.empty())
            x = -1;
        else{
            while(A.size()){
                B.push(A.top());
                A.pop();
            }
            x = B.top();
            B.pop();
        }
        return x;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

包含min函数的栈

剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode） (leetcode-cn.com)

用两个栈，第一个用来正常存，第二个用来存当前栈的最小值。

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
class MinStack {
    
public:
    /** initialize your data structure here. */
    stack<int> A,B;
    MinStack() {
        
    }
    
    void push(int x) {
        A.push(x);
        int min_x = (B.empty()||x<B.top())?x:B.top();
        B.push(min_x);
    }
    
    void pop() {
        A.pop();
        B.pop();
    }
    
    int top() {
        return A.top();
    }
    
    int min() {
        return B.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

Day2

从尾到头打印链表

遍历链表，将节点数据存入到栈中，然后再出栈，就行了。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> res;
        ListNode* p = head;
        while(p){
            res.push(p->val);
            p = p->next;
        }
        vector<int> num;
        while(res.size()){
            num.push_back(res.top());
            res.pop();
        }
        return num;
    }
};

反转链表

剑指 Offer 24. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

解法1：遍历这个链表，然后用头插法插入每一个元素(有手就行，代码就不给了)

解法2：直接做，思路的话看着代码自己画一遍就懂了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL)return head;
        ListNode *p=head,*q=p->next,*pt=NULL;
        while(q){
            p->next = pt;
            pt = p;
            p = q;
            q = q->next;
        }
        p->next = pt;
        return p;
    }
};

复杂链表的复制

在这题中，首先需要将复制的节点接到对应节点的next上，然后根据原来节点的random改变复制节点的randomp->next->random=p->random->next，然后把链表分开即可。

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode） (leetcode-cn.com)

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
45
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 复制节点
        for(Node* p = head;p;){
            Node* tmp = new Node(p->val);
            Node* next = p->next;
            p->next = tmp;
            tmp->next = next;
            p = next;
        }
        // 跟新random
        for(Node* p = head;p;p=p->next->next)
        {
            if(p->random){
                p->next->random = p->random->next;
            }
        }
        Node* h = new Node(-1);
        Node* now = h;
        // 分开链表
        for(Node* p = head;p;p=p->next){
            now->next = p->next;
            now = now->next;
            p->next = now->next;
        }

        return h->next;
    }
};

Day3

替换空格

剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

记录一下原来字符串的长度，然后遍历字符串，看一下有多少个空格，每个空格会替换成%20，多增加2个字符

所以最终字符串的长度为s.size()+2*cnt。然后用双指针，从原来的长度，和新的字符串长度的最后的位置向前，如果原字符串不为空格就直接等，不然就要替换掉，并且新字符串的指针要减去2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string replaceSpace(string s) {
        int cnt=0,len=s.size();
        for(char a:s)
            if(a==' ')cnt++;
        s.resize(s.size()+2*cnt);
        for(int i = len-1,j=s.size()-1;i<j;i--,j--){
            if(s[i]!=' ')s[j]=s[i];
            else{
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=2;
            }
        }
        return s;
    }
};

做旋转字符串

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力解法，先记录字符串的长度，然后substr字符串前面指定长度的字符串添加到右边，然后在用substr，从指定位置长度开始向后取出原来字符串的长度

1
2
3
4
5
6
7
8
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int len = s.size();
        s = s+s.substr(0,n);
        return s.substr(n,len);
    }
};

解法2：翻转字符串三次即可

第一次：翻转前n个字符

第二次：再翻转n后面的字符

第三次：翻转整个字符串

比如

abcdef 3

第一次：cba def

第二次：cba fed

第三次：defabc

1
2
3
4
5
6
7
8
9
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};

Day4

数组中重复的数字

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)

我的解法：遍历数组，存入哈希表中，key是数组对应数字的值，value是其出现的次数，当次数大于1时就返回

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> mp;
        for(int a:nums){
            if(mp[a])return a;
            mp[a]++;
        }
        return 0;
    }
};

在排序数组中查找数字

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力方法

遍历数组，记录目标值出现的次数，O(n)O(n)，代码：有手就行

解法2：二分查找法

首先用一个二分查找其左边界，再用另一个二分查找其右边界，然后右边界-左边界+1即可,O(2logN)=O(logN)O(2logN)=O(logN)

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 数组为0就0
        if(!nums.size())return 0;
        // 查找左边界
        // 目标值左边界要满足：左边小于target右边大于等于target
        int l=0,r=nums.size()-1,mid;
        while(l<r){
            mid = l+r>>1;
            if(nums[mid]>=target) r = mid;
            else l = mid+1;
        }
        int pos = l;
        // 是否存在左边界
        if(nums[pos]!=target)return 0;
        // 查找右边界
        l = 0,r = nums.size()-1;
        while(l<r){
            mid=l+r+1>>1;
            if(nums[mid]<=target) l=mid;
            else r = mid-1;
        }
        return l-pos+1;
    }
};

0~n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力解法

遍历数组，找出来即可，O(n)O(n)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for(int i = 0;i<nums.size();i++)
            if(nums[i]!=i)
                return i;
        return nums.size();
    }
};

解法2：二分查找法

下标：0 1 2 3 4 5 6（0~n-1）

数组：0 1 2 4 5 6 7 (给的数组)

从上面可以看出，缺失的数字是3，在3的位置，左边的数字和下标是相等的右边是不等的，可以根据这个性质进行二分。O(logN)O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0,r = nums.size()-1;
        while(l<r){
            int mid = l+r>>1;
            if(mid != nums[mid]) r = mid;
            else l = mid+1;
        }
        if(nums[l]==l)l++;
        return l;
    }
};

Day5

今天拉了，竟然每题都只能暴力做

二维数组中的查找

剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力方法，O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(vector<int>a :matrix)
            for(int b:a)
                if(b==target)
                    return true;
        return false;
    }
};

解法2：二分的方法

选择矩阵的右上角这个点开始找，假设这个点的位置为x，如果我们的目标比x大，在x的左边他的值一定小于x，并且目标比x大，且这个点没有右边，所以这个时候就可以向下找一行。

同理，如果我们的目标比x小，他下面的目标一定比x大，所以也一定比目标大，所以这一列就没有答案了，这时候可以向左一行寻找。

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

旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力方法，O(n)O(n)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int mins = 1e9;
        for(int a:numbers)
            if(a<mins)mins = a;
        return mins;
    }
};

解法2：二分的方法

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
class Solution {
public:
    int minArray(vector<int>& numbers) {
        // 原数组在反转点的前半部分经过翻转后变成了后半部分
        // 即原数组的前半部分和新数组的后半部分相等
        // 输入的参数是新数组
        if(numbers.empty())return -1;
        int n = numbers.size()-1;
        // 删除原数组翻转点前半部分重复的数字
        while(n>0&&numbers[n]==numbers[0])n--;
        // 如果原数组反转点没有前半部分数字
        if(numbers[n]>=numbers[0])return numbers[0];
        // 二分
        int l = 0,r = n;
        while(l<r){
            int mid = l+r>>1;
            // 如果中间这个值比第一个数字大的话
            // 说明mid在新数组的后半部分，那么他前面包括他自己会有最小值
            if(numbers[mid]<numbers[0])r = mid;
            // 否则说明当前mid在新数组的前半部分，他后面会有最小值
            else l = mid+1;
        }
        return numbers[l];
    }
};

第一个只出现一次的字符

剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode） (leetcode-cn.com)

暴力模拟解法

这里其实可以不用队列，因为我这里遍历的是哈希表，他是无序的所以要队列表示一下顺序

如果重新遍历字符串的话，就不需要队列了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    char firstUniqChar(string s) {
        if(!s.size())return ' ';
        unordered_map<char,int> mp;
        queue<char> q;
        for(char a:s){
            if(!mp[a])q.push(a);
            mp[a]++;
        }
        char ans = ' ';
        while(q.size()){
            if(mp[q.front()]==1){
                ans = q.front();
                break;
            }
            else q.pop();
        }
        return ans;
    }
};

Day6

从上到下打印二叉树

面试题32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com)

从上到下表示从左到右输出上到下的每一层，用二叉树的宽搜就行了。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;
        if(!root)return res;
        q.push(root);
        while(q.size()){
            TreeNode* now = q.front();
            q.pop();
            res.push_back(now->val);
            if(now->left)q.push(now->left);
            if(now->right)q.push(now->right);
        }
        return res;
    }
};

从上到下打印二叉树2

剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com)

这题不太一样，他每一层的数都要做成一个数组

解法1：暴力解法

同样是宽搜，不过这次用了两个队列。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q1,q2;
        vector<vector<int>> res;
        if(!root)return res;
        q1.push(root);
        while(q1.size()||q2.size()){
            vector<int> tmp;
            while(q1.size()){
                TreeNode* now = q1.front();
                q1.pop();
                tmp.push_back(now->val);
                if(now->left)q2.push(now->left);
                if(now->right)q2.push(now->right);
            }
            if(tmp.size())res.push_back(tmp);
            tmp.clear();
            while(q2.size()){
                TreeNode* now = q2.front();
                q2.pop();
                tmp.push_back(now->val);
                if(now->left)q1.push(now->left);
                if(now->right)q1.push(now->right);
            }
            if(tmp.size())res.push_back(tmp);
        }
        return res;
    }
};

解法2：在每一层的结束添加一个空指针，减少了多个队列的使用

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)return res;
        queue<TreeNode*> q;
        // 在每一层结束的位置加一个nullptr
        q.push(root);
        q.push(nullptr);
        vector<int> tmp;
        while(q.size()){
            TreeNode* t = q.front();
            q.pop();
            // 如果当前的位置为nullptr
            // 说明这一层结束了
            if(!t){
                // 如果tmp为空的话说明下一层已经没有元素了
                if(tmp.empty())break;
                // 添加进答案
                res.push_back(tmp);
                // 清空存储数组
                tmp.clear();
                // 下一层的结束加一个nullptr
                q.push(nullptr);
                continue;
            }
            tmp.push_back(t->val);
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }
        return res;
    }
};

从上到下打印二叉树3

剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode） (leetcode-cn.com)

这次是按Z字型，分层打印了，在第二题的基础上加个flag，确定插入结果的数组是否需要翻转

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
45
46
47
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)return res;
        queue<TreeNode*> q;
        // 在每一层结束的位置加一个nullptr
        q.push(root);
        q.push(nullptr);
        vector<int> tmp;
        // true就需要翻转，否则不需要
        bool flag = false;
        while(q.size()){
            TreeNode* t = q.front();
            q.pop();
            // 如果当前的位置为nullptr
            // 说明这一层结束了
            if(!t){
                // 如果tmp为空的话说明下一层已经没有元素了
                if(tmp.empty())break;
                if(flag)reverse(tmp.begin(),tmp.end());
                // 每一行取反
                flag = !flag;
                // 添加进答案
                res.push_back(tmp);
                // 清空存储数组
                tmp.clear();
                // 下一层的结束加一个nullptr
                q.push(nullptr);
                continue;
            }
            tmp.push_back(t->val);
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }
        return res;
    }
};

Day7

树的子结构

剑指 Offer 26. 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)

主要考察边界条件的判断，这题用的是dfs，详解见代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        // 如果两棵树之一为空就不是其字结构
        if(!A||!B)return false;
        // 如果B时A的一部分就返回true
        if(ispart(A,B))return true;
        // 反之，如果B是A的左子树或右子树的一部分，则为true
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
    // B是否为A的一部分
    bool ispart(TreeNode*A,TreeNode*B){
        // 如果B遍历完了，不管A有没有遍历完，都说明B是A的一部分
        if(!B)return true;
        // 如果A遍历完了，但是B没遍历完，说明A不是B的一部分
        // 或者如果B没有遍历完，但是A的值和B的值不一样了，说明A不是B的一部分
        if(!A||A->val != B->val)return false;
        // 如果A的值和B的值相同
        // 那么B的左子树要是A的左子树的一部分并且B的右子树数A的左子树的一部分
        return ispart(A->left,B->left)&&ispart(A->right,B->right);
    }
};

二叉树的镜像

剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com)

实现一个交换函数，然后先交换root节点，然后递归镜像其左右子树即可。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        // 如果当前节点为空，就返回空
        if(!root)return NULL;
        // 交换当前节点
        swapTreeNode(root);
        // 递归镜像左右子树
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
	// 交换当前节点的左右子树
    void swapTreeNode(TreeNode* head){
        if(head){
            TreeNode* tmp = head->left;
            head->left = head->right;
            head->right = tmp;
        }
    }
};

对称的二叉树

剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com)

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 a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 如果未空就返回true
        if(!root)return true;
        // 确认一下左边和右边是不是对称的
        return dfs(root->left,root->right);
    }

    bool dfs(TreeNode* a, TreeNode*b){
        // 如果a或b为空，只有两个都是空的时候才为true
        if(!a||!b)return !a&&!b;
        // 如果a和b的值不相等，说明不对称
        if(a->val!=b->val)return false;
        // a的左值要等于b的右值
        // a的右值要等于b的左值
        return dfs(a->right,b->left)&&dfs(a->left,b->right);
    }
};

Day8

斐波那契数列

剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com)

这题刚学过编程的人都会了，我就不多说了,递归的方法会TLE，所以这里用迭代的方法计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int fib(int n) {
        const int N = 110,mod = 1e9+7;
        int f[N];
        memset(f,0,sizeof f);
        f[1]=1;
        for(int i = 2;i<=n;i++){
            f[i] = (f[i-1]+f[i-2])*1ll%mod;
        }
        return f[n];
    }
};

青蛙跳台问题

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode） (leetcode-cn.com)

这题就是斐波那契数列套壳，青蛙可以跳一级，也可以跳两级，也就是说如果当前位置是i的话，他要么从i-1的位置来，要么从i-2的位置来

那么最终的结果肯定和斐波那契数列一样有通项公式f[i]=f[i−1]+f[i−2]f[i] = f[i-1]+f[i-2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numWays(int n) {
        const int N = 110,mod = 1e9+7;
        int f[N];// 跳上N级台阶的做法
        memset(f,0,sizeof f);
        f[1] = 1;// 上一级台阶只有一种做法
        f[0] = 1;
        for(int i = 2;i<=n;i++){
            f[i] = (f[i-1]+f[i-2])*1ll%mod;
        }
        return f[n];
    }
};

股票的最大利润

剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode） (leetcode-cn.com)

明明是暴力题还要打上dp的tag，误导人是吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 是空的话就返回0
        if(prices.empty())return 0;
        // 肯定不会再第0天卖，所以最小值从第0天开始
        // 最小值拿来干什么？
        // 假设我们要在第5天卖，那我们买入的时间肯定是前4天中，price最小的那一天买入啊
        int min_v = prices[0],ans=0;
        for(int i = 1;i<prices.size();i++){
            // 如果最小值大于今天的价格，更新一下最小值，并且今天不卖出
            if(min_v>prices[i])min_v = prices[i];
            // 如果今天可以卖出，看一下哪个利润更大
            else ans = max(ans,prices[i]-min_v);
        }
        return ans;
    }
};

Day9

（昨天没写，今天补上）

连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com)

f[i]表示以i结尾的连续子数组最大和的值，然后遍历一遍f[i]=max(f[i-1]+nums[i],nums[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int f[100010];
        memset(f,0,sizeof f);
        f[0] = nums[0];
        for(int i = 1;i<nums.size();i++){
            f[i] = max(f[i-1]+nums[i],nums[i]);
        }
        int res = -110;
        for(int i = 0 ;i<nums.size();i++){
            if(res<f[i])
                res = f[i];
        }
        return res;
    }
};

礼物的最大价值

剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode） (leetcode-cn.com)

这题就是计算一下当前位置向右向下取得的价值是否比对应位置的最大价值大就行了，f[i][j]作为转换方程，他表示在(i,j)位置取得礼物的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        vector<vector<int>> f(grid.size(),vector<int>(grid[0].size()));
        f[0][0] = grid[0][0];
        int dx[]={1,0},dy[]={0,1};
        for(int i = 0 ;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                for(int k = 0;k<2;k++){
                    int x = i+dx[k],y = j+dy[k];
                    if(x<grid.size()&&y<grid[0].size()){
                        f[x][y] = max(f[x][y],f[i][j]+grid[x][y]);
                    }
                }
            }
        }
        return f[grid.size()-1][grid[0].size()-1];
    }
};

Day10

把数字翻译成字符串

剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode） (leetcode-cn.com)

f[i]表示前i个字符可以翻译的种数

比如：1223

1 可以翻译成a

12 可以翻译成ab,J

122可以翻译成abb,jb,av

1223可以翻译成abbc,jbc,avc,abw,jw

共5种

观察一下，第一个字符只有一种，得到初始条件f[0]=1

第二行，第一个字符已经确定了有f[0]种，然后本身直接翻译，就是一种等于f[0]，再观察一下当前和前一个组合是否在范围内，12显然在，所以在f[0]的基础上还要加上当前位置往后2格的种类数f[1-2]=f[-1]越界了，所以默认为1

第三行，前两个字符已经确定了，本身直接翻译就有f[3-1]=f[2]种，再观察前一个和当前的组合是否在范围内，22显然在，所以在f[2]的基础上还要加上f[2-2]=f[0]=1，所以f[3]=f[2]+f[0]=2+1=3

于是可以得到转化方程f[i] = f[i-1] + 前一个和当前的组合在范围内？(当前位置-2之后不为负数？1:f[i-2]):0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int translateNum(int num) {
        string a = to_string(num);
        vector<int> f(a.size());
        f[0] = 1;
        for(int i = 1;i<a.size();i++){
            f[i] = f[i-1];
            if(a[i-1]=='1'||(a[i-1]=='2'&&a[i]<'6')){
                if(i>1)f[i] +=f[i-2];
                else f[i]+=1;
            }
        }
        return f[a.size()-1];
    }
};

最长不含重复字符的子字符串

[剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)

子串：连在一起的叫子串

子序列：可以不连在一起的叫子序列

定义目标串的起点和终点都在最初的位置，然后开始向后遍历终点，终点位置如果没有出现在哈希表里，就将当前位置的字符作为key，value为end+1放到哈希表中，每次更新最长的距离为num = max(num,end-start+1)，如果当前字符已经出现过了，就确定是在start之前还是之后出现的，更细一下start的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> mp;
        int n=s.size(),start,end,res=0;
        for(start=0,end=0;end<n;end++){
            if(mp[s[end]]){
                start = max(start,mp[s[end]]);
            }
            res = max(res,end-start+1);
            mp[s[end]]=end+1;
        }
        return res;
    }
};

Day11

删除链表的节点

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode） (leetcode-cn.com)

就单纯的链表删除方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(!head)return head;
        if(head->val==val)return head->next;
        ListNode* p = head;
        while(p->next){
            if(p->next->val==val){
                p->next = p->next->next;
                break;
            }
            p = p->next;
        }
        return head;
    }
};

链表中倒数第K个节点

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode） (leetcode-cn.com)

先遍历一次看有多少个节点，再计算一下倒数第k个节点对应正数第几个节点nums-k，然后在遍历一次就行了

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int nums = 0,pos = 0;
        ListNode* p = head;
        while(p){
            nums++;
            p = p->next;
        }
        p = head;
        pos = nums-k;
        if(pos<0)return nullptr;
        while(pos--){
            p = p->next;
        }
        return p;
    }
};

Day12

合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode） (leetcode-cn.com)

就是归并排序的合并部分

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * head = new ListNode(-1);
        ListNode*t = head,*p=l1,*q=l2;
        while(p&&q){
            if(p->val<=q->val){
                t->next = p;
                p = p->next;
            }
            else {
                t->next = q;
                q = q->next;
            }
            t = t->next;
            t->next = nullptr;
        }
        if(p) t->next = p;
        if(q) t->next = q;
        return head->next;
    }
};

两个链表的第一个公共节点

剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode） (leetcode-cn.com)

解法1：使用哈希表存储每个节点出现的次数，如果出现了两次就直接返回

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_map<ListNode*,int> mp;
        int ans = 0;
        while(headA||headB){
            if(headA){
                if(mp[headA])return headA;
                mp[headA]++;
                headA = headA->next;
            }
            if(headB){
                if(mp[headB])return headB;
                mp[headB]++;
                headB = headB->next;
            }
        }
        return nullptr;
    }
};

解法2：就一直循环遍历两个链表，即使两个链表长度不一样，但经过有限次次循环后仍然能实现同时遍历到相交节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*p = headA,*q = headB;
        while(p!=q){
            p = (p)?p->next:headA;
            q = (q)?q->next:headB;
        }
        return p;
    }
};

Day13

调整数组顺序使奇数位于偶数前面

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)

感觉像快排的改进版

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        if(!nums.size())return nums;
        int l = -1,r = nums.size();
        while(l<r){
            do l++; while(l<r&&nums[l]%2);
            do r--; while(l<r&&nums[r]%2==0);
            if(l<r) swap(nums[l],nums[r]);
        }
        return nums;
    }
};

和为s的两个数字

剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode） (leetcode-cn.com)

解法1：哈希大法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int a:nums){ 
            if(a<target&&mp[target-a])return {target-a,a};
            mp[a]++;
        }
        return {};
    }
};

解法2:：双指针法

双指针过程，左右加和比s大，右边左移，比s小，左边右移，等于返回

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<r){
            int s = nums[l]+nums[r];
            if(s>target)r--;
            else if(s<target)l++;
            else return {nums[l],nums[r]};
        }
        return {};
    }
};

翻转单词顺序

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode） (leetcode-cn.com)

解法1：直接翻转法

先把整个字符串翻转过来，然后从左往右遍历，如果是空格就停止，翻转这部分的字符串（但这个方法A不了，虽然没什么问题，为什么A不了？因为他要输出的结果太变态了）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(),s.end());
        int pos = 0,end;
        while((end=s.find(' ',pos))!=string::npos){
            reverse(s.begin()+pos,s.begin()+end);
            pos = end+1;
        }
        reverse(s.begin()+pos,s.end());
        return s;
    }
};

解法2：上面的方法能A的版本

找个vector装起来吧

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:
    string reverseWords(string s) {
        int l = 0;
        while(s[l]==' ')l++;
        s = s.substr(l,s.size()-l);
        vector<string> ans;
        string res;
        reverse(s.begin(),s.end());
        int pos = 0,end;
        while((end=s.find(' ',pos))!=string::npos){
            reverse(s.begin()+pos,s.begin()+end);
            if(s[pos]!=' ') ans.push_back(s.substr(pos,end-pos));
            pos = end+1;
        }
        reverse(s.begin()+pos,s.end());
        ans.push_back(s.substr(pos,s.size()-pos));
        res = ans[0];
        for(int i = 1;i<ans.size();i++)
            res = res+" "+ans[i];
        return res;
    }
};

解法3：python有手就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = s.strip()
        data = s.split(' ')
        a = ""
        print(data)
        for i in range(1,len(data)+1):
            if data[len(data)-i]!='':
                a = a+data[len(data)-i]+" "
        return a.strip()

Day14

矩阵中的路径

剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode） (leetcode-cn.com)

先确定起始位置，然后遍历位置的四个方向，确定是否与我们的字符串匹配，典型的dfs

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
class Solution {
public:
    bool st[210][210];
    bool exist(vector<vector<char>>& board, string word) {
        // 枚举起点
        for(int i = 0;i<board.size();i++)
            for(int j = 0;j<board[0].size();j++)
                // 起点满足要求
                if(word[0]==board[i][j]){
                    st[i][j] = true;
                    if(dfs(i,j,board,word.substr(1,word.size()-1)))
                        return true;
                    st[i][j] = false;
                }
        return false;
    }
    // 从这个位置是否能得到字符串顺序的选择方式
    bool dfs(int x,int y,vector<vector<char>>& board,string word){
        int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
        // 字符串遍历完了，说明是存在的
        if(word=="")return true;
        // 不然就从当前位置遍历四个方向
        for(int i = 0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            // 新方向是否越界，是否经过，是否和字符串
            if(nx>=0&&ny>=0&&nx<board.size()&&ny<board[0].size()&&!st[nx][ny]&&word[0]==board[nx][ny]){
                st[nx][ny] = true;
                if(dfs(nx,ny,board,word.substr(1,word.size()-1)))
                    return true;
                st[nx][ny] = false;
            }
        }
        //如果四个方向都不对，那就返回false
        return false;
    }
};

机器人的运动范围

剑指 Offer 13. 机器人的运动范围 - 力扣（LeetCode） (leetcode-cn.com)

这题也是dfs，先写个check函数，确保坐标位数之和小于k，然后深搜，如果当前位置没有来过，并且满足check，就总数+1，并且这个位置设置为true，然后遍历当前位置的四个方向，否则直接退出。

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:
    int cnt;
    bool st[110][110];
    int movingCount(int m, int n, int k) {
        // 从0,0位置开始
        dfs(0,0,m,n,k);
        return cnt;
    }

    void dfs(int x,int y,int m,int n,int k){
        // 当前位置没有来过，并且满足check
        if(!st[x][y]&&check(x,y,k))cnt++,st[x][y]=true;
        else return;
        // 遍历这个位置的四个方向
        int dx[] = {-1,0,1,0},dy[]={0,1,0,-1};
        for(int i = 0 ;i<4;i++){
            int a = x+dx[i],b = y+dy[i];
            if(a>=0&&b>=0&&a<m&&b<n&&!st[a][b])
                dfs(a,b,m,n,k);
        }
    }
    
    bool check(int x,int y,int k){
        int res = 0;
        while(x||y){
            res = res+x%10+y%10;
            x/=10;
            y/=10;
        }
        return res<=k;
    }
};

Day15

二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode） (leetcode-cn.com)

创建结果数组，和路径数组，然后深搜二叉树的路径，满足条件直接存入结果中即可。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root,0,target);
        return ans;
    }

    void dfs(TreeNode* root,int sum,int target){
        // 如果节点为空的话就直接返回
        if(root==nullptr)return;
        // 不然就将这个点插入到path中
        path.push_back(root->val);
        // sum的和增加
        sum+=root->val;
        // 如果当前为叶子节点
        if(root->left==nullptr&&root->right==nullptr){
            // 看看是否满足要求
            if(target==sum) ans.push_back(path);
        }else{
            // 否则遍历他的左右子树
            dfs(root->left,sum,target);
            dfs(root->right,sum,target);
        }
        // 插入后需要移除，切换到下一路径
        path.pop_back();
    }
};

二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode） (leetcode-cn.com)

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return nullptr;
        // dfs将树转化成双向链表后，返回最左和最右的两个节点
        auto res = dfs(root);
        res.first->left = res.second;
        res.second->right = res.first;
        return res.first;
    }

    pair<Node*,Node*> dfs(Node* root){
        // 如果左右都有
        if(root->left&&root->right){
            // 先获取左右的最左和最右
            auto l = dfs(root->left),r = dfs(root->right);
            // 构建双向链表
            l.second->right = root,root->left = l.second;
            root->right = r.first,r.first->left = root;
            // 返回最左和左右
            return {l.first,r.second};
        }
        // 只做左边
        if(root->left){
            auto l = dfs(root->left);
            l.second->right = root,root->left = l.second;
            return {l.first,root};
        }
        // 只做右边
        if(root->right){
            auto r = dfs(root->right);
            root->right = r.first,r.first->left = root;
            return {root,r.second};
        }
        // 没有孩子，就返回自己
        return {root,root};
    }

};

二叉搜索树的第K大节点

剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int res;
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
    // 公用一个k
    void dfs(TreeNode* root,int &k){
        if(!root)return;
        // 中序遍历的二叉排序树可以得到有序的序列
        // 先左后右是正序，反之是倒序
        dfs(root->right,k);
        k--;
        if(!k)res = root->val;
        dfs(root->left,k);
    }
};

Day16

把数组排成最小的数

剑指 Offer 45. 把数组排成最小的数 - 力扣（LeetCode） (leetcode-cn.com)

这题是一个·贪心题，排序的时候要满足一个要求，即AB的组合方式要比BA的组合方式小即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    static bool cmp(int a,int b){
        string A = to_string(a);
        string B = to_string(b);
        return A+B<B+A;
    }
    string minNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string res;
        for(int i = 0 ;i<nums.size();i++)
            res += to_string(nums[i]);
        return res;
    }
};

扑克牌中的顺子

剑指 Offer 61. 扑克牌中的顺子 - 力扣（LeetCode） (leetcode-cn.com)

模拟题，首先先去除0的数字，然后判断有没有两张牌相同，有就是false，反之则还要判断是否最大值和最小值之间的差值小于4,即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        if(nums.empty())return false;
        sort(nums.begin(),nums.end());
        int k =0;
        while(nums[k]==0)k++;
        for(int i = k+1;i<nums.size();i++)
            if(nums[i] == nums[i-1])
                return false;
        return nums.back()-nums[k] <= 4;
    }
};

Day17

最小的K个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力，直接排序输出o(Nlog(N)+K)o(Nlog(N)+K)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        if(k >= arr.size()) return arr;
        vector<int> vec(arr.begin(), arr.begin()+k);
        return vec;
    }
};

解法2：用堆来存储，当堆中的数据大于k时，直接弹出最大值O(Nlog(K))O(Nlog(K))

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> heap;
        for(int a:arr){
            heap.push(a);
            if(heap.size()>k)heap.pop();
        }
        vector<int> res;
        while(heap.size())res.push_back(heap.top()),heap.pop();
        return res;
    }
};

数据流的中位数

剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode） (leetcode-cn.com)

解法1：直接有序插入，然后取中间即可

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> res;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(res.empty())res.push_back(num);
        else{
            int pos = 0;
            while(pos<res.size()&&res[pos]<num)pos++;
            res.insert(res.begin()+pos,num);
        }
    }
    
    double findMedian() {
        if(!res.size())return 0;
        if(res.size()%2)return res[res.size()/2]*1.0;
        else return (res[res.size()/2-1]+res[res.size()/2])/2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

解法2：用两个堆进行维护

举个例子，42315，小根堆存放45，大根堆存放321，那么他的中位数就是大根堆的堆顶

我们要保证大根堆比小根堆多1，或者相等，所以当我们要插入一个数6时

先插入大根堆，这时大根堆堆顶就是6，他比小根堆堆顶大，那就将两个交换一下

得到结果：小根堆存放56，大根堆存放4321

这时大根堆比小根堆多2了，为了维持平衡，就将大根堆堆顶放进小根堆中

得到结果：小根堆存放456，大根堆存放321

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> max_heap;
    priority_queue<int,vector<int>,greater<int>> min_heap;
    MedianFinder() {

    }
    
    void addNum(int num) {
        // 直接放入大跟堆
        max_heap.push(num);
        // 如果大跟堆的的最小值，比小根堆的最大值要大，就交换一下
        if(min_heap.size()&&max_heap.top()>min_heap.top()){
            int a = max_heap.top(),b = min_heap.top();
            max_heap.pop(),min_heap.pop();
            max_heap.push(b),min_heap.push(a);
        }
        // 如果大根堆比小根堆的数量多2，就将大根堆的堆顶放到小根堆中
        if(max_heap.size()>min_heap.size()+1){
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    
    double findMedian() {
        if(max_heap.size()+min_heap.size()&1)return max_heap.top();
        else return (max_heap.top()+min_heap.top())/2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

Day18

二叉树的深度

剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode） (leetcode-cn.com)

要实现一个输出二叉树深度的函数，那么当当前节点是NULL是输出0，否则，输出左子树和右子树深度的最大值，然后+1（当前节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;;
    }
};

平衡二叉树

剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode） (leetcode-cn.com)

就是左子树和右子树的最大深度不超过1，用上一题代码，再判断一下就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool ans = true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root){
        if(!root)return 0;
        int left = dfs(root->left),right = dfs(root->right);
        if(abs(left-right)>1)ans = false;
        return max(left,right)+1;
    }
};

Day19

求1+2+…+n

剑指 Offer 64. 求1+2+…+n - 力扣（LeetCode） (leetcode-cn.com)

解法1：等差数列求和公式总会吧，但是这题不能用乘除法，我就不写代码了

解法2：骤死性评估

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int ans;
    int sumNums(int n) {
        cal(n);
        return ans;
    }
    // 骤死性评估
    bool cal(int n){
        // 每次递归计算这个结果
        ans += n;
        // 当n为0时，前面的数字为假，将不会进行后面的判断
        return n && cal(n-1);
    }
};

二叉搜索树的最近公共祖先

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)

二叉搜索的节点满足如下性质：

  1. 该节点的左边的所有节点，一定比该节点小
  2. 该节点的右边的所有节点，一定比该节点大

如果，p,q在这个节点的两边，那么直接返回这个节点，如果都在左边就遍历左边，如果都在右边，就遍历右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 为空直接返回
        if(!root)return NULL;
        // 如果在两边
        if((p->val <= root->val&&q->val>=root->val)||(p->val >= root->val&&q->val<=root->val))return root;
        // 如果在左边，就去左子树找
        if(p->val < root->val&&q->val<root->val)return lowestCommonAncestor(root->left,p,q);
        // 否则去右边找
        return lowestCommonAncestor(root->right,p,q);
    }
};

二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)

直接看代码吧，代码有解析

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 如果当前遍历的节点为空，返回空
        if(!root)return nullptr;
        // 如果遍历到p或者q，如果p，q在同侧，肯定会先遍历到p或者q，那么他们的公共祖先肯定是两者之一
        // 如果不在同侧，那么遍历到p或q之后，肯定不会有另一了，所以直接返回当前节点
        if(root == p || root ==q)return root;
        // 看看p或q在左边还是右边
        // 如果在两侧的话,p,q都不为空
        // 在左侧的话，肯定只有left不空
        // 在右侧则只有right不空
        TreeNode* left = lowestCommonAncestor(root->left,p,q),*right = lowestCommonAncestor(root->right,p,q);
        // 如果在两侧，就直接返回当前节点
        if(left&&right)return root;
        // 如果在单侧
        // 如果左不空，则返回左
        if(left)return left;
        // 否则返回右
        return right;
    }
};

Day20

重建二叉树

剑指 Offer 07. 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int,int> mp;
    vector<int> P,I;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        P= preorder,I = inorder;
        // 记录各个点在中序遍历中的位置
        for(int i = 0 ;i<I.size();i++)mp[I[i]] = i;
        return dfs(0,P.size()-1,0,I.size()-1);
    }
    // 生成前序遍历范围为[pl,pr]且中序遍历在[il,ir]的节点构成的树
    TreeNode* dfs(int pl,int pr,int il,int ir){
        // 如果pr比pl小，说明没有节点了
        if(pl>pr)return NULL;
        // 先构建前序遍历的第一个节点(根节点)
        TreeNode* root = new TreeNode(P[pl]);
        // 找出根节点在中序遍历的位置
        int k = mp[root->val];
        // 生成其左子树
        auto left = dfs(pl+1,pl+k-il,il,k-1);
        // 生成其右子树
        auto right = dfs(pl+k-il+1,pr,k+1,ir);
        // 合并
        root->left = left,root->right = right;
        return root;
    }
};

数值的整数次方

剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode） (leetcode-cn.com)

解法1：递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    double myPow(double x, int n) {
        // 基本条件结束
        if(x == 0.0)return 0;
        if(n == 0) return 1;
        if(n == -1) return 1/x;
        if(n == 1)return x;
        // 比如我们要知道40，那么只用知道20即可，因为x**40=x**(20+20)=(x**20)*(x**20)
        // 如果是奇数41，那么x**40=x**(20+20+1)=(x**20)*(x**20)*x
        double res = myPow(x,n>>1);
        return n&1?res*res*x:res*res;
    }
};

解法2：快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double myPow(double x, int n) {
        long a = n;
        if(a<0){
            a = -a;
            x = 1/x;
        }
        double res = 1;
        while(a){
            if(a&1)res*=x;
            x *= x;
            a>>=1;
        }
        return res;
    }
};

二叉搜索树的后续遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode） (leetcode-cn.com)

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:
    bool verifyPostorder(vector<int>& postorder) {
       return dfs(postorder,0,postorder.size()-1);
    }
    // 后续遍历最后一个节点一定是根节点
    // 平衡二叉树的左子树的数字一定比根小
    // 平衡二叉树的右子树一定比根大
    bool dfs(vector<int>& postorder,int l,int r){
        // 如果当前子树没有节点，或者只有一个节点，就返回ture
        if(l>=r)return true;
        // 获取根
        int root = postorder[r];
        int k = l;
        // 获取左子树的节点
        while(k<r&&postorder[k]<root)k++;
        // 看看右子树是否都比根大
        for(int i = k;i<r;i++)
            if(postorder[i]<root)return false;
        // 左子树和右子树都满足平衡二叉树的条件就是true
        return dfs(postorder,l,k-1)&&dfs(postorder,k,r-1);
    }
};

Day21

二进制中1的个数

剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n){
            if(n&1)cnt++;
            n>>=1;
        }
        return cnt;
    }
};

不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int add(int a, int b) {
        while(b){
            // 不进位加法
            int s = a^b;
            // 进位
            int c =  (unsigned int)(a&b)<<1;
            // 做一遍不进位的加法+进位
            a = s,b=c;
        }
        return a;
    }
};

Day22

数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int res=0,div,a=0,b=0;
        // 找出这两个数字的异或结果
        for(int i:nums)
            res ^= i;
        // 找出这两个数第一个不同的位置
        // lowbit(x)，位运算经典操作
        div = -res&res;
        // 根据这个位置进行分组异或
        for(int i:nums){
            if(i&div)a^=i;
            else b^=i;
        }
        return {a,b};
    }
};

数组中数字出现的次数2

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（LeetCode） (leetcode-cn.com)

解法1：哈希暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int,int> hash;
        for(int i :nums)
            hash[i]++;
        int res;
        for(auto a=hash.begin();a!=hash.end();a++)
            if(a->second==1)
                {res = a->first;break;}
        return res;
    }
};

解法2：自动机，把目标值每一位单独来看，因为计算机本身是32位并行运算的，位运算之间互不干扰，所以你对以为做运算，也就等于对其他位也做了运算，我也解释不出来，

假设当前位有一个输入1，那么从a,b初始化后从状态(0,0)，获得状态a = (0^1)&~0=1&1=1,b=(0^1)&~1=1&0=0即(1,0)，同理，如果再获得一个1从(1,0)可以获得状态(a=(1^1)&~0=0&1=0,b=(0^1)&~0=1&1=1)即(0,1)，再获得一个1，就会得到状态(0,0)，这是就满足，如果有3个1，就会回到最初的状态，这对应了题目中的出现3次的数字，如果出现0呢？(0,0)输入0得到(a=(0^0)&~0=0,b=(0^0)&~0=0)即(0,0)，同理(1,0)和(0,1)分别得到一个0，就会得到(1,0)和(0,1)，因此获得0并不会影响结果。当把数组中的数字都经过这个自动机转化后，就能得到只出现一次的数字了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a=0,b=0;
        for(int n:nums){
            a = (a^n)&~b;
            b = (b^n)&~a;
        }
        return a;
    }
};

Day23

数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode） (leetcode-cn.com)

解法1：暴力哈希法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> res;
        for(int i :nums)
            res[i]++;
        int t = 0;
        for(auto a = res.begin();a!=res.end();a++)
            if(a->second > nums.size()/2){
                t = a->first;
                break;
            }
        return t;
    }
};

解法2：摩尔投票法

这题的思路就是，当前认为是众数的数字就在cnt上+1否则就-1，如果当前的cnt为0是，就替换众数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0,data = 0;
        for(int a:nums){
            if(cnt == 0)data = a;
            cnt += a==data?1:-1;
        }
        return data;
    }
};

构建乘积数组

剑指 Offer 66. 构建乘积数组 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if(a.empty())return {};
        int n = a.size();
        // 初始化构造数组
        vector<int> b(n);
        // 双指针，先令b[i]等于其左边的乘积
        for(int i = 0 ,p=1;i<n;i++){
            b[i] = p;
            p *= a[i];
        }
        // 再令b[i]乘上右边的乘积
        for(int i = n-1,p=1;~i;i--){
            b[i] *= p;
            p *= a[i];
        }
        return b;
    }
};

Day24

剪绳子1

剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    int cuttingRope(int n) {
        /*
        数学知识：
        假设N>0, 满足题意的最优解是这个N=n1+n2+...+nk
        1.  ni 一定没有 >= 5的数字，理由如下
            如果ni>=5，那么他可以被拆分成3*(ni-3)，这样会使得乘积变大，但是，加和并没改变
            证明：3*(ni-3) = 3*ni - 9 > ni   ->  2*ni > 9
            ni >= 5, 2*ni>=10 > 9
        2. ni 也一定没有=4的数字，理由如下
            如果ni = 4, 4=2*2，4就可以拆成2
        3. ni 一定没有=1的数字，因为拆成1之后没有使得原来的数字变大
        
        所以最优解中一定是由2和3组成的数字
        */
        // 2的话，就只能55开，即1和1
        // 3的话，1，2最大了，最少为两段
        if(n<=3)return 1*(n-1);
        int res = 1;
        // 如果n%3=1的话，说明2的个数应该有2个，因为2*2 = 4 %3 = 1
        // 这时结果乘上4，然后不要这个4即可
        if(n%3==1)res*=4,n-=4;
        // 如果n%3=2的话，说明2的个数应该有1个，因为1*2 = 2 %3 = 2
        // 这时结果乘上2，然后不要这个2即可
        if(n%3==2)res*=2,n-=2;
        // 剩下的数字都是3了
        while(n)res*=3,n-=3;
        return res;
    }
};

和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        // 连续至少有两个吧，有两个是不是遍历一半就行了
        for(int i = 1,j=1,s=1;i<=target/2+1;i++){
            // 双指针算法，假设当i~j刚好为s时，如果i变大时，j变小或不变，则会导致i~j小于s，所以j也只会变大
            while(s < target)s+=++j;
            // 如果当前的加和结果比目标值大，并且i和j相差1，就将这个结果加进去
            if(s==target&&j-i>=1){
                vector<int> a;
                for(int k = i ;k<=j;k++)a.push_back(k);
                res.push_back(a);
            }
            // i要变大，所以要减去个i
            s -= i;
        }
        return res;
    }
};

圆圈中最后剩下的数字

剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode） (leetcode-cn.com)

经典约瑟夫问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n==1)return 0;
        return (lastRemaining(n-1,m)+m)%n;
    }
};
/*
我们的函数是在n中干掉第m个之后最后剩下的那个人的坐标
f(n,m） 在干掉一个人后会变成f(n-1，m）的一个问题
在干掉了一个人的编号后，为：				m,m+1,m+2,m+3,...
字问题最初的编号(即n-1的问题)，为：	   0, 1 , 2 , 3 ,...
当我们得到子问题的解后，要映射回原来的坐标就是 (res+m)%n
*/

Day 25

顺时针打印矩阵（据说面试必考）

剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode） (leetcode-cn.com)

解法1：我的暴力模拟方法（我是笨比）

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty())return {};
        vector<int> res;
        int l = 0,r=matrix[0].size()-1,t=0,b=matrix.size()-1;
        int x=0,y=0;
        int mode = 0,dx,dy;
        while(x>=t&&x<=b&&y>=l&&y<=r){
            res.push_back(matrix[x][y]);
            // 向右
            if(mode == 0){
                dy=1;
                // 右上角
                if(y+dy>r){
                    mode = 1;
                    t++;
                    x++;
                    continue;
                }
                y+=dy;
            // 向下
            }else if(mode == 1){
                dx = 1;
                // 右下角
                if(x+dx>b){
                    mode = 2;
                    r--;
                    y--;
                    continue;
                }
                x+=dx;
            // 向左
            }else if(mode == 2){
                dy = -1;
                // 左下角
                if(y+dy<l){
                    mode = 3;
                    b--;
                    x--;
                    continue;
                }
                y+=dy;
            // 向上
            }else if(mode==3){
                dx = -1;
                // 左上角
                if(x+dx<t){
                    mode = 0;
                    l++;
                    y++;
                    continue;
                }
                x+=dx;
            }
        }   
        return res;
    }
};

解法2：巧妙模拟

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int n = matrix.size();
        if(!n)return {};
        int m = matrix[0].size();

        vector<vector<bool>> st(n,vector<bool>(m,false));
        // 左下右上
        int dx[4] = {-1,0,1,0},dy[4]={0,1,0,-1};
        // 当前位置和当前方向
        int x = 0,y=0,d=1;
        for(int i = 0 ;i<n*m;i++){
            // 将当前值放入结果中
            res.push_back(matrix[x][y]);
            // 标记
            st[x][y] = true;
            // 更新值
            int a = x+dx[d],b = y+dy[d];
            // 如果这个值越界了，或使用过了
            if(a<0||a>=n||b<0||b>=m||st[a][b]){
                // 更新方向
                d = (d+1)%4;
                // 重新更新位置
                a = x+dx[d],b = y+dy[d];
            }
            x=a,y= b;
        }
        return res;
    }
};

栈的压入，弹出序列

剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode） (leetcode-cn.com)

模拟入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        	// 长度不同直接false
            if(pushed.size() != popped.size())return false;
            stack<int> st;
            int p = 0;
        	// 把每个元素入栈
            for(auto x:pushed){
                st.push(x);
                // 每次按照弹出顺序弹出
                while(st.size()&&st.top()==popped[p])st.pop(),p++;
            }
        	// 如果能全部弹出就是正确
            return st.empty();
    }
};

Day26

表示数字的字符串

剑指 Offer 20. 表示数值的字符串 - 力扣（LeetCode） (leetcode-cn.com)

解法1：直接模拟

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
class Solution {
public:
    bool isNumber(string s) {
        int i = 0,j=s.size()-1;
        while(i<=j&&s[i]==' ')i++;
        while(i<=j&&s[j]==' ')j--;
        if(i>j)return false;

        s = s.substr(i,j-i+1);
        if(s[0]=='+'||s[0]=='-')s=s.substr(1);
        if(s.empty()||(s[0]=='.'&&s.size()==1))return false;

        int dot = 0,e=0;
        for(int i = 0;i<s.size();i++){
            if(s[i]>='0'&&s[i]<='9');
            else if(s[i]=='.'){
                dot++;
                if(dot>1||e)return false;
            }
            else if(s[i]=='e'||s[i]=='E'){
                e++;
                if(!i||i+1==s.size()||e>1||s[i-1]=='.'&&i==1)return false;
                if(s[i+1]=='+'||s[i+1]=='-'){
                    if(i+2==s.size())return false;
                    i++;
                }
            }
            else return false;
        }
        return true;
    }
};

解法2：正则表达式，C++不太友好，反正我超时了，我崩溃了，写了好久的正则，呜呜呜，我是笨蛋

解法3：状态自动机，可以根据写好的正则式转化成NFA再转化成DFA（编译原理内容），然后根据建立好的DFA进行模拟，如果能够进入终态就是符合的，我就不写代码了，后面有时间再看看

把字符串转换成整数

剑指 Offer 67. 把字符串转换成整数 - 力扣（LeetCode） (leetcode-cn.com)

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:
    int strToInt(string str) {
        if(!str.size())return 0;
        bool fu=false;
        long long num =0;
        int k = 0;
        // 去除空格
        while(k<str.size()&&str[k]==' ')k++;
        // 正负判断
        if(str[k]=='+')k++;
        else if(str[k]=='-')k++,fu=true;
        // 取数值
        while(k<str.size()&&str[k]>='0'&&str[k]<='9'){
            num = num * 10+str[k]-'0';
            // 越界警告
            if(fu&&-1*num<INT_MIN){num = INT_MIN,fu=false;break;}
            if(!fu&&num>INT_MAX){num = INT_MAX;break;}
            k++;
        }
        // 取值
        if(fu) num*=-1;
        if(INT_MAX<=num)return INT_MAX;
        if(INT_MIN>=num)return INT_MIN;
        return num;
    }
};

Day 27

滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode） (leetcode-cn.com)

经典的单调队列算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    // 初始化单调栈
    int q[100010];
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        // 初始化头和尾的索引
        int hh = 0,tt=-1,n=nums.size();
        // 遍历数组
        for(int i = 0 ;i<n;i++){
            // 如果队列中有数据，并且当前的队头超过了滑动窗口
            if(hh<=tt&&i-k+1>q[hh])hh++;
            // 当队列不单调时就让其变得单调
            while(hh<=tt&&nums[q[tt]] <= nums[i])tt--;
            q[++tt] = i;
            // 满足滑动窗口条件才输出结果
            if(i>=k-1)res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

队列的最大值

剑指 Offer 59 - II. 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com)

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
class MaxQueue {
public:

    queue<int> q;
    deque<int> mq;
    MaxQueue() {

    }
    
    int max_value() {
        // deque存储单调队列，从大到小排序
        return mq.size()?mq.front():-1;
    }
    
    void push_back(int value) {
        // 如果单调队列中有数据，并且如果要插入当前数据使得他不再单调，就去除队尾
        while(mq.size()&&mq.back() <= value) mq.pop_back();
        // 插入当前元素进入单调队列和队列中
        mq.push_back(value);
        q.push(value);
    }
    
    int pop_front() {
        // 如果单调队列中没有数字就直接返回-1
        if(!mq.size())return -1;
        // 如果当前出队的头和单调队列中队头相同就出队
        if(q.front()==mq.front())
            mq.pop_front();
        // 返回结果
        int res = q.front();
        q.pop();
        return res;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

Day28

序列化二叉树

剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode） (leetcode-cn.com)

解法1：自欺欺人写法

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    TreeNode* res;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        res = root;
        return "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return res;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

解法2：前序遍历序列化

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // 初始化字符串
        string res;
        dfs_s(root,res);
        return res;
    }

    void dfs_s(TreeNode* root,string &res){
        // 如果当前节点为空，写入null
        if(!root){
            res += "null ";
            return;
        }
        // 将结果加入序列字符串中，并以空格隔开
        res += to_string(root->val)+" ";
        // 处理左子树
        dfs_s(root->left,res);
        // 处理右子树
        dfs_s(root->right,res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data,u);
    }

    TreeNode* dfs_d(string data,int &u){
        // 如果字符串遍历完了就寄了
        if(u==data.size())return NULL;
        // 用个变量记录下一个空格的位置
        int k = u;
        while(data[k]!=' ')k++;
        // 如果当前的值是null，就返回null
        if(data[u]=='n'){
            u = k+1;
            return NULL;
        }
        // 将字符串转化成值，有负值
        int val = 0,sign = 0;
        if(data[u]=='-') sign = 1;
        for(int i = u+sign;i<k;i++) val = val*10+data[i]-'0';
        if(sign) val *= -1;
        // 更新位置
        u = k+1;
        // 创建几点
        auto root =new TreeNode(val);
        // 更新左右
        root->left = dfs_d(data,u);
        root->right = dfs_d(data,u);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

字符串的排列

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode） (leetcode-cn.com)

解法1：爆搜+set去重

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
class Solution {
public:
    set<string> res;
    vector<string> permutation(string s) {
        int n = s.size();
        vector<bool> st(n,false);
        dfs(s,st,0,"");
        vector<string> ress;
        for(auto i = res.cbegin();i != res.cend();i++)
            ress.push_back(*i);
        return ress;
    }
    void dfs(string s,vector<bool> &st,int u,string a){
        if(u==s.size()){
            res.insert(a);
            return;
        }
        for(int i = 0 ;i<s.size();i++){
            if(st[i])continue;
            st[i] = true;
            dfs(s,st,u+1,a+s[i]);
            st[i] = false;
        }
    }
};

解法2：STL的魔法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> res;
        sort(s.begin(),s.end());
        do {
            res.push_back(s);
        } while(next_permutation(s.begin(), s.end()));
        return res;
    }
};

Day29

正则表达式匹配

面试题19. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)

这题我好像写过了，可以全局搜一下

丑数

剑指 Offer 49. 丑数 - 力扣（LeetCode） (leetcode-cn.com)

假设丑数序列为： S = a1,a2,a3,a4…

有序列（2的倍数） S1 = b1,b2,b3,b4…

有序列（3的倍数） S2 = c1,c2,c3,c4…

有序列（5的倍数） S3 = d1,d2,d3,d4…

S = 1,2,3,4,5,6,8,9,…=1并S1并S2并S3

并且S1/2= S，S2/3=S，S3/5=S

因此我们想把1放进数组里，然后用三个指针指向1，三个指针分别乘2,3,5，每次插入他们乘积的最小值，然后如果他们的乘积等于最小值，就移动这个指针，移动n-1次即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> f(1,1);
        int a=0,b=0,c=0;
        while(--n){
            int t = min(f[a]*2,min(f[b]*3,f[c]*5));
            f.push_back(t);
            if(f[a]*2==t)a++;
            if(f[b]*3==t)b++;
            if(f[c]*5==t)c++;
        }
        return f.back();
    }
};

n个骰子的点数

剑指 Offer 60. n个骰子的点数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<double> dicesProbability(int n) {
        // f[i,j]前i个骰子，出j的方案数
        vector<vector<int>> f(n+1,vector<int>(n*6+1));
        // 0个选择出0，结果为1
        f[0][0] = 1;
        // 遍历n个骰子
        for(int i = 1;i<=n;i++)
            // 遍历所有可能性
            for(int j = 1;j<=i*6;j++)
                // 遍历骰子的可能性，但是骰子的上限不能超过6
                for(int k = 1;k<=min(j,6);k++)
                    f[i][j] += f[i-1][j-k];
        vector<double> res;
        // 总选择数
        double total = (double)pow(6,n);
        for(int i = n;i<=n*6;i++)res.push_back(f[n][i]/total);
        return res;
    }
};

Day30

打印从1到最大的n位数

剑指 Offer 17. 打印从1到最大的n位数 - 力扣（LeetCode） (leetcode-cn.com)

写了这么多奇奇怪怪的题，突然碰到这题，感觉自己受到侮辱

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        long  big = pow(10,n);
        int tmp = 1;
        while(tmp<big)
            res.push_back(tmp++);
        return res;
    }
};

数组中的逆序对

剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)

归并排序的思想，首先把数组分成两段，理想应该左边的数据都比右边的大

那么就双指针遍历两头，如果左边端的数字比右边端的数字大，那么就下一个左边段的数字

但是如果有一个右边端的数字j比左边段的数字小，那么，从当前位置i，到mid的数字都会会右边段的数字j形成逆序对，即mid-i+1个

所以归并+状态记录就结束了

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
class Solution {
public:
	// 返回序列中逆序对的个数
    int merge(vector<int>& a,int l,int r){
        if(l>=r)return 0;
        int mid = l+r>>1;
        vector<int> tmp;
        int i = l,j = mid+1;
        // 左边逆序对个数+右边逆序对个数
        int res = merge(a,l,mid)+merge(a,mid+1,r);
        while(i<=mid&&j<=r){
            if(a[i]<=a[j])tmp.push_back(a[i++]);
            else{
                // 如果右边端的一个数比左边段大，就会构成逆序对
                tmp.push_back(a[j++]);
                res+=mid-i+1;
            }
        }
        while(i<=mid)tmp.push_back(a[i++]);
        while(j<=r)tmp.push_back(a[j++]);
        i = l;
        for(int x:tmp)a[i++] = x;
        return res;
    }

    int reversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size()-1);
    }
};

Day31(最后一天)

剪绳子2

剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode） (leetcode-cn.com)

和第24天的剪绳子一样的题，只是这次要取一个膜

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int cuttingRope(int n) {
        const int mod = 1e9+7;
        if(n<=3)return n-1;
        int res = 1;
        if(n%3==1)res *=4,n-=4;
        if(n%3==2)res*=2,n-=2;
        while(n)res= res *1ll* 3%mod,n-=3;
        return res;
    }
};

1~n整数中1出现的次数

剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

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 countDigitOne(int n) {
        // 是0 就不存在了
        if(!n)return 0;
        vector<int> number;
        // 把数字存入数组中
        while(n) number.push_back(n%10),n/=10;
        // 记录有多少个1
        int res = 0;
        // 遍历数字的每一位
        for(int i = number.size()-1;i>=0;i--)
        {
            // 左边值右边值
            auto left = 0,right = 0,t = 1;
            // 原数据计算左边的数值大小
            for(int j = number.size()-1;j>i;j--) left = left*10+number[j];
            // 计算原数据右边的数值大小
            for(int j = i-1;j>=0;j--)right = right*10+number[j],t*=10;
            // 左边数字的选择可以从0~left-1),t表示当前位置往后有n位数，即这n位数随便选，可选的总数是t
            res+=left*t;
            // 当左边为left时
            if(number[i]==1)res+=right+1;//如果当前位置上的数字是1，那么右边部分只能从0~right
            else if(number[i]>1)res+=t;// 否则可以0~t
        }
        return res;
    }
};

数字序列中某一位的数字

剑指 Offer 44. 数字序列中某一位的数字 - 力扣（LeetCode） (leetcode-cn.com)

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:
    int findNthDigit(int n) {
        // i是当前选中数集合中有多少位，比如i=1表示{0~9},i=2表示{10~99}
        // s是i位的情况下集合中元素的数量
        // base表示集合中最小的那个元素
        long long i = 1,s = 9,base=1;
        // n是所有数组平铺之后的总位数
        // 如果n比当前集合所有位数都大，就减去这个区间的数，然后换到下一个位数
        // i（一个元素有多少位）*s（这个元素集合中元素的个数）
        while(n>i*s){
            // 减去
            n-=i*s;
            // 加位
            i++;
            // 扩张集合个数
            s*=10;
            // 扩张base
            base *=10;
        }
        // number：目标数字的值
        // 现在还剩 n位 然后他应该是n位数字集合中的第n/i个数，但是如果能整除就直接结果，不然就得向上取整
        // 然后c++没有向上取整，所以用(n+i-1)/i表示向上取整
        // 所以这个数字应该是base+x-1(减一是因为从0开始)
        int number = base + (n+i-1)/i-1;
        // 确定一下目标值是这个数字的第几位
        // 如果这个结果不是0，说明就是第n%i位，但是如果是0的话就是最后一位，即i
        int r = n%i?n%i:i;
        // 然后如果你是第r位的话只用做i-r-1次除法就行，然后直接取模
        for(int j = 0;j<i-r;j++)number/=10;
        return number%10;
    }
};

结语

31天终于写完了，感觉之前写过了的又忘了，感觉自己还是什么都不会，但是学这种东西就是得不断重复的，所以加油吧！