/ 笔记  

【更新中】LeetCode自用刷题记录

LeetCode自用刷题思路

自用的刷题记录，以防后续不记得之前自己怎么想的~ 正式的题解还是看官方题解和**“代码随想录”**吧

数组

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

注意开闭区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int middle = 0;
    while (left <= right){
        middle = (left + right) / 2;
        if (nums[middle] == target) {
            return middle;
        }
        else if (nums[middle] > target) {
            right = middle - 1;
        }
        else {
            left = middle + 1;
        }
    }
    return -1;
}

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

快指针指向原始数组，慢指针指向新数组。如果等于val，slow不加；不等于val，fast指向的值赋给slow指向的值

1
2
3
4
5
6
7
8
9
10
11
int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        // 快指针指向原始数组，慢指针指向新数组。如果等于val，slow不加；不等于val，fast指向的值赋给slow指向的值
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

动态数组不行！

中途比较，两头的数字一定是最大的，其平方一定在平方数组的末尾

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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    
    int left = 0;
    int right = numsSize - 1;
    
    int* ans = (int*)malloc(sizeof(int) * numsSize);

    // 中途比较，两头的数字一定是最大的，其平方一定在平方数组的末尾

    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[left] * nums[left] >= nums[right] * nums[right]) {
            ans[i] = nums[left] * nums[left];
            left++;
        }
        else {
            ans[i] = nums[right] * nums[right];
            right--;
        }
    }
    return ans;
}

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

暴力解法过不了

张开的窗口之和至少要能够装下target。首先移动end（必须到结尾），至少要装下target。接着，start向右，找最小的长度，装不下了，end向右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int minSubArrayLen(int target, int* nums, int numsSize) {
    int length = 100001;
    int start = 0;
    int sum = 0;
    for(int end = 0; end < numsSize; end++) {
        sum += nums[end];
        while (sum >= target) { //这个while是精髓！！！ 滑动初始窗口
            if ((end - start + 1) < length) {
                length = end - start + 1;
            }            
            sum -= nums[start];
            start++;
        }
    }
    if (length < 100001) {
        return length;
    }
    else {
        return 0;
    }
}

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

找规律，注意边界

找规律，第一步先把第一行填满，后续每次转弯向右，每两次需要步长减一。注意，横纵坐标有没有超出范围，且二维数组第一位为行，第二位为列

image-20240326200626892 
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
71
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    // 初始化返回的结果数组
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    int** ans = (int**)malloc(sizeof(int*) * n);
    int i;
    for (int i = 0; i < n; i++) {
        ans[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }

    int shiftX = 0;
    int shiftY = 0;
    int inputNum = 1;
    int directionX = 0; // 0往左，1往右
    int directionY = 0; // 0往下，1往上
    
    for (int step = n; step > 0; step-- ) {
        if (step == n) {
            for (int i = 0; i < step; i++) {
                ans[shiftY][shiftX] = inputNum;
                inputNum++;
                shiftX++;
            }
            shiftX--;
        }
        else {
            // 先移动Y方向
            if (directionY == 0) {
                for (int i = 0; i < step; i++) {
                    shiftY++;
                    ans[shiftY][shiftX] = inputNum;
                    inputNum++;
                }
                directionY = 1;
            }
            else {
                for (int i = 0; i < step; i++) {
                    shiftY--;
                    ans[shiftY][shiftX] = inputNum;
                    inputNum++;
                }
                directionY = 0;
            }
            //再移动X方向
            if (directionX == 0) {
                for (int i = 0; i < step; i++) {
                    shiftX--;
                    ans[shiftY][shiftX] = inputNum;
                    inputNum++;
                }
                directionX = 1;
            }
            else {
                for (int i = 0; i < step; i++) {
                    shiftX++;
                    ans[shiftY][shiftX] = inputNum;
                    inputNum++;
                }
                directionX = 0;
            }
        }
    }

    return ans;
}

链表

链表和数组对比

插入/删除 查询 使用场景
数组 O(n)O(n) O(1)O(1) 数据量固定，频繁查询，较少增删
链表 O(1)O(1) O(n)O(n) 数据量不固定，频繁增删，较少查询

  • C：——《数据结构与算法/软件技术基础》周大为版

    1
    2
    3
    4
    typedef struct node {
        int data;
        struct node *next;
    } linklist;

  • C++：

    1
    2
    3
    4
    5
    struct ListNode {
        int val;  // 节点上存储的元素
        ListNode *next;  // 指向下一个节点的指针
        ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
    };

——代码随想录

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

定义虚拟头节点dummyHead，以解决第一个节点就是val值的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* p = dummyHead;
    while(p->next != NULL) {
        if (p->next->val == val) {
            p->next = p->next->next;
        }
        else {
            p = p->next;
        }
    }
    return dummyHead->next;
    
}

707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

找准指向的元素。前一个还是后一个。另外需要分类分析头尾的情况。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
typedef struct MyLinkedList{
    int val;
    struct MyLinkedList* next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    // 定义虚拟头节点
    MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    head->next = NULL;
    return head;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    MyLinkedList* p = obj->next; //定义工作指针
    for (int i = 0; p != NULL; i++) {
        if (i == index) {
            return p->val;
        }
        else {
            p = p->next;
        }
    }
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList* newHead = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newHead->next = obj->next;
    newHead->val = val;
    obj->next = newHead;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* p = obj->next; //定义工作指针
    MyLinkedList* newTail = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newTail->val = val;
    newTail->next = NULL;
    if (p != NULL) {
        while(p->next != NULL) {
            p = p->next;
        }
        p->next = newTail;
    }
    else {
        obj->next = newTail;
    }
    
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList* p = obj->next; //工作指针
    if (index == 0) {
        myLinkedListAddAtHead(obj, val);
    }
    MyLinkedList* newAdd = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newAdd->val = val;
    for(int i = 0; p != NULL; i++) {
        if (i == index - 1) {
            newAdd->next = p->next;
            p->next = newAdd;
            break;
        }
        else {
            p = p->next;
        }
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    MyLinkedList* p = obj->next;
    if (index == 0){
        if (p != NULL) {
            obj->next = p->next;
        }
    }
    else {
        for (int i = 0; p->next != NULL; i++) {
            if (i == index - 1) {
                p->next = p->next->next; 
                if (p->next == NULL) {
                    break;
                }
                else {
                    p = p->next;
                }    
            }
            else {
                p = p->next;
            }
        }
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    while(obj != NULL) {
        MyLinkedList* temp =  obj;
        obj = obj->next;
        free(temp);
    }
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

【双指针】注意链表不带头节点。所以双指针的工作和带头结点的不同。

image-20240326200013905

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;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    //head 不带头节点
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *p = NULL;
    struct ListNode *q = head;
    while (q != NULL) {
        struct ListNode *r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    // head->next = NULL;
    head = p;
    return head;
}

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

image-20240326195630531

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;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    typedef struct ListNode ListNode;
    ListNode *dummyHead = (ListNode*)malloc(sizeof(ListNode));
    ListNode *p = (ListNode*)malloc(sizeof(ListNode)); // 定义头节点和工作指针
    dummyHead->next = head;
    p = dummyHead;
    while(p->next != NULL && p->next->next != NULL) {
        ListNode *temp = (ListNode*)malloc(sizeof(ListNode));
        temp = p->next;
        p->next = p->next->next;
        temp->next = p->next->next;
        p->next->next = temp;
        p = p->next->next;
    }
    return dummyHead->next;
}

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解法一——暴力解法，两次遍历

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;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    typedef struct ListNode ListNode;
    ListNode *dummyNode = (ListNode*)malloc(sizeof(ListNode));
    dummyNode->next = head;
    ListNode *p = dummyNode;
    int count = 0;
    while (p->next != 0) {
        count++;
        p = p->next;
    }
    p = dummyNode;
    for (int i = 0; i < count - n; i++) {
        p = p->next;
    }
    p->next = p->next->next;
    return dummyNode->next;
}

解法二——双指针，让快慢指针间隔n位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    typedef struct ListNode ListNode;
    ListNode *dummyNode = (ListNode*)malloc(sizeof(ListNode));
    dummyNode->next = head;
    ListNode *fast = dummyNode;
    ListNode *slow = dummyNode;
    int count = 0;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while(fast-> next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummyNode->next;
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

计算链表长度的差，移动到剩余相同长度，一个一个节点比较

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    typedef struct ListNode ListNode;

    ListNode *p = headA;
    ListNode *q = headB;

    // 计算链表长度的差
    int lenA = 0, lenB = 0;
    int gap = 0;
    while (p != NULL) {
        lenA++;
        p = p->next;
    }
    while (q != NULL) {
        lenB++;
        q = q->next;
    }

    // 移动到相同长度
    p = headA;
    q = headB;
    if (lenA > lenB) {
        gap = lenA - lenB;
        while(gap != 0) {
            gap--;
            p = p->next;
        }
    }
    else {
        gap = lenB - lenA;
        while(gap != 0) {
            gap--;
            q = q->next;
        }
    }
    
    // 一个一个比较
    while (p != NULL && q != NULL){
        if (p == q) {
            return p;
        }
        else {
            p = p->next;
            q = q->next;
        }
    }
    return NULL;

}

官方题解——双指针的思路

两者长度分别为m,nm,n，假设公共部分为后cc，则m=a+cm=a+c, n=b+cn=b+c

开始先指向自己，走完自己全程指向对方

  • 两链表相交：
    • 长度相等：两个指针会同时到达两个链表相交的节点
    • 长度不等：走到第一个公共节点的距离是相同的，第一个走的是a+c+ba+c+b，第二个走的是b+c+ab+c+a
  • 两个链表不相交
    • 长度相等：同时到达两个链表自己的尾节点变成NULL
    • 长度不等：两个指针都会遍历完两个链表（自己加对方），变成NULL

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

img

慢指针每次走一步，快指针每次走两部

相遇时

  • slow： x+yx+y

  • fast：x+y+n(y+z)x+y+n(y+z)​ 比slow多走了n圈

  • 重要的等式！！！

    2(x+y)=x+y+n(y+z)2(x+y)=x+y+n(y+z)

    于是可以推导出x=n(y+z)−y=(n−1)(y+z)+zx=n(y+z)-y = (n-1)(y+z)+z，至少多走了一圈，所以n≥1n\ge 1合理.

  • 所以x和z的关系就是差了整数圈的关系！

  • 所以从头节点走到环形入口的距离等于整数圈+相遇节点到入口。

    • 所以从相遇点、头节点出发的两个指针，每次走一步，相遇的位置一定是环形入口。
    • 代码注意后续这么动的时候，slow和fast在不在变，会导致判断条件有问题！
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;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        // 先追及
        slow = slow->next;
        fast = fast->next->next;

        // 后从头开始
        if (slow == fast) {
            ListNode *p = head;
            ListNode *q = slow;
            while (p != q) {
                p = p->next;
                q = q->next;
            }
            return p;
        }
    }
    return NULL;
}

以下开始以C艹为主

哈希表

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

  • 数组
  • set （集合）
  • map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log⁡n)O(\log n) O(log⁡n)O(\log n)
std::multiset 红黑树 有序 是 否 O(log⁡n)O(\log n) O(log⁡n)O(\log n)
std::unordered_set 哈希表 无序 否 否 O(1)O(1) O(1)O(1)`

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(log⁡n)O(\log n) O(log⁡n)O(\log n)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log⁡n)O(\log n) O(log⁡n)O(\log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1)O(1) O(1)O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的。

  • 当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
  • 再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

——代码随想录

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

**注意：**若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

把小写字母表看作哈希表。

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 isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return 0;
        }

        vector <int> alphabetS(26);
        vector <int> alphabetT(26);

        for (int i = 0; i < s.length(); i++) {
            alphabetS[s[i] - 'a'] += 1;
            alphabetT[t[i] - 'a'] += 1;
        }

        if (alphabetS == alphabetT) {
            return 1;
        }
        else {
            return 0;
        }

    }
};

或者通过是不是都是0来判断，减少空间需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isAnagram(char* s, char* t) {

    if (strlen(s) != strlen(t)) {
        return 0;
    }

    int *alphabet = (int*)malloc(sizeof(int) * 26);
    for (int i = 0; i < 26; i++) {
        alphabet[i] = 0;
    }

    for (int i = 0; i < strlen(s); i++) {
        alphabet[s[i] - 'a'] += 1;
        alphabet[t[i] - 'a'] -= 1;
    }

    for (int i = 0; i < 26; i++) {
        if (alphabet[i] != 0){
            return 0;
        }
    }
    return 1;

}

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

解法一——建立数组hash表

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> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector <int> hash(1001);
        unordered_set <int> output;

        for (int num:nums1) {
            hash[num] += 1;
        }
        for (int num:nums2) {
            if (hash[num] != 0) {
                output.insert(num);
            }
        }
        
        vector <int> output_vec;
        output_vec.assign(output.begin(), output.end());
        return output_vec;

    }
};

解法二——用无序set做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set <int> nums1_set(nums1.begin(), nums1.end());
        unordered_set <int> output_set;

        for (int num:nums2) {
            if (nums1_set.find(num) != 0) {
                output_set.insert(num);
            }
        }

        return vector <int> (output_set.begin(), output_set.end());
    }
};

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

无限循环是重点！！！

重点是可能会陷入无限循环。
需要先判断在不在之前存储的集合里面，再将sum添加进集合里面。
同时集合.find的判定是和end()比。

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:
    bool isHappy(int n) {
        unordered_set <int> results;
        int sum = n;
        int mod = n;

        while (results.find(sum) == results.end()) {
            results.insert(sum);
            mod = sum;
            sum = 0;
            // 下列循环求mod的各位平方和
            while (mod != 0) {
                sum += (mod % 10) * (mod % 10);
                mod /= 10;
            }
            // cout << sum << " ";
        }
        if (sum == 1) {
            return true;
        }
        else {
            return false;
        }
    }
};

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解法一——暴力解法

复杂度O(n2)\mathcal O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if( nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

解法二——利用哈希表的思路

利用键值对，在之前保存的键值对中找有没有能够匹配的元素。注意find的时候，是find的键值对的键，而非值，返回的是键值对的结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int,int> nums_map;

        for (int i = 0; i < nums.size(); i++) {
            if (nums_map.find(target - nums[i]) != nums_map.end()) {
                return {nums_map.find(target - nums[i])->second, i};
            }
            nums_map[nums[i]] = i;
        }
        return {};
    }
};

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

首先是无序的，但是需要次数，所以需要通过unordered_map。

分组的思想降低for循环的次数

map新增值不需要判断是否存在键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map <int, int> sumTwo;
        int counts = 0;

        for (int num1:nums1) {
            for (int num2:nums2) {
                sumTwo[num1 + num2] += 1;
            }
        }

        for (int num3:nums3) {
            for (int num4:nums4) {
                if (sumTwo.find(- (num3 + num4)) != sumTwo.end()) {
                    counts += sumTwo[- (num3 + num4)];
                }
            }
        }

        return counts;
    }
};

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

小写字母建立hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int alphabet[26];
        if (magazine.length() < ransomNote.length()) {
            return 0;
        }
        for (int i = 0; i < magazine.length(); i++) {
            alphabet[magazine[i] - 'a'] += 1;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            alphabet[ransomNote[j] - 'a'] -= 1;
            if (alphabet[ransomNote[j] - 'a'] < 0) {
                return 0;
            }
        }
        return 1;
    }
};

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

去重很困难。考虑双指针法

去重的位置非常重要！同时要考虑使用双指针而非哈希表。

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector <vector <int>> output;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) { // 最左边的元素大于0，那么不可能和为0
                return output;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //第一个数，去重
                continue;
            }
            // 双指针启动！
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                }
                else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                }
                else {
                    output.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++; // 第二个数，去重，要求左右顺序不能错。如果这个数和后一个一样，那么会导致第二个数有重复，所以右移
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;// 第三个数，去重
                    }
                    //找到答案，同时收缩
                    left++;
                    right--;
                }
            }
        }
        return output;
    }
};

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

这边的重点是第二个数要求j > i+1而非j>0，不然数相等时候会往右缩。

同时注意不加(long)可能会溢出。

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector <vector <int>> output;
        //先要从小到大排
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            // if (nums[i] > target && nums[i] >= 0) {
            //     break; //剪枝处理，类似之前的首元素大于0，那么必然不行
            // }
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = i + 1; j < nums.size(); j++) {
                // if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                //     break; //剪枝处理，类似之前的首元素大于0，那么必然不行
                // }
                if (j > i+1 && nums[j] == nums[j-1]) {  // 这边的重点是j > i+1而非j>0
                    continue;
                }
                // 双指针
                int left = j + 1;
                int right = nums.size() - 1;
                while(left < right) {
                    if ((long) nums[i] + nums[j] + nums[left] + nums[right] < target) { //会溢出
                        left++;
                    }
                    else if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        right--;
                    }
                    else {
                        output.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left+1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right-1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return output;
    }
};

字符串

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

注意right的其实位置是length-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            int temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
};

541. 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

还是写的有点复杂了，可以把两个大于等于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
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string reverseStr(string s, int k) {
        int loop = s.length() / (2 * k) + 1;
        for (int i = 0; i < loop; i++) {
            // 如果不是最后一个loop，则反转当前loop前k个
            if (i != loop - 1) {  //和下面last_loop >= k合并
                int left = 2 * i * k;
                int right = 2 * i * k + (k - 1);
                while (left < right) {
                    swap(s[left], s[right]);
                    left++;
                    right--;
                }
            }
            else {
                int last_loop = s.length() % (2 * k);
                int left = 2 * i * k;
                int right;
                if (last_loop < k) { //0的情况也没事，不会进入while循环。
                    right = s.length() - 1;
                } 
                else {  //和上面i != loop - 1合并
                    right = 2 * i * k + (k - 1);
                }
                while (left < right) {
                    swap(s[left], s[right]);
                    left++;
                    right--;
                }
            }
        }
        return s;
    }
};

54. 替换数字(kamacoder)

题目描述

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 a1b2c3，函数应该将其转换为 anumberbnumbercnumber。

输入描述

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

从后往前替换字符，复杂度低，左边不用管。

img

注意处理完之后要左移一下，且判断条件注意边界。

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
# include <iostream> 

using namespace std;

int main() {
    string s;
    while (cin >> s) {
        int countNum = 0;
        int oldSize = s.length();
        for (int i = 0; i < oldSize; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                countNum++;
            }
        }
        // cout << countNum << endl;
        s.resize(s.size() + 5 * countNum);
        for (int left = oldSize - 1, right = s.size() - 1; left >= 0; left--){
            if (s[left] < '0' || s[left] > '9') { // 不应该有等号
                s[right] = s[left];
                right--;
            }
            else {
                s[right--] = 'r';
                s[right--] = 'e';
                s[right--] = 'b';
                s[right--] = 'm';
                s[right--] = 'u';
                s[right--] = 'n'; // 注意先减还是后减去
            }
        }
        cout << s << endl;
    }
    return 0;
}

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

fig

反转整个字符串。
同时操作反转单词和去除空格，要定义一个变量表示当前单词头，然后快慢指针删除空格. （代码随想录中分开处理。）

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
class Solution {
public:
    void reverseString (string &s, int left, int right) {
        while (left < right) {
            swap(s[left++], s[right--]);
        }
    }
    string reverseWords(string s) {
        // 反转整个字符串
        reverseString (s, 0, s.length() - 1);

        // 同时操作反转单词和去除空格，要定义一个变量表示当前单词头，然后快慢指针删除空格.
        // 慢指针指向单词尾部时，从单词头到慢指针反转。
        // 处理完一个单词后，注意单词之间有空格
        int wordHead = 0;
        int slow = 0;
        for (int fast = 0; fast < s.length(); fast++) {
            /*三种情况（前两种可以合并）：
            ① fast=0 且 s[fast] 不为空，要传给slow
            ② fast!=0 且 s[fast] 不为空，要传给slow 
            （这样不好处理最后一个单词）③ fast!=0 且 s[fast] 为空，s[fast-1] 不为空，要传给slow，同时从wordHead到slow-1逆转，wordHead移动到空格后
            ③ fast!=0 且 s[fast] 不为空，s[fast+1] 为空或者句子结尾，要传给slow后，同时从wordHead到slow逆转，slow补齐空格，wordHead移动到空格后
            所以先处理情况三*/
            if (s[fast] != ' ') {
                s[slow] = s[fast];
                if (s[fast+1] == ' ' || fast+1 >= s.length()) {
                    reverseString(s, wordHead, slow);
                    s[++slow] = ' ';
                    wordHead = slow + 1;
                }
                slow++;
            }
        }
        // 重置string长度，注意slow移向上一个单词的后一个格了
        s.resize(slow-1);
        return s;
    }
};

55. 右旋字符串 (kamacoder)

题目描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

输入描述

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述

输出共一行，为进行了右旋转操作后的字符串。

解法一——直接字符串提取拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <queue>
using namespace std;

int main() {
    int k;
    string s;
    
    cin >> k;
    cin >> s;
    
    int length = s.length();
    
    string s1 = s.substr(0, length - k);
    string s2 = s.substr(length - k, k);
    
    cout << s2 << s1;
    return 0;
}

解法二——“整体反转字符串”+“两个反转单词”

在原本字符串中处理，变成“整体反转字符串”+“两个反转单词”的过程。

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
#include <iostream>
#include <algorithm>
using namespace std;

// void reverseString (string &s, int left, int right) {
//     while (left < right) {
//         swap (s[left++], s[right--]);
//     }
// }

int main() {
    int k;
    string s;
    
    cin >> k;
    cin >> s;
    
    // int length = s.length();
    // reverseString(s, 0, length-1);
    // reverseString(s, 0, k-1);
    // reverseString(s, k, length-1);
    
    reverse(s.begin(), s.end()); //左闭右开
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    
    
    cout << s;
    return 0;
}

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

  1. 注意：如果单纯通过一层for循环判断时候，当flag倒了的时候，可能前面部分字符还是重复了needle的少部分，所以需要回溯。

解法一—— 暴力解法也能解，取所有的n长字串即可。

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:
    int strStr(string haystack, string needle) {
        int flag = 0;
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            if (needle[j] == haystack[i]) {
                flag++;
                j++;
                if (j == needle.length()) {
                    return i - j + 1;
                }
            }
            else {
                flag = 0;
                i = i - j;
                j = 0;
            }
        }
        return -1;
    }
};

解法二——KMP算法

  1. KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

  2. 前缀表

    • 为什么需要？不想完全回溯。
      image-20240329202856323

    • 当前位置既然不能完全满足匹配串，那么至多能匹配上多少？也就是说可以少回溯多少呢？也就知道子串（匹配串）需要回溯到什么位置——这由当前位置的上一个前缀表值来确定。

      image-20240329202910993

  3. next数组的定义

    • 初始化（前缀末尾（即最长相等前后缀长度）j、后缀末尾i）

    • 前后缀不相等（防止越界j>0且s[i]!=s[j]时，j要连续回溯到next[j-1]）

    • 前后缀相等（j可以递增，同时后缀i指向位置的前缀表值为j）

    • 请注意这里最后一个为什么是2：这是由于B的时候发现匹配不上了，那么j=3也就要回溯到j=next[j-1]=next[2]=1这个位置。这里需要注意为什么明明是后缀的问题，要用前缀来看呢？因为后缀和前缀相等，所以后缀要回溯的值等于前缀需要回溯到的值（好乱啊55555555）
      image-20240329203055212

      image-20240329202935587

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
class Solution {
public:
    void getNext (int* next, string &s) {
        int j = 0; //前缀末尾，即最长相等前后缀长度
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j-1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.length() == 0) {
            return 0;
        }

        int next[needle.length()];
        getNext(next, needle); //获取前缀表

        int j = 0; //指向匹配串
        for (int i = 0; i < haystack.length(); i++) { //i指向文本串
            while (j > 0 && haystack[i] != needle[j]){ //注意这里也要连续回溯
                j = next[j - 1];
            }
            if(haystack[i] == needle[j]) {
                j++;
                if (j == needle.length()) {
                    return i - j + 1;
                }
            }
        }
        return -1;        
    }
};

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

解法一——移动匹配

那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s

图二
——来自代码随想录

代码也来自代码随想录代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // r
        return false;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

不过这种解法还有一个问题，就是 我们最终还是要判断 一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数。 却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）。

解法二——优化的KMP算法

（不是很能看懂最后一步）

假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是x，所以s是由n * x组成。

因为字符串s的最长相同前后缀的长度一定是不包含s本身，所以 最长相同前后缀长度必然是m * x，而且n - m = 1，（这里如果不懂，看上面的推理）

所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。

最长相等前后缀的长度为：next[len - 1]

数组长度为：len。

如果len % (len - next[len - 1] ) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

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:
    bool repeatedSubstringPattern(string s) {
        int j = 0;
        int next[s.length()];
        next[0] = 0;
        int maxLoop = 1;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s[j] != s[i]) {
                j = next[j - 1];
            }
            if (s[j] == s[i]) {
                j++;
            }
            next[i] = j;
            if (next[i] > maxLoop) {
                maxLoop = next[i];
            }
        }
        for (int i = 0; i < s.length(); i++) {
            cout << next[i] << ' ';
        }
        if(s.length() % (s.length() - maxLoop) == 0) {
            return true;
        }
        else{
            return false;
        }
        
    }
};

双指针

  • 数组

    • [移除元素](#27. 移除元素)：通过两个指针在一个for循环下完成两个for循环的工作。

  • 字符串

    • [反转字符串](#344. 反转字符串)：使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。时间复杂度是O(n)。
    • [替换数字](#54. 替换数字(kamacoder))：首先扩充数组到每个空格替换成"number"之后的大小。然后双指针从后向前替换空格。
    • [反转字符串中的单词](#151. 反转字符串中的单词)：两次反转，同时要去除冗余空格，注意erase操作也是O(n)的操作

  • 链表

    • [反转链表](#206. 反转链表)：只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。

    • [删除链表的倒数第 N 个结点](#19. 删除链表的倒数第 N 个结点)：快指针多走N个节点

    • [相交链表](#160. 相交链表)：计算链表长度的差，移动到剩余相同长度，一个一个节点比较

    • [环形链表II](#142. 环形链表 II)：

    • 如何通过双指针判断是否有环，而且还要找到环的入口。

      使用快慢指针（双指针法），分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

  • N数之和

    • 使用了哈希法解决了两数之和，但是哈希法并不适用于三数之和！去重不好操作
    • [三数之和](#15. 三数之和)：①先排序；②双指针的移动原则；③通过前后两个指针不算向中间逼近，在一个for循环下完成两个for循环的工作。
    • [四数之和](#18. 四数之和)：在三数之和的基础上再套一层for循环，依然是使用双指针法。
    • 对于三数之和使用双指针法就是将原本暴力O(n3)O(n^3)的解法，降为O(n2)O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n4)O(n^4)的解法，降为O(n3)O(n^3)的解法。

栈、队列

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

队列是先进先出的数据结构，不允许有遍历行为，stack和queue不提供迭代器

——代码随想录

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

双栈——操作均集中在push

注意pop只会去掉顶上的元素，不会把顶上元素值返回回来。

image-20240401104414302

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
class MyQueue {
public:
    stack <int> left;
    stack <int> right;
    MyQueue() {
        /* 双栈操作，定义两个栈
        进队列时，先把右栈所有元素pop出压入左栈，再把加入元素压入左栈栈顶；接着左栈依次出栈，右栈依次入栈；
        出队即右栈出栈pop即可
        是否为空即判断右栈是否为空 */
    }
    
    void push(int x) {
        while (right.size() != 0) {
            left.push(right.top());
            right.pop();
        }
        left.push(x);
        while (left.size() != 0) {
            right.push(left.top());
            left.pop();
        }
    }
    
    int pop() {
        int output = right.top();
        right.pop();
        return output;
    }
    
    int peek() {
        return right.top();
    }
    
    bool empty() {
        if (right.size() == 0) {
            return true;
        }
        return false;
    }
};

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

双栈的官方题解——输入栈、输出栈

将一个栈当作输入栈，用于压入 push传入的数据；另一个栈当作输出栈，用于 pop和 peek操作。

每次 pop或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

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
class MyQueue {
public:
    stack<int> queueIn;
    stack<int> queueOut;
    MyQueue() {

    }
    
    void push(int x) {
      queueIn.push(x);
    }
    
    int pop() {
      if (queueOut.empty()) {
        while (!queueIn.empty()) {
          int x = queueIn.top();
          queueOut.push(x);
          queueIn.pop();
        }
      }
      int x = queueOut.top();
      queueOut.pop();
      return x;
    }
    
    int peek() {
      int x = this->pop();
      queueOut.push(x);
      return x;
    }
    
    bool empty() {
      if (queueIn.empty() && queueOut.empty()) {
        return true;
      } else {
        return false;
      }
    }
};

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

两个队列

——将pop出来的前面的元素存在另一个queue里面

fig1

——官方题解

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
class MyStack {
public:
    queue <int> queue1;
    queue <int> queue2;
    MyStack() {

    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        while (queue1.size() > 1) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        int output = queue1.front();
        queue1.pop();
        swap(queue1, queue2);
        return output;
    }
    
    int top() {
        return queue1.back();
    }
    
    bool empty() {
        if (queue1.size() == 0) {
            return true;
        }
        else {
            return false;
        }
    }
};

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

一个队列

——将前面pop出来的继续push回去即可

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
class MyStack {
public:
    queue <int> queue1;
    MyStack() {

    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        int queueSize = queue1.size();
        for (int i = 0; i < queueSize - 1; i++) {
            queue1.push(queue1.front());
            queue1.pop();
        }
        int output = queue1.front();
        queue1.pop();
        return output;
    }
    
    int top() {
        return queue1.back();
    }
    
    bool empty() {
        if (queue1.size() == 0) {
            return true;
        }
        else {
            return false;
        }
    }
};

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

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

注意右括号的情况要判断一下栈是否为空。注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 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
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
class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        stack <char> bracks;
        for (int i  = 0; i < s.length(); i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                bracks.push(s[i]);
            }
            else {
                switch (s[i]) {
                    case ')':
                        if (!bracks.empty() && bracks.top() == '(') {
                            bracks.pop();
                            break;
                        }
                        else {
                            return false;
                        }
                    case ']':
                        if (!bracks.empty() && bracks.top() == '[') {
                            bracks.pop();
                            break;
                        }
                        else {
                            return false;
                        }
                    case '}':
                        if (!bracks.empty() && bracks.top() == '{') {
                            bracks.pop();
                            break;
                        }
                        else {
                            return false;
                        }
                    default:
                        return false;
                }
            }
        }
        if (bracks.size() == 0) {
            return true;
        }
        else {
            return false;
        }
    }
};

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

解法一——stack

注意size会变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeDuplicates(string s) {
        stack <char> words;
        for (int i = 0; i < s.length(); i++) {
            if (!words.empty() && s[i] == words.top()) {
                words.pop();
            }
            else {
                words.push(s[i]);
            }
        }
        string sNew;
        int wordsSize = words.size(); //注意size会变
        for (int j = 0; j < wordsSize; j++) {
            sNew = words.top() + sNew; //在前面加上字母
            words.pop();
        }
        return sNew;
    }
};

貌似每次在前面加字母会带来大量的时间消耗和内存消耗，所以下面那个循环可以改成这个。

image-20240401144455896

1
2
3
4
5
while (!words.empty()) {
           sNew += words.top() ; //在前面加上字母
           words.pop();
       }
       reverse(sNew.begin(), sNew.end());

解法二——以字符串为栈

进一步的以字符串为栈,也是比较快的，消耗内存也比较小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string removeDuplicates(string s) {
        string sNew;
        for (int i = 0; i < s.length(); i++) {
            if (!sNew.empty() && s[i] == sNew.back()) {
                sNew.pop_back();
            }
            else {
                sNew.push_back(s[i]);
            }
        }
        return sNew;
    }
};

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

用栈来解决

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
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack <int> nums;
        int result;
        for (string token:tokens) {
            if (token == "+" ) {
                result = nums.top();
                nums.pop();
                result = nums.top() + result;
                nums.pop();
                nums.push(result);
            }
            else if (token == "-") {
                result = nums.top();
                nums.pop();
                result = nums.top() - result;
                nums.pop();
                nums.push(result);
            }
            else if (token == "*") {
                result = nums.top();
                nums.pop();
                result = nums.top() * result;
                nums.pop();
                nums.push(result);
            }
            else if (token == "/") {
                result = nums.top();
                nums.pop();
                result = nums.top() / result;
                nums.pop();
                nums.push(result);
            }
            else { // 数字
                nums.push(stoi(token));
            }
        }
        return nums.top();
    }
};

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

单调队列问题

只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列

设计单调队列的时候，pop，和push操作要保持如下规则：

  1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
  2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int numsSize = nums.size();
        deque <int> window; //这个双向队列里面存的是索引，而非数字本身，防止有重复，被误pop（？）
        vector <int> output;

        for (int i = 0; i < numsSize; i++) {
            // push操作①： 如果该值比之前的大，那么就pop掉之前的直到剩下比它大的
            while (!window.empty() && nums[i] > nums[window.back()]) {
                window.pop_back();
            }
            window.push_back(i); //push操作②：此时队列中剩下的只有比它大的，且在队头 

            // 将之前的序号pop
            if (!window.empty() && window.front() < i - k + 1) {
                window.pop_front();
            }

            // 取出当前窗口的最大值
            if (i >= k - 1) {
                output.push_back(nums[window.front()]);
            } 
        }
        return output;
    }
};

###　347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解法一——对map的值进行排序

注意力扣不能直接用cmp，得包装一层结构体，同时要将map转化为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
class Solution {
public:
    struct cmp{
        bool operator ()(pair<int,int> &x, pair<int,int> &y) {
            return x.second > y.second;
        }
    };
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> numsMap; //无序即可，后续要排序
        vector <int> output(k);
        for (int num:nums) {
            numsMap[num] ++;
        }
        cmp cp;
        vector <pair<int,int>> numsMap_vector(numsMap.begin(), numsMap.end());
        sort(numsMap_vector.begin(), numsMap_vector.end(), cp);
        int i = 0; // output序号
        for (auto p = numsMap_vector.begin(); p < numsMap_vector.begin() + k; p++) {
            output[i++] = p->first; //这一这里p是一个指针
        }
        return output;
    }
};

解法二——优先级序列

要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。建立一个小顶堆，然后遍历「出现次数数组」：

  • 如果堆的元素个数小于 k，就可以直接插入堆中。
  • 如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 k 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
  • 堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

优先级队列的基本操作与普通队列类似，不同的是每次获得队内的元素是优先级最高的元素（要从堆的顶部开始），因此使用的是top()方法，而不是front()方法。如下：

  1. push() ：入队。向队列添加一个元素，无返回值；
  2. pop() ：将队列中优先级最高的元素出队。将队列中优先级最高的元素删除（出队），无返回值；
  3. top() ：获得队列优先级最高的元素。此函数返回值为队列中优先级最高的元素，常与pop()函数一起，先通过top()获得队列中优先级最高的元素，然后将其从队列中删除；
  4. size() ：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名。
  5. empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。

——C++——优先级队列（priority_queue）_c++优先队列-CSDN博客

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
class Solution {
public:
    struct cmp_greater{
        bool operator ()(pair<int,int> &x, pair<int,int> &y) {
            return x.second > y.second;
        }
    };
    struct cmp_less{
        bool operator ()(pair<int,int> &x, pair<int,int> &y) {
            return x.second < y.second;
        }
    };
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> numsMap;
        vector <int> output;
        for (int num:nums) {
            numsMap[num] ++;
        }
        
        // // 建立优先级序列（用小顶堆, 大于当前节点的要下沉，大小为k）
        // priority_queue <pair<int,int>, vector<pair<int,int>>, cmp_greater> pri_que; 
        // // 扫描所有频率值
        // for (auto p = numsMap.begin(); p != numsMap.end(); p++) {
        //     pri_que.push(*p);
        //     if (pri_que.size() > k) {
        //         pri_que.pop();
        //     }
        // }

        // 建立优先级序列（用大顶堆, 小于当前节点的要下沉，大小不限制）
        priority_queue <pair<int,int>, vector<pair<int,int>>, cmp_less> pri_que; 
        // 扫描所有频率值
        for (auto p = numsMap.begin(); p != numsMap.end(); p++) {
            pri_que.push(*p);
        }

        // 可以按照任意顺序输出， 注意优先级序列也没有begin和end
        for (int i = 0; i < k; i++) {
            output.push_back(pri_que.top().first); // 取数值
            pri_que.pop();
        }

        return output;
    }
};

二叉树

二叉树的种类：

  • 满二叉树
  • 完全二叉树
  • 二叉搜索树（二叉排序树）：二叉搜索树是一个有序树，左子树（若非空）上所有结点的值均小于它的根结点的值，右子树（若非空）上所有结点的值均大于它的根结点的值，左右子树也分别为二叉排序树。
  • 平衡二叉搜索树[AVL（Adelson-Velsky and Landis）树]：它是一棵空树或它的左右两个子树的高度（深度）差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    • C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是O(log⁡n)O(\log n)​
    • 红黑树就是一种二叉平衡搜索树
  • 辨析
    1. 平衡二叉搜索树是不是二叉搜索树和平衡二叉树的结合？——是的，是二叉搜索树和平衡二叉树的结合。
    2. 平衡二叉树与完全二叉树的区别在于底层节点的位置？——是的，完全二叉树底层必须是从左到右连续的，且次底层是满的。
    3. 堆是完全二叉树和排序的结合，而不是平衡二叉搜索树？——堆是一棵完全二叉树，同时保证父子节点的顺序关系（有序）。 但完全二叉树一定是平衡二叉树，堆的排序是父节点大于子节点，而搜索树是父节点大于左孩子，小于右孩子，所以堆不是平衡二叉搜索树。

二叉树的遍历：

  • 深度优先遍历
    • 前序遍历DLR（递归法，迭代法）
    • 中序遍历LDR（递归法，迭代法）
    • 后序遍历LRD（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

二叉树的定义：

  • C++：

    1
    2
    3
    4
    5
    6
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

  • C：——《数据结构与算法/软件技术基础》周大为版

    1
    2
    3
    4
    5
    typedef struct node {
        int data;
        struct node *lchild, *rchild;
    } bitree;
    bitree *root; //root指向根节点指针
二叉树大纲

——代码随想录

二叉树的深度优先DFS遍历（144前序/145后序/94中序）

方法一——递归

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

前序

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 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 preorder (TreeNode *p, vector <int> &output) {
        if (p != NULL) {
            output.push_back(p->val);
            preorder(p->left, output);
            preorder(p->right, output);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector <int> output;
        preorder(root, output);
        return output;
    }
};

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void inorder (TreeNode *p, vector <int> &output) {
        if (p != NULL){
            inorder(p->left, output);
            output.push_back(p->val);
            inorder(p->right, output);
        }
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector <int> output;
        inorder(root, output);
        return output;
    }
};

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void postorder(TreeNode *p, vector<int> &output) {
        if (p != NULL) {
            postorder(p->left, output);
            postorder(p->right, output);
            output.push_back(p->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector <int> output;
        postorder(root, output);
        return output;
    }
};

方法二——非递归迭代

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

前序——先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子

二叉树前序遍历（迭代法） 
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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector <int> output;
        stack <TreeNode*> S;
        if (root == NULL) {
            return output;
        }
        S.push(root); // 放入根节点
        while (!S.empty()) {
            TreeNode *p = S.top();
            output.push_back(p->val); //根的值
            S.pop();
            if (p->right != NULL) { //先压入右子树, 先入栈后出
                S.push(p->right);
            }
            if (p->left != NULL) { //后压入左子树
                S.push(p->left);
            } 
        }
        return output;
    }
};

中序——在遍历左子树之前先把根节点入栈；当左子树遍历完成，根节点出栈，遍历右子树。借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素，

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> output;
        stack <TreeNode*> S;
        TreeNode *p = root;
        while (p != NULL || !S.empty()) { // 第一个条件是为了第一次能够满足，以能够先押入根节点
            if (p != NULL) { // 指针访问到左边的最底层的
                S.push(p);
                p = p->left; // 左子树
            }
            else { // p为空，那么栈里面的就是他的祖先节点（如果目前是右子树的话甚至不一定是父节点），
                p = S.top();
                S.pop();
                output.push_back(p->val); // 根节点
                p = p->right; // 右子树
            }
        }
        return output;
    }
};

后序

DLR（先序）→调整左右顺序DRL（逆先序）→reverseLRD（后序）\text{DLR（先序）} \xrightarrow{\text{调整左右顺序}}\text{DRL（逆先序）}\xrightarrow{\text{reverse}}\text{LRD（后序）} 

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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector <int> output;
        stack <TreeNode*> S;
        if (root == NULL) {
            return output;
        }
        S.push(root);
        while (!S.empty()) {
            TreeNode *p = S.top();
            S.pop();
            output.push_back(p->val); // 压入根节点
            if (p->left) {
                S.push(p->left); //压入左节点，后出
            }
            if (p->right) {
                S.push(p->right); //压入右节点，先出
            }
        }
        reverse(output.begin(), output.end());
        return output;
    }
};

方法三——二叉树的统一迭代法

将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

二叉树的层序（广度优先）BFS遍历（102/107/199/637/429/515/116/117）

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

基本思想：在上层先被访问的节点，他的下层孩子在该层也会被先访问到。因此使用队列，当一个元素出队，他的孩子将会进入队列。

力扣的题目返回的是二维数组，需要对层也包裹一层，所以需要定义qSize来确定每层的大小，将每层的遍历结果输出到output中。

解法一——非递归迭代
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() : 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>> levelOrder(TreeNode* root) {
        vector <vector<int>> output;
        if (root == NULL) {
            return output;
        }
        queue <TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            int qSize = Q.size(); // 为了返回二维数组，需要知道每层有多少个
            vector <int> outputLayer;
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front(); 
                outputLayer.push_back(p->val); //根节点出队
                Q.pop();
                if (p->left) {
                    Q.push(p->left); //push左孩子入队
                }
                if (p->right) {
                    Q.push(p->right); //push右孩子入队
                }
            }
            output.push_back(outputLayer);
        }
        return output;
    }
};
解法二——递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void levelorderTraversal (TreeNode *p, vector<vector<int>> &output, int depth) {
        if (p == NULL) {
            return ; //空指针返回父节点。为什么不把判定条件放在访问孩子前呢？因为无法判断是否为空树
        }
        if (output.size() == depth) {
            output.push_back(vector<int>()); //当前层还没有加入过，创建对应层的数组
        }
        output[depth].push_back(p->val);
        // 访问孩子，在孩子对应层的vector尾部加入
        levelorderTraversal(p->left, output, depth+1);
        levelorderTraversal(p->right, output, depth+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector<int>> output;
        int depth = 0;
        levelorderTraversal(root, output, depth);
        return output;
    }
};

107.二叉树的层次遍历II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

对102的正向层次遍历reverse。

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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> output;
        queue <TreeNode*> Q;
        if (root == NULL) {
            return output;
        }
        Q.push(root);
        while (!Q.empty()) {
            int qSize = Q.size();
            vector <int> outputLayer;
            for (int i = 0; i < qSize; i++) {
                outputLayer.push_back(Q.front()->val);
                if (Q.front()->left) {
                    Q.push(Q.front()->left);
                }
                if (Q.front()->right) {
                    Q.push(Q.front()->right);
                }
                Q.pop();
            }
            output.push_back(outputLayer);
        }
        reverse(output.begin(),output.end());
        return output;
    }
};

199.二叉树的右视图

给定一个二叉树的 根节点 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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector <int> output;
        queue <TreeNode*> Q;
        if (root == NULL) {
            return output;
        }
        Q.push(root);
        while (!Q.empty()) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++) {
                if (i == qSize - 1) {// 每层的最后一个元素需要保存值
                    output.push_back(Q.front()->val);
                }
                if (Q.front()->left) {
                    Q.push(Q.front()->left);
                }
                if (Q.front()->right) {
                    Q.push(Q.front()->right);
                }
                Q.pop();
            }
        }
        return output;
    }
};

637.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10−510^{-5}以内的答案可以被接受。

注意与答案相差10−510^{-5}以内的答案，所以要用double了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> output;
        queue <TreeNode*> Q;
        if (root == NULL) {
            return output;
        }
        Q.push(root);
        while (!Q.empty()) {
            int qSize = Q.size();
            double sumLayer = 0.0;
            for (int i = 0; i < qSize; i++) {
                sumLayer += Q.front()->val;
                if (Q.front()->left) {
                    Q.push(Q.front()->left);
                }
                if (Q.front()->right) {
                    Q.push(Q.front()->right);
                }
                Q.pop();
            }
            output.push_back(sumLayer/qSize);
        }
        return output;
    }
};

429.N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 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
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector <vector<int>> output;
        queue <Node*> Q;
        if(root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            vector <int> outputLayer;
            for (int i = 0; i < qSize; i++) {
                Node* p = Q.front();
                outputLayer.push_back(p->val);
                for (int j = 0; j < p->children.size(); j++) {
                    if (p->children[j] != NULL) {
                        Q.push(p->children[j]);
                    }
                }
                Q.pop();
            }
            output.push_back(outputLayer);
        }
        return output;
    }
};

515.在每个树行中找最大值

给定一棵二叉树的根节点 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
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> output;
        queue <TreeNode*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size(); 
            int maxLayer = INT_MIN; //注意有负数
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front(); 
                if (p->val > maxLayer) {
                    maxLayer = p->val;
                }
                Q.pop();
                if (p->left) {
                    Q.push(p->left); //push左孩子入队
                }
                if (p->right) {
                    Q.push(p->right); //push右孩子入队
                }
            }
            output.push_back(maxLayer);
        }
        return output;
    }
};

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 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
34
35
36
37
38
39
40
41
42
43
44
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue <Node*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++) {
                Node *p = Q.front();
                Q.pop();
                if (i != qSize - 1) {
                    p->next = Q.front();
                }
                if (p->left) {
                    Q.push(p->left);
                }
                if (p->right) {
                    Q.push(p->right);
                }
            }
        }
        return root;
    }
};

117.填充每个节点的下一个右侧节点指针II

给定一个二叉树：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

代码同116

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue <Node*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++) {
                Node *p = Q.front();
                Q.pop();
                if (i != qSize - 1) {
                    p->next = Q.front();
                }
                if (p->left) {
                    Q.push(p->left);
                }
                if (p->right) {
                    Q.push(p->right);
                }
            }
        }
        return root;
    }
};

另见

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解法一——递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* temp;
        if (root != NULL) {
            temp = root->left;
            root->left = root->right;
            root->right = temp;
            invertTree(root->left);
            invertTree(root->right);
        }
        return root;
    }
};

解法二——迭代（深度优先）

DLR

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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
            return root;
        }
        stack <TreeNode*> S;
        S.push(root);
        while (!S.empty()) {
            TreeNode *p = S.top();
            S.pop();
            swap(p->left, p->right); //就这一步不一样
            if (p->left) {
                S.push(p->left);
            }
            if (p->right) {
                S.push(p->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
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue <TreeNode*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front();
                Q.pop();
                swap(p->left, p->right); //就这一步不一样
                if (p->left) {
                    Q.push(p->left);
                }
                if (p->right) {
                    Q.push(p->right);
                }
            }
        }
        return root;
    }
};

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

把NULL存进去的层序遍历。，遍历每一层时候，前半段用stack存进去，后半段pop对比。一个很垃圾的逻辑，一定程度上NULL==0，所以这里使用了非常丑陋的76777777来表示这个位置是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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        bool flagSymmetric = true;
        int depth = 0;
        bool flagNULL = false; // 判断下层是否全空
        queue <TreeNode*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        while(!Q.empty() && flagSymmetric && !flagNULL) {
            int qSize = Q.size();
            stack <int> S;
            flagNULL = true; // 判断下层是否全空
            // cout << qSize << " ";
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front();
                Q.pop();
                if (i < qSize / 2 || depth == 0) { // 第二个条件为了第一层，防止没有东西可pop
                    if (p == NULL) {
                        S.push(76777777);
                    }
                    else {
                        S.push(p->val);
                    }
                }
                else if (p == NULL) {
                    if (S.top() != 76777777) {
                        flagSymmetric = false;
                        break;
                    }
                    S.pop();
                }
                else if (S.top() != p->val) { // 大于一半，且top和目前的val不等，那么不对称
                    flagSymmetric = false;
                    break;
                }
                else { //大于一半，且目前还对称
                    S.pop();
                }
                // 将孩子加入队列，由于要对称，不需要考虑NULL的情况
                if (p != NULL) {
                    Q.push(p->left);
                    Q.push(p->right);
                    if (p->left || p->right){ //只要有一个不为0，下一层就不会全空
                        flagNULL = false;
                    }
                }
            }
            depth++;
        }
        return flagSymmetric;
    }
};

解法一——递归法

总体思路就是左子树的左边要和右子树的右边相等

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 checkSymmetric(TreeNode *p, TreeNode *q) {
        if (!p && !q) { // 都空
            return true;
        }
        else if (!p || !q) { //有一个空
            return false;
        }
        else if (p->val != q->val) { // 非空且不等
            return false;
        }
        // 左子树的左和右子树的右 && 左子树的右和右子树的左
        return checkSymmetric(p->left, q->right) && checkSymmetric(p->right, q->left) ;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        return checkSymmetric(root->left, root->right);
    }
};

解法二——迭代法

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:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        queue <TreeNode*> Q;
        Q.push(root->left);
        Q.push(root->right);
        while (!Q.empty()) {
            TreeNode *p = Q.front(); // 左子树
            Q.pop();
            TreeNode *q = Q.front(); // 右子树
            Q.pop();
            if (p == NULL && q == NULL) { //都空
                continue;
            }
            else if (p == NULL || q == NULL)  { //有一个空
                return false;
            }
            else if (p->val != q->val) {
                return false;
            }
            Q.push(p->left); //左子树左
            Q.push(q->right); //右子树右
            Q.push(p->right); //左子树右
            Q.push(q->left); //右子树左
        }
        return true;
    }
};

这两道题目基本和本题是一样的，只要稍加修改就可以AC。

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        else if (!p || !q) {
            return false;
        }
        else if (p->val != q->val) {
            return false;
        }
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

    }
};

572.另一个树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

先进行层次遍历，遍历到相同的节点值时候，开始比较是否是同一棵树

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 Solution {
public:
    bool isSametree (TreeNode *p, TreeNode *q) {
        if (!p && !q) {
            return true;
        }
        else if (!p || !q || p->val != q->val){
            return false;
        }
        return isSametree(p->left, q->left) && isSametree(p->right, q->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        // 先进行层次遍历，遍历到相同的节点值时候，开始比较是否是同一棵树
        queue <TreeNode*> Q;
        bool flagSubtree = false;
        if (root && subRoot) {
            Q.push(root);
        }
        while (!Q.empty() && !flagSubtree) {
            TreeNode *p = Q.front();
            Q.pop();
            if (p->val == subRoot->val) {
                flagSubtree = isSametree(p, subRoot);
            }
            // cout << p->val << " ";
            if (p->left) {
                Q.push(p->left);
            }
            if (p->right) {
                Q.push(p->right);
            }
        }
        return flagSubtree;
    }
};

三种官方题解：

  • 方法一：深度优先搜索暴力匹配
  • 方法二：深度优先搜索序列上做串匹配
  • 方法三：树哈希

104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

递归求解——深度优先遍历

时间复杂度：O(n)O(n)，其中nn为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)O(\text{height})，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

——力扣官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 如果根节点为空，则深度为0
        if (root == NULL) {
            return 0;
        }

        // 递归计算左右子树的深度
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // 返回左右子树深度的最大值加上根节点本身的深度1
        return max(leftDepth, rightDepth) + 1;
    }
};

非递归迭代——广度优先遍历

  • 时间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
  • 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到O(n)O(n)​。

——力扣官方题解

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 maxDepth(TreeNode* root) {
        queue <TreeNode*> Q;
        int depth = 0;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            depth++;
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front();
                Q.pop();
                if (p->left) {
                    Q.push(p->left);
                }
                if (p->right) {
                    Q.push(p->right);
                }
            }
        }
        return depth;
    }
};

559. N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

递归
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 a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) {
            return 0;
        }
        int depth = 0;
        for (int i = 0; i < root->children.size(); i++) {
            depth = max(depth, maxDepth(root->children[i]));
        }
        return depth + 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
class Solution {
public:
    int maxDepth(Node* root) {
        queue <Node*> Q;
        if (root != NULL) {
            Q.push(root);
        }
        int depth = 0;
        while (!Q.empty()) {
            int qSize = Q.size();
            depth++;
            for (int i = 0; i < qSize; i++){
                Node* p = Q.front() ;
                Q.pop();
                for (int j = 0; j < p->children.size(); j++) {
                    if (p->children[j]) {
                        Q.push(p->children[j]);
                    }
                }
            }            
        }
        return depth;
    }
};

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

注意要考虑一条路到底的情况，即存在单边树的情况。左右孩子都为空的节点才是叶子节点！

image-20240402191845973

非递归迭代——广度优先遍历

注意判断左右为空的时候是“且”，而非“或” 只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点

时间复杂度：O(N)O(N)，其中 NN 是树的节点数。对每个节点访问一次。

空间复杂度：O(N)O(N)，其中 NN 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。

——力扣官方题解

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 minDepth(TreeNode* root) {
        queue <TreeNode*> Q;
        int depth = 0;
        bool flag = true;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty() && flag) {
            int qSize = Q.size();
            depth++;
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front();
                Q.pop();
                if (p->left == NULL && p->right == NULL) { //注意这里是且而非或
                    flag = false; 
                    break;
                }
                if (p->left != NULL) {
                    Q.push(p->left);
                    if (p->right != NULL) {
                        Q.push(p->right);
                    }
                }
                else {
                    Q.push(p->right); // flag为真时，left为空，right必然不为空，不为真时Q无意义
                }
            }
        }
        return depth;
    }
};

递归——深度优先遍历

必须要考虑单边树不存在的问题——需要分别考虑根节点左右孩子

时间复杂度：O(N)O(N)，其中NN是树的节点数。对每个节点访问一次。

空间复杂度：O(H)O(H)，其中 HH 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为O(N)O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(log⁡N)O(\log N)。

——力扣官方题解

遍历的顺序为后序（左右中）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        // 必须要考虑单边树不存在的问题——需要分别考虑根节点左右孩子
        else if (root->left == NULL) {
            return minDepth(root->right) + 1;
        }
        else if (root->right == NULL) {
            return minDepth(root->left) + 1;
        }
        return min(minDepth(root->left),minDepth(root->right)) + 1;
    }
};

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

解法一——层次遍历

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:
    int countNodes(TreeNode* root) {
        queue <TreeNode*> Q;
        bool flagEnd = false;
        int nums = 0;
        if (root != NULL) {
            Q.push(root);
            nums++;
        }
        while (!Q.empty() && !flagEnd) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++) {
                TreeNode *p = Q.front();
                Q.pop();
                if (p->left) {
                    Q.push(p->left);
                    nums++;
                }
                else {
                    flagEnd = true;
                    break;
                }
                if (p->right) {
                    Q.push(p->right);
                    nums++;
                }
                else {
                    flagEnd = true;
                    break;
                }
            }
        }
        return nums;
    }
};

解法二——完全二叉树+二分法

这个思路有个问题，二分法的判断标准是大了，小了，这里的判断是是否为NULL。

通过每一次二分查找可以从上到下确定一层是往左走还是往右走。for循环包含depth次，每一次当前层指向right，下面的层都指向left，如果有值，那么该层应该指向right，为NULL则该层指向left，在进行下一层。当指向right的时候得注意nums要增加多少，我感觉我现在就在凑。

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
class Solution {
public:
    int countNodes(TreeNode* root) {
        int depth = 0;
        if (root == NULL) {
            return 0;
        }
        // 先找出二叉树的最大深度
        TreeNode *p = root;
        while(p != NULL) {
            p = p->left;
            depth++;
        }
        vector <bool> direction(depth); //每一次指向的方向，右为0，左为1。
        int nums = pow(2, depth - 1) - 1;//前(depth-1)层
        // 二分查找最后一层的最后一个顶点
        for (int i = 0; i < depth - 1; i++) { //depth次才能判断每次向左向右
            TreeNode *p = root;
            for (int j = 0; j < i; j++) { // 前i层已经确定方向
                if (direction[j] == 1) {
                    p = p->left;
                }
                else {
                    p = p->right;
                }
            }
            p = p->right;
            for (int k = i + 1; k < depth - 1; k++) { //后面的层往左
                p = p->left;
            }
            if (p == NULL) { //为NULL，该层指向left
                direction[i] = 1;
                // cout <<  " NULL ";
            }
            else { //指向right
                nums += pow(2, depth - i - 2);
                // cout << p->val << " ";
            }
        }
        // cout << endl;
        // for (int i = 0 ;i < depth-1; i++) {
        //     cout << direction[i] << " ";
        // }
        return nums + 1;
    }
};

原来官方题解也是这个办法啊，一定分析的比我好。。。

具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数 kkk，如果第 kkk 个节点存在，则节点个数一定大于或等于 kkk，如果第 kkk 个节点不存在，则节点个数一定小于 kkk，由此可以将查找的范围缩小一半，直到得到节点个数。

如何判断第 kkk 个节点是否存在呢？如果第 kkk 个节点位于第 hhh 层，则 kkk 的二进制表示包含 h+1h+1h+1 位，其中最高位是 111，其余各位从高到低表示从根节点到第 kkk 个节点的路径，000 表示移动到左子节点，111 表示移动到右子节点。通过位运算得到第 kkk 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 kkk 个节点是否存在。

——力扣官方题解

fig1

完全二叉树的性质

完全二叉树总能拆分成许多的满二叉树。

222.完全二叉树的节点个数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
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        TreeNode *p = root->left;
        TreeNode *q = root->right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (p != NULL) {
            p = p->left;
            leftDepth++;
        }
        while (q != NULL) {
            q = q->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) { //满二叉树
            return (2 << leftDepth) - 1; //位运算，移位运算
        }
        return countNodes(root->left) + countNodes(root->right) + 1; // 加上根节点
    }
};

110. 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

自顶向下的递归

首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int height (TreeNode* p) {
        if (p == NULL){
            return 0;
        }
        else {
            return max(height(p->left), height(p->right)) + 1;
        }
    }
    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

自底向上的递归

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −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
class Solution {
public:
    int height (TreeNode* p) {
        if (p == NULL){
            return 0;
        }
        int leftHeight = height(p->left);
        int rightHeight = height(p->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return max(height(p->left), height(p->right)) + 1;
        
    }
    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        if (height(root) == -1) {
            return false;
        }
        else {
            return true;
        }        
    }
};

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

注意要回溯！！！所以要把之前的节点值存起来

257.二叉树的所有路径

解法一——递归+使用栈

函数参数我就使用了引用，即 vector<int>& path ，这是会拷贝地址的，所以 本层递归逻辑如果有path.push_back(cur->val); 就一定要有对应的 path.pop_back()

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 Solution {
public:
    void preorder(TreeNode *p, vector<int> &path,vector <string> &output) {
        if (!p->left && !p->right){ //左右为空，终止，记录path
            string s;
            for (int i = 0; i < path.size(); i++){
                s += to_string(path[i]);
                s += "->";
            }
            s += to_string(p->val);
            output.push_back(s);
            return; 
        }
        
        if (p->left) {
            path.push_back(p->val);
            preorder(p->left, path, output);
            path.pop_back();// 回溯
        }
        if (p->right) {
            path.push_back(p->val);
            preorder(p->right, path, output);
            path.pop_back();// 回溯
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector <string> output;
        if (root == NULL) {
            return output;
        }
        vector <int> path;
        preorder(root, path, output);
        return output;
    }
};

解法二——递归+使用字符串+隐式回溯

注意path是不变的，隐式回溯了。

使用的是 string path，这里并没有加上引用& ，即本层递归中，path + 该节点数值，但该层递归结束，上一层path的数值并不会受到任何影响。 如图所示：

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:
    void preorder(TreeNode *p, string path,vector <string> &output) {
        if (!p->left && !p->right){ //左右为空，终止，记录path
            output.push_back(path + to_string(p->val));
            return; 
        }
        
        if (p->left) {
            preorder(p->left, path + to_string(p->val) + "->", output); //注意path是不变的，隐式回溯了
        }
        if (p->right) {
            preorder(p->right, path + to_string(p->val) + "->", output);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector <string> output;
        if (root == NULL) {
            return output;
        }
        string path;
        preorder(root, path, output);
        return output;
    }
};

解法三——迭代

使用两个栈，一个存节点，一个存路径。因为路径拼接不易，所以直接存入整体路径。为了防止路径的top被污染，所以和取S的栈顶工作节点p一样，也把路径pathS先取出来，方便后续进一步使用。

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:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector <string> output;
        stack <string> path; // 存放路径
        stack <TreeNode*> S; // 前序遍历
        if (root != NULL) {
            S.push(root);
            path.push (to_string(root->val));
        }
        while (!S.empty()) {
            TreeNode *p = S.top();
            S.pop();
            string pathS = path.top(); //取出路径防止后续拼接时候多拼接一部分
            path.pop();
            if (!p->left && !p->right) {
                output.push_back(pathS);
            }
            if (p->right){
                S.push(p->right);
                path.push(pathS + "->" + to_string(p->right->val)); //考虑到stack出来拼接不方便，把存进去的时候直接把之前的也拼上
            }
            if (p->left){
                S.push(p->left);
                path.push(pathS + "->" + to_string(p->left->val));
            }

        }
        return output;
    }
};

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

注意是左叶子，不是左节点。

解法一——层次遍历BFS

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
lass Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue <TreeNode*> Q;
        int leftSum = 0;
        if (root != NULL) {
            Q.push(root);
        }
        while (!Q.empty()) {
            int qSize = Q.size();
            for (int i = 0; i < qSize; i++){
                TreeNode *p = Q.front();
                Q.pop();
                if (p->left){
                    Q.push(p->left);
                    if (!p->left->left && !p->left->right){
                        leftSum += p->left->val;
                    }
                }
                if (p->right) {
                    Q.push(p->right);
                }
            }
        }
        return leftSum;
    }
};

解法二——深度优先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
class Solution {
public:
    int preorder (TreeNode* p) {
        int ans = 0;
        if (p->left) {
            if (!p->left->left && !p->left->right) {
                ans += p->left->val;
            }
            else {
                ans += preorder(p->left);
            }
        }
        if (p->right) {
            ans += preorder(p->right);
        }
        return ans;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return preorder(root);
    }
};

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

解法一——BFS+flag

欸，我傻了，这个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
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue <TreeNode*> Q;
        int bottomLeftValue = root->val;
        Q.push(root);
        bool flagNULL = false;
        while (!Q.empty() && !flagNULL){
            int qSize = Q.size();
            flagNULL = true;
            for (int i = 0; i < qSize; i++){
                TreeNode *p = Q.front();
                Q.pop();
                if (i == 0){
                    bottomLeftValue = p->val;
                }
                if (p->left){
                    Q.push(p->left);
                    flagNULL = false;
                }
                if (p->right) {
                    Q.push(p->right);
                    flagNULL = false;
                }
            }
        }
        return bottomLeftValue;
    }
};

解法二——BFS，左右节点相反

在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue <TreeNode*> Q;
        int bottomLeftValue = root->val;
        Q.push(root);
        while (!Q.empty() ){
                TreeNode *p = Q.front();
                Q.pop();
                if (p->right){
                    Q.push(p->right);
                }
                if (p->left) {
                    Q.push(p->left);
                }
                bottomLeftValue = p->val;
        }
        return bottomLeftValue;
    }
};

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
class Solution {
public:
    void preorder (TreeNode *p, int depth, int &bottomLeftValue, int &maxDepth){ // DLR最先遍历到的就是最左节点
        int output = 0;
        if(!p->left && !p->right){ //全空
            if (depth > maxDepth) {
                maxDepth = depth;
                bottomLeftValue = p->val;
            }
        }
        if (p->left) {
            preorder(p->left, depth + 1, bottomLeftValue, maxDepth);
        }
        if (p->right) {
            preorder(p->right, depth + 1, bottomLeftValue, maxDepth);
        }
    }
    
    int findBottomLeftValue(TreeNode* root) {
        int depth = 0;
        int maxDepth = 0;
        int bottomLeftValue = 0;
        preorder(root, depth + 1, bottomLeftValue, maxDepth);
        return bottomLeftValue;
    }
};

路径总和（112/113）

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

迭代

注意深度优先遍历回溯时候，可能无法减去双亲结点的值，所以得把双亲的值保存，类似于“[257. 二叉树的所有路径](#257. 二叉树的所有路径)”中的保存方式。此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。

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:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack <pair<TreeNode*,int>> S;
        if (root != NULL){
            S.push(pair<TreeNode*,int>(root, root->val)); //根节点和为0
        }
        while (!S.empty()){
            pair<TreeNode*,int> p = S.top();
            S.pop();
            if (!p.first->left && !p.first->right) { //叶子
                if (p.second == targetSum) {
                    return true;
                }
            }
            if (p.first->right) {
                S.push(pair<TreeNode*,int>(p.first->right, p.second + p.first->right->val));
            }
            if (p.first->left) {
                S.push(pair<TreeNode*,int>(p.first->left, p.second + p.first->left->val));
            }
        }
        return false;
    }
};
递归

  1. 确定递归函数的参数和返回类型

    参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。

    再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

    • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
    • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
    • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

  2. 确定终止条件

    不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。

    如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。

  3. 确定单层递归的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack <pair<TreeNode*,int>> S;
        if (root == NULL){ // 递归时候没有判断左右节点是否非空，所以这里开始的时候要判断
            return false;
        }
        int count = targetSum - root->val; 
        if (!root->left && !root->right && count == 0) { // 利用减代替加可以少传递一个参数
            return true;
        }
        if (hasPathSum(root->left, count)) { // 如果是true 立刻返回
            return true;
        }
        if (hasPathSum(root->right, count)) {
            return true;
        }
        return false;
    }
};

另一个版本——代码随想录

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right && sum == root->val) {
            return true;
        }
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

迭代

思路类似“[257. 二叉树的所有路径](#257. 二叉树的所有路径)”中的保存方式，知识这里路径的保存利用stack套vector，而非之前的stack套string

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
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> output;
        stack <pair<TreeNode*, int>> S;
        stack <vector<int>> pathAll;
        if (root) {
            S.push(pair<TreeNode*, int>(root, root->val));
            pathAll.push(vector<int>(1, root->val)); // 注意这里的vector写法
        }
        while(!S.empty()) {
            pair<TreeNode*, int> p = S.top() ;
            S.pop();
            vector<int> path = pathAll.top();
            pathAll.pop();
            // for (int num:path){
            //     cout << num << " ";
            // }
            // cout << endl;
            if (!p.first->left && !p.first->right && p.second == targetSum){
                output.push_back(path);
            }
            if (p.first->right){
                S.push(pair<TreeNode*,int>(p.first->right, p.second + p.first->right->val));
                path.push_back(p.first->right->val);
                pathAll.push(path);
                path.pop_back();
            }
            if (p.first->left){
                S.push(pair<TreeNode*,int>(p.first->left, p.second + p.first->left->val));
                path.push_back(p.first->left->val);
                pathAll.push(path);
                path.pop_back();
            }
        }
        return output;
    }
};
递归

不需要返回值

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:
    vector<vector<int>> output;
    vector<int> path;

    void findPath(TreeNode* p, int targetSum) {
        if (p == NULL) {
            return;
        }
        path.push_back(p->val);
        if (!p->left && !p->right && targetSum == 0) {
            output.push_back(path);
        }
        if (p->left) {
            findPath(p->left, targetSum - p->left->val);
        }
        if (p->right) {
            findPath (p->right, targetSum - p->right->val);
        }
        path.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == NULL) {
            return output;
        }
        findPath (root, targetSum - root->val);
        return output;
    }
};

从遍历序列恢复二叉树

  • 由DLR和LDR的遍历序列可以唯一地确定一棵二叉树
  • 由LRD和LDR的遍历序列可以唯一地确定一棵二叉树
  • 通过DLR或者LRD的遍历序列确定二叉树或子树的根节点，通过LDR确定左右子树的序列。

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

一层一层切割

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间

img106.从中序与后序遍历序列构造二叉树

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 Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 递归
        // 数组大小为0，空节点
        if (inorder.empty() && postorder.empty()) {
            return NULL;
        }

        //不为空，postorder的最后一个元素是根节点
        TreeNode* p = new TreeNode (postorder[postorder.size() - 1]);

        // 找到中序的切割点
        int cutPoint;
        for (cutPoint = 0; cutPoint < inorder.size(); cutPoint++) {
            if (inorder[cutPoint] == postorder[postorder.size() - 1]) {
                break;
            }
        }

        // 分割中序 （左闭右开）
        vector<int> inorder_left(inorder.begin(), inorder.begin() + cutPoint);
        vector<int> inorder_right(inorder.begin() + cutPoint + 1, inorder.end()); //不包含分割点

        // 分割后序 （左闭右开）中序数组大小一定是和后序数组的大小相同的
        vector<int> postorder_left(postorder.begin(), postorder.begin() + inorder_left.size());
        vector<int> postorder_right(postorder.begin() + inorder_left.size(), postorder.end() - 1); //不包含分割点，最后一个

        // 对左右子树递归
        p->left = buildTree(inorder_left, postorder_left);
        p->right = buildTree(inorder_right, postorder_right);

        return p;
    }
};

为了减少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
36
37
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

——官方题解

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

利用无序映射做

这里利用pre_index++来表示前序的根节点也是和上述同理。更好理解的话还是把先序、中序的头尾都放在helper函数的输入里面。

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
class Solution {
    int pre_index;
    unordered_map <int, int> idx_map;
public:
    TreeNode* helper (int in_begin, int in_end, vector<int> & preorder, vector<int>& inorder) {
        if (in_begin > in_end) {
            return NULL;
        }

        // 找到分割点
        int cutPoint = idx_map[preorder[pre_index]]; // 这是分割点在inorder中的下标索引

        //　建立节点
        TreeNode *p = new TreeNode(preorder[pre_index]); // 分割点的值是preorder[begin]

        // 前序的分割点递增
        pre_index++;

        //左右子树
        p->left = helper(in_begin, cutPoint - 1, preorder, inorder);
        p->right = helper(cutPoint + 1, in_end, preorder, inorder);

        return p;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre_index = 0;
        int index = 0;
        for (int num:inorder) {
            idx_map[num] = index++;
        }
        return helper(0, inorder.size() - 1, preorder, inorder);
    }
};

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的最大二叉树 。

思路非常类似于“从遍历序列恢复二叉树”，但是这里需要注意的是不需要建立哈希表存储索引和值的关系，因为你每次要在序列中找到最大值，还是需要通过for循环来寻找，因此unordered_map在这里作用不大。

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:
    TreeNode* helper (vector<int>& nums, int begin, int end) {
        if (begin > end) {
            return NULL;
        }
        // 递归求解，每次先找最大
        int maxNumIndex = begin;
        for(int i = begin + 1; i <= end; i++){ //从begin+1开始可以减少工作量哈
            if (nums[i] > nums[maxNumIndex]) {
                maxNumIndex = i;
            }
        }
        TreeNode* root = new TreeNode(nums[maxNumIndex]);
        root->left = helper(nums, begin, maxNumIndex - 1);
        root->right = helper(nums, maxNumIndex + 1, end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
};

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

解法一——迭代+层次遍历+列举所有情况

非常朴素的想法，层次遍历+列举所有情况，将左右操作都从第二个子树合并到第一个子树上，所有的节点不存在问题，都通过创建0节点解决。这里需要注意的是不光要将0节点加到队列中以保证两子树的队列长度一致，同时子树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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 层次遍历，在root1上操作
        queue <TreeNode*> Q1;
        queue <TreeNode*> Q2;
        if (root1 != NULL || root2 != NULL) {
            if (root1 == NULL) {
                root1 = new TreeNode(0);
            }
            if (root2 == NULL) {
                root2 = new TreeNode(0);
            }
            Q1.push(root1);
            Q2.push(root2);
        }
        while (!Q1.empty() || !Q2.empty()) {
            TreeNode *p1 = Q1.front();
            Q1.pop();
            TreeNode *p2 = Q2.front();
            Q2.pop();
            if (p1 && p2) {
                p1->val += p2->val;
            }
            // left、right四种情况
            // if (p1->left) {
            //     Q1.push(p1->left);
            //     if (p2->left) {
            //         Q2.push(p2->left);
            //     }
            //     else {
            //         Q2.push(new TreeNode(0));
            //     }
            // }
            // if (p1->right) {
            //     Q1.push(p1->right);
            //     if (p2->right) {
            //         Q2.push(p2->right);
            //     }
            //     else {
            //         Q2.push(new TreeNode(0));
            //     }
            // }
            // if (!p1->left && p2->left) {
            //     p1->left = new TreeNode(0);
            //     Q1.push(p1->left);
            //     Q2.push(p2->left);
            // }
            // if (!p1->right && p2->right) {
            //     p1->right = new TreeNode(0);
            //     Q1.push(p1->right);
            //     Q2.push(p2->right);
            // }
            // 其余的p1、p2左右子树均不存在的情况不需要考虑
            // 综合一下只有两种情况，都不存在，和其他
            if (p1->left || p2->left){
                if(!p1->left){
                    p1->left = new TreeNode(0);
                }
                if(!p2->left){
                    p2->left = new TreeNode(0);
                }
                Q1.push(p1->left);
                Q2.push(p2->left);
            }
            if (p1->right || p2->right){
                if(!p1->right){
                    p1->right = new TreeNode(0);
                }
                if(!p2->right){
                    p2->right = new TreeNode(0);
                }
                Q1.push(p1->right);
                Q2.push(p2->right);
            }
        }
        return root1;
    }
};

解法二——递归+深度优先

如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；

如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；且即使其中一个有子树也不需要管了，毕竟另外一个直接空了

如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

——力扣官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2){
            return NULL;
        }
        if (!root1 && root2) {
            return root2;
        }
        if (root1 && !root2) {
            return root1;
        }
        TreeNode *merged = new TreeNode (root1->val + root2->val);
        merged->left = mergeTrees(root1->left, root2->left);
        merged->right = mergeTrees(root1->right, root2->right);
        return merged;
    }
};

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

二叉搜索树(二叉排序树)是一个有序树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) {
            return NULL;
        }
        TreeNode *p = root;
        while (p != NULL) {
            if (p->val == val) {
                return p;
            }
            if (p->val > val) {
                p = p->left;
            }
            else {
                p = p->right;
            }
        }
        return NULL;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root || root->val == val){
            return root;
        }
        if (root->val > val) {
            return searchBST(root->left, val);
        }
        else {
            return searchBST(root->right, val);
        }
    }
};

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了，而是左子树都小于中间节点，右子树都大于中间节点。

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

迭代——中序遍历

定义flag，防止第一次比较order超范围有问题

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
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // 中序遍历
        stack <TreeNode*> S;
        vector<int> order;
        bool flag = true;
        TreeNode *p = root;
        while (p != NULL || !S.empty()){
            if (p != NULL) {
                S.push(p);
                p = p->left;
            }
            else {
                p = S.top();
                S.pop();
                if (flag) {
                    order.push_back(p->val);
                    flag = false;
                    // cout << p->val << " ";
                }
                else if (p->val > order[order.size() - 1]) {
                    order.push_back(p->val);
                    // cout << p->val << " ";
                }
                else {
                    return false;
                }
                p = p->right;
            }
        }
        return true;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode *pre = NULL; //记录前一个，中序的前一个总比后一个小
    bool isValidBST(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        bool validLeft = isValidBST(root->left);
        
        if (pre != NULL && pre->val >= root->val) {
            return false;
        }
        pre = root;

        bool validRight = isValidBST(root->right);
        
        return validLeft && validRight;
    }
};

530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 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
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack <TreeNode*> S;
        TreeNode *p = root;
        int pre = -1;
        int minDistance = INT_MAX;
        while(p || !S.empty()){
            if(p){
                S.push(p);
                p = p->left;
            }
            else {
                p = S.top();
                S.pop();
                if((pre != -1) && (p->val - pre) < minDistance) {
                    minDistance = p->val - pre;
                }
                pre = p->val;
                p = p->right;
            }
        }
        return minDistance;
    }
};

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

几个可以利用的特点：

  1. 中序遍历是有序的
  2. 遍历一次就可以找到所有的众数——如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），不仅要更新maxCount，而且要清空结果集

递归

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
class Solution {
public:
    int count;
    int maxCount;
    vector<int> output;
    TreeNode* pre = NULL; //不能直接定义int类型，否则，NULL==0
    void inorder(TreeNode* p){
        if(p->left) {
            inorder(p->left);
        }
        // 判断、计数
        if (pre == NULL){
            count = 1;
        }
        else if (pre->val == p->val) {
            count++;
        }
        else { //不相等清零
            count = 1;
        }
        pre = p; //更新节点
        //比较
        if (count > maxCount) {
            maxCount = count;
            output.clear();
            output.push_back(p->val);
        }
        else if (count == maxCount) {
            output.push_back(p->val);
        }
        if(p->right) {
            inorder(p->right);
        }        
    }

    vector<int> findMode(TreeNode* root) {
        if (root == NULL) {
            return output;
        }
        int maxCount = 0;
        inorder(root);
        return output;
    }
};

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

236.二叉树的最近公共祖先2

  • 如何从底向上遍历？
  • 遍历整棵树，还是遍历局部树？
  • 如何把结果传到根节点的？

思路有点难想，一共分为两种情况：

  • 情况一：p、q分属在一个顶点的左右子树上
  • 情况二：p在q的子树下，q在p的子树下

首先考虑“情况一”，在递归寻找的过程中，如果我能找到这个其中一个节点，我就回传（此时不需要考虑是否为叶子节点，为什么呢？此时其实就是“情况二”）。如果一个顶点的左右都有值，那就说明这个节点是公共节点，又因为我们是从下到上回溯的，所以碰到的一定是最近公共祖先（也就是最深的，再往上的一定至少有一边为NULL）。

下面考虑“情况二”的问题。如果p在q的子树下或q在p的子树下，题目中又保证p 和 q 均存在于给定的二叉树中，且互不相同，那么是不是就可以说假设我现在找到了p，如果我在后续的递归遍历中再也没有找到q，那么q一定就在p的子树中，所以这就解决了一个节点属于另一个元素的孩子的问题。

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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) {
            return root; //NULL就直接回传，如果遇到需要找的p、q也回传，注意如果q（p）在p（q）的子树下就不往下递归了，虽然我没递归到，但是一定在这个下面。
        }
        // 左右子树递归寻找
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right,  p, q);
        if (left && right) {
            return root; // 如果左右子树都有，那他就是最近公共祖先
        }
        else if (left && !right) {
            return left;
        }
        else if (right && !left) {
            return right;
        }
        else { //都为空
            return NULL;
        }

    }
};

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

  • 是公共祖先：因为是有序树，所以 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的值 一定是在[p,q][p, q]​区间的。即 中节点->val > p->val && 中节点->val < q->val 或者 中节点->val > q->val && 中节点->val < p->val。
  • 最近公共祖先：如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。【反证法】此时，如果最近公共祖先在左子树中，说明p、q必须都得在左子树中，和“一个结点值大于根节点”矛盾；如果最近公共祖先在右子树中，说明p、q必须都得在右子树中，和“一个结点值小于根节点”矛盾；只剩最后一种情况：根节点就是最近公共祖先呗

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) { //p，q都在左子树
            return lowestCommonAncestor(root->left, p, q);
        }
        if (root->val < p->val && root->val < q->val) { //p，q都在右子树
            return lowestCommonAncestor(root->right, p, q);
        }
        if ((root->val <= p->val && root->val >= q->val) || (root->val >= p->val && root->val <= q->val)) { // 分叉点或者就是其中一个节点，其实这个就是上两个以外的else
            return root;
        }
        return NULL;
    }
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (root->val > p->val && root->val > q->val) { //p，q都在左子树
                root = root->left;
            }
            else if (root->val < p->val && root->val < q->val) { //p，q都在右子树
                root = root->right;
            }
            else { // 分叉点或者就是其中一个节点，其实这个就是上两个以外的else
                return root;
            }
        }
        return NULL;
    }
};

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

根据定义完成。

  • 注意root因为要返回，所以不能直接对他操作
  • 需要考虑空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
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) { // 考虑空节点的问题
            return new TreeNode(val);
        }
        TreeNode *p = root;
        while (p) {
            if (val > p->val)  {
                if (p->right) {
                    p = p->right;
                }
                else {
                    p->right = new TreeNode(val);
                    break;
                }
            }
            else {
                if (p->left) {
                    p = p->left;
                }
                else {
                    p->left = new TreeNode(val);
                    break;
                }
            }
        }
        return root; // 注意root不能变
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) { // 考虑空节点的问题,递归中其实就是最后一步
            return new TreeNode(val);
        }
        if (val > root->val)  {
            root->right = insertIntoBST(root->right, val); //接收到的就是返回的原始root，只是新增了子节点
        }
        else {
            root->left = insertIntoBST(root->left, val);
        }
        return root; 
    }
};

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。
  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回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
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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL) {
            return root;
        }
        // 先要找到删除元素
        TreeNode *p = root;
        TreeNode *pParent = NULL;
        bool direction = true; // 布尔值判断是在parent的左子树（true）还是右子树（false）
        while (p) {
            if (key > p->val) {
                pParent = p;
                p = p->right;
                direction = false;
            }
            else if(key < p->val) {
                pParent = p;
                p = p->left;
                direction = true;
            }
            else { //相等
                break;
            }
        }
        if (p == NULL) { //没找到
            return root;
        }
        // 对删除元素操作
        TreeNode *q = NULL; // q用于指示pParent后续指向何方
        if (!p->left && !p->right) { // 全空
            q = NULL;
        }
        else if (!p->left && p->right) { // 左空右不空
            q = p->right;
        }
        else if (p->left && !p->right) { // 左不空右空
            q = p->left;
        }
        else {// 左右都不空
            q = p->right; //指向右子树，并将原来的左子树放在原来的右子树的最左下方
            TreeNode *pLeft = p->left; //原来的左子树
            p = p->right;
            while (p->left) {
                p = p->left; // 指向原来的右子树的最左下方
            }
            //此时p->left为空
            p->left = pLeft;
        }
        // 将新子树节点放置在原来pParent下方，这里需要注意，万一删除的节点就是根节点的情况
        if (pParent) { //删除的节点非根节点
            if(direction) {
                pParent->left = q;
            }
            else {
                pParent->right = q;
            }
            return root;
        }
        else { //删除的节点就是根节点
            return q;
        }        
    }
};

递归

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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL) {
            return root;
        }
        
        // 对删除元素操作
        if (root->val == key) {
            if (!root->left && !root->right) { // 全空
                return NULL;
            }
            else if (!root->left && root->right) { // 左空右不空
                return root->right;
            }
            else if (root->left && !root->right) { // 左不空右空
                return root->left;
            }
            else {// 左右都不空          
                TreeNode *rootRight = root->right;
                while (rootRight->left) {
                    rootRight = rootRight->left; // 指向原来的右子树的最左下方
                }
                //此时rootRight->left为空
                rootRight->left = root->left;
                // cout << rootRight->val << " ";
                return root->right;
            }
        }

        // 递归寻找左右
        if (root->val > key) {
            root->left = deleteNode(root->left, key);
        }
        else {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

先找到两个临界点值。

  • low：工作节点p满足p->val >= low && p->left->val < low， 则p = p->right
  • high：工作节点p满足p->val <= high && p->right->val > high， 则p = p->left

例如对于low的临界点来说，他一定是左孩子，双亲一定大于他，他本身的右孩子也一定大于他。**但是要注意右孩子可能还是会有小于low的情况出现！！！**所以要用while

此外处理根节点不在范围内的问题时候，不能分开来考虑，例如先low，后high，否则可能有问题。

迭代

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:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        while (root && (root->val > high || root->val < low)) { // 不能分开来，先左后右
            if (root->val > high) {
                root = root->left;
            }
            else {
                root = root->right;
            }
        }
        if (!root) {
            return root;
        }
        TreeNode *p = root;
        // 找low的临界点
        while (p) {
            while (p->val >= low && p->left && p->left->val < low) { // 注意这里是while
                p->left = p->left->right;
            }
            p = p->left; // 还没到临界点
        }
        p = root;
        // 找high的临界点
        while (p) {
            while (p->val <= high && p->right && p->right->val > high) {// 注意这里是while
                p->right = p->right->left;
            }
            p = p->right; // 还没到临界点
        }
        return root;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) {
            return root;
        }
        if (root->val < low) {
            return trimBST(root->right, low, high);
        }
        if (root->val > high) {
            return trimBST(root->left, low, high);
        }

        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        return root;
    }
};

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

注意是所有节点的左右子树的深度相差不超过 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* helper (vector<int>&nums, int left, int right){
        if (left > right) {
            return NULL;
        }
        TreeNode* p = new TreeNode(nums[(left + right) / 2]);
        p->left = helper(nums, left, (left + right) / 2 - 1);
        p->right = helper(nums, (left + right) / 2 + 1, right);
        return p;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
};

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

逆中序遍历

迭代

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:
    TreeNode* convertBST(TreeNode* root) {
        stack <TreeNode*> S;
        TreeNode *p = root;
        int sum = 0;
        while(p || !S.empty()){
            if (p) {
                S.push(p);
                p = p->right;
            }
            else {
                p = S.top();
                S.pop();
                sum += p->val;
                p->val = sum;
                p = p->left;
            }
        }
        return root;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if (root == NULL) {
            return root;
        }
        if (root->right) {
            root->right = convertBST(root->right);
        }
        sum += root->val;
        root->val = sum;
        if (root->left) {
            root->left = convertBST(root->left);
        }
        return root;
    }
};

回溯

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合

    • 剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了。
    • 一个集合来求组合的话，就需要startIndex；多个集合取组合，各个集合之间相互不影响，那么就不用startIndex
    • 去重问题——used

  • 切割问题：一个字符串按一定规则有几种切割方式

  • 子集问题：一个N个数的集合里有多少符合条件的子集

    • 在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

  • 排列问题：N个数按一定规则全排列，有几种排列方式

  • 棋盘问题：N皇后，解数独等等

组合是不强调元素顺序的，排列是强调元素顺序。

回溯法解决的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。for循环横向遍历，递归纵向遍历，回溯不断调整结果集
回溯算法理论基础

  • 在for循环上做剪枝操作是回溯法剪枝的常见套路！

模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
回溯算法大纲

以下来自回溯算法入门级详解 + 练习（持续更新）

「回溯算法」强调了「深度优先遍历」思想的用途，用一个 不断变化 的变量，在尝试各种可能的过程中，搜索需要的结果。强调了 回退 操作对于搜索的合理性。

回溯算法用于 搜索一个问题的所有的解 ，通过深度优先遍历的思想实现。

与动态规划的区别：

  • 共同点——用于求解多阶段决策问题。多阶段决策问题即：

    • 求解一个问题分为很多步骤（阶段）；

    • 每一个步骤（阶段）可以有多种选择。

  • 不同点

    • 动态规划只需要求我们评估最优解是多少，最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果；
    • 回溯算法可以搜索得到所有的方案（当然包括最优解），但是本质上它是一种遍历算法，时间复杂度很高。

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

77.组合1

解法一——暴力回溯

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<vector<int>> output;
    vector<int> temp;
    void backtracking(int n, int k, int start) {
        if (temp.size() == k) {
            output.push_back(temp);
            return;
        }

        for (int i = start; i <= n; i++) {
            temp.push_back(i);
            backtracking(n, k, i + 1); //递归
            temp.pop_back(); //回溯
        }
    }

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return output;        
    }
};

解法二——回溯+剪枝

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
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<vector<int>> output;
    vector<int> temp;
    void backtracking(int n, int k, int start) {
        if (temp.size() == k) {
            output.push_back(temp);
            return;
        }

        for (int i = start; i <= n - (k - temp.size()) + 1; i++) {
            temp.push_back(i);
            backtracking(n, k, i + 1); //递归
            temp.pop_back(); //回溯
        }
    }

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return output;        
    }
};

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

隐含sum的回溯，通过两个方法剪枝

  • i的范围，要保证后续有这么多的树可以取
  • sum和target的关系，如果加上当前数target已经炸了，那么就不往下了，这里隐含了一点，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
class Solution {
public:
    vector<vector<int>> output;
    vector<int> temp;
    
    void backtracking(int k, int target, int start, int sum) {
        if (temp.size() == k && sum == target) {
            output.push_back(temp);
            return;
        }

        for (int i = start; i <= 9 - (k - temp.size()) + 1; i++) {
            if (sum + i > target) {
                break;
            }
            temp.push_back(i);
            backtracking (k, target, i + 1, sum + i); // 隐含sum的回溯
            temp.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, 0);
        return output;
    }
};

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。img

注意alphabet的定义方式是大括号。此外digitsStart不能使用stoi，这个也不知道是为什么。此外需要注意为空的情况。

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:
    vector<string> output;
    string temp;
    vector<string> alphabet = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void backtracking(string digits, int start) {
        if (start == digits.length()) {
            output.push_back(temp);
            return ;
        }
        int digitsStart = digits[start] - '0';
        for (int i = 0; i < alphabet[digitsStart].length(); i++) {
            temp.push_back(alphabet[digitsStart][i]);
            backtracking(digits, start + 1);
            temp.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.length() == 0) {
            return output;
        }
        backtracking(digits, 0);
        return output;
    }
};

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

  • 组合没有数量要求
  • 元素可无限重复选取

有两点需要注意：

  • 递归的时候下一次的start是i，不是i+1，也不是start。不是start（因为是这个数及其以后的可选），也不是i+1（因为可以重复选取）
  • 剪枝时候的判定条件sum + candidates[i] > target就break，数组需要有序
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:
    vector<vector<int>> output;
    vector<int> temp;
    void backtracking (vector<int>& candidates, int target, int sum, int start) {
        if (sum == target) {
            output.push_back(temp);
            return;
        }

        for (int i = start; i < candidates.size(); i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            temp.push_back(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i); // 隐含sum的回溯，注意这里是i不是start（因为是这个数及其以后的可选），也不是i+1（因为可以重复选取）
            temp.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 注意需要有序的时候，我们的break策略才是成立的
        backtracking(candidates, target, 0, 0);
        return output;
    }
};

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

candidates中有重复的数字，这个重复数字可以在同一个解里面使用，但是解集不能包含重复的元素。例如：

1
2
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:[[1,1,6],[1,2,5],[1,7],[2,6]]

所以不能直接通过以下方式将输入candidates数组去重来实现

1
2
3
sort(candidates.begin(), candidates.end());
auto end_unique = unique(candidates.begin(), candidates.end());
candidates.erase(end_unique, candidates.end());

我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

40.组合总和II

与39题的区别：

  • 同意元素不能无限取，所以递归时候是i+1。
  • 加入了这一个判断i > start && candidates[i] == candidates[i-1]，以防止出现一摸一样的结果。第二部分很好理解，就是说如果这一个和上一个值是一样的，那我就跳过。但是注意到同一个树枝上面的元素是可以重复的，所以需要i > start这一约束，防止直接不让重复了，也就保证了示例中的[1,1,6]这组解还是能够出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> output;
    vector<int> temp;
    void backtracking (vector<int>& candidates, int target, int sum, int start) {
        if (sum == target) {
            output.emplace_back(temp);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }
            if (sum + candidates[i] > target) {
                break;
            }
            temp.emplace_back(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return output;
    }
};

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是向前和向后读都相同的字符串。

解法一——暴力回溯

检测到是回文串送入temp

  • 在处理组合问题的时候，递归参数需要传入start，表示下一轮递归遍历的起始位置，这个start就是切割线。
  • 为了方便处理回文串，也要传入start和end，就可以减少切割。
  • start == s.length() - 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
class Solution {
public:
    vector<vector<string>> output;
    vector<string> temp;

    bool isPalindrome (string s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    void backtracking (string s, int start) {
        if (start > s.length() - 1) { // 注意这里是>，而非==，因为最后一个start也要存入
            output.emplace_back(temp);
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                temp.emplace_back(s.substr(start, i - start + 1));
            }
            else {
                continue;
            }
            backtracking(s, i + 1);
            temp.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return output;
    }
};

解法二——回溯+优化回文串的识别

给定字符串"abcde", 在已知"bcd"不是回文字串时, 不再需要去双指针操作"abcde"而可以直接判定它一定不是回文字串。

具体来说, 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。

image-20240410155458022

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
class Solution {
public:
    vector<vector<string>> output;
    vector<string> temp;
    vector<vector<bool>> isPalindrome; //放事先计算好的是否回文子串的结果

    void computePalindrome (string &s) {
        // isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 
        isPalindrome.resize(s.length(), vector<bool> (s.length(), true)); // 创建二维数组，长度为s.length() x s.length()，全部赋值为true
        for (int i = s.length() - 1; i >= 0; i--) {
            for(int j = i + 1; j < s.length(); j++) {
                // 需要保证计算[i, j]区间时候，[i+1, j-1]区间已经计算完毕
                isPalindrome[i][j] = (s[i] == s[j]) && isPalindrome[i+1][j-1];
                // if (j == i) {isPalindrome[i][j] = true;} // 等于的时候必然是true，不需要重新赋值
                // else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);} //差一位的时候，第二个条件相当于已经满足了，因为是true
                // else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
            }
        }
    }

    void backtracking (string s, int start) {
        if (start > s.length() - 1) { // 注意这里是>，而非==，因为最后一个start也要存入
            output.emplace_back(temp);
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                temp.emplace_back(s.substr(start, i - start + 1));
                backtracking(s, i + 1);
                temp.pop_back();
            }           
        }
    }

    vector<vector<string>> partition(string s) {
        computePalindrome(s);
        backtracking(s, 0);
        return output;
    }
};

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

先考虑暴力回溯，在考虑剪枝

解法一——暴力回溯，temp是字符串数组

注意这里不需要代码中对i的for循环，这个本来就是递归要做的循环，还是没有理解透啊，加入这个循环以后会导致缺数。

这里也考虑了一点剪枝的问题

  • 比如j < start + 3，就是每个segment值不会大于255，那么就不会大于3.
  • 此外if (segment > 4) {continue;}，就是对于segment分段总数的限制。
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
class Solution {
public:
    vector<string> output;
    vector<string> temp;
    bool isValidSegment (string sSegment) { // 左右皆为闭
        if (sSegment.size() > 1 && sSegment[0] == '0') { // 多位前导0的情况
            return false;
        }
        // cout << sSegment << ",";
        int num = stoi(sSegment);
        if (num < 0 || num > 255){
            return false;
        }
        else {
            return true;
        }
    }

    void backtracking(string s, int start, int segment) {
        if (start == s.length() && segment == 4){
            // string tempOutput = temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3];
            // cout << temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3] << endl;
            output.emplace_back(temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3]);
            return;
        }


        // for (int i = start; i < s.length(); i++){
            for (int j = start; j < start + 3 && j < s.length(); j++) {
                string sSegment = s.substr(start, j - start + 1);
                if (segment > 4) {
                    continue;
                }
                if (isValidSegment(sSegment)) {
                    temp.emplace_back(sSegment);
                    backtracking(s, j + 1, segment + 1);
                    temp.pop_back();
                }
            }
        // }
    }

    vector<string> restoreIpAddresses(string s) {
        backtracking(s, 0, 0);
        return output;
    }
};

解法二——temp就是对源字符串加点

代码随想录的方法

93.复原IP地址

1
2
3
4
5
6
7
8
9
for (int i = startIndex; i < s.size(); i++) {
    if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
        s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
        pointNum++;
        backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
        pointNum--;                         // 回溯
        s.erase(s.begin() + i + 1);         // 回溯删掉逗点
    } else break; // 不合法，直接结束本层循环
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

数组的 子集 是从数组中选择一些元素（可能为空）。

其实还是一个组合问题，和顺序无关。

子集是收集树形结构中树的所有节点的结果。

而组合问题、分割问题是收集树形结构中叶子节点的结果。

解法一——递归

思路一——每个元素有选和不选两个情况

递归的过程就是每次去掉一个数，再求子集。而每个元素又选和不选两个情况

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking (vector<int> nums, int start) {
        if (start == nums.size()) {
            output.emplace_back(temp);
            return;
        }

        temp.emplace_back(nums[start]);
        backtracking(nums, start + 1);
        temp.pop_back();
        backtracking(nums, start + 1);
        
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        // vector<int> empty;
        // output.emplace_back(empty);
        backtracking(nums, 0);
        return output;
    }
};
思路二——遍历整个树的所有节点

78.子集

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking (vector<int> nums, int start) {
        output.emplace_back(temp);
        if (start >= nums.size()) {
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            temp.emplace_back(nums[i]);
            backtracking(nums, i + 1);
            temp.pop_back();
        }
        
        // backtracking(nums, start + 1);
        
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        // vector<int> empty;
        // output.emplace_back(empty);
        backtracking(nums, 0);
        return output;
    }
};

解法二——枚举迭代

创建一个0，1的mask实现枚举，相当于一个二进制的数组和当前数组取与。

其中，<<是左移运算，每次乘2.

  • 1 << numsSize创建0∼2numsSize−10\sim 2^{numsSize-1}的二进制序列长度。
  • 1 << i判断该mask下，这个数字要不要push进去。注意1 << 0出来的是001，1 << 1出来的是010，1 << 2出来的是100，刚好与mask的各个位置吻合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> output;
        vector<int> temp;
        int numsSize = nums.size();
        for (int mask = 0; mask < (1 << numsSize); mask++) {
            temp.clear();
            for (int i = 0; i < numsSize; i++) {
                if (mask & (1 << i)) {
                    temp.emplace_back(nums[i]);
                }
            }
            output.emplace_back(temp);
        }
        return output;
    }
};

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

解法一——递归

套路类似“40. 组合总和 II”，先排序，如果和上一个相同的话，那就continue

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking(vector<int> nums, int start) {
        output.emplace_back(temp);

        for  (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            temp.emplace_back(nums[i]);
            backtracking(nums, i + 1);
            temp.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return output;
    }
};

解法二——枚举迭代

mask需要考虑去重，i不需要考虑去重。

要加入一个判断if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1])，这个不好想啊！

对于当前选择的数x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> output;
    vector<int> temp;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int numSize = nums.size();
        sort(nums.begin(), nums.end());
        for (int mask = 0; mask < (1 << numSize); mask++) {
            temp.clear();
            bool flag = true;
            for (int i = 0; i < numSize; i++) {
                if (mask & (1 << i)) {
                    if(i > 0 && (mask >>(i-1) & 1) == 0 && nums[i] == nums[i-1]) {
                        flag = false;
                        break;
                    }
                    temp.emplace_back(nums[i]);
                }
            }
            if (flag) {
                output.emplace_back(temp);
            }
        }
        return output;
    }
};

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以和子集问题并不一样！！！

解法一——深搜

定义之前的最大值last

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking(vector<int> nums, int start, int last) {
        if (start == nums.size()) {
            if (temp.size() >= 2) {
                output.emplace_back(temp);
            }
            return;
        }

        if (nums[start] >= last) { // 输入并递归
            temp.emplace_back(nums[start]);
            backtracking(nums, start + 1, nums[start]);
            temp.pop_back();
        }
        if (nums[start] != last) {
            backtracking(nums, start + 1, last);
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0, INT_MIN);
        return output;
    }
};

解法二——回溯+set去重

以下写法if (i > start && nums[i] == nums[i-1])是错误的，因为可能重复值并不出现在相邻元素，即使改成if (i > start && nums[i] == last)也不对，需要判断之前的所有元素才行。如测试用例[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void backtracking(vector<int> nums, int start, int last) {
        if (temp.size() >= 2) {
            output.emplace_back(temp);
        }

        for(int i = start; i < nums.size(); i++){ 
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            if (nums[i] >= last) {
                temp.emplace_back(nums[i]);
                backtracking(nums, i+1, nums[i]);
                temp.pop_back();
            }
            // else {
            //     backtracking(nums, i+1, last);
            // }
        }
    }

所以需要用到set来记录之前的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void backtracking(vector<int> nums, int start, int last) {
    if (temp.size() >= 2) {
        output.emplace_back(temp);
    }

    unordered_set<int> thisLayer;
    for(int i = start; i < nums.size(); i++){ // 使用set对本层元素进行去重
        if (i > start && thisLayer.find(nums[i]) != thisLayer.end()) {
            continue;
        }
        if (nums[i] >= last) {
            temp.emplace_back(nums[i]);
            thisLayer.insert(nums[i]);
            backtracking(nums, i+1, nums[i]);
            temp.pop_back();
        }
    }
}

或者用数组来作为哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void backtracking(vector<int> nums, int start, int last) {
    if (temp.size() >= 2) {
        output.emplace_back(temp);
    }

    int thisLayer[201] = {0};
    for(int i = start; i < nums.size(); i++){ 
        if (i > start && thisLayer[nums[i] + 100] != 0) {
            continue;
        }
        if (nums[i] >= last) {
            temp.emplace_back(nums[i]);
            thisLayer[nums[i] + 100]++;
            backtracking(nums, i+1, nums[i]);
            temp.pop_back();
        }
    }
}

此外可以不定义last元素。

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking(vector<int> nums, int start) {
        if (temp.size() >= 2) {
            output.emplace_back(temp);
        }

        int thisLayer[201] = {0};
        for(int i = start; i < nums.size(); i++){ 
            if ((!temp.empty() && nums[i] < temp.back()) || thisLayer[nums[i] + 100] != 0) {
                continue;
            }
            temp.emplace_back(nums[i]);
            thisLayer[nums[i] + 100]++;
            backtracking(nums, i+1);
            temp.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return output;
    }
};

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

排列问题

排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

46.全排列

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

这里的used数组和非递减子集中的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
26
27
28
29
class Solution {
public:
    vector<vector<int>> output;
    vector<int> temp;
    
    void backtracking(vector<int> nums, vector<bool> &used) {
        if (temp.size() == nums.size()) { // 终止条件
            output.emplace_back(temp);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            temp.emplace_back(nums[i]);
            backtracking(nums, used);
            temp.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used (nums.size(), false);
        backtracking(nums, used);
        return output;
    }
};

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

解法一——利用unordered_map

相当于定义了一个hash表，存储每个数字(first，键)能用多少次(second，值)

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<vector<int>> output;
    vector<int> temp;

    void backtracking(vector<int> nums,  unordered_map<int,int> &used) {
        if (temp.size() == nums.size()) {
            output.emplace_back(temp);
            return;
        }

        for (auto p = used.begin(); p != used.end(); p++) { 
            if (p->second == 0 ) {
                continue;
            }
            p->second--;
            temp.emplace_back(p->first);
            backtracking(nums, used);
            temp.pop_back();
            p->second++;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        unordered_map<int,int> used;
        for (int num:nums) {
            used[num] ++;
        }
        backtracking(nums, used);
        return output;
    }
};

解法二——利用used数组，并对其限制条件

只要设定一个规则，保证在填第idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

这里涉及两个条件，关系为“或”，第二个条件很好理解，用过了就不能用了，第一个条件有点难理解：

  • i > 0 && nums[i] == nums[i-1] && used[i-1] == false
  • used[i] == true

i > 0 && nums[i] == nums[i-1] && used[i-1] == false限制了从左到右填入的顺序，属于是“同层（树层）剪枝”

image-20240411144113495

47.全排列II2

如果该作i > 0 && nums[i] == nums[i-1] && used[i-1] == true，则变成“不同层（树枝）剪枝”，情况复杂很多

image-20240411144439089

47.全排列II3

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:
    vector<vector<int>> output;
    vector<int> temp;

    void backtracking(vector<int> nums,  vector<bool> &used) {
        if (temp.size() == nums.size()) {
            output.emplace_back(temp);
            // cout << "return " << endl;
            return;
        }

        for (int i = 0; i < nums.size(); i++) { 
            // for (bool jj:used) {
            //     cout << jj << " ";
            // }
            if ((i > 0 && nums[i] == nums[i-1] && used[i-1] == false) || used[i] == true) {
                // cout << "continue "<< endl;
                continue;
            }
            // cout << endl;
            temp.emplace_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            temp.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return output;
    }
};

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

一个机场映射多个机场，同时由于字典顺序小的行程，所以需要里面套的是有序的map：两种表示

  • unordered_map<string, multiset> targets：unordered_map<出发机场, 到达机场的集合> targets遍历multiset不能删除元素
  • unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。

有几个点需要注意：

  • 最终的路径长度应该是比ticket长度要大1的
  • 在使用迭代器遍历元素时候，如果要改变元素值，需要使用&，即for (auto &p : airports[last])
  • vector，map元素遍历时候的写法要注意。难还难在容器的选择和使用上
  • 该题目的情况下，应该采用有返回值的回溯比较好。
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 Solution {
public:
    vector<string> output;
    unordered_map <string, map<string, int>> airports;

    bool backtracking (string last, int ticketsSize) {
        if (output.size() == ticketsSize + 1) {
            return true;
        }

        for (auto &p : airports[last]) {
            if (p.second !=  0) {
                p.second--;
                output.emplace_back(p.first);
                if (backtracking(p.first, ticketsSize)) {
                    return true;
                }
                output.pop_back();
                p.second++;
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        int ticketsSize = tickets.size();
        // 建立unordered_map存储一对多的机场关系
        for (auto p: tickets) {
            airports[p[0]][p[1]] ++;
        }
        output.emplace_back("JFK");
        backtracking(output.back(), ticketsSize);
        return output;
    }
};

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

根据题意暴力回溯即可，和代码随想录不同。

  • 利用 columns 数组记录每个皇后的位置，最后再构建棋盘
  • 这样判断是否合理时候比较简单，只需要考虑列不同、左斜、右斜等几种情况即可。
  • 其实还可以进一步简化，当第一行只需要一半即可，因为偶数时候必定有对称的情况，奇数时候除了第一行刚好为中间，其余也有对称情况。
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
class Solution {
public:
    vector<vector<string>> output;
    vector<int> columns; //n个位置，表示第n个皇后在第n行的第几个格子
    void backtracking (int n, int row) {
        if (row == n) {
            vector<string> temp(n, string(n, '.'));            
            for (int i = 0; i < n; i++) {
                // if (!(n % 2) && columns[0] == n / 2) { // 奇数列情况，中间的情况是不能反转的
                temp[i][columns[i]] = 'Q';
            }
            output.emplace_back(temp);
            // cout << endl;
            return;
        }
        bool flag = false; // flag检测列标是否和前面元素冲突
        for(int column = 0; column < n; column++) { //第row元素的列标, 一定有一个反转的情况成立
            flag = false;
            for (int j = 0; j < row; j++) { // j表示前面的行
                if (columns[j] == column || (row - j) == (columns[j] - column) || (row - j) == - (columns[j] - column)) { // 列标重合，斜线
                    flag = true;
                    break;
                }
            }
            if (!flag) { // 没问题，回溯
                columns.emplace_back(column);
                backtracking(n, row + 1);
                columns.pop_back();
            }
        }

    }

    vector<vector<string>> solveNQueens(int n) {
        backtracking(n, 0);
        return output;
    }
};

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

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
71
class Solution {
public:
    bool backtracking(vector<vector<char>>& board, int row, int column) {
        if (row >= 9 || column >= 9) {
            return true;
        }
        if (board[row][column] < '1' || board[row][column] > '9') { // 注意这里是或的关系
            int num = 1;
            for (num = 1; num < 10; num++) {
                // cout << row << " " << column << " " << num << endl;
                if (isValid(board, row, column, num)) {
                    board[row][column] = num + '0';
                    // cout << row << " " << column << " " << num << endl;
                    if (column == 9 - 1) {
                        if (backtracking(board, row + 1, 0)) {
                            return true;
                        } // 换行
                    }
                    else {
                        if (backtracking(board, row, column + 1)) {
                            return true;
                        } // 继续
                    }
                    board[row][column] = '.';
                }
            }
            if (num == 10 && board[row][column] == '.') {
                return false; // 不能让一元素为.，说明前面是有错的, 注意已经自增过了，所以这里是10
            }
        }
        if (column == 9 - 1) {
            if (backtracking(board, row + 1, 0)) {
                return true;
            } // 换行
        }
        else {
            if (backtracking(board, row, column + 1)) {
                return true;
            } // 继续
        }
        return false;
    }
    
    bool isValid (vector<vector<char>>& board, int row, int column, int num) {
        // cout << row << " " << column << " " << num << endl;
        for (int i = 0; i < 9; i++) { // 检查同一行
            if (board[row][i] - '0' == num) {
                return false;
            }
        }
        for (int j = 0; j < 9; j++) { // 检查同一列
            if (board[j][column] - '0' == num) {
                return false;
            }
        }
        int blockLeft = (column / 3) * 3;
        int blockTop = (row / 3) * 3;
        for (int i = blockLeft; i < blockLeft + 3; i++) {
            for (int j = blockTop; j < blockTop + 3; j++) {
                if (board[j][i] - '0' == num) {
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board, 0, 0);
    }
};

代码随想录的解答略有区别，主要是他直接把每个顶点的循环放在backtracking里面了，这样里面每一次跑都会进入两层for循环，如果有值就continue；此外循环可以直接通过for (char k = '1'; k <= '9'; k++)来进行，就不需要补+'0'的操作了。

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

如何验证可不可以用贪心算法呢？最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心算法一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

贪心算法大纲

区间类问题——先排序

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

解法一——两重for循环

优先满足胃口大的

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 findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int output = 0;
        int gStart = g.size() - 1;
        for (int i = s.size() - 1; i >= 0; i--) { // 优先满足胃口大的
            for (int j = gStart; j >= 0; j--) {
                // cout << s[i] << " " << g[j] << endl;
                if (s[i] >= g[j]) {
                    
                    output++;
                    gStart = j - 1; // 从目前满足的下一个开始
                    break;
                }
            }
        }
        return output;
    }
};

解法二——一层for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int output = 0;
        int sStart = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; i--) { // 优先满足胃口大的
            if (sStart >= 0 && s[sStart] >= g[i]) {
                output++;
                sStart--;
            }
        }
        return output;
    }
};

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

  • 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
  • 其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

考虑的因素

  • 单调坡度只记录首尾
  • 需要考虑平坡（两种情况）
    img
  • 只有一个或两个元素——两个元素判断是否是平坡

解法一——贪心

起点终点、平坡比较难判断。。。（还是没太想清楚，后面仔细想想）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) {
            return nums.size();
        }

        int index0, index1; 
        int output = (nums[1] - nums[0] == 0) ? 1 : 2; 
        for (index0 = 0, index1 = 1; index1 < nums.size() - 1; index1++) {
            cout << " index0: " << nums[index0] << " index1: " << nums[index1] << " index2:" << nums[index1+1];
            cout << " prev: " << (nums[index1] - nums[index0]) << " curr: " << (nums[index1+1] - nums[index1])<< endl;
            if (((nums[index1] - nums[index0]) * (nums[index1 + 1] - nums[index1]) < 0) || ((nums[index1] - nums[index0]) == 0) && (nums[index1 + 1] - nums[index1]) != 0) { //满足摆动
                output++;
                index0 = index1;
            }
        }
        return output;
    }
};

解法二——动态规划

考虑用动态规划的思想来解决这个问题。

  1. up[i] 表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。
  2. down[i] 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

up[i]={up[i−1], nums [i]≤nums[i−1]max⁡(up[i−1], down [i−1]+1), nums [i]> nums [i−1]down⁡[i]={down⁡[i−1], nums [i]≥ nums [i−1]max⁡(up[i−1]+1, down [i−1]), nums [i]< nums [i−1]\begin{aligned} & u p[i]= \begin{cases}u p[i-1], & \text { nums }[i] \leq n u m s[i-1] \\ \max (u p[i-1], \text { down }[i-1]+1), & \text { nums }[i]>\text { nums }[i-1]\end{cases} \\ & \operatorname{down}[i]= \begin{cases}\operatorname{down}[i-1], & \text { nums }[i] \geq \text { nums }[i-1] \\ \max (u p[i-1]+1, \text { down }[i-1]), & \text { nums }[i]<\text { nums }[i-1]\end{cases} \end{aligned}

仅需要前一个状态来进行转移，所以我们维护两个变量即可。

——官方题解

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 wiggleMaxLength(vector<int>& nums) {
        int numSize = nums.size();
        if (numSize < 2) {
            return numSize;
        }
        vector <int> up(numSize) ;
        vector <int> down(numSize);
        up[0] = down[0] = 1; //长度为 1 的序列，它既是「上升摆动序列」，也是「下降摆动序列」。
        for(int i = 1; i < numSize; i++) {
            if (nums[i] > nums[i-1]) { // 比上一个大
                up[i] = max(up[i-1], down[i-1] + 1); //上摆情况是在“上一元素上摆”和“上一元素下摆的基础上加上这个元素上摆”
                down[i] = down[i-1]; // 加入这个元素不能组成下摆
            }
            else if (nums[i] < nums[i-1]) { // 比上一个元素小，不可能上摆
                down[i] = max(down[i-1], up[i-1] + 1);
                up[i] = up[i-1];
            }
            else { // 相等
                up[i] = up[i-1];
                down[i] = down[i-1];
            }
        }
        return max(up[numSize-1], down[numSize-1]);
    }
};

仅需要前一个状态来进行转移，所以我们维护两个变量即可。每有一个「峰」到「谷」的下降趋势，down 值才会增加，每有一个「谷」到「峰」的上升趋势，up 值才会增加。且过程中 down 与 up 的差的绝对值值恒不大于 1，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int numSize = nums.size();
        if (numSize < 2) {
            return numSize;
        }
        int up = 1, down = 1; //长度为 1 的序列，它既是「上升摆动序列」，也是「下降摆动序列」 之和
        for(int i = 1; i < numSize; i++) {
            if (nums[i] > nums[i-1]) { // 比上一个大
                up =  down + 1); //上摆情况是在“上一元素上摆”和“上一元素下摆的基础上加上这个元素上摆”
            }
            else if (nums[i] < nums[i-1]) { // 比上一个元素小，不可能上摆
                down =  up + 1;
            }
        }
        return max(up, down);
    }
};

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。子数组 是数组中连续的 非空 元素序列。

解法一——贪心

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

注意“连续和”为负数的时候前一个数字一定为负数，所以应该要舍弃。其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。

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 sum = 0;
        int output = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > output) {
                output = sum;
            }
            if (sum <= 0) {
                sum = 0;
            }
        }
        return output;
    }
};

解法二——动态规划

其实和贪心的思路很类似，只是把sum变成了dp数组。但是思路比贪心好想。

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

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

解法一——贪心

其实最终利润是可以分解的，那么本题就很容易了！

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

但是不同的天的是可以叠加的。所以可以一天一天的利润考虑，只要有利润>0就买。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int output = 0;
        int profitDay = 0;
        for (int i = 1; i < prices.size(); i++) {
            profitDay = prices[i] - prices[i-1];           
            if (profitDay > 0) {
                output += profitDay;
            }
        }
        return output;
    }
};

解法二——动态规划

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第ii天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i−1i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第ii天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int> (2));
        dp[0][0] -= prices[0]; // 第0天持有股票目前的利润
        dp[0][1] = 0; // 第0天不持有股票
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]); // 第i-1天有股票不动，或第i-1天没有股票买进
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]); // 第i-1天没有股票不动，或第i-1天有股票卖出
        }
        return dp[prices.size()-1][1];
    }
};

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

**转化为跳跃覆盖范围究竟可不可以覆盖到终点！**每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxIndex = 0;
        int numSize = nums.size();
        for (int i = 0; i <= maxIndex && i < numSize; i++) {
            maxIndex = max(maxIndex, i + nums[i]);
            if (maxIndex >= numSize - 1) {
                return true;
            }
        }
        return false;
    }
};

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

生成到每个位置所需的最少跳跃次数。每个位置的最少跳跃次数是连续的。只要每一次在这个最小跳跃次数覆盖范围内找下一次的覆盖范围即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jump(vector<int>& nums) {
        int minJump = 0; //记录当前位置需要最少几次跳跃到达
        int maxIndex = 0; //记录当前能到达的最远位置
        int premaxIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if(premaxIndex < 0) {
                minJump++;
                premaxIndex = maxIndex - i;
            }
            if (nums[i] + i > maxIndex) { // 可以更新maxIndex
                maxIndex = nums[i] + i;
            }
            premaxIndex--;
            // cout << i << " " << minJump << " " << maxIndex << endl;
        }
        return minJump;
    }
};

1005. K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和

解法一——逻辑复杂的分类讨论

分三种情况：

  • 负数：①负数个数>=k，②负数个数<k
  • 0：有无0
  • 正数

其实0和负数可以统一考虑，当非正数<k时，倒数的那个数字反转剩余次数即可。

先排序，优先反转小的负数，这里考虑的一些情况：

  • 负数或0：k用完没有？用完了那就只能是负数了
  • 正数：k还有没有没用完，只需要考虑模2为1的情况，也就是得翻转一个数的情况，没用完有两种情况
    • 前面有负数，且那个负数绝对值比正数最小的要小，反转最大的负数
    • 前面没有负数了，或者负数绝对值比正数最小的要大，反转最小的正数
  • 还有一个情况，全是负数，那么可能出现出循环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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        bool flagNotPositive = true; //非正数
        int output = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= 0) {
                if (k > 0) {
                    output -= nums[i];
                }
                else {
                    output += nums[i];
                }
                k--;
            }
            else {
                if (flagNotPositive == true) {
                    flagNotPositive = false;
                    if (k > 0 && k % 2 == 1) {
                        if (i > 0 && -nums[i-1] < nums[i] ) {
                            output += 2 * nums[i-1];
                        }
                        else {
                            output -= 2 * nums[i];
                        }
                    }
                }
                output += nums[i];
            }
            // cout << nums[i] << " " << output << endl;
        }
        if (k > 0 && k % 2 == 1 &&  nums[nums.size()-1] < 0) {
            output += 2 * nums[nums.size()-1];
        }
        return output;
    }
};

解法二——贪心

这里思路和我最大的不同就是按照绝对值大小排序。。。能减轻很多负担

  • 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
  • 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
  • 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
  • 第四步：求和

两次贪心：

  • 局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
  • 一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大，全局最优：整个 数组和 达到最大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort (nums.begin(), nums.end(), cmp);
        int output = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 && k-- > 0) {
                nums[i] = - nums[i];
            }
            output += nums[i];
        }
        if (k > 0 && k % 2 == 1) {
            output -= 2 * nums[nums.size()-1]; // 不管最后一个数原本是正负均成立，因为转成正数了
        }
        return output;
    }
};

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

解法一——暴力解法+一点点优化

如果x到达不了y+1，那么x-y之间的点也不可能到达y+1，因为中间任何一点的油都是拥有前面的余量的，所以下次遍历直接从y+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 canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        // if (accumulate(gas.begin(), gas.end(), 0) < accumulate(gas.begin(), gas.end(), 0)) {
        //     return -1;
        // }
        for (int i = 0; i < n; i++) {
            int gasSum = 0;
            int j = 0;
            for (j = 0; j < n; j++) {
                int station = (i + j) % n;
                gasSum = gasSum + gas[station] - cost[station];
                if (gasSum < 0) {
                    // cout << "break" << endl;
                    break;
                }
                // cout <<  station << " " << gasSum << endl;
            }
            if (j == n) { // 说明转完一圈了
                return i;
            }
            else {
                i = i + j;
            }
        }
        return -1;
    }
};

解法二——贪心

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

——代码随想录

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

解法一——两次贪心

两次贪心的策略：

  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candys(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {//从左到右贪心
            if (ratings[i] > ratings[i-1]) {
                candys[i] = candys[i-1] + 1;
            }
        }
        for (int j = ratings.size() - 2; j >= 0; j--) {// 从右往左贪心，注意更新值的时候比较的值要已经更新过了
            if (ratings[j] > ratings[j+1]) {
                candys[j] = max(candys[j] , candys[j+1] + 1);
            }
        }
        return accumulate(candys.begin(), candys.end(), 0);
    }
};

解法二——常数空间遍历

我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre：

  • 如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。
    fig1
  • 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。
    • 我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。
      fig2
    • 同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。
      fig3

我们只要记录当前递减序列的长度 dec，最近的递增序列的长度 inc 和前一个同学分得的糖果数量 pre 即可。

——力扣官方题解

可以同时考虑两边的问题，只是右边的问题通过前面递减序列加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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int pre = 1;
        int dec = 0;
        int inc = 1;
        int output = 1;
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i-1]) {
                dec = 0;
                output += ++pre;
                inc = pre;
            }
            else if (ratings[i] == ratings[i-1]) { //相等=》归一
                dec = 0;
                pre = 1;
                output += pre;
                inc = 1;
            }
            else { //小于
                // cout << " A " << dec << " B " << inc << " ";
                dec ++;
                if (dec == inc) { // 合并入最后一个上升节点
                    dec ++;
                }
                output += dec; //而非pre，因为最新加入的这个元素一定是1，但是递减序列中前面的元素还需要+1
                pre = 1;
            }
            // cout << output << " ";
        }
        return output;
    }
};

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

账单是20的情况，为什么要优先消耗一个10和一个5呢？因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

局部最优：遇到账单20，优先消耗美元10，完成本次找零。

全局最优：完成全部账单的找零。

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 lemonadeChange(vector<int>& bills) {
        int note5 = 0;
        int note10 = 0;
        for (int i = 0; i < bills.size(); i++) {
            if (bills[i] == 5) {
                note5 ++;
            }
            else if (bills[i] == 10) {
                note5 --;
                note10 ++;
                if (note5 < 0) {
                    return false;
                }
            }
            else { // 20 dollar
                if (note10 > 0 && note5 > 0) {
                    note10--;
                    note5--;
                }
                else if (note5 >= 3) {
                    note5 = note5 - 3;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

在按照身高从大到小排序后：

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

解法一——插入用数组

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:
    static bool cmp (vector<int> x, vector<int> y) {
        return x[0] > y[0] || (x[0] == y[0] && x[1] < y [1]);
        // 保证这个元素前面的值比他大或相等
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        int peopleSize = people.size();
        // 先考虑身高，前面的都比他大或者相等，相等的时候k越小越靠前
        sort (people.begin(), people.end(), cmp);
        // for (int i = 0; i < peopleSize; i++) {
        //     cout << "[" << people[i][0] << "," << people[i][1] << "],";
        // }
        // cout << endl;
        // 只需要按照k为下标重新插入队列即可，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点
        vector<vector<int>> Q;
        for (int i = 0; i < peopleSize; i++) {
            Q.insert(Q.begin() + people[i][1], people[i]);
        }

        return Q;
    }
};

解法二——插入用链表

list内部使用链表实现

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:
    static bool cmp (vector<int> x, vector<int> y) {
        return x[0] > y[0] || (x[0] == y[0] && x[1] < y [1]);
        // 保证这个元素前面的值比他大或相等
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        int peopleSize = people.size();
        // 先考虑身高，前面的都比他大或者相等，相等的时候k越小越靠前
        sort (people.begin(), people.end(), cmp);

        // 只需要按照k为下标重新插入队列即可，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点
        list<vector<int>> Q;
        for (int i = 0; i < peopleSize; i++) {
            int position = people[i][1];
            list<vector<int>>::iterator it = Q.begin();
            while (position--) {
                it++;
            }
            Q.insert(it, people[i]);
        }
        return vector<vector<int>> (Q.begin(), Q.end());
    }
};

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

思路就是先排序，先按照start从小到大排序，如果start相等则按照end从小到大排序。

然后遍历每个point，找当前遍历过的所有点里哪个end最小，一旦一个点的start超过了这个最小的end，那就不得不射一箭了。射完箭以后minEnd需要重置。

最后要补射一箭，因为最后一个区间没有射箭呢。

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:
    static bool cmp (vector<int> x, vector<int> y) {
        if (x[0] == y[0]) {return x[1] < y[1];}
        return x[0] < y[0]; // 小的在前
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort (points.begin(), points.end());
        int arrow = 0;
        int minEnd = INT_MAX;
        for (int i = 0; i < points.size(); i++) {
            if (points[i][1] < minEnd) { // 当前的end比之前的end还要小
                minEnd = points[i][1];  
            }
            if (points[i][0] > minEnd) { //start坐标大于之前的最小的end，必须射箭
                arrow++;
                minEnd = points[i][1]; 
            }
        }
        return arrow + 1; // 最后一部分没有射箭
    }
};

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路——排序加哈希表

先按照每个区间的长度排序，区间长度一致按照start从小到大。然后再建立哈希表保存左闭右开区间的元素。

这个思路是错误的，并不是说区间长度越小越不容易造成重叠的。

【反例】万一有这么一组数字[[-100,1],[1,2],[2,3],[3,100],[-3,7]]。按照以上的逻辑会首先排成[[1,2],[2,3],[-3,7],[-100,1],[3,100]]，然后得到的结果应该去除[-100,1],[3,100]这两个，保留以下三个[1,2],[2,3],[-3,7]。然后正确的应该是保留四个[1,2],[2,3],[-100,1],[3,100]，去除一个[-3,7]

想复杂了，其实和452是一样的！！！

解法一——贪心+左边缘

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:
    static bool cmp (const vector<int> &x, const vector<int> &y) {
        // if (x[0] == y[0]) {
        //     return x[1] < y[1];
        // }
        return x[0] < y[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int erase = 0;
        int minEnd = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < minEnd) {
                erase++;
                if (intervals[i][1] < minEnd) {
                    minEnd = intervals[i][1];
                }
            }
            else {//大于之前的区间了，重新计数
                minEnd = intervals[i][1];
            }
        }
        return erase;
    }
};

解法二——贪心+右边缘

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    static bool cmp (const vector<int> &x, const vector<int> &y) {
        // if (x[0] == y[0]) {
        //     return x[1] < y[1];
        // }
        return x[1] < y[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; //非重叠区间至少有一个
        int minEnd = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= minEnd) {
                count++;                
                minEnd = intervals[i][1];
            }
        }
        return intervals.size() - count;
    }
};

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

记录下每个字母出现的end位置，从前往后遍历，当前字母的end位置更加靠后了，更新maxEnd，如果end更前则不用管。当走到maxEnd的时候，分割这个片段。

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> partitionLabels(string s) {
        int alphabet[26] = {0}; // 记录每个字母出现的end位置
        for (int i = 0; i < s.size(); i++) {
            alphabet[s[i] - 'a'] = i;
        }
        int maxEnd = alphabet[s[0] - 'a']; //当前片段目前能够分割的最后位置
        int prevEnd = -1; // 上一次的end（不含）
        vector <int> output;
        for (int i = 0; i < s.size(); i++) {
            if (alphabet[s[i] - 'a'] > maxEnd) {
                maxEnd = alphabet[s[i] - 'a'];
            }
            if (i == maxEnd) {
                output.emplace_back(maxEnd - prevEnd);
                prevEnd = maxEnd;
            }
        }
        return output;
    }
};

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

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:
    static bool cmp (const vector<int> &x, const vector<int> &y){
        return x[0] < y[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort (intervals.begin(), intervals.end(), cmp);
        vector<int> temp(2,0);
        temp[0] = intervals[0][0];//当前区间左边缘
        temp[1] = intervals[0][1];//当前区间右边缘（含）
        vector<vector<int>> output;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > temp[1]) { // 保存上一个区间
                output.emplace_back(temp);
                temp = intervals[i];
            }
            else { // 左边缘小于等于当前右边缘
                temp[1] = max(temp[1], intervals[i][1]);
            }
        }
        output.emplace_back(temp); // 保存最后一个区间
        return output;
    }
};

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

n / 10 * 10 - 1 最后一位必然是9，比别的大或等于，所以可以不考虑最后一位。只考虑前几位即可。

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
class Solution {
public:
    bool isIncreaseingDigits(int n) {
        int prev = n % 10;
        n /= 10;
        while (n != 0) {
            // cout << n%10 << " " << prev <<" ";
            if (n % 10 > prev) {
                return false;
            }
            prev = n % 10;
            n /= 10;
        }
        return true;
    }
    int monotoneIncreasingDigits(int n) {
        if (n < 10 || isIncreaseingDigits(n)) {
            return n;
        }
        int prev = n; // 前缀部分，每次只需要判断前缀是否为单调递增即可，因为最后一位必然是9.
        int divideTime = 0;
        while (!isIncreaseingDigits(prev - 1)) {
            // n / 10 * 10 - 1 最后一位必然是9，比别的大或等于，所以可以不考虑最后一位。
            prev = prev / 10;
            divideTime++;
        }
        while(divideTime != 0){
            prev *= 10;
            divideTime--;
        }

        return prev - 1;
    }
};

代码随想录的方法使用字符串操作。

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

深度优先，后序遍历

两个注意点：

  • 空节点命名为哪个状态，应当是1已经覆盖，因为叶子节点实际上并不需要单独的摄像头
  • 根节点返回0的情况，即根节点还没有摄像头覆盖，需要+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
/**
 * 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:
    int inorder (TreeNode* p, int &numCamera) {  
        // 0: 未覆盖； 1: 已覆盖； 2: 摄像头
        if (p == NULL) {
            return 1;
        }

        int left = inorder(p->left, numCamera);
        int right = inorder(p->right, numCamera);

        if (left == 0 || right == 0) { // 包含00，01，10，02，20
            numCamera++;
            return 2; // 摄像头
        }
        else if (left == 2 || right == 2) { // 包含22，21，12
            return 1; // 已经覆盖
        }
        else { //11
            return 0;
        }

    }
    int minCameraCover(TreeNode* root) {
        int numCamera = 0;
        if (root == nullptr ) {
            return 0;
        }
        if (inorder(root, numCamera) == 0) {
            return numCamera + 1;
        }
        return numCamera;
    }
};

动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

动态规划问题：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
img

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

解法一——直接递推

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 fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int prev0 = 0;
        int prev1 = 1;
        int temp;
        while (n != 1) {
            temp = prev0 + prev1;
            prev0 = prev1;
            prev1 = temp;
            n--;
        }
        return temp;
    }
};

解法二——动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int n) {
        if (n <= 1) {
            return n;
        }
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int dp[46] = {0};
        dp[1] = 1; // 上1楼只有一种方式
        dp[2] = 2; //上2楼有两种方式
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 上到这个楼层有两个方式，一个台阶、两个台阶
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[3] = {0};
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for (int i = 2; i < cost.size(); i++) {
            // 到第二层有两种方式：下标0直接2步上来，下标1一步上来
            dp[2] = min(dp[0], dp[1]) + cost[i];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return min(dp[0], dp[1]);
    }
};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

img

解法一——动态规划硬解

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:
    int uniquePaths(int m, int n) {
        vector<vector<int>> roadMap (m, vector<int> (n,0));
        roadMap[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                else if (j == 0) {
                    roadMap[i][j] = roadMap[i - 1][j];
                }
                else if (i == 0) {
                    roadMap[i][j] = roadMap[i][j - 1];
                }
                else {
                    roadMap[i][j] = roadMap[i - 1][j] + roadMap[i][j - 1];
                }
            }
        }
        return roadMap[m - 1][n - 1];
    }
};

改一下，更简单、更快一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> roadMap (m, vector<int> (n,0));
        roadMap[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    roadMap[i][j] = 1;
                }
                else {
                    roadMap[i][j] = roadMap[i - 1][j] + roadMap[i][j - 1];
                }
            }
        }
        return roadMap[m - 1][n - 1];
    }
};

解法二——数论方法

组合问题

无论怎么走，走到终点都需要 m + n - 2 步，一定有m - 1要往下走，那么就需要Cm+n−2m−1\mathbf C_{m+n-2}^{m-1}​次

Anm=n!(n−m)!Cnm=n!(n−m)!m!\begin{gathered} \mathbf A_n^m=\frac{n!}{(n-m)!}\\ \mathbf C_n^m = \frac{n!}{(n-m)!m!} \end{gathered}

则计算

Cm+n−2m−1=(m+n−2)!(n−1)!(m−1)!=(m+n−2)⋯(n+1)n(m−1)⋯1\mathbf C_{m+n-2}^{m-1} = \frac{(m+n-2)!}{(n-1)!(m-1)!} = \frac{(m+n-2)\cdots(n+1)n}{(m-1)\cdots1} 

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long output = 1;
        for (int numerator = n, denominator = 1; numerator < m + n - 1; numerator++, denominator++ ) {
            output = output * numerator / denominator;
        }
        return output;
    }
};

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。
img

解法一——动态规划

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:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int temp = -1;
        // 初始化 第一行 第一列
        for (int i = 0; i < obstacleGrid.size(); i++) {
            if (obstacleGrid[i][0] == 1) {
                temp = 0;
            }
            obstacleGrid[i][0] = temp;
        }
        temp = -1;
        for (int j = 1; j < obstacleGrid[0].size(); j++) {
            if (obstacleGrid[0][0] == 0 || obstacleGrid[0][j] == 1) {
                temp = 0;
            }
            obstacleGrid[0][j] = temp;
        }
        for (int i = 1; i < obstacleGrid.size(); i++) {
            for (int j = 1; j < obstacleGrid[0].size(); j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                }
                else { // 不需要分类讨论了。障碍和两边都挡住的就是0啊，那加上去也没影响
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
        }
        // for (int i = 0; i < obstacleGrid.size(); i++) {
        //     for (int j = 0; j < obstacleGrid[0].size(); j++) {
        //         cout << obstacleGrid[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return - obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

解法一——数论？技巧？

我们知道正方形面积最大，所以分出来的数字一定比较接近。所以我直接遍历了分n种的情况，每次算当前的成绩比较。

但是这里需要注意，因为不是整除，所以可能需要考虑向上向下取整两种情况。

向下取整的情况最后一个比较好考虑，就是普通的因子+余数。

向上取整的要稍微想一想，是普通的因子+余数-之前i-1个因子每个都多考虑了1。或者利用以下这组关系

(n/i+1)⋅(i−1)+x=(n/i)⋅i+n%i=n(n/i+1)\cdot(i-1)+x = (n/i)\cdot i+ n\%i = n 

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 integerBreak(int n) {
        long long maxNum  = 0;
        for (int i = 2; i <= n; i++) {
            long long prod = 1;
            if (n % i > i - n % i){  // 说明要进位
                int factor = n / i + 1;
                for (int j = 0; j < i - 1; j++) {
                    prod *= factor;
                }
                prod *= n % i + n / i - (i - 1);
            }
            else {
                int factor = n / i;
                for (int j = 0; j < i - 1; j++) {
                    prod *= factor;
                }
                prod *= (factor + n % i);
            }
            if (maxNum < prod) {
                maxNum = prod;
            }
        }
        return maxNum;
    }
};

解法二——动态规划

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

dp[i]最大乘积是怎么得到的呢？其实可以从1遍历j，然后有两种渠道得到dp[i].

  • 一个是j * (i - j) 直接相乘。
  • 一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

注意第一种情况表示i-j不拆；第二种情况会拆分i-j，因为我们保存在数组中的值必定是拆分过的，那么也就没有保存i-j这个本身的值，例如dp[2]=1，但是如果一个数乘上2，反而还要比1大呢。

在遍历过程中会j和i-j的地位是完全对等的，也就是说拆j和拆i-j是完全一致的。

所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
        int dp[59] = {0};
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i/2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

96.不同的二叉搜索树1

当1为头结点的时候，其右子树有两个节点，这两个节点的布局，和n为2的时候两棵树的布局是一样的！

当3为头结点的时候，其左子树有两个节点，这两个节点的布局，和n为2的时候两棵树的布局也是一样的！

当2为头结点的时候，其左右子树都只有一个节点，布局和n为1的时候只有一棵树的布局也是一样的！

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

意思是当有3个元素的时候，1、2、3每个元素都有可能当根节点，而每个元素作为根节点的时候的，左右子树所有有可能的序列类型。

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

——代码随想录

代码中的递推公式使用的是

dp[i]+=dp[j]∗dp[i−j−1],j=0,1,⋯ ,i−1dp[i] +=dp[j]*dp[i-j-1],\quad j = 0,1,\cdots, i-1 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numTrees(int n) {
        int dp[20];
        dp[0] = 1; //为0的子树有一种
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1]; // 左子树从0到i-1个元素，右子树从i-1到0个元素；
            }
        }
        return dp[n];
    }
};
持续更新中

本文标题:【更新中】LeetCode自用刷题记录

文章作者:Levitate_

发布时间:2024年03月29日 - 21:38:44

原始链接:https://levitate-qian.github.io/2024/03/30/LeetCode-problems/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。