刷题使我快乐.jpg
2021-05-19 09:22:40 #数据结构与算法  #数据结构与算法  #CPP 

要注意！！！

  1. 先看测试用例
  2. 找测试用例的边界，如元素为空、一个元素、两个元素等特殊情况
  3. 根据特殊的测试用例设置退出条件
  4. 用语言总结一遍算法思路，边画图边说
  5. 根据常规测试用例画图走一遍代码

数组

寻找两个正序数组的中位数

类似于归并排序的双指针：

  1. 计算数组大小和，得出中位数的位置

    大小和为奇数：直接取中位数

    大小和为偶数：取中间两位数的平均值

  2. 双指针分别指向两个数组开端，并依据中位数位置，循环相应次数

  3. 得到中位数

注意情况：

  1. 正常进行，两个指针分别指向两个数组中某个位置
  2. 一个数组为空，另一个数组不为空
  3. 排序时，一个排空了，但未到中位数位置

版本 1，利用vector<int> temp，缓冲，存入数组前一半，便于判断奇偶数情况，空间开销大

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 Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 两数组可能一个为空，另一个只有一个元素
        // 注意这种情况
        int ptr1=0,ptr2=0;
        int len=nums1.size()+nums2.size();

        if(len==1) return nums1.empty()?nums2[0]:nums1[0];

        vector<int> temp(len/2);
        while(ptr1+ptr2<len/2){
            if(ptr1==nums1.size()){
                temp.emplace_back(nums2[ptr2]);
                ++ptr2;
            }else if(ptr2==nums2.size()){
                temp.emplace_back(nums1[ptr1]);
                ++ptr1;
            }else{
                if(nums1[ptr1] <= nums2[ptr2]){
                    temp.emplace_back(nums1[ptr1]);
                    ++ptr1;
                }else{
                    temp.emplace_back(nums2[ptr2]);
                    ++ptr2;
                }
            }
        }
        int tem=0;
        if(ptr1==nums1.size()) tem=nums2[ptr2];
        else if(ptr2==nums2.size()) tem=nums1[ptr1];
        else tem=nums1[ptr1]<=nums2[ptr2]?nums1[ptr1]:nums2[ptr2];

        if(len%2) return tem;
        return (double)(temp[temp.size()-1]+tem)/2;
    }
};

版本 2，不利用vector<int> temp，利用int temp保存循环中每次跳过的值

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:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 两数组可能一个为空，另一个只有一个元素
        // 注意这种情况
        int ptr1=0,ptr2=0;
        int len=nums1.size()+nums2.size();

        if(len==1) return nums1.empty()?nums2[0]:nums1[0];

        int temp;
        while(ptr1+ptr2<len/2){
            if(ptr1==nums1.size()) temp=nums2[ptr2++];
            else if(ptr2==nums2.size()) temp=nums1[ptr1++];
            else{
                if(nums1[ptr1] <= nums2[ptr2]) temp=nums1[ptr1++];
                else temp=nums2[ptr2++];
            }
        }
        int tem=0;
        if(ptr1==nums1.size()) tem=nums2[ptr2];
        else if(ptr2==nums2.size()) tem=nums1[ptr1];
        else tem=nums1[ptr1]<=nums2[ptr2]?nums1[ptr1]:nums2[ptr2];

        if(len%2) return tem;
        return (double)(temp+tem)/2;
    }
};

栈和队列

栈的压入、弹出序列

边界条件：

  1. 两个序列长度不等
  2. 两个序列为空
  3. 一个序列为空另一个序列不为空

思路：

  1. 设置一个栈，用来放置压入序列
  2. 设置两个变量记录压入序列push_count和弹出序列的位置pop_count
  3. 对弹出序列从头到尾依次判断
  4. 当前弹出序列的元素只可能是栈顶和还未入栈的元素
  5. 如果是栈顶，弹出栈顶并判断下一个弹出序列的元素
  6. 如果不是栈顶，继续将压入序列的元素压入，并在下一次循环判断栈顶和弹出序列的元素
  7. 正常退出循环条件：push_count和pop_count都等于序列长度时，表示判断完成，返回true
  8. 异常退出循环条件：当将压入序列所有元素压入栈并且栈顶还与弹出序列当前元素不等时，说明当前元素被压入栈顶之下，因此不是弹出序列，会导致push_count再次 +1，大于压入序列的长度，此时可以直接退出循环，返回false
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 Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()!=popped.size()) return false;
        if(pushed.empty() && popped.empty()) return true;
        if(pushed.empty() || popped.empty()) return false;

        stack<int> stack;
        int push_count=0;
        int pop_count=0;
        while(push_count < pushed.size() || pop_count < popped.size()){
            if(stack.empty() || popped[pop_count]!=stack.top()){
                if(push_count+1>pushed.size()) return false;
                stack.emplace(pushed[push_count]);
                ++push_count;
            }
            else{
                stack.pop();
                ++pop_count;
            }
        }
        return true;
    }
};

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

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:
    vector<int> exchange(vector<int>& nums) {
        if(nums.size()>1){
            int head=0;
            int last=nums.size()-1;
            int tmp=0;
            while(head<last){
                while(nums[head]%2==1 && head<last) ++head;
                while(nums[last]%2==0 && head<last) --last;

                if(head<last){
                    tmp=nums[head];
                    nums[head]=nums[last];
                    nums[last]=tmp;
                }
            }
        }

        return nums;
    }
};

栈的最小值

利用两个栈，一个数据栈正常压入数据，另一个最小栈压入当前最小的值

每次数据栈压值时，与最小栈的栈顶比较，小于等于最小栈栈顶时，同步压入最小栈

数据栈弹出值时，如果与最小栈的栈顶相等，则同步弹出最小栈的栈顶

注解：当压栈值大于最小栈栈顶时，不需要考虑它是否要压入最小栈。因为既然最小栈存在比它小的值，则根据先进后出原则，当前压栈值必然比小于它的数据栈元素先出栈

利用 vector 作为栈的容器比较合适

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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack():stackData(),stackMin() {}

    void push(int x) {
        stackData.emplace(x);
        if(stackMin.empty() || x<=stackMin.top()) stackMin.emplace(x);
    }

    void pop() {
        if(stackData.top()==stackMin.top()) stackMin.pop();
        stackData.pop();
    }

    int top() {
        return stackData.top();
    }

    int min() {
        return stackMin.top();
    }

private:
    stack<int,vector<int>> stackData,stackMin;
};

/**
 * 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->getMin();
 */

用两个栈实现队列

一个插入栈用作插入元素，另一个弹出栈用作弹出元素

将插入栈的元素依次弹出到弹出栈，即完成元素的调头

插入元素时，只需要将元素插入到插入栈即可

删除元素时，判断删除栈有没有元素：有元素则直接删除，没有元素则将插入栈的所有元素弹出，调头放入删除栈

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 CQueue {
public:
    CQueue():push(),pop(){}

    void appendTail(int value) {
        push.emplace(value);
    }

    int deleteHead() {
        if(pop.empty()){
            if(push.empty()) return -1;
            while(!push.empty()){
                pop.emplace(push.top());
                push.pop();
            }
        }
        int temp=pop.top();
        pop.pop();
        return temp;
    }
private:
    stack<int> push,pop;
};

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

用队列实现栈

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
class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> queue[2];
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        // 默认0有元素，1没有元素
        int i=0,j=1;
        if(queue[i].empty()&&!queue[j].empty()){// 0没有元素，1有元素
            swap(i,j);
        }
        queue[i].emplace(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        // 默认0有元素，1没有元素
        int i=0,j=1;
        if(queue[i].empty() && queue[j].empty()){
            throw "栈中无元素";
        }
        else if(queue[i].empty() && !queue[j].empty()){// 0没有元素，1有元素
            swap(i,j);
        }
        while(queue[i].size()!=1){
            queue[j].emplace(queue[i].front());
            queue[i].pop();
        }
        int tmp=queue[i].front();
        queue[i].pop();
        return tmp;
    }

    /** Get the top element. */
    int top() {
        // 默认0有元素，1没有元素
        int i=0,j=1;
        if(queue[i].empty()&&!queue[j].empty()){// 0没有元素，1有元素
            swap(i,j);
        }
        return queue[i].back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return queue[0].empty()&&queue[1].empty();
    }
};

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

链表

合并两个排序的链表

递归

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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL) return l2;
        else if(l2==NULL) return l1;

        ListNode* node=NULL;

        if(l1->val < l2->val){
            l1->next=mergeTwoLists(l1->next,l2);
            node=l1;
        }else {
            l2->next=mergeTwoLists(l1,l2->next);
            node=l2;
        }

        return node;
    }
};

迭代

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
/**
 * 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) {
        if(l1==NULL) return l2;
        else if(l2==NULL) return l1;

        ListNode* head=new ListNode();
        ListNode* cur=head;

        while(l1!=NULL && l2!=NULL){
            if(l1->val < l2->val){
                cur->next=l1;
                l1=l1->next;
            }
            else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next = (l1==NULL?l2:l1);

        return head->next;
    }
};

删除链表中的节点

对于需要被删除的结点，可以通过将下一个结点的内容覆盖待删除结点，然后 delete 下一个结点

这种方法不需要从链表头遍历得到待删除结点的上一个结点

重点在于：

  1. 待删除结点是不是链表尾？是的话，删除后，倒数第二个结点的 next 指针应当设置为 nullptr；即需要遍历链表得到上一个结点
  2. 待删除结点是不是链表头？是的话，正常删除就完事了哈哈哈
  3. 待删除结点既是链表头又是链表尾？当作链表尾删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if(node==NULL) return;

        ListNode* next_ptr=node->next;
        node->val=next_ptr->val;
        node->next=next_ptr->next;
        delete next_ptr;
        next_ptr=NULL;
    }
};

链表中倒数第 k 个节点

需要注意：

  1. 传入空链表，返回 NULL
  2. 传入 K 值为 0，返回 NULL
  3. 传入 K 值大于链表长度，返回 NULL
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
/**
 * 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){
        if(head==NULL || k==0) return NULL;

        ListNode* focus_ptr=head;
        ListNode* count_ptr=head;

        int count=0;

        while(count!=k-1){
            // 如果k值大于链表长度，返回NULL
            if(count_ptr->next==NULL) return NULL;
            count_ptr=count_ptr->next;
            ++count;
        }

        while(count_ptr->next!=NULL){
            count_ptr=count_ptr->next;
            focus_ptr=focus_ptr->next;
        }

        return focus_ptr;
    }
};

反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

示例：

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

迭代实现：

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 *reverseList(ListNode *head) {
        ListNode *pre, *cur, *nxt;
        pre = NULL;
        cur = head;
        nxt = head;
        while (cur != NULL) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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 == nullptr || head->next == nullptr) return head;
        ListNode *last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

一开始，第十一行的判断条件是if(head->next==nullptr)，这里忽略了传参时传入空结点的情况，导致测试正确，提交错误

反转链表的固定范围

给你单链表的头指针head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回反转后的链表

示例：

1
2
输入：head = [5], left = 1, right = 1
输出：[5]
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *successor;//记录后驱

    ListNode *reverse(ListNode *head, int n) {
        if (n == 1) {
            successor = head->next;
            return head;
        }
        ListNode *last = reverse(head->next, n - 1);
        head->next->next = head;
        head->next = successor;
        return last;
    }

    ListNode *reverseBetween(ListNode *head, int left, int right) {
        if (left == 1) {
            return reverse(head, right);
        }
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }
};

可以看作，翻转链表的前 n 个结点（27、28 行），反转完成后，从未反转处接上结点即可

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

示例：

1
2
输入：head = [1,3,2]
输出：[2,3,1]

利用栈先进后出的原则输出，也可以用递归输出

数据少时使用递归，数据多时使用栈

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:
    void reverse(vector<int> &vector, ListNode *head) {
        if (head != NULL) {
            if (head->next != NULL) reverse(vector, head->next);
            vector.push_back(head->val);
        }
    }

    vector<int> reversePrint(ListNode *head) {
        vector<int> vector;
        reverse(vector, head);
        return vector;
    }
};

二叉树

二叉树的递归遍历

给定一个二叉树的根节点root，返回它的递归遍历

实例：

1
2
输入：root = [1,null,2,3]
输出：[1,3,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() : 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:
    // 前序递归遍历
    void traversal(TreeNode* root,vector<int> &vector){
        if(root==nullptr) return;
        vector.emplace_back(root->val);
        traversal(root->left,vector);
        traversal(root->right,vector);
    }
    // 中序递归遍历
        void traversal(TreeNode* root,vector<int> &vector){
        if(root==nullptr) return;
        traversal(root->left,vector);
        vector.emplace_back(root->val);
        traversal(root->right,vector);
    }
    // 后序递归遍历
        void traversal(TreeNode* root,vector<int> &vector){
        if(root==nullptr) return;
        traversal(root->left,vector);
        traversal(root->right,vector);
        vector.emplace_back(root->val);
    }

    vector<int> recursionTraversal(TreeNode* root) {
        vector<int> vector;
        traversal(root,vector);
        return vector;
    }
    }
};

二叉树的迭代遍历

前序迭代

压入根结点，然后迭代以下操作：

判断栈是否为空，不为空则取出栈顶元素，打印值，然后先压入右子结点（如果有），再压入左子节点（如果有）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vector;
        if(root==nullptr) return vector;
        stack<TreeNode*> stack;
        stack.emplace(root);
        while(!stack.empty()){
            root=stack.top();
            stack.pop();
            vector.emplace_back(root->val);
            if(root->right!=nullptr) stack.emplace(root->right);
            if(root->left!=nullptr) stack.emplace(root->left);
        }
        return vector;
    }
};

中序迭代

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<int> inorderTraversal(TreeNode* root) {
        vector<int> vector;
        if(root==nullptr) return vector;
        stack<TreeNode*> stack;
        while(!stack.empty()||root!=nullptr){
            if(root!=nullptr){
                stack.emplace(root);
                root=root->left;
            }
            else{
                root=stack.top();
                stack.pop();
                vector.emplace_back(root->val);
                root=root->right;
            }
        }
        return vector;
    }
};

后序迭代

准备栈 1 和栈 2

弹出栈 1 栈顶元素并压入左、右子结点到栈 1 中，将弹出元素压入到栈 2；迭代进行

依次弹出栈 2 的元素

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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> vector;
        if(root==nullptr) return vector;
        stack<TreeNode*> stack1,stack2;
        stack1.emplace(root);
        while(!stack1.empty()){
            root=stack1.top();
            stack1.pop();
            stack2.emplace(root);
            if(root->left!=nullptr) stack1.emplace(root->left);
            if(root->right!=nullptr) stack1.emplace(root->right);
        }
        while(!stack2.empty()){
            root=stack2.top();
            stack2.pop();
            vector.emplace_back(root->val);
        }
        return vector;
    }
};

从上到下打印二叉树 I

利用队列，依次放入结点

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> vector;
        if(root==NULL) return vector;

        queue<TreeNode*> queue;
        queue.emplace(root);
        while(!queue.empty()){
            root=queue.front();
            queue.pop();
            vector.emplace_back(root->val);
            if(root->left!=NULL) queue.emplace(root->left);
            if(root->right!=NULL) queue.emplace(root->right);
        }
        return vector;
    }
};

从上到下打印二叉树 II

思路一致，利用队列。因为改由vector<vector<int>>返回，所以利用两个队列分别记录每层的结点

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 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) {
        std::vector<vector<int>> vector;
        if(root==NULL) return vector;

        std::vector<int> vec;
        queue<TreeNode*> queue1,queue2;
        queue1.emplace(root);
        while(!queue1.empty() || !queue2.empty()){
            if(!queue1.empty()){
                while(!queue1.empty()){
                    root=queue1.front();
                    queue1.pop();
                    vec.emplace_back(root->val);
                    if(root->left!=NULL) queue2.emplace(root->left);
                    if(root->right!=NULL) queue2.emplace(root->right);
                }
                vector.emplace_back(vec);
                vec.clear();
            }
            else{
                while(!queue2.empty()){
                    root=queue2.front();
                    queue2.pop();
                    vec.emplace_back(root->val);
                    if(root->left!=NULL) queue1.emplace(root->left);
                    if(root->right!=NULL) queue1.emplace(root->right);
                }
                vector.emplace_back(vec);
                vec.clear();
            }
        }
        return vector;
    }
};

从上到下打印二叉树 III

本来以为针对队列 2 改变插入左右子结点的顺序，发现不对，某些层顺序是反序的

于是想到用栈，还是两个栈，只是双数层（也就是外循环的前一个if判断）先插入左子结点，再插入右子结点；单数层（也就是外循环的后一个if判断）先插入右子结点，再插入左子结点

构建一棵树，按照这个流程画个图就懂了

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 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) {
        std::vector<vector<int>> vector;
        if(root==NULL) return vector;

        std::vector<int> vec;
        stack<TreeNode*> stack1,stack2;
        stack1.emplace(root);
        while(!stack1.empty() || !stack2.empty()){
            if(!stack1.empty()){
                while(!stack1.empty()){
                    root=stack1.top();
                    stack1.pop();
                    vec.emplace_back(root->val);
                    if(root->left!=NULL) stack2.emplace(root->left);
                    if(root->right!=NULL) stack2.emplace(root->right);
                }
                vector.emplace_back(vec);
                vec.clear();
            }
            else{
                while(!stack2.empty()){
                    root=stack2.top();
                    stack2.pop();
                    vec.emplace_back(root->val);
                    if(root->right!=NULL) stack1.emplace(root->right);
                    if(root->left!=NULL) stack1.emplace(root->left);
                }
                vector.emplace_back(vec);
                vec.clear();
            }
        }
        return vector;
    }
};

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
 3
/ \
9  20
 /  \
15   7

通过前序遍历的第一个元素，可用得出当前二叉树的根结点

在中序遍历中，根据根结点的位置，根结点之前是左子树，根结点之后是右子树

通过递归实现

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
/**
 * 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 *build(const vector<int>::iterator &beginPre, const vector<int>::iterator &endPre,
                    const vector<int>::iterator &beginIn, const vector<int>::iterator &endIn) {
        if (beginPre == endPre || beginIn == endIn) return NULL;

        // 通过前序序列的第一个元素构建根结点
        TreeNode *node = new TreeNode(*beginPre);

        // 切割中序序列
        int i = 0;
        vector<int>::iterator tmp = beginIn;
        while (*tmp != node->val) {
            ++i;
            ++tmp;
        }

        // 向左子树传入序列
        node->left = build(beginPre + 1, beginPre + i + 1, beginIn, beginIn + i);
        // 向右子树传入序列
        node->right = build(beginPre + i + 1, endPre, beginIn + i + 1, endIn);

        return node;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return build(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

树的子结构

注意点：

  1. 树的子结构可能是个完整树，也可能存在 NULL
  2. 子结构可能是一个根结点，也可能是两层的树，也可能是多层的树
    3.isSame()中的判断条件和顺序是很重要的
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
/**
 * 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 isSame(TreeNode* A, TreeNode* B){
        if(B == NULL) return true;
        if(A == NULL) return false;
        // 以上两个顺序很重要
        // 首先判断B是否为空，为空的话直接返回true即可
        // 如果B不为空，则判断A是否为空：A如果为空，则不相同，返回false

        if(A->val != B->val) return false;
        // 当A和B都不为空时，再判断二者的值是否相等
        // 注意，如果相等，不能直接返回true，需要继续判断二者的子树是否相等
        // 如果不等则可以直接返回false

        return isSame(A->left,B->left) && isSame(A->right,B->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        bool result=false;

        if(A!=NULL && B!=NULL){
            if(A->val == B->val) result=isSame(A,B);
            if(!result) result=isSubStructure(A->left,B);
            if(!result) result=isSubStructure(A->right,B);
        }

        return result;
    }
};

二叉树的镜像

注意点：

  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
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 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!=NULL){
            TreeNode* tmp=root->left;
            root->left=root->right;
            root->right=tmp;

            mirrorTree(root->left);
            mirrorTree(root->right);
        }
        return root;
    }

    // 递归
    TreeNode* mirrorTree(TreeNode* root) {
        if(root!=NULL){
            stack<TreeNode* > stack;
            TreeNode* tmp=NULL;
            TreeNode* node=NULL;
            stack.emplace(root);
            while(!stack.empty()){
                node=stack.top();
                stack.pop();
                tmp=node->left;
                node->left=node->right;
                node->right=tmp;

                if(node->left!=NULL) stack.emplace(node->left);
                if(node->right!=NULL) stack.emplace(node->right);
            }
        }
        return 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// 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 {
    Node* pre=NULL;
    Node* head=NULL;
public:
    void build(Node* node){// 1为左,0为右
        if(node!=NULL){
            build(node->left);
            if(pre==NULL) head=node;
            else pre->right=node;
            node->left=pre;
            pre=node;
            build(node->right);
        }
        return;
    }

    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return root;
        build(root);
        pre->right=head;
        head->left=pre;
        return head;
    }
};

动态规划

动态规划问题，简而言之就是从所有解题策略中寻求最优解

  1. 先明白暴力递归的策略，思考如何穷举，即得出状态转移方程
  2. 自底向上地找出基础情况

    斐波那契数列中的基础情况：

    零钱兑换中的基础情况：当amount为 0 时，最少硬币个数为 0

    青蛙跳台阶的基础情况：

    最长回文子串的基础情况：单个字符可以构成回文子串

  3. 确定状态，也就是决定问题的变量，由基础情况自底向上逐渐增加

    斐波那契数列中的状态：n的取值

    零钱兑换中的状态：目标金额amount所对应的最少硬币个数

    青蛙跳台阶的状态：n的取值，即要跳多少层台阶

    最长回文子串的状态：回文子串的长度

  4. 确定选择，也就是导致状态发生变化的行为

    斐波那契数列中的选择：

    零钱兑换中的选择：对于amount，当减去对应硬币面值时，如何选择使硬币个数最少（比如硬币面值 1、2、5，目标金额为 14、13、10 所需的最少硬币个数为 4、4、2，则目标金额为 15 时，需要最少 3 个硬币）

    青蛙跳台阶的选择：

    最长回文子串的选择： 当前回文子串 左右的字符 和 是否相等？相等则最长回文子串长度 +1

  5. 由以上得出状态转移方程
  6. 明白如何聪明地穷举，利用备忘录、DP table 甚至是一个备忘变量

斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;

        int pre=1;
        int cur=1;
        int sum=0;

        for(int i=2;i<n;++i){
            sum=pre+cur;
            pre=cur;
            cur=sum;
        }

        return sum;
    }
};

零钱兑换

自底向上的说，总金额amount对应的最少硬币个数，相当于总金额amount-coins对应的最少硬币个数 +1。总金额为 0 时，最少硬币个数为 0；总金额为 1 时，最少硬币个数为 1；……。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        vector<int> dp(amount+1,amount+1);
        dp[0]=0;

        for(int i=0;i<dp.size();++i){
            for(int coin:coins){
                if(i-coin < 0) continue;
                dp[i]=min(dp[i],1+dp[i-coin]);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
};

青蛙跳台阶问题

青蛙可以一次跳一个台阶，也可以一次跳两个台阶。那么，在这次跳之前，青蛙可能是跳了一个台阶上来的，也可能是跳了两个台阶上来的

那么青蛙从上一次跳的台阶，跳到这次跳的台阶，就有两种跳法

那这次跳台阶，也有两种跳法

那从地上跳到n级台阶，就可能是从n-1跳了一个台阶上来的，也可能是从n-2跳了两个台阶上来的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numWays(int n) {
        if(n<1) return 1;
        if(n==1 || n==2) return n;

        int pre=1;
        int cur=2;
        int sum=0;
        for(int i=3;i<=n;++i){
            sum=(pre+cur)%1000000007;// 答案需要取模
            pre=cur;
            cur=sum;
        }
        return sum;
    }
};

最长回文子串

暴力破解：找到每个回文子串，记录最长值

  1. 在字符串中分割出一个子串
  2. 判断子串是否为回文串

算法

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

  1. 升序排序，找中位数
  2. 投票法

    核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

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