AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

代码随想录笔记

作者：AllinToyou | 2024-05-24 19:35:23

踩

代码随想录

算法

数组

二分法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //[l,r)
        int l=0,r = nums.size();
        int mid = (l+r)/2;
         //等号取不到
        while (l<r){
            if (nums[mid] == target) {return mid;}
            //整数除法小数点都舍掉要进一
            else if (nums[mid]<target) {l = mid+1;}
            else {r = mid;}
            mid = (l+r)/2;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

移除元素（双指针）

移除

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
1
2
3

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int l=0,r=0;
        //遍历一次数组
        for (int  &a:nums){
            if (l!=r) {nums[l] = nums[r];}
            //左指针保留，空出位置
            if (a==val) l-=1;
            l++;
            r++;
        }
        return l;
    }
};



class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int sptr=0;
        for (int fptr=0;fptr<nums.size();fptr++){
			//遇到不同sptr加一
            if (nums[fptr]!=val) {nums[sptr++] = nums[fptr];
        }}
        return sptr;
    }
};
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

移动零

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int sptr = 0;
        for (int fptr=0;fptr<nums.size();fptr++){
            if (nums[fptr]!=0){
                int temp =  nums[sptr];
                nums[sptr++] = nums[fptr];
                nums[fptr] = temp;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

有序数组平方

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

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
1
2

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //创建登场数组
        vector<int> v(nums.size(),0);
        int l=0, r=nums.size()-1;
        //从最后元素开始
        for (int k=nums.size()-1;k>-1;k--){
            //比较左端和右端的绝对值
            if (abs(nums[l])<abs(nums[r])){
                v[k] = nums[r]*nums[r];
                r--;
            }
            else {
                v[k]=nums[l]*nums[l];
                l++;
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

长度最小子数组

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1
2
3

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        
        int l=0,len = nums.size()+1, sum=0;
        for (int r=0;r<nums.size();r++){
            //有一个元素大于target则返回1
            if (nums[r]>=target) return 1;
            sum += nums[r];
            //循环知道长度范围内小于target
            while (sum>=target){
                len = (len<=(r-l+1)) ? len:r-l+1;
                sum -= nums[l++];
            }
        }
		//判读累加是否有大于target
        return (len==nums.size()+1) ? 0:len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

旋转矩阵! !

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: 
[ [ 1, 2, 3 ], 
[ 8, 9, 4 ], 
[ 7, 6, 5 ] ]
1
2
3
4
5
6

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> arr(n,vector<int>(n,0));
        //loop循环次数，xy初始值，cnt计数值
        int loop = n/2, x=0,y=0,cnt=1;
        //确定边界
        int sub=1;
        //实际坐标
        int x1,y1;
        for (;loop>0;loop--){
        //sub=1，防止边界溢出
        for (y1=y;y1<n-sub;y1++){
            arr[x][y1] = cnt++;
        }
        for (x1=x;x1<n-sub;x1++){
            arr[x1][y1] = cnt++;
        }
        for (;y1>y;y1--){
            arr[x1][y1] = cnt++;
        }
        for (;x1>x;x1--){
            arr[x1][y1] = cnt++;
        }
        //初始值进一位，边界同理
        x++;y++;
        sub++;}
        //判断是否为奇数，中间格子赋值
        if (n%2) arr[n/2][n/2] = cnt;
    return arr;
    }
};
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

链表

定义

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

移除链表指定元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除目标头结点
        while (head != NULL && head->val==val){
            ListNode *temp = head;
             head = head->next;
             delete temp;
        }
        //other
        ListNode *cur = head;
        while (cur != NULL && cur->next != NULL){
            if (cur->next->val==val){
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
            }
            //一定要加else，避免连续出现目标值
            else {cur = cur->next;}

        }
        return head;
    }
};

//建立虚拟头节点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *virhead = new ListNode(0);
        //将虚拟头结点指向head，这样方面后面做删除操作
        virhead->next = head;
        ListNode *cur = virhead;
        while(cur->next != NULL){
            if (cur->next->val == val){
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
            }
            else {cur = cur->next;}

        }
        //重新赋值头节点
        head = virhead->next; 
        delete virhead;
        return head;
    }
};
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 MyLinkedList {
public:
    //定义节点
    struct LinkeNode{
        int val;
        LinkeNode* next;
        //节点初始化，next指向nullptr
        LinkeNode(int val=0): val(val), next(nullptr){}
    };
    //初始化函数，便于后面操作
    MyLinkedList() {
        _size = 0;
        //虚拟头节点，方便后续操作统一
        _dummyhead = new LinkeNode(0);
    }
    
    int get(int index) {
        //无效下标
        if (index>_size-1 || index<0){
            return -1;
        }
        LinkeNode*cur = _dummyhead->next;
        while (index--){
            cur = cur->next;
        }

        return cur->val;
    }
    //添加头节点
    void addAtHead(int val) {
        
        LinkeNode* add = new LinkeNode(val);
        add->next = _dummyhead->next;
        _dummyhead->next = add;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkeNode* add = new LinkeNode(val);
        LinkeNode* cur = _dummyhead;
        int i = _size;
        //不能用_size--,会让长度清零
        while(i--){
            cur = cur->next;
        }
        cur->next = add;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index<0 || index>_size){
            return;
        }
        LinkeNode* add = new LinkeNode(val);
        LinkeNode* cur = _dummyhead;
        while(index--){
            cur = cur->next;
        }
        add->next = cur->next;
        cur->next = add;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if (index<0 ||index>_size-1)
        {return;}
        LinkeNode*cur = _dummyhead;
        while(index--){
            cur = cur->next;
        }
        LinkeNode* sub = cur->next;
        cur->next = sub->next;
        //记得释放
        delete sub;
        //delete命令指示释放了sub指针原本所指的那部分内存，
        //被delete后的指针sub的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句sub=nullptr,sub会成为乱指的野指针
        //如果之后的程序不小心使用了sub，会指向难以预想的内存空间
        sub=nullptr;
        _size--;
    }

private:
    //定义数据
    int _size;
    LinkeNode* _dummyhead;
};


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

翻转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //当前链表
        ListNode* cur = head;
        //前列表
        ListNode* pre = nullptr;
        //憨批列表
        ListNode* temp;
        //翻转一次操作
        while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
        }
        head = pre;
        return head;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

两两交换节点

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


//不设置虚拟头节点来交换每两个节点中的链接会很复杂
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //创建虚拟头节点指向头节点
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        //当前变量值
        ListNode* cur = dummyhead;
        //定义临时值
        ListNode* temp;
        //cur->next->next需确保cur->next存在先
        while (cur->next != nullptr&& cur->next->next != nullptr){
            temp = cur->next;
            cur->next = cur->next->next;
            temp->next = cur->next->next;
            cur->next->next = temp;
            cur = cur->next->next;   
        }
        return dummyhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

删除倒数第n个结点

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead = new ListNode(0);
            dummyhead->next = head;
        	//双指针，快指针检测终点，慢指针做删除动作
            ListNode * fptr=dummyhead, *sptr=dummyhead;
        	//快指针提前走n步
            for (int i=0;i<n;i++){
                fptr = fptr->next;
            }
        //检测终点
            while (fptr->next != nullptr){
                fptr = fptr->next;
                sptr = sptr->next;
            }
        //删除操作
            ListNode* temp = sptr->next;
            sptr->next = temp->next;
            delete temp;
            return dummyhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

链表相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //计算长度，确定起点
        int lena=0, lenb=0;
         ListNode*cur = headA;
        
         while (cur != nullptr){
            lena++;
            cur = cur->next;
         }
         cur = headB;
         while (cur != nullptr){
            lenb++;
            cur = cur->next;
         }
        //确保heada为长节点
         if (lenb>lena){  
            swap(lena, lenb);
            swap(headA, headB);
         }
         ListNode* cura = headA;
        //长节点开头对其短节点
         for (int sub = lena-lenb;sub>0;sub--){
            cura = cura->next;
         }
        cur = headB;
         while(cura != nullptr){
             if (cur==cura){
                 return cur;
             }
             cur = cur->next;
             cura = cura->next;
             
         }
         return 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

环形链表！！

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

相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

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

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

//引用代码随想录

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fptr = head, *sptr = head;
        while (fptr != NULL && fptr->next != NULL){
            fptr = fptr->next->next;
            sptr = sptr->next;
			// 一快一慢，若相遇则有环
            if (fptr==sptr){
                //根据数学公式推导，与头节点相遇即为入口
                while (head!=sptr){
                    head = head->next;
                    sptr = sptr->next;
                }
                return sptr;
            }

        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

哈希表

 int hash[26] = {0};//数组，长度确定时使用
unordered_set<int> result_set;//无序集合，自动去重
unordered_map<int,int> hash_table; hash_table[key] = val;//python字典，
1
2
3

相同字母字符串

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
1
2
3
4
5

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size()!=t.size()) return false;
        int hash[26] = {0};
        //记录每个字母出现的次数
        for (int i=0;i<s.size();i++){
            hash[s[i]-'a']++;
        }
        //字母出现负数就为false，相同则减1
        for (int i=0;i<t.size();i++){
            if (hash[t[i]-'a']==0) return false;
            else
            hash[t[i]-'a']--;
        }
        //若不全为零则字母不相同
        for (int i=0;i<26;i++){
            if (hash[i]!=0) return false;
        }
    return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

求数组交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
1
2
3
4

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //创建hash表，无序无重复；
        unordered_set<int> result_set;
		//nums1求集合，去重
        unordered_set<int> nums_set(nums1.begin(),nums1.end());
        for (int n:nums2){
            if (nums_set.find(n)!=nums_set.end()){
                //unordered_ser自动去重
                result_set.insert(n);
            }
        }
        return vector<int> (result_set.begin(),result_set.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求快乐数

快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：输入：n = 19      输出：true
解释：
12 + 92 = 82
=82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    //依次求位数上的平方和
    int ret(int n){
        int num=0;
        int a;
        while (n>=1){
            a = n%10;
            num+=a*a;
            n/=10;
        }
        return num;
    }
    bool isHappy(int n) {
        unordered_set<int> hash_set;
        while ((n=ret(n))!=1){
            //如果不存在就插入
            if (hash_set.find(n)==hash_set.end()){
                hash_set.insert(n);
            }
            //存在说明陷入循环
            else return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

两数之和

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //创建map，便于值键对应
        unordered_map<int,int> hash_table;
        for (int i=0;i<nums.size();i++){
            auto iter = hash_table.find(target-nums[i]);
            if (iter != hash_table.end()){
                //如果找到缺少的数的下标就放回
                return {iter->second,i};
            }
            //没有则放入
            hash_table[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四数之和

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6

//利用哈希表存值，使时间复杂度缩短2个指数
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int>map;
        //map：key记录a+b，val记录count（a+b）
        for (int a:nums1){
            for (int b:nums2){
                map[a+b]++;
            }
        }
        int cnt = 0;
        //如果c+d+a+b则cnt加一
        for (int c:nums3){
            for (int d:nums4){
                if (map.find(0-(c+d)) != map.end()){
                    cnt += map[0-c-d];
                }
            }
        }
        return cnt;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

找字符串

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
1
2
3
4
5
6

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int arr[26]={0};
        //出现在rans中就加一
        for (auto &s:ransomNote){
            arr[s-'a']++;
        }
        //出现在maga中则对应值减一
        for (auto &s:magazine){
            arr[s-'a']--;
        }
        for (int i:arr){
            //存在大于零的则说明rans中有字符没被maga抵消
            if (i>0) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三数之和！！

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
1
2
3
4
5
6

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> arr;
        //排序，确定指针方向
        sort(nums.begin(),nums.end());
        //左右指针
        int l,r;
        int sum;
        for (int i=0;i<nums.size()-2;i++){
            //后面都比零大，不可能为零
            if (nums[i]>0) break;
            //去重重复元素
            if (i>0 &&nums[i]==nums[i-1]) continue;
            l = i+1;
            r = nums.size()-1;

            while (l<r){
                sum = nums[i]+nums[l]+nums[r];
            if (sum==0){
                arr.push_back(vector<int>{nums[i],nums[l],nums[r]});
                //去除相同的值
                while(l<r && nums[l]==nums[l+1]) l++;
                while(l<r && nums[r]==nums[r-1]) r--;
                //指针各自更新
                l++;r--;
                }
            else if (sum>0){
                r--;
            }
            else l++;
        }
        }
    return arr;
    }
};
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

四数之和

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

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> arr;
       	//双指针使用前要排序
        sort(nums.begin(), nums.end());
        int n=nums.size();
        int l,r;
        //注意长度
        long sum;
        for (int i=0;i<n-3;i++){
            //后面都大于等于零则总和无法减小
            if (nums[i]>target && nums[i]>=0) break;
            //避免重复操作
            if (i>0 && nums[i]==nums[i-1]) continue;
            for (int j=i+1;j<n-2;j++){
                if (nums[i]+nums[j]>target && nums[j]>=0) break;
                //注意，j要大于i+1才有效
                if (j>i+1 && nums[j]==nums[j-1]) continue;
                l=j+1;r=n-1;
                while (l<r){
                    //强制转换
                    sum = (long) nums[i]+nums[j]+nums[l]+nums[r];
                    if (sum==target){
                        arr.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]});
                        //过滤掉重复的
                        while (l<r && nums[l+1]==nums[l]) l++;
                        while (l<r && nums[r-1]==nums[r]) r--;
                        //l，r各自更新
                        l++;r--;
                    }
                    else if (sum<target) l++;
                    else r--;
                }
            }
        }
        return arr;

    }
};
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:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int temp;
        //对称交换
        for (int l = s.size()/2;l>0;l--){
            temp = s[l-1]; 
            s[l-1]=s[n-l];
            s[n-l] = temp;
        }
    }
};


class Solution {
public:
    void reverseString(vector<char>& s) {
        //双链表交换，减少运算
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

反转字符串 ||

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
1
2
3
4
5
6

class Solution {
public:
    
    //定义反转函数
    void reverse(string& s, int start, int end){
            for (;start<(start+end+1)/2;start++,end--){
                swap(s[start], s[end]);
            }
        }
    string reverseStr(string s, int k) {
        
        int i=0;
        //判断是否能够完成，每隔 2k 个字符的前 k 个字符进行反转
        for (;i+2*k<s.size();i+=(2*k)){
            reverse(s,i,i+k-1);
        }
		//判断剩余数量的字符是否到达K
        if (i+k-1<s.size()-1){
            reverse(s,i,i+k-1);
        }
        //不到达则全部反转
        else{
            reverse(s,i,s.size()-1);
        }
    return s;
    }
};
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

反转字符串中的单词

输入：s = "the sky is blue"  输入：s = "    the       sky   is blue     "
输出："blue is sky the"      输出："blue is sky the"
1
2

class Solution {
public:
    //定义反转函数
    void reserve(string &s, int start, int end){
        for (;start<(start+end+1)/2;start++,end--){
            swap(s[start],s[end]);
        }
    }
    string reverseWords(string s) {
        int sptr=0,fptr=0;
        //过滤前面的空格
        while (s[fptr]==' ') fptr++;
        //替换中间的空格
        for (;fptr<s.size();fptr++){
            if (s[fptr]!=' '){
                s[sptr++] = s[fptr];
            }
            else{
                if (s[fptr-1]!=' ')
                    s[sptr++] = s[fptr];
                
            }
        }
        //如果后面有空格就替换掉
        if (s[sptr-1]==' ') s.resize(sptr-1);
        //没有就直接截掉后面空间
        else s.resize(sptr);
        //全部反转
        reserve(s,0,s.size()-1);
        sptr = 0;fptr=0;
        for (;fptr<s.size();fptr++){
            if (s[fptr]==' '){
                //每个单词反转
                reserve(s, sptr, fptr-1);
                sptr=fptr+1;
            }
        }
        //最后一个单词反转
        reserve(s,sptr,fptr-1);
    return s;
    }
};
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

字符串左旋

输入: password = "s3cur1tyC0d3", target = 4
输出: "r1tyC0d3s3cu"
1
2

class Solution {
public:
    //定义反转函数
    void reverse(string& s, int start, int end){
        for (;start<(start+end+1)/2;start++,end--){
            swap(s[start], s[end]);
        }
    }
    string dynamicPassword(string password, int target) {
        int n = password.size();
        //全部反转
        reverse(password,0,n-1);
        //以target为界分别反转
        reverse(password,0,n-target-1);
        reverse(password,n-target,n-1);
        return password;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

KMP算法!!

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

前缀表

//计算s中的前后缀相同字符串的长度 （aabaa）（01012）
void getNext(int *next, string s){
    int j=0; next[0]=0;
    for (int i=1;i<s.size();i++){
        //如果不同则依次寻找相同前缀，直到j为0
        while (j>0&&s[j]!=s[i]){
            j = next[j-1];
        }
        //如果相等则前缀加一
        if (s[j]==s[i]){
            j++;
        }
        //j既可以表示长度，也可以表示相同前缀的后一字符
        next[i]=j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

具体比较

int strStr(string haystack, string needle) {
        if (needle.size()==0) return 0;
        int next[needle.size()];
    	//得到前缀表
        getNext(next, needle);
        int j=0;
    	//遍历数组
        for (int i=0;i<haystack.size();i++){
            //如果不同，这返回到j-1下标相同前缀的后一字符进行比较，直到j为0
            while (j>0&&haystack[i]!=needle[j]){
                j = next[j-1];
            }
			//相同这needle下标加1
            if (haystack[i]==needle[j]){

                j++;
            }
            //退出条件
            if (j==needle.size()) {
                return (i-needle.size()+1);}
        }
        return -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

判断是否为重复字符串

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
1
2
3

原理

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

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

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

class Solution {
public:
    //运用kmp算法，数组长度减去最长相同前后缀
    void getNext(int *next, string s){
        int j=0;next[0]=0;
        for (int i=1;i<s.size();i++){
            while (j>0&&s[j]!=s[i]){
                j = next[j-1];
            }

            if (s[j]==s[i]){
                j++;
            }
            next[i] = j;
        }

    }
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        if (n==1) return false;
        int next[n];
        getNext(next,s);
        //next[n-1]不能为零
        if (next[n-1]!=0 && n%(n-next[n-1])==0) return true;
        return 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

栈与队列

栈实现队列

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

class MyQueue {
public:
    MyQueue() {

    }
    //定义进栈和出栈
    stack<int> stIn, stOut;
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        //如何出栈为空，则进栈依次进入出栈
        if (stOut.empty()){
            while (!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    int peek() {
        int top = this->pop();
        //模拟的队列，记得加回出栈
        stOut.push(top);
        return top;
    }
    
    bool empty() {
        //同时空是为空
        return (stIn.empty() && stOut.empty());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

队列实现栈

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

//两个队列，一个复制拷贝
class MyStack {
public:
    MyStack() {

    }

    queue<int> que1,que2;

    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size = que1.size();
        //留下一个元素，que2复制que1
        while (--size){
            que2.push(que1.front());
            que1.pop();
        }
        int result = que1.front();
        que1 = que2;
        while (!que2.empty()) que2.pop();
        return result;
    }
    //栈的top对应队列的末尾
    int top() {
        return que1.back();
    }
    
    bool empty() {
        return que1.empty();
    }
};



class MyStack {
public:
    MyStack() {

    }
    queue<int> que;
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        //出队的队列再次进队
        while (--size){
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
输入：s = "()[]{}"        输入：s = "(]"
输出：true				  输出：false
1
2
3

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        //如果为奇数这错误
        if (s.size()%2 == 1) return false;
        for(int i=0;i<s.size();i++){
            //右括号添加对应的左括号，方便消除
            if (s[i]=='{') {st.push('}');}
            else if (s[i]=='('){ st.push(')');}
            else if (s[i]=='['){ st.push(']');}
            //如果添加左括号找不到对应的或者为空则错误
            else if (st.empty() || st.top()!=s[i]) return false;
            else st.pop();
        }
        if (st.empty()) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

输入："abbaca"
输出："ca"
1
2

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        //不同就进入
        for (char a:s){
            if (st.empty()||st.top()!=a){
                st.push(a);
            }
            //相同则抵消
            else{
                st.pop();
            }
        }
        string result;
        while (!st.empty()){
            result += st.top();
            st.pop();
        }
        //记得倒叙
        reverse(result.begin(),result.end());
        return result;
    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        //直接用字符串操作
        for (char a:s){
            if (result.empty()||result.back()!=a){
                result.push_back(a);
            }
            else result.pop_back();
        }
        return result;
    }
};
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

逆波兰表达式求值

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
1
2
3

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long>st;
        for (int i=0;i<tokens.size();i++){
            if (tokens[i]=="*"||tokens[i]=="-"||tokens[i]=="+"||tokens[i]=="/"){
                //取出右边两个元素
                long long num2 = st.top();
                st.pop();
                long long num1 = st.top();
                st.pop();
                //加入结果
                if (tokens[i]=="+") {st.push(num1+num2);}
                else if (tokens[i]=="-") {st.push(num1-num2);}
                else if (tokens[i]=="*") {st.push(num1*num2);}
                else if (tokens[i]=="/") {st.push(num1/num2);}
            }
            else {
                //数字直接进入
                st.push(stoll(tokens[i]));
            }
        }
        //返回栈顶元素
    return st.top();
    }
};
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

滑动列表最大值

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
1
2

class Solution {
private:
    //定义单调递减队列
    class MyQueue{
        public:
        deque<int> que;
        void pop(int val){
            //相等则排出
            if (!que.empty()&&que.front()==val){
                que.pop_front();
            }
        }
        
        void push(int val){
            //若前面元素小于val，则前面元素排出
            while(!que.empty()&&que.back()<val){
                que.pop_back();
            }
            que.push_back(val);
        }

        int top(){
            return que.front();
        }

    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> arr;
        MyQueue que;
        //确保最大值为front
        for (int i=0;i<k;i++){
            que.push(nums[i]);
        }
        arr.push_back(que.top());
        for (int i=k;i<nums.size();i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            arr.push_back(que.top());
        }
        return arr;
    }
};
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

二叉树

理论基础

类型

满二叉树
完全二叉树

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

二叉搜索树
平衡二叉搜索树

存储
1. 链表
2. 数组

遍历方式

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

类定义

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

前中后序遍历（深度）

递归

//前序
void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;//确定遍历终止条件
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
//中序
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}
//后序
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}
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> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        st.push(root);
        TreeNode* cur;
        //中右左放入，先进后出
        while (!st.empty()){
            cur = st.top();
            st.pop();
            if (cur==nullptr) continue;
            result.push_back(cur->val);
            if (cur->right) st.push(cur->right);//右
            if (cur->left) st.push(cur->left);//左
        }
        return result;
    }
};
//中序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        while (cur!=nullptr || !st.empty()){
            //一直向左下迭代
            if (cur!=nullptr){
                st.push(cur);
                cur = cur->left;
            }
            //没有左节点则中节点添加到result中，再向右节点判断
            else{
                cur = st.top();
                result.push_back(cur->val);
                st.pop();
                cur = cur->right;
            }

        }
        return result;
    }
};
//后序
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        st.push(cur);
        //中  左右放入
        while(!st.empty()){
            cur = st.top();
            st.pop();
            if (cur==nullptr) continue;
            result.push_back(cur->val);
            //先进后出
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
        //反转则成为左右中
        reverse(result.begin(), result.end());
        return result;
    }
};
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

层序遍历（宽度）

//迭代
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> result;
       queue<TreeNode*> que;
       TreeNode*cur=root; 
       if (root) que.push(root);
        //队列
        while (!que.empty()){
            int size = que.size();
            vector<int> vec;
            //每层循环
            for (int i=0; i<size;i++){
                cur = que.front();
                que.pop();
                vec.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(vec);
        }
    return result;
    }
};

//递归
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int deepth){
        if (!cur) return;
        //不存在则初始化
        if (result.size()==deepth) result.push_back(vector<int>());
        result[deepth].push_back(cur->val);
        //递归
        if (cur->left) order(cur->left,result,deepth+1);
        if (cur->right) order(cur->right, result, deepth+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        //deepth作为层数标记
        order(root, result, 0);
        return result;
    }
};
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 Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        if (left==nullptr&& right==nullptr) return true;
        else if (left==nullptr&&right!=nullptr) return false;
        else if (left!=nullptr&&right==nullptr) return false;
        else if (left->val!=right->val) return false;
		//外层和内层是否都为1
        return (compare(left->left, right->right)&& compare(left->right, right->left));

    }
    bool isSymmetric(TreeNode* root) {
        if (root==nullptr) return true;
        return compare(root->left, root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求二叉树深度

class Solution {
public:
    int getdepth(TreeNode* node){
        if (node==nullptr) return 0;
     	//节点数加一
        return 1+max(getdepth(node->left), getdepth(node->right));
    }
    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11

求二叉树节点数

//通用
class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == NULL) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        //累加
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

//求完全二叉树
class Solution {
public:
    int cntnode(TreeNode* node){
        if (node==nullptr) return 0;
        int left=0,right=0;
        TreeNode*leftn = node->left;
        TreeNode*rightn = node->right;
        //完全二叉树中子树若为满二叉树则最右和最左深度抑制
        while (leftn){
            left++;
            leftn=leftn->left;
        }
        while (rightn){
            right++;
            rightn=rightn->right;
        }
        //相等则说明是完全二叉树，2*2**left-1
        if (left==right) return (2<<left)-1;
        //不等则左右节点相加
        else return 1+cntnode(node->left)+cntnode(node->right);
    }
    int countNodes(TreeNode* root) {
        return cntnode(root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

判断平衡二叉树

class Solution {
public:
    int getdepth(TreeNode* node){
        if (node==nullptr) return 0;
        //左右节点有一个为-1则为-1，每个节点都要判断
        int leftdepth = getdepth(node->left);
        if (leftdepth==-1) return -1;
        int rightdepth = getdepth(node->right);
        if (rightdepth==-1) return -1;
		//若大于一则不是平衡节点，返回-1，否则返回长度
        return (abs(leftdepth-rightdepth)>1) ?-1:1+max(leftdepth, rightdepth);
    }
    bool isBalanced(TreeNode* root) {
        return getdepth(root)==-1?false:true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树所有路径

class Solution {
public:
    vector<string> result;
    //递归函数
    void getpath(TreeNode*node, string path){
        //若为叶节点则将path加入result
        if (!node->left&&!node->right){
            result.push_back(path);
            return;
        }
        //左右节点有一个存在有则可以继续递归
        if (node->left)
        getpath(node->left, path+"->"+to_string(node->left->val));
        if (node->right)
        getpath(node->right, path+"->"+to_string(node->right->val));
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        getpath(root,to_string(root->val));
        return result;
    }
};
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 sum=0;
    
    void get_left(TreeNode* node, int is_left){
        if (node->left==nullptr&&node->right==nullptr){
            //若if_left为1则加入sum
            if (is_left) sum+=node->val;
            return;
        }
        //左节点标记为1
        if (node->left) get_left(node->left, 1);
        if (node->right) get_left(node->right, 0);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root==nullptr) return 0;
        //根节点不标记
        get_left(root,0);
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

找树左下角的值

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

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int result;
        queue<TreeNode*> que;
        que.push(root);
        //层序遍历
        while (!que.empty()){
            int size = que.size();
            //第一个就是每层的最左边
            result=que.front()->val;
            TreeNode*cur;
            for (int i=0;i<size;i++){
                cur=que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }   
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
1
2

class Solution {
public:
    bool sumpath(TreeNode*node, int sub){
        if (node==nullptr) return false;
        if (node->left==nullptr&&node->right==nullptr){
            //为叶节点且总和为target
            if (sub-node->val==0) return true;
            return false;
        }
        sub = sub-node->val;
        bool rbool = sumpath(node->right, sub); 
        bool lbool = sumpath(node->left, sub);
        //有一个是TRUE就为true
        return rbool||lbool;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return sumpath(root,targetSum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

后序遍历

给定中序和后序数组，构建树
1

class Solution {
public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
        if (postorder.size()==0) return nullptr;
        //创建根节点
        int root_val = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(root_val);
        //后序只有一个说明是叶节点
        if (postorder.size()==1) return root;
        //更新长度
        postorder.resize(postorder.size()-1);
        int order_index;
        //找到中序中对应的值
        for (order_index=0;order_index<inorder.size();order_index++){
            if (inorder[order_index]==root_val) break;
        }
		//以根节点为中心分开
        vector<int> leftorder(inorder.begin(),inorder.begin()+order_index);
        vector<int> rightorder(inorder.begin()+order_index+1, inorder.end());
		//和中序长度一致即可
        vector<int> leftpost(postorder.begin(),postorder.begin()+order_index);
        vector<int> rightpost(postorder.begin()+order_index,postorder.end());
		//递归
        root->left=traversal(leftorder, leftpost);
        root->right=traversal(rightorder, rightpost);
        return root;

    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal(inorder, postorder);
    }
};
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:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){
        if (preorder.size()==0) return nullptr;
        //前序是数组起点
        int root_val = preorder[0];
        TreeNode* root = new TreeNode(root_val);
        if (preorder.size()==1) return root;
        int inidex;
        for (inidex=0;inidex<inorder.size();inidex++){
            if (inorder[inidex]==root_val) break;
        }
        vector<int> left_in(inorder.begin(),inorder.begin()+inidex);
        vector<int> right_in(inorder.begin()+inidex+1,inorder.end());
        //0下标记得跳过
        vector<int> left_pre(preorder.begin()+1,preorder.begin()+1+inidex);
        vector<int> right_pre(preorder.begin()+inidex+1,preorder.end());
        root->left=traversal(left_pre,left_in);
        root->right=traversal(right_pre,right_in);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return traversal(preorder,inorder);
    }
};
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

最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
1
2
3
4

class Solution {
public:
    TreeNode* traversal(vector<int>& vec){
        int n = vec.size();
        if (n==0) return nullptr;
        int j=0;
        //找出最大值
        for (int i=1;i<n;i++){
            if (vec[j]<vec[i]) j=i;
        }
        TreeNode* root = new TreeNode(vec[j]);
        if (n==1) return root;//叶节点
        //以最大值为分割
        vector<int> left_vec(vec.begin(), vec.begin()+j);
        root->left = traversal(left_vec);
        vector<int> right_vec(vec.begin()+j+1,vec.end());
        root->right = traversal(right_vec);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums);
    }
};
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:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //有一个为空则返回另一个，都为空则返回nullptr
        if (root1==nullptr) return root2;
        if (root2==nullptr) return root1;
        //都不为空，值相加
        TreeNode* root = new TreeNode(root2->val+root1->val);
        //前序遍历
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root2->right, root1->right);
        return root;
    }
};
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==nullptr) return nullptr;
        if (root->val==val) return root;
        //右节点大于根节点
        else if (root->val<val) return searchBST(root->right,val);
        //左节点小于根节点
        else return searchBST(root->left,val);
    }
};
1
2
3
4
5
6
7
8
9
10
11

验证二叉树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
1
2
3
4
5

class Solution {
public:
    //中序遍历
    void insort(TreeNode*cur, vector<int>& arr){
        if (cur==nullptr) return;
        insort(cur->left, arr);
        arr.push_back(cur->val);
        insort(cur->right, arr);
    }

    bool isValidBST(TreeNode* root) {
        vector<int> arr;
        insort(root, arr);
        //若不递增则为FALSE
        for (int i=1;i<arr.size();i++){
            if (arr[i]<=arr[i-1]) return false;
        }
        return true;
    }
};

//second
//递归中序
class Solution {
public:
    long long maxval = LONG_MIN;//从左到右记录最大值
    bool isValidBST(TreeNode* root) {
        if (root==nullptr) return true;//终止条件
        //左中右
        bool left = isValidBST(root->left);
        if (maxval<root->val) maxval=root->val;//若左边比右边大则返回false
        else return false;
        bool right = isValidBST(root->right);
        return left&&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
32
33
34
35
36

二叉树中的众数

class Solution {
public:
    //中序遍历
    void invec(TreeNode* node, vector<int>& vec){
        if (node==nullptr) return;
        invec(node->left,vec);
        vec.push_back(node->val);
        invec(node->right,vec);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> vec;
        invec(root, vec);
        int max_time = 1;
        int cur_time = 1;
        vector<int> result;
        //遍历vec，出现不同就更新上一元素的出现评率，若为最大则更新最大值，并清零数组再添加元素
        for (int i=1;i<vec.size();i++){
            if (vec[i]==vec[i-1]) {
                cur_time++;
            }
            else {
                if (cur_time>max_time){
                    result.clear();
                    result.push_back(vec[i-1]);
                    max_time=cur_time;
                    
                }
                else if (cur_time==max_time){
                    result.push_back(vec[i-1]);   
                }
            cur_time=1;
            }
        }
        //注意，数组末端元素要独立判断一次
        if (cur_time>max_time){
            result.clear();
            result.push_back(vec[vec.size()-1]);
        }
        else if (cur_time==max_time) result.push_back(vec[vec.size()-1]);
    return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //最先出现目标节点向上移动
        if (root==p||root==q||root==NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p,q);
        TreeNode* right = lowestCommonAncestor(root->right, p,q);
        //都不为空说明目标节点在左右子树，返回根节点
        if (left!=NULL&&right!=NULL) return root;
        //有一个为空则说明两个目标节点都在另一个子树上
        else if (left==NULL&&right!=NULL) return right;
        else if (left!=NULL&&right==NULL) return left;
        else return NULL;
    }
};
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){
            //都大于则祖先在左边
            TreeNode* left = lowestCommonAncestor(root->left, p,q);
            if (left!=NULL) return left;
        }
        都小于祖先在右边
        if (root->val<p->val&&root->val<q->val){
            TreeNode* right = lowestCommonAncestor(root->right,p,q);
            if (right!=NULL) return 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:
    void insert(TreeNode* node, int val){
        //节点存在就递归下去，不存在就直接添加新节点
        if (val>node->val){
            if (node->right==nullptr)
            {node->right = new TreeNode(val);
            }
            else insert(node->right, val);
            return;
        }
        if (val<node->val){
            if (node->left==nullptr)
            {node->left = new TreeNode(val);
            return;}
            else insert(node->left,val);
            return;
        }

    }
        
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        //为空就创建一个树
        if (root==nullptr) return new TreeNode(val);
        insert(root,val);
        return root;

    }
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root==nullptr) return new TreeNode(val);
        if (val<root->val) root->left = insertIntoBST(root->left, val);
        if (val>root->val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

删除搜索二叉树节点

class Solution {
public:
    //递归函数
    TreeNode* delete1(TreeNode* node, int key){
        //遍历到空节点就直接返回
        if (node==nullptr) return node;
        //找到值就继续删除操作
        if (node->val==key){
            //左右有一个为空另一个直接接上
            if (node->right!=nullptr&&node->left==nullptr){
                TreeNode* ret = node->right;
                delete node;
                return ret;
            }
            if (node->right==nullptr&&node->left!=nullptr){
                TreeNode* ret = node->left;
                delete node;
                return ret;
            }
            //都为空就返回空节点
            if (node->left==nullptr&&node->right==nullptr){
                delete node;
                return nullptr;
            }
            //都不为空就让右节点接到左节点最右下方
            if (node->left!=nullptr&&node->right!=nullptr){
                TreeNode* cur = node->left;
                while (cur->right!=nullptr){
                    cur = cur->right;
                }
                cur->right = node->right;
   				//记得删除操作
                TreeNode* ret = node->left;
                delete node;
                return ret;
            }
        }
        //判断目标节点位置
        else if (node->val>key){
            node->left = delete1(node->left,key);
        }
        else node->right = delete1(node->right,key);
        //返回
        return node;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        root = delete1(root, key);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

修剪二叉树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root==nullptr) return nullptr;
        //小于则递归右节点，直到出现正常的右节点
        if (root->val<low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
        //大于则递归左节点
        if (root->val>high){
            TreeNode* left = trimBST(root->left,low,high);
            return left;
        }
        //没问题就向下递归
        root->left = trimBST(root->left,low,high);
        root->right =  trimBST(root->right, low, high);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

将递增数组转化成二叉树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        //数组只有一个元素直接返回节点
        if (n==1) return new TreeNode(nums[0]);
        //没有元素就返回空
        if (n==0) return nullptr;
        int midd = nums[n/2];
        //以中间元素作为头节点可以确保左右子树节点数最大相差1，是平衡二叉树
        TreeNode* root=new TreeNode(midd);
        //引用需要创建变量
        //以中间节点为界左右分开
        vector<int> left_nums(nums.begin(),nums.begin()+n/2);
        root->left = sortedArrayToBST(left_nums);
        vector<int> right_nums(nums.begin()+n/2+1,nums.end());
        root->right = sortedArrayToBST(right_nums);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树转化成累加树

class Solution {
public:
    int sum=0;
    //递归，右中左遍历
    void changeVal(TreeNode* node){
        if (node==nullptr) return;
        changeVal(node->right);
        sum+=node->val;
        node->val= sum;
        changeVal(node->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        changeVal(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

回溯

组合问题

输入：n = 4, k = 2                          输入：n = 1, k = 1
输出：                                       输出：[[1]]
[ [2,4],                  
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4], ]
1
2
3
4
5
6
7
8

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    //回溯函数
    void backtrack(int n, int k, int start){
        //终止条件
        if (path.size()==k){
            result.push_back(path);
            return;
        }
        //for (int i=start;i<=n-(k-path.size())+1;i++)  优化（例如当k=4，n=4时，若start=2，则不可能完成4个元素）
        for (int i=start;i<=n;i++){
            path.push_back(i);
            backtrack(n,k,i+1);
            //回溯
            path.pop_back();
        }

    }
    vector<vector<int>> combine(int n, int k) {
        backtrack(n,k,1);
        return result;
    }
};
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

组合累和

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
1
2
3
4
5
6

class Solution {
public:
    vector<int> path;
    vector<vector<int>> resulr;
    void backstrack(int k, int sub, int start){
        //若小于零说明累加已经大于目标值了
        if (sub<0) return;
        //等于则返回
        if (k==path.size()){
            //目标值
            if (sub==0)
                resulr.push_back(path);
            return;
        }
        //起点不能大于剩余值
        int top = 9<sub?9:sub; 
        //保留空余位置
        for (;start<=top-(k-path.size())+1;start++){
            path.push_back(start);
            backstrack(k, sub-start, start+1);
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backstrack(k,n,1);
        return resulr;
    }
};
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<string> result;
    string path;
    const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};
    void backstrack(string digits, int index, int k){
        int num = digits[index]-'0';//string转出int
        //终止条件
        if (path.size()==k) {
            result.push_back(path);
            return;}
        for (int i=0;i<letterMap[num].size();i++){
            path.push_back(letterMap[num][i]);
            backstrack(digits, index+1, k);
            path.pop_back();//回溯
        }

    }
    vector<string> letterCombinations(string digits) {
        if (digits.size()==0) return result;
        backstrack(digits, 0, digits.size());
        return result;
    }
};
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

数组组合（可重复）

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
1
2

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtrack(vector<int> target, int index,int sub){
        if (sub==0){ result.push_back(path); return;
        }
        //sub-target[i]>=0剪枝
        for (int i=index;i<target.size()&&sub-target[i]>=0;i++){
            path.push_back(target[i]);
            //继续从i开始
            backtrack(target, i,sub-target[i]);
            path.pop_back();
        }
        

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //从小到大排序，若加上candidates[i]已经超过target了，后面就不用进行了
        sort(candidates.begin(),candidates.end());
        backtrack(candidates, 0,target);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

数组组合（可重复）||

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

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtrack(vector<int>& vec, int i,int sub){
        if (sub==0){
            result.push_back(path);
            return;
        }
        for (int index = i;index<vec.size()&&sub-vec[index]>=0;index++){
            //避免出现重复的组合
            if (index>i&&vec[index]==vec[index-1]) continue;
            path.push_back(vec[index]);
            backtrack(vec,index+1,sub-vec[index]);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //排序，方便剪枝
        sort(candidates.begin(),candidates.end());
        backtrack(candidates, 0,target);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

分割回文字符串

输入：s = "aab"  			            输入：s = "a"						                  输出：[["a","a","b"],["aa","b"]]        输出：[["a"]]
1

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;
    //判断是否是回文字符串
    bool is_s(string s){
        for (int i=0,j=s.size()-1;i<(s.size()/2);i++,j--){
            if (s[i]!=s[j]) return false;
        }
        return true;
    }
    void dfs(string s){
        int n = s.size();
        if (n==0){
            result.push_back(path);
            return;
        }
        //从首字符开始判断前缀是否为回文，是则递归下去
        for (int i=1;i<=n;i++){
            if (is_s(string(s.begin(),s.begin()+i))){
                path.push_back(string(s.begin(),s.begin()+i));
                dfs(string(s.begin()+i,s.end()));
                path.pop_back();
            }
        }

    }
    vector<vector<string>> partition(string s) {
        dfs(s);
        return result;
    }
};
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

复原ip地址

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1：                                            示例 2：
输入：s = "25525511135"                             输入：s = "0000"
输出：["255.255.11.135","255.255.111.35"]           输出：["0.0.0.0"]                         
1
2
3
4

class Solution {
public:
    vector<string> result;//返回值
    string path;//记录字符串
    void dfs(string& s, int start, int depth){
        //如果下标大于
        if (start>s.size()) return;
        //说明分割了4份了
        if (depth==4){
            //遍历完全了
            if (start==s.size()){
                //记得删掉后面小数点
                path.erase(path.end()-1);
                result.push_back(path);
                //加上，统一操作
                path+='.';    
            }
        return;
        }
        int n = s.size()-start;
        //剪枝。每份最小一个数字，最大三个数字
        if (n<(4-depth)||n>3*(4-depth)) return;
        
        if (start<s.size()&& s[start]=='0'){
            //不能用下标索引
            path+="0.";
            dfs(s,start+1,depth+1);
            //删除加上小数点
            path.erase(path.end()-2,path.end());
            return;
        }
        int i=1;
        for (;i<3;i++){
            if (start+i>s.size()) return;
            string pathone(s.begin()+start,s.begin()+start+i);
            path+=pathone+'.';
            dfs(s,start+i,depth+1);
            path.erase(path.end()-i-1,path.end());
        }
        //三位数数字才可能大于255
        if (start+i>s.size()) return;
        string pathone(s.begin()+start,s.begin()+start+i);
        if (stoi(pathone)<=255){
            path+=pathone+'.';
            dfs(s,start+i,depth+1);
            path.erase(path.end()-i-1,path.end());
        }
    }
    vector<string> restoreIpAddresses(string s) {
        dfs(s,0,0);
        return result;
    }
};
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

求子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
1
2
3

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& vec, int start){
        //加上空集
        result.push_back(path);
        for (;start<vec.size();start++){
        //每次长度减一，元素不重复取
        path.push_back(vec[start]);
        dfs(vec, start+1);
        path.pop_back();}
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

求子集||

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
1
2
3
4
5

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums, int start){
        result.push_back(path);
        for (int i=start;i<nums.size();i++){
            //多加一个判断即可
            if (i>start&&nums[i]==nums[i-1]) continue;
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //排序，确保重复元素相邻
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
1
2
3
4

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    //判断是否为递增数列
    bool is_add(vector<int>& nums){
        for (int i=1;i<nums.size();i++){
            if (nums[i-1]>nums[i]) return false;
        }
        return true;
    }
    void dfs(vector<int>& nums, int start){
        //剪枝，不是递增直接返回
        if (!is_add(path)) return;
        if (path.size()>1) result.push_back(path);
        //记录该层出现的元素
        unordered_set<int> used;
        for (int i=start;i<nums.size();i++){
            //防止重复元素出现
            if (used.find(nums[i])!=used.end())continue;
            used.insert(nums[i]);
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(nums,0);
        return result;
    }
};
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

全排列

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

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums, vector<int>& used){
        //相等则添加，并返回
        if (path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        //用used记录已使用的数字
        for (int i=0;i<nums.size();i++){
            if (used[i]==1) continue;
            used[i]=1;
            path.push_back(nums[i]);
            dfs(nums,used);
            //回溯
            used[i]=0;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(),0);
        dfs(nums,used);
        return result;
    }
};
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

全排列||

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
1
2

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums,vector<int>& used){
        if (path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for (int i=0;i<nums.size();i++){
            //重复且前一个数字没被使用过才跳过
            if (used[i]==1||(i>0&&used[i-1]==0 &&nums[i]==nums[i-1])) continue;
            used[i]=1;
            path.push_back(nums[i]);
            dfs(nums,used);
            used[i]=0;
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int> used(nums.size(),0);
        dfs(nums,used);
        return result;
    }
};
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

sort(nums.begin(),nums.end());
    dfs(nums,0);
    return result;
}
1
2
3
4

};


#### 递增子序列

1
2
3

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]


```c++
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    //判断是否为递增数列
    bool is_add(vector<int>& nums){
        for (int i=1;i<nums.size();i++){
            if (nums[i-1]>nums[i]) return false;
        }
        return true;
    }
    void dfs(vector<int>& nums, int start){
        //剪枝，不是递增直接返回
        if (!is_add(path)) return;
        if (path.size()>1) result.push_back(path);
        //记录该层出现的元素
        unordered_set<int> used;
        for (int i=start;i<nums.size();i++){
            //防止重复元素出现
            if (used.find(nums[i])!=used.end())continue;
            used.insert(nums[i]);
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(nums,0);
        return result;
    }
};
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

全排列

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

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums, vector<int>& used){
        //相等则添加，并返回
        if (path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        //用used记录已使用的数字
        for (int i=0;i<nums.size();i++){
            if (used[i]==1) continue;
            used[i]=1;
            path.push_back(nums[i]);
            dfs(nums,used);
            //回溯
            used[i]=0;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(),0);
        dfs(nums,used);
        return result;
    }
};
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

全排列||

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
1
2

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums,vector<int>& used){
        if (path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for (int i=0;i<nums.size();i++){
            //重复且前一个数字没被使用过才跳过
            if (used[i]==1||(i>0&&used[i-1]==0 &&nums[i]==nums[i-1])) continue;
            used[i]=1;
            path.push_back(nums[i]);
            dfs(nums,used);
            used[i]=0;
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int> used(nums.size(),0);
        dfs(nums,used);
        return result;
    }
};
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/618846

代码随想录笔记

算法

数组

二分法

移除元素（双指针）

移除

移动零

有序数组平方

长度最小子数组

旋转矩阵! !

链表

定义

移除链表指定元素

链表类的定义 ！！

翻转链表

两两交换节点

删除 倒数第n个结点

链表相交

环形链表！！

哈希表

相同字母字符串

求数组交集

求快乐数

两数之和

四数之和

找字符串

三数之和！！

四数之和

字符串

反转字符串

反转字符串 ||

反转字符串中的单词

字符串左旋

KMP算法!!

前缀表

具体比较

判断是否为重复字符串

栈与队列

栈实现队列

队列实现栈

有效的括号

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

逆波兰表达式求值

滑动列表最大值

二叉树

理论基础

类型

平衡二叉搜索树

存储

遍历方式

类定义

前中后序遍历（深度）

递归

迭代

层序遍历（宽度）

对称二叉树

求二叉树深度

求二叉树节点数

判断平衡二叉树

二叉树所有路径

左子叶之和

找树左下角的值

路径总和

后序遍历

前序遍历

最大二叉树

合并二叉树

二叉树搜索

验证二叉树

二叉树中的众数

二叉树的最近公共祖先

搜索二叉树的最近公共组训

二叉树插入节点

删除搜索二叉树节点

修剪二叉树

将递增数组转化成二叉树

二叉树转化成累加树

回溯

组合问题

组合累和

链表类的定义！！

删除倒数第n个结点