Shuwen's blog

生活 & 学习

0%

leetcode之算法学习计划

发表于 更新于 分类于

链接：https://leetcode-cn.com/study-plan/algorithms/?progress=x7xottv

算法入门

image-20210825235602576

2021/08/25，已完成，（´v｀），为什么感觉我更喜欢算法（而不是ctf，😔，算法好好练练，以后再重新学学网安吧。

第 1 天 二分查找

704. 二分查找

easy

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int pivot,left=0,right=nums.size();//设置3个变量：当前指针、左边界、右边界
        while(left <= right){//结束
            pivot = left + (right-left) / 2;//指针在中间的位置
            if(nums[pivot] == target) return pivot;//相等返回
            if(target < nums[pivot]) right = pivot-1;//小于情况
            else left = pivot + 1;//大于情况
        }
        return -1;//直接返回
    }
};

278. 第一个错误的版本

mine

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstBadVersion(int n) {
        int pivot,left=1,right=n;
        while(left <= right){
            pivot = left + (right-left) / 2;
            if(isBadVersion(pivot)==true && isBadVersion(pivot-1)==false) return pivot;
            else if(isBadVersion(pivot)==true) right = pivot-1;
            else if(isBadVersion(pivot)==false) left = pivot + 1;
        }
        return 1;
    }
};

answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1,right=n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
};

35. 搜索插入位置

mine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int pivot,left=0,right=nums.size()-1;
        while(left < right){
            pivot = left + (right - left) / 2;
            if(target == nums[pivot]) return pivot;
            else if(target > nums[pivot]) left = pivot+1;
            else if(target <nums[pivot]) right = pivot-1;
        }
        if(target > nums[left]){
            return left+1;
        }else{
            return left;
        }
    }
};

answer

  1. 转换目标：「在一个有序数组中找第一个大于等于 target 的下标」。
  2. ans初值设置为数组长度：存在一种情况是 target 大于数组中的所有数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0,right = n-1,ans = n;
        while(left <= right){
            int mid = ((right-left) >> 1) + left;
            if(target <= nums[mid]){
                ans = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }
};

第 2 天 双指针

977. 有序数组的平方

mine

直接排序

时间复杂度：O(nlog⁡n)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

双指针

由于原数组已经有序，故可以使用两个指针从0开始一个向左，一个向右，分别比较大小

时间复杂度：O(n)

  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
    32
    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& nums) {
            int n = nums.size();
            int negative = -1;
            for(int i=0;i<n;++i){
                if(nums[i] < 0){
                    negative = i;//negative是最右的负数
                }else{
                    break;
                }
            }
            vector<int> ans;
            int i = negative,j=negative+1;
            while(i>=0 || j<n){
                if(i<0){//左边的走完了，一直走右指针即可
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }else if(j == n){
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else if(nums[i] * nums[i] < nums[j] * nums[j]){
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else {
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }
            }
            return ans;
        }
    };

  2. 从左右向0走

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

189. 旋转数组

answer1

由于直接放，会覆盖，所以增加一个额外数组

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for(int i=0;i<n;i++){
            newArr[(i+k)%n] = nums[i];//i表示第几个，+k表示右移，由于可能溢出，故取%
        }
        nums.assign(newArr.begin(),newArr.end());
    }
};

answer2

数组翻转

原始数组
翻转所有元素
翻转[0,k mod n−1] 区间的元素
翻转[k mod n,n−1] 区间的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void reverse(vector<int>& nums,int start,int end){
        while(start < end){
            swap(nums[start],nums[end]);
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k%=nums.size();
        reverse(nums,0,nums.size()-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.size()-1);
    }
};

answer3

image-20210730160407116

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k%n;
        int count = gcd(k,n);
        for(int start =0;start<count;++start){//往后走
            int current = start;
            int prev = nums[start];
            do{//里面是一轮
                int next = (current+k) %n;
                swap(nums[next],prev);
                current = next;
            }while(start!=current);
        }
    }
};

第 3 天 双指针

283. 移动零

right指向右边的非0，left指向左边的0。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(),left=0,right=0;
        while(right < n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

167. 两数之和 II - 输入有序数组

二分查找，其中i的下标是第一个元素，mid下标是第二个元素

i从0 ～ size-1

第二个元素从low～high，也就是1～size-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0;i<numbers.size();i++){
            int low = i+1,high = numbers.size()-1;
            while(low <= high){
                int mid = low + (high - low)/2;
                if(numbers[mid] == target - numbers[i]){
                    return {i+1,mid+1};
                }else if(numbers[mid] > target - numbers[i]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
        }
        return {-1,-1};
    }
};

双指针

从两边依次往里走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0,high = numbers.size()-1;
        while(low < high){
            int sum = numbers[low] + numbers[high];
            if(sum == target){
                return {low+1,high+1};
            }else if(sum < target){
                ++low;
            }else{
                --high;
            }
        }
        return {-1,-1};
    }
};

第 4 天 双指针

344. 反转字符串

mine

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int times = n / 2;
        for(int i = 0; i < times; i++){
            swap(s[i], s[n-i-1]);
        }
    }
};

answer

我写的和答案，本质是一样的，但是思考过程不一样。

我其实没有用到双指针这一思想，而是直接左边过去的思路。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for(int left = 0,right = n-1;left < right;++left,--right){
            swap(s[left],s[right]);
        }
    }
};

557. 反转字符串中的单词 III

split

C++没有字符串分割函数split，自己实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<string> split(const string& str, const string& delim) {  
    vector<string> res;  
    if("" == str) return res;  
    //先将要切割的字符串从string类型转换为char*类型  
    char * strs = new char[str.length() + 1] ; //不要忘了  
    strcpy(strs, str.c_str());   

    char * d = new char[delim.length() + 1];  
    strcpy(d, delim.c_str());  

    char *p = strtok(strs, d);  
    while(p) {  
        string s = p; //分割得到的字符串转换为string类型  
        res.push_back(s); //存入结果数组  
        p = strtok(NULL, d);  
    }  
    return res;  
}

使用

1
split(s," ");

mine

image-20210802213123802

虽然效率好像不是很高，不过也算是自己实现的，，，hhh

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:
    string reverseWords(string s) {
        vector<string> v = split(s," ");
        string ans="";
        for(int i=0;i<v.size()-1;i++){
            ans += reverse(v[i])+" ";
        }
        ans += reverse(v[v.size()-1]);
        return ans;
    }
    string reverse(string s){
        for(int i=0;i<s.size()/2;i++){
            swap(s[i],s[s.size()-i-1]);
        }
        return s;
    }
    vector<string> split(const string& str, const string& delim) {  
        vector<string> res;  
        if("" == str) return res;  
        //先将要切割的字符串从string类型转换为char*类型  
        char * strs = new char[str.length() + 1] ; //不要忘了  
        strcpy(strs, str.c_str());   
    
        char * d = new char[delim.length() + 1];  
        strcpy(d, delim.c_str());  
    
        char *p = strtok(strs, d);  
        while(p) {  
            string s = p; //分割得到的字符串转换为string类型  
            res.push_back(s); //存入结果数组  
            p = strtok(NULL, d);  
        }  
        return res;  
    } 
};

answer1

不使用split，巧妙使用while解决

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:
    string reverseWords(string s) {
        string ret;
        int length = s.length();
        int i=0;
        while(i < length){
            int start = i;
            while(i < length && s[i] != ' '){//start是一个单词的开始，i找到该单词的结尾
                i++;
            }
            for(int p = start;p<i;p++){
                ret.push_back(s[start + i - 1 -p]);//从该单词结尾往前加到ret字符串上面
            }
            while(i < length && s[i] == ' '){
                i++;//下一个开始也要跳过空格
                ret.push_back(' ');//加上空格
            }
        }
        return ret;
    }
};

answer2

相当于我的思路同answer1的结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string reverseWords(string s) {
        int length = s.length();
        int i=0;
        while(i < length){
            int start = i;
            while(i<length && s[i] != ' '){
                i++;
            }
            int left = start,right = i-1;
            while(left < right){
                swap(s[left],s[right]);
                left++;
                right--;
            }
            while(i < length && s[i] == ' '){
                i++;
            }
        }
        return s;
    }
};

第 5 天 双指针

876. 链表的中间结点

wowo，太强了，hhh，第一次100%，自己写的

image-20210802222127027

mine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* l = head;
        int length=1;
        while(head->next!=nullptr){
            length++;
            head = head->next;
        }
        int times = length / 2 + 1;
        
        for(int i=1;i<times;i++){
            l = l->next;
        }
        return l;
    }
};

answer1

将链表放入数组中，取下标中值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> A={head};
        while(A.back()->next!=NULL){
            A.push_back(A.back()->next);
        }
        return A[A.size()/2];//因为反着压，所以不用+1
    }
};

answer2

跟我写的一样，称为单指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int n=0;
        ListNode* cur = head;
        while(cur != nullptr){
            ++n;
            cur = cur->next;
        }
        int k=0;
        cur = head;
        while(k<n/2){
            ++k;
            cur = cur->next;
        }
        return cur;
    }
};

answer3

快慢指针，太强了

快指针走到最后，慢指针刚好在中间。

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;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!= NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

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

answer1

按着题目思路一步步解的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode* head){
        int length = 0;
        while(head){
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);
        int length = getLength(head);//head已经走到尾巴了
        ListNode*cur = dummy;
        for(int i=1;i<length-n+1;i++){//第一个是多加的0
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        return ans;
    }
};

answer2

这种给右边的长度，可以用栈解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);//head副本，前面多了一个节点0
        stack<ListNode*> stk;
        ListNode*cur = dummy;
        while(cur){
            stk.push(cur);
            cur = cur->next;
        }
        for(int i=0;i<n;i++){
            stk.pop();
        }
        ListNode* prev = stk.top();//取出要删除的前一节点，
        prev->next = prev->next->next;//删除
        ListNode* ans = dummy->next;//返回删除后的链表（所有操作都是对同一个链表）;
        delete dummy;
        return ans;
    }
};

answer3

快慢指针，i了i了。

通过两个指针，一个先走，另一个再走，成功把后面的长度转换到了前面。

让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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);
        ListNode* first = head;
        ListNode* second = dummy;
        for(int i=0;i<n;i++){
            first = first->next;//first先走那几步
        }
        while(first){//first走到尾，second刚好到达目标地点
            first=first->next;
            second=second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

第 6 天 滑动窗口

3. 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int rk=-1,ans=0;
        int n = s.size();
        for(int i=0;i<n;i++){
            if(i!=0){
                occ.erase(s[i-1]);
            }
            while(rk+1<n && !occ.count(s[rk+1])){
                occ.insert(s[rk+1]);
                rk++;
            }
            ans = max(ans,rk-i+1);
        }
        return ans;
    }
};

567. 字符串的排列

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 checkInclusion(string s1, string s2) {
        int n = s1.length(),m=s2.length();
        if(n > m){
            return false;
        }
        vector<int> cnt1(26),cnt2(26);
        for(int i=0;i<n;i++){
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if(cnt1 == cnt2){
            return true;
        }
        for(int i=n;i<m;i++){
            ++cnt2[s2[i]-'a'];//滑动窗口，长度为子串长度n
            --cnt2[s2[i - n]-'a'];//右边+1，左边-1
            if(cnt1==cnt2){
                return true;
            }
        }
        return false;
    }
};

第 7 天 广度优先搜索 / 深度优先搜索

733. 图像渲染

深度优先。

题目的意思类似于画图里面的油漆，hhh。

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:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    void dfs(vector<vector<int>>& image,int x,int y,int color,int newColor){
        if(image[x][y] == color){
            image[x][y] = newColor;
            for(int i=0;i<4;i++){
                int mx = x+dx[i],my=y+dy[i];
                if(mx>=0&&mx<image.size() && my>=0&&my<image[0].size()){
                    dfs(image,mx,my,color,newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if(currColor != newColor){
            dfs(image,sr,sc,currColor,newColor);
        }
        return image;
    }
};

广度优先，加入队列实现

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:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if(currColor == newColor) return image;
        int n = image.size(),m=image[0].size();
        queue<pair<int,int>> que;
        que.emplace(sr,sc);
        image[sr][sc]=newColor;
        while(!que.empty()){
            int x = que.front().first,y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
                int mx = x+dx[i],my=y+dy[i];
                if(mx>=0&&mx<n && my>=0&&my<m&&image[mx][my]==currColor){
                    que.emplace(mx,my);
                    image[mx][my]=newColor;
                }
            }
        }
        return image;
    }
};

695. 岛屿的最大面积

深度优先，多了一个刚开始要循环所有（起点遍历）

是图的遍历

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:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    int dfs(vector<vector<int>>& grid,int x,int y){
        if(x<0 || y<0 || x == grid.size() || y==grid[0].size()||grid[x][y]!=1){
            return 0;
        }
        grid[x][y]=0;
        int ans = 1;
        for(int i=0;i<4;i++){
            int mx = x+dx[i],my = y+dy[i];
            ans += dfs(grid,mx,my);
        }
        return ans;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans =0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                ans = max(ans,dfs(grid,i,j));
            }
        }
        return ans;
    }
};

使用栈，非递归

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:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans =0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                int cur = 0;
                stack<int> stacki;
                stack<int> stackj;
                stacki.push(i);
                stackj.push(j);
                while(!stacki.empty()){
                    int x = stacki.top(),y=stackj.top();
                    stacki.pop();
                    stackj.pop();
                    if(x<0||y<0||x==grid.size()||y==grid[0].size()||grid[x][y]!=1){
                        continue;
                    }
                    ++cur;
                    grid[x][y]=0;
                    int dx[4]={1,0,0,-1};
                    int dy[4]={0,1,-1,0};
                    for(int i=0;i<4;i++){
                        int mx = x+dx[i],my=y+dy[i];
                        stacki.push(mx);
                        stackj.push(my);
                    }
                }
                ans=max(ans,cur);
            }
        }
         return ans;
    }
};

广度优先

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:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
        for(int i = 0; i < grid.size() ; i++){
            for(int j = 0; j < grid[0].size(); j++){
                int cur = 0;
                queue<pair<int ,int>> que;
                    que.emplace(i,j);
                    while(!que.empty()){
                        int x = que.front().first,y = que.front().second;
                        que.pop();
                        if(x < 0 || y < 0 || x == grid.size() || y==grid[0].size() || grid[x][y] != 1){
                            continue;
                        }
                        ++cur;
                        grid[x][y] = 0;
                        for(int k = 0; k < 4; k++){
                            int mx = x + dx[k], my = y+dy[k];
                                que.emplace(mx,my);
                        }
                    }
                    ans = max(ans,cur);
            }
        }
        return ans;
    }
};

总结

广度优先和深度优先，类似于模板题，多做些题，应该可以掌握。

第 8 天 广度优先搜索 / 深度优先搜索

617. 合并二叉树

深度优先

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 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==nullptr) return t2;
        if(t2==nullptr) return t1;

        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left,t2->left);
        merged->right = mergeTrees(t1->right,t2->right);
        return merged;
    }
};

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition for a 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == nullptr) return t2;
        if(t2 == nullptr) return t1;
        TreeNode* merged = new TreeNode(t1->val + t2->val);
        queue<TreeNode*> q,q1,q2;
        q.push(merged);
        q1.push(t1);
        q2.push(t2);
        while(!q1.empty() && !q2.empty()){
            TreeNode* node = q.front();//三句话合在一起要用auto，不然报错
            TreeNode* node1 = q1.front();
            TreeNode* node2=q2.front();
            q.pop();
            q1.pop();
            q2.pop();
            TreeNode* left1 = node1->left;
            TreeNode* left2 = node2->left;
            TreeNode* right1 = node1->right;
            TreeNode* right2 = node2->right;
            if(left1 != nullptr || left2!=nullptr){
                if(left1!=nullptr && left2!=nullptr){
                    auto left = new TreeNode(left1->val + left2->val);
                    node->left = left;
                    q.push(left);
                    q1.push(left1);
                    q2.push(left2);
                }else if(left1 !=nullptr){
                    node->left = left1;
                }else{
                    node->left = left2;
                }
            }
            if(right1 != nullptr || right2!=nullptr){
                if(right1!=nullptr && right2!=nullptr){
                    auto right = new TreeNode(right1->val + right2->val);
                    node->right = right;
                    q.push(right);
                    q1.push(right1);
                    q2.push(right2);
                }else if(right1 !=nullptr){
                    node->right = right1;
                }else{
                    node->right = right2;
                }
            }
        }
        return merged;
    }
};

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) {
        if(root == nullptr) return root;

        queue<Node*> Q;
        Q.push(root);
        while(!Q.empty()){
            int size = Q.size();
            for(int i=0;i<size;i++){
                Node* node = Q.front();
                Q.pop();
                if(i<size-1){//一层的左边size-1个
                    node->next = Q.front();
                }
                if(node->left!=nullptr){
                    Q.push(node->left);
                }
                if(node->right!=nullptr){
                    Q.push(node->right);
                }
            }
        }
        return root;
    }
};

使用已建立的 next 指针，高级，根据具体题目分析可得

image-20210808100955721

image-20210808101008138

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
// Definition for a 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) {
        if(root == nullptr) return root;

        Node* leftmost = root;
        while(leftmost -> left !=nullptr){
            Node* head = leftmost;
            while(head != nullptr){
                head->left->next = head->right;//第一种
                if(head->next != nullptr){//第二种
                    head->right->next = head->next->left;
                }
                head = head->next;//指针右移
            }
            leftmost = leftmost->left;//下一层
        }
        return root;
    }
};

第 9 天 广度优先搜索 / 深度优先搜索

542. 01 矩阵

广度优先

多源最短路->找到所有的0，距离为0，广播一次，找到所有的元素距离为1，再次广播，距离为2->依此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    const int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n));
        vector<vector<int>> seen(m,vector<int>(n));
        queue<pair<int,int>> q;

        //将所有的0添加进初始队列中
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    q.emplace(i,j);
                    seen[i][j]=1;
                }
            }
        }
        //广度优先
        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int dx = x+dirs[i][0];
                int dy = y+dirs[i][1];
                if(dx>=0 && dx<m && dy>=0 && dy<n && !seen[dx][dy]){
                    dist[dx][dy] = dist[x][y]+1;
                    q.emplace(dx,dy);
                    seen[dx][dy] = 1;
                }
            }
        }
        return dist;
    }
};

动态规划

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<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n,INT_MAX/2));//初始化距离为很大的数
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j] == 0){
                    dist[i][j] = 0;
                }
            }
        }
        //左下到右下
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i-1>=0){
                    dist[i][j] = min(dist[i][j],dist[i-1][j]+1);//当前节点是左边和当前节点最小值
                }
                if(j-1>=0){
                    dist[i][j] = min(dist[i][j],dist[i][j-1]+1);//当前节点是上边和当前节点的最小值
                }
            }
        }
        //右上到左下
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(i+1 < m){
                    dist[i][j] = min(dist[i][j],dist[i+1][j]+1);
                }
                if(j+1<n){
                    dist[i][j] = min(dist[i][j],dist[i][j+1]+1);
                }
            }
        }
        return dist;
    }
};

994. 腐烂的橘子

本质上就是多源广度优先的搜索过程

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 cnt;
    int dis[10][10];
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> Q;
        memset(dis,-1,sizeof((dis)));
        cnt = 0;
        int n = grid.size(),m = grid[0].size(),ans=0;
        //初始化
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == 2){//2是腐烂,距离为0
                    Q.push(make_pair(i,j));//所有的腐烂橘子入队                                                                                          
                    dis[i][j] = 0;
                }
                else if(grid[i][j] == 1) cnt += 1;//cnt统计一共多少个好的橘子
            }
        }
        //广度优先搜索
        while(!Q.empty()){
            pair<int,int> x = Q.front();//x是从队列中取出来的腐烂橘子
            Q.pop();
            for(int i=0;i<4;i++){
                int tx = x.first + dx[i];//寻找腐烂橘子的上下左右
                int ty = x.second + dy[i];
                if(tx<0 || ty<0 || tx >=n || ty >=m || !grid[tx][ty] || ~dis[tx][ty]) continue;//错误的上下左右
                dis[tx][ty] = dis[x.first][x.second] + 1;//发散+1
                Q.push(make_pair(tx,ty));//发散后的入列
                if(grid[tx][ty] == 1){//感染一个正常橘子
                    cnt -= 1;//正常橘子数目-1
                    ans = dis[tx][ty];//ans是当前的值
                    if(!cnt) break;//如果正常橘子被感染完全了,结束
                }
            }
        }
        return cnt ? -1:ans;//cnt=0返回ans;cnt=1返回-1,则是不可能感染所有的橘子
    }
};

第 10 天 递归 / 回溯

21. 合并两个有序链表

最简洁明了的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr){
            return l1;
        }else if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

迭代

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

206. 反转链表

mine

image-20210809102021413

注释了，100%，不注释，58%，不晓得为啥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //if(head == nullptr) return head;
        vector<int> v;

        while(head!=nullptr){
            v.push_back(head->val);
            head = head->next;
        }

        ListNode* prehead = new ListNode(-1);
        ListNode* pre = prehead;
        for(int i=v.size()-1;i>=0;i--){
            prehead -> next = new ListNode(v[i]);
            prehead = prehead -> next;
        }
        return pre->next;
    }
};

answer1

迭代，有点绕

改指针，转过来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while(curr){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

answer2

递归，高级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

第 11 天 递归 / 回溯

77. 组合

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

    //cur是当前是数字几
    void dfs(int cur,int n,int k){
        if(temp.size() + (n-cur+1)<k){//无法拼凑到k个数
            return;
        }
        if(temp.size() == k){//一种组合
            ans.push_back(temp);
            return;
        }
        //选择cur加入
        temp.push_back(cur);
        dfs(cur+1,n,k);
        temp.pop_back();
        //不选择cur加入
        dfs(cur+1,n,k);
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return ans;
    }
};

高级，，，就很神奇

通过j<k，通知个数

通过temp[j]+1 == temp[j+1]，让最大就增加到两个相邻；否则用++temp[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
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    vector<vector<int>> combine(int n, int k) {
        for(int i=1;i<=k;i++){
            temp.push_back(i);        
        }
        temp.push_back(n+1);//哨兵

        int j=0;
        while(j<k){
            ans.emplace_back(temp.begin(),temp.begin()+k);
            j=0;
            while(j<k && temp[j]+1 == temp[j+1]){
                temp[j] = j+1;
                ++j;
            }
            ++temp[j];
        }
        return ans;
    }
};

46. 全排列

就c++的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void backtrack(vector<vector<int>>& res,vector<int>&output,int first,int len){
        if(first == len){
            res.emplace_back(output);
            return;
        }
        for(int i=first;i<len;i++){
            swap(output[i],output[first]);
            backtrack(res,output,first+1,len);
            swap(output[i],output[first]);
        }
    }
      
    }
};

784. 字母大小写全排列

深度搜索，全排列

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<string> ans;
    bool isSmall(char c){
        return c>='a' && c<='z';
    }
    bool isBig(char c){
        return c>='A' && c<='Z';
    }
    void dfs(string& now,string& s,int i){
        if(i==s.length())
            ans.push_back(now);
        else{
            if(isSmall(s[i])){
                now.push_back(s[i]-('a'-'A'));
                dfs(now,s,i+1);
                now.pop_back();
            }else if(isBig(s[i])){
                now.push_back(s[i]+('a'-'A'));
                dfs(now,s,i+1);
                now.pop_back();
            }now.push_back(s[i]);
            dfs(now,s,i+1);
            now.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        string now;//now是当前完成的字符串，s是原始串
        dfs(now,s,0);
        return ans;
    }
};

递归的位运算

image-20210822153225929

大小A差距32，所以异或32即可

A的32位为0，不同为1，就加上32了

a的32位位1，相同为0，就减去32了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void dfs(string s,int n,vector<string>& res){
        if(s.size() == n) return res.push_back(s);
        if(isdigit(s[n])) return dfs(s,n+1,res);
        dfs(s,n+1,res);
        s[n] ^= (1<<5);
        dfs(s,n+1,res);
    }
    vector<string> letterCasePermutation(string s) {
        vector<string> res;
        dfs(s,0,res);
        return res;
    }
};

非递归

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<string> letterCasePermutation(string s) {
        vector<string> result{s};
        int n = s.size();
        for(int i=0;i<n;i++){//循环每个字符
            if(isupper(s[i])){//当前字符为大写
                int size = result.size();
                for(int j=0;j<size;j++){//当原来所有的字符串，改位置改为小写
                    string temp = result[j];
                    temp[i] = tolower(temp[i]);
                    result.emplace_back(temp);
                }
            }else if(islower(s[i])){
                int size = result.size();
                for(int j=0;j<size;j++){
                    string temp = result[j];
                    temp[i] = toupper(temp[i]);
                    result.emplace_back(temp);
                }
            }
        }
        return result;
    }
};

第 12 天 动态规划

70. 爬楼梯

动态规划

f(x)=f(x−1)+f(x−2)

「滚动数组思想」把空间复杂度优化成 O(1)

fig1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=1;i<=n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
};

矩阵快速幂

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<long long>> multiply(vector<vector<long long>>&a,vector<vector<long long>> &b){
        vector<vector<long long>> c(2,vector<long long>(2));
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j];
            }
        }
        return c;
    }
    vector<vector<long long>> matrixPow(vector<vector<long long>> a,int n){
        vector<vector<long long>> ret = {{1,0},{0,1}};//初始为单位矩阵
        while(n>0){
            if(n&1 == 1){
                ret = multiply(ret,a);//每次积累
            }
            n>>=1;
            a=multiply(a,a);
        }
        return ret;
    }
    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1,1},{1,0}};
        vector<vector<long long>> res = matrixPow(ret,n);
        return res[0][0];
    }
};

通向公式，数学yyds

image-20210826002323668

1
2
3
4
5
6
7
8
class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1+sqrt5)/2,n+1) - pow((1-sqrt5)/2,n+1);
        return round(fibn/sqrt5);//round:四舍五入
    }
};

198. 打家劫舍

最简单的动态规划

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

类似于滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int size = nums.size();
        if(size==1){
            return nums[0];
        }
        int first = nums[0],second = max(nums[0],nums[1]);
        for(int i=2;i<size;i++){//三个分别是：first、second、max
            int temp = second;
            second = max(first+nums[i],second);
            first = temp;
        }
        return second;
    }
};

120. 三角形最小路径和

枚举所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n,vector<int>(n));
        f[0][0] = triangle[0][0];//最左边的情况
        for(int i=1;i<n;i++){//中间
            f[i][0] = f[i-1][0]+triangle[i][0];
            for(int j=1;j<i;j++){
                f[i][j] = min(f[i-1][j-1],f[i-1][j])+triangle[i][j];
            }
            f[i][i] = f[i-1][i-1]+triangle[i][i];//最右边
        }
        return *min_element(f[n-1].begin(),f[n-1].end());//min_element取容器中的最小值，*取的是二维数组中取出来的一维数组的值
    }
};

空间复杂度的优化

用两个长度为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
34
35
36
37
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(2,vector<int>(n));//2n的空间
        f[0][0] = triangle[0][0];
        for(int i=1;i<n;i++){
            int curr = i%2;//第一个n
            int prev = 1-curr;//第二个n，实现交替0 1，1 0
            f[curr][0] = f[prev][0] + triangle[i][0];//当前值还是用i，保存的地址是curr和prev
            for(int j=1;j<i;j++){
                f[curr][j] = min(f[prev][j-1],f[prev][j])+triangle[i][j];
            }
            f[curr][i] = f[prev][i-1]+triangle[i][i];
        }
        return *min_element(f[(n-1)%2].begin(),f[(n-1)%2].end());

    }
};class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(2,vector<int>(n));//2n的空间
        f[0][0] = triangle[0][0];
        for(int i=1;i<n;i++){
            int curr = i%2;//第一个n
            int prev = 1-curr;//第二个n，实现交替0 1，1 0
            f[curr][0] = f[prev][0] + triangle[i][0];//当前值还是用i，保存的地址是curr和prev
            for(int j=1;j<i;j++){
                f[curr][j] = min(f[prev][j-1],f[prev][j])+triangle[i][j];
            }
            f[curr][i] = f[prev][i-1]+triangle[i][i];
        }
        return *min_element(f[(n-1)%2].begin(),f[(n-1)%2].end());//f[(n-1)%2:最后一行的结果

    }
};

空间复杂度n的优化，不过没太看懂，就一点点感觉那种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> f(n);
        f[0] = triangle[0][0];
        for(int i=1;i<n;i++){
            f[i] = f[i-1] + triangle[i][i];
            for(int j=i-1;j>0;j--){
                f[j] = min(f[j-1],f[j])+triangle[i][j];
            }
            f[0] += triangle[i][0];
        }

        return *min_element(f.begin(),f.end());
    }
};

第 13 天 位运算

231. 2 的幂

根据位运算的特点得到两个公式

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && (n&(n-1)) == 0;
    }
};
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && (n&(-n)) == n;
    }
};

如果事最大的2幂次的约数，那么就是了。interesting

1
2
3
4
5
6
7
class Solution {
public:
    static constexpr int BIG = 1<<30;
    bool isPowerOfTwo(int n) {
        return n>0 && BIG % n == 0;
    }
};

191. 位1的个数

正常的简答逻辑

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret=0;
        for(int i=0;i<32;i++){
            if(n&(1<<i)){
                ret++;
            }
        }
        return ret;
    }
};

效率比之前的好，每次把最后一个1位置零

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

第 14 天 位运算

190. 颠倒二进制位

rev存的是结果，一开始是全0，将数n依次从前头的1与到rev里面。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev=0;
        for(int i=0;i<32 && n>0;++i){
            rev |= (n&1) << (31-i);
            n>>=1;
        }    
        return rev;
    }
};

高级，没太看懂，大概意思就是每次分治，先2位交换，逐步扩展到最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
private:
    const uint32_t M1 = 0x55555555;
    const uint32_t M2 = 0x33333333;
    const uint32_t M3 = 0x0f0f0f0f;
    const uint32_t M4 = 0x00ff00ff; 
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n >> 1)& M1) | ((n&M1) << 1);
        n = ((n >> 2)& M2) | ((n&M2) << 2);
        n = ((n >> 4)& M3) | ((n&M3) << 4);
        n = ((n >> 8)& M4) | ((n&M4) << 8);  
        return n>>16 | n<< 16;
    }
};

136. 只出现一次的数字

hhh，之前看过这个视频，做出来饿了

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

和答案基本一致，就是不太会用加强for循环，emm，其实主要用在能放一组元素的变量里面

1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(auto e:nums) ret^=e;
        return ret;
    }
};

算法基础

第 1 天 二分查找

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找得改进

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 binarySearch(vector<int>& nums, int target,bool lower) {
        int left = 0,right = (int)nums.size()-1,ans = (int)nums.size();
        while(left<=right){
            int mid = (left + right) / 2;
            if(nums[mid] > target || (lower && nums[mid] >= target)){
                right = mid-1;
                ans = mid;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }
    vector<int> searchRange(vector<int> nums,int target){
        int leftId = binarySearch(nums,target,true);
        int rightId = binarySearch(nums,target,false)-1;
        if(leftId<=rightId && rightId<nums.size() && nums[leftId]==target&&nums[rightId]==target){
            return vector<int>{leftId,rightId};
        }
        return vector<int>{-1,-1};
    }
};

33. 搜索旋转排序数组

分两半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if(!n){
            return -1;
        }
        if(n==1){
            return nums[0] == target ?0:-1;
        }
        int l=0,r=n-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid] == target) return mid;
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target && target<nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[n-1]){
                    l = mid+1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

74. 搜索二维矩阵

匿名函数

参考链接

格式：

1
[capture](parameters)->return-type{body}
  • 当parameters为空的时候，()可以被省去
  • 当body只有“return”或者返回为void，那么”->return-type“可以被省去

upper_bound

参考链接

lower_bound( begin,end,num)：查找第一个大于等于num得数

upper_bound( begin,end,num)：查找第一个大于num得数

参考链接

是c++ stl里面得函数

1
binary_search(arr[],arr[]+size , indx) b
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto row = upper_bound(matrix.begin(),matrix.end(),target,[](const int b,const vector<int>&a){
            return b < a[0];
        });
        if(row == matrix.begin()){
            return false;
        }
        --row;
        return binary_search(row->begin(),row->end(),target);
    }
};

矩阵式的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(),n = matrix[0].size();
        int low = 0,high = m*n - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            int x = matrix[mid / n][mid % n];
            if(x < target){
                low = mid + 1;
            }else if(x>target){
                high = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};

第 2 天 二分查找

153. 寻找旋转排序数组中的最小值

mine

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 findMin(vector<int>& nums) {
        int n = nums.size();
        if(!n){
            return -1;
        }
        if(n==1){
            return nums[0];
        }
        int l =0,r = n-1;
        while(l <= r){
            int mid = (l+r) / 2;
            if(nums[mid] < nums[(mid+1)%n] && nums[(mid+n-1)%n] > nums[mid]){
                return nums[mid];
            }else if(nums[r] > nums[mid]){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return -1;

    }
};

answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size()-1;
        while(low < high){
            int pivot = low + (high - low) / 2;
            if(nums[pivot] < nums[high]){
                high = pivot;
            }else{
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

162. 寻找峰值

mine

没看出来要怎么用二分查找，这里的数组无序呀，，，然后就循环求，效率还好，，，

image-20210827115136407

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

哦，是求峰值，不是最大值，打扰了

有意思，根据情况分类，只要满足一个条件就可以找到了

image-20210827115552132

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

二分递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>&nums,int l,int r){
        if(l == r){
            return l;
        }
        int mid = (l+r)/2;
        if(nums[mid]>nums[mid+1]){
            return search(nums,l,mid);
        }
        return search(nums,mid+1,r);
    }
    int findPeakElement(vector<int>& nums) {
        return search(nums,0,nums.size()-1);
    }
    
};

第 3 天 双指针

82. 删除排序链表中的重复元素 II

思路很简单，看怎么写了，代码给注释

有利地方：链表有序

难点：

  1. 怎么判断重复了，easy
  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
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head){
            return head;
        }
        ListNode* dummy = new ListNode(0,head);//头节点指向最前面
        ListNode* cur = dummy;
        while(cur->next && cur->next->next){//存在是前提
            if(cur->next->val == cur->next->next->val){//出现连续
                int x = cur->next->val;//取出值
                while(cur->next && cur->next->val == x){//循环是否等于x
                    cur->next = cur->next->next;//删除节点
                }
            }else{
                cur=cur->next;//不用删除，往后走即可
            }
        }
        return dummy->next;
    }
};

15. 三数之和

两数之和的升级版，首先肯定是先确定一个值，剩下就简化为两数之和。

为了不重复怎么办：

  • 首先对数组排序
  • 其次前两个数判断是否连续了
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<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        //为了不重复，首先进行一次排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for(int first = 0;first<n;first++){
            //first是三元组的第一个数，两次枚举这两个应该不同
            if(first > 0&& nums[first]==nums[first-1]){
                continue;
            }
            int third = n-1;//双指针法：second从左走到右边，third从右边走到左边
            int target = -nums[first];//因为需要和为0，简化为两数求和
            for(int second=first+1;second<n;second++){
                //两次枚举不同值
                if(second > first+1 && nums[second]==nums[second-1]){
                    continue;
                }
                //双指针开始：大了，右指针左移
                while(second < third && nums[second]+nums[third] > target){
                    --third;
                }
                //指针重合,over
                if(second == third){
                    break;
                }
                if(nums[second]+nums[third]==target){
                    ans.push_back({nums[first],nums[second],nums[third]});
                }
            }
        }
        return ans;
    }
};

第 4 天 双指针

844. 比较含退格的字符串

mine

锻炼自己写代码的能力

image-20210829132310691

中间遇到几个问题

  1. 判断！=0
  2. 两个stack放在一起，由于长度不一样，有问题
  3. 结果用s.size，做结束的判断，由于pop，导致这个值在变化
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:
    bool backspaceCompare(string s, string t) {
int s_size = s.size();
        int t_size = t.size();
        stack<char> s1;
        stack<char> s2;

        for(int i=0;i<s_size;i++){
            s1.push(s[i]);
            if(s[i]=='#'){
                if(s1.size()!=0){
                    s1.pop();
                }
                if(s1.size()!=0){
                    s1.pop();
                }
            }
        }
        for(int i=0;i<t_size;i++){
            s2.push(t[i]);
            if(t[i]=='#'){
                if(s2.size()!=0){
                    s2.pop();
                }
                if(s2.size()!=0){
                    s2.pop();
                }
            }
        }

        if(s1.size()==0 && s2.size()==0){
            return true;
        }
        if(s1.size()!=s2.size()){
            return false;
        }
        int len = s1.size();
        for(int i=0;i<len;i++){
            if(s1.top() == s2.top()){
                s1.pop();
                s2.pop();
            }else{
                cout<<"winter";

                return false;
            }
        }
        return true;
    }
};

answer1：重构字符串

其实和我的思路是一样的，但是代码简介，，hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

answer2

双指针

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:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            //解决两个字符串的#
            while (i >= 0) {
                if (S[i] == '#') {
                    skipS++, i--;
                } else if (skipS > 0) {
                    skipS--, i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T[j] == '#') {
                    skipT++, j--;
                } else if (skipT > 0) {
                    skipT--, j--;
                } else {
                    break;
                }
            }
            //没有#了，判断字符串是否相等
            if (i >= 0 && j >= 0) {
                if (S[i] != T[j]) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};

986. 区间列表的交集

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>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> res;
        if(firstList.size() == 0 || secondList.size() == 0) return res;
        int i = 0, j = 0, l, r;
        int len1 = firstList.size();
        int len2 = secondList.size();
        while(i < len1 && j < len2){
            l = max(firstList[i][0], secondList[j][0]);
            r = min(firstList[i][1], secondList[j][1]);
            if(l <= r){ // 找到交集的情况
                vector<int> tmp;
                tmp.push_back(l);
                tmp.push_back(r);
                res.push_back(tmp);
            }
            // 无论是否交汇，j中较小只都应该向前移动
            if(firstList[i][1] == r){
                ++i;
            }else{
                ++j;
            }
        }
        return res;
    }
};

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};

今天用ipad做的，结果找不到代码了，，，，就直接拿的答案，，，

第 5 天 滑动窗口

438. 找到字符串中所有字母异位词

暴力算法，是真的很慢，hhh

image-20210830201604705

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> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.length() < p.length()) return res;
        int length = p.length();
        //暴力循环
        for(int i=0;i<s.length()-p.length()+1;i++){
            if(isyiwei(s.substr(i,length),p)){
                res.push_back(i);
            }
        }
        return res;
    }
    //判断是否是异味，主要是看每个字符的长度是不是一样
    bool isyiwei(string str_a,string str_b){
        int num[26]={0};
        int size = str_a.length();
        for(int i=0;i<size;i++){
            //一个+，一个-，除非str_a和str_b一样，返回true
            num[str_a[i]-'a']+=1;
            num[str_b[i]-'a']-=1;
        }
        for(int i=0;i<26;i++){
            if(num[i]!=0)return false;
        }
        return true;
    }
};

保存，每次加上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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int length_p = p.length();
        int length_s = s.length();
        vector<int>res;
        if(length_p > length_s) return res;//从长度

        //最开始
        vector<int> temp_s(26,0),temp_p(26,0);
        for(int i=0;i<length_p;i++){
            temp_p[p[i]-'a']++;
            temp_s[s[i]-'a']++;
        }
        if(temp_p == temp_s) res.push_back(0);

        //循环加上一位
        for(int i=0;i+length_p<length_s;i++){
            //去掉s[i]，换上s[i+length]，相当于滑动窗口的移动
            temp_s[s[i]-'a']--;
            temp_s[s[i+length_p]-'a']++;
            if(temp_p==temp_s){
                res.push_back(i+1);
            }
        }
        return res;
    }
};

713. 乘积小于K的子数组

由于题目要求是连续的子数组，所以很明显要用滑动窗口进行求解

image-20210830203223375

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 numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1) return 0;
        int n = nums.size();
        int res=0,l=0,r=0;
        int windows_mul = 1;
        while(r<n){
            windows_mul*=nums[r];
            //不满足条件，剔除左边的元素
            while(windows_mul>=k){
                windows_mul/=nums[l];
                l++;
            }
            //满足条件，加入右边的元素
            res += (r-l+1);
            r++;
        }
        return res;
    }
};

209. 长度最小的子数组

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        int ans = INT_MAX;
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                if(sum >= target){
                    ans = min(ans,j-i+1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0:ans;
    }
};

滑动窗口

我照着第二个进行了修改，差一点点，好吧，题目没好好看，找的是>=的最小长度，wuwu

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 minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;

        int res=INT_MAX,l=0,r=0;
        int cur_len;
        int windows_plus = 0;
        while(r<n){
            windows_plus+=nums[r];
            while(windows_plus >= target){
                res = min(res,r-l+1);
                windows_plus -= nums[l];
                l++;
            }
            r++;
        }
        return res == INT_MAX? 0: res;
    }
};

第 6 天 广度优先搜索 / 深度优先搜索

200. 岛屿数量

通过dfs，一次可以把一个岛屿置0，然后循环，找到1，则记作1个岛屿，把改岛屿置零

好像做过类似的题，，，，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
void dfs(vector<vector<char>>& grid,int r,int c){
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c]='0';//遍历过，置0

    if(r-1 >= 0 && grid[r-1][c]=='1') dfs(grid,r-1,c);
    if(r+1 < nr && grid[r+1][c]=='1') dfs(grid,r+1,c);
    if(c-1 >= 0 && grid[r][c-1]=='1') dfs(grid,r,c-1);
    if(c+1 < nc && grid[r][c+1]=='1') dfs(grid,r,c+1);
}
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();

        int num_island = 0;
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    ++num_island;
                    dfs(grid,r,c);
                }
            }
        }
        return num_island;
    }
};

广度优先

其实和深度优先一样，找到一个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
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();

        int num_island = 0;
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    ++num_island;
                    grid[r][c]='0';
                    queue<pair<int,int>> neighbors;
                    neighbors.push({r,c});
                    while(!neighbors.empty()){
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first,col = rc.second;
                        if(row-1>=0 && grid[row-1][col]=='1'){
                            neighbors.push({row-1,col});
                            grid[row-1][col]='0';
                        }
                        if(row+1<nr && grid[row+1][col]=='1'){
                            neighbors.push({row+1,col});
                            grid[row+1][col]='0';
                        }
                        if(col-1>=0 && grid[row][col-1]=='1'){
                            neighbors.push({row,col-1});
                            grid[row][col-1]='0';
                        }
                        if(col+1<nc && grid[row][col+1]=='1'){
                            neighbors.push({row,col+1});
                            grid[row][col+1]='0';
                        }
                    }
                }
            }
        }
        return num_island;
    }
};

并查集

发现是一种new算法，没做过的

通过看了视频学习了一下，讲的真好（鼓掌）

视频链接

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
//固定
class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid){
        count=0;
        int m = grid.size();
        int n = grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    parent.push_back(i*n+j);
                    ++count;
                }else{
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }
    int find(int i){
        if(parent[i]!=i){
            parent[i]=find(parent[i]);
        }
        return parent[i];
    }
    void unit(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx,rooty);
            }
            parent[rooty]=rootx;
            if(rank[rootx]==rank[rooty]) rank[rootx]+=1;
            --count;
        }
    }
    int getCount() const{
        return count;
    }
private:
    vector<int> parent;
    vector<int> rank;
    int count;
};
class Solution{
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();
        UnionFind uf(grid);
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    grid[r][c]=='0';
                    if(r-1>=0 && grid[r-1][c]=='1') uf.unit(r*nc+c,(r-1)*nc+c);
                    if(r+1<nr && grid[r+1][c]=='1') uf.unit(r*nc+c,(r+1)*nc+c);
                    if(c-1>=0 && grid[r][c-1]=='1') uf.unit(r*nc+c,r*nc+c-1);
                    if(c+1<nc && grid[r][c+1]=='1') uf.unit(r*nc+c,r*nc+c+1);
                }
            }
        }
        return uf.getCount();
    }
};

547. 省份数量

深度优先

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:
    void dfs(vector<vector<int>>& isConnected,vector<int>& visited,int provinces,int i){
        for(int j=0;j<provinces;j++){
            if(isConnected[i][j]==1 && !visited[j]){
                visited[j]=1;
                dfs(isConnected,visited,provinces,j);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles=0;
        for(int i=0;i<provinces;i++){
            if(!visited[i]){
                dfs(isConnected,visited,provinces,i);
                circles++;
            }
        }
        return circles;
    }
};

广度优先

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 findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles=0;
        queue<int> Q;
        for(int i=0;i<provinces;i++){
            if(!visited[i]){
                Q.push(i);
                while(!Q.empty()){
                    int j = Q.front();Q.pop();
                    visited[j]=1;
                    for(int k=0;k<provinces;k++){
                        if(isConnected[j][k]==1 && !visited[k]){
                            Q.push(k);
                        }
                    }
                }
                circles++;
            }
        }
        return circles;
    }
};

并查集

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 Find(vector<int>& parent,int index){
        if(parent[index]!=index){
            parent[index]=Find(parent,parent[index]);
        }
        return parent[index];
    }
    void Union(vector<int>& parent,int index1,int index2){
        parent[Find(parent,index1)] = Find(parent,index2);
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> parent(provinces);
        for(int i=0;i<provinces;i++){
            parent[i]=i;
        }
        for(int i=0;i<provinces;i++){
            for(int j=i+1;j<provinces;j++){
                if(isConnected[i][j]==1){
                    Union(parent,i,j);
                }
            }
        }
        int circles=0;
        for(int i=0;i<provinces;i++){
            if(parent[i]==i){
                circles++;
            }
        }
        return circles;
    }
};

第 7 天 广度优先搜索 / 深度优先搜索

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

广度优先

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:
    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            Node *last = nullptr;
            for (int i = 1; i <= n; ++i) {
                Node *f = q.front();
                q.pop();
                if (f->left) {
                    q.push(f->left);
                }
                if (f->right) {
                    q.push(f->right);
                }
                if (i != 1) {
                    last->next = f;
                }
                last = f;
            }
        }
        return root;
    }
};

使用已经建立的next指针

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
/*
// 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:
    void handle(Node* &last,Node* &p,Node* &nextStart){
        if(last){
            last->next=p;
        }
        if(!nextStart){
            nextStart=p;
        }
        last=p;
    }
    Node* connect(Node* root) {
        if(!root){
            return nullptr;
        }
        Node* start = root;
        while(start){
            Node* last = nullptr,*nextStart = nullptr;
            for(Node* p = start;p!=nullptr;p = p->next){
                if(p->left){
                    handle(last,p->left,nextStart);
                }
                if(p->right){
                    handle(last,p->right,nextStart);
                }
            }
            start = nextStart;
        }
        return root;
    }
};

572. 另一棵树的子树

深度优先+暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : 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:
    bool check(TreeNode* root,TreeNode* subRoot){
        if(!root && !subRoot) return true;
        if((root && !subRoot) || (!root && subRoot) || (root->val != subRoot->val)){
            return false;
        }
        return check(root->left,subRoot->left) && check(root->right,subRoot->right);
    }
    bool dfs(TreeNode* root,TreeNode* subRoot){
        if(!root) return false;
        return check(root,subRoot) || dfs(root->left,subRoot) || dfs(root->right,subRoot);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        return dfs(root,subRoot);
    }
};
Q：如果阅读本文需要付费，你是否愿意为此支付1元？