持续更新

数组

三树之和

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
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    if(nums.size()<3) return ans;
    sort(nums.begin(), nums.end());
    if(nums[0]>0) return ans;
    int i = 0;
    while(i<nums.size()-2){
        if(nums[i]>0) break;        //将这个if语句放这里提前终止循环
        int left = i+1, right = nums.size()-1;
        while(left< right){
            
            // 转换为long long避免加法过程中溢出
            long long y = static_cast<long long>(nums[i]);
            long long x = static_cast<long long>(nums[left]);
            long long z = static_cast<long long>(nums[right]);
            if(x + y >0-z)
                right--;
            else if(x + y <0-z)
                left++;
            else{
                ans.push_back({nums[i], nums[left], nums[right]});
                // 相同的left和right不应该再次出现，因此跳过
                while(left<right&&nums[left]==nums[left+1])
                    left++;
                while(left<right&&nums[right] == nums[right-1])
                    right--;
                left++;
                right--;
            }
        }
        // 避免nums[i]作为第一个数重复出现
        // while(i+1<nums.size()&&nums[i] == nums[i+1]) i++;
        // i++;
        do{i++;}while(i+1<nums.size()&&nums[i-1] == nums[i]);
    }
    return ans;
}

查找

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = (right - left) / 2 + left;
        int num = nums[mid];
        if (num == target) {
            return mid;
        } else if (num > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

LRU

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 LRUCache {
    int capacity;
    list<pair<int,int>> cachelist;//实际缓存列表
    unordered_map<int,decltype(cachelist.begin())> cache;
    //保存的缓存的迭代器
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    int get(int key) {
        if (!cache.count(key))
            return -1;
        // cout<<"cend:"<<  ->first;
        // 将缓存中的键值对移动到缓存列表的末尾，表示最近使用
        cachelist.splice(cachelist.cend(), cachelist, cache[key]);
        return cache[key]->second;
    }
    
    void put(int key, int value) {
        if(!cache.count(key)){//缓存列表里没有出现要进入的k
            //如果满了，就把最前删掉，然后加到链表尾
            if(cachelist.size()==capacity){
                // 移除最久未使用的键值对
                cache.erase(cachelist.front().first); // 从缓存映射中删除对应的键
                cachelist.pop_front(); // 从缓存列表中删除最前面的元素
            }
            cache[key] = cachelist.emplace(cachelist.cend(),key,value);

        }else{//缓存列表里有这个新来的任务
            //根据key更新任务内容
            cache[key]->second = value;
            //把这个迭代器插入队尾
            cachelist.splice(cachelist.cend(),cachelist,cache[key]);
        }
    }
};

二叉树

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>>res;
    if(!root){
        return res;
    }
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        vector<int> tmp;
        // for(int i=0; i<q.size() ;i++){
            //因为q在增加，可以先在外面int n =q.size()
            // 再for(int i=0; i<n ;i++){
        for(int i = q.size(); i > 0; --i) {
            root = q.front();
            q.pop();
            tmp.push_back(root->val);
            if(root->left) q.push(root->left);
            if(root->right) q.push(root->right);
        }
        res.push_back(tmp);
    }
    return res;
}

最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root){
        return nullptr;
    }
    if(root==p || root==q){
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left,p,q);
    TreeNode* right = lowestCommonAncestor(root->right,p,q);
    if(!left){
        return right;
    }
    if(!right){
        return left;
    }
    if(left && right){
        return root;
    }
    return nullptr;
}

二叉树最大直径 dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int depth(TreeNode* root,int &res){
        if(!root) return 0;
        int l = depth(root->left,res);
        int r = depth(root->right,res);
        res = max(res, l+ r );
        return max(l,r)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int res = 0;
        depth(root,res);
        return res;
    }
};

翻转二叉树

1
递归左右子树

二叉搜索树第k小的元素【没懂，记住了】

迭代方法，在找到答案后停止，不需要遍历整棵树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode* > nodes;
        while(root && nodes.size() >0){
            while(root){
                stack.push(root); //左子树一直进栈
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            k--;
            if(k==0) break;
            root = root->right;
        }
        return root->val;
    }
};

判断树a是否是b的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL) {
    }
};
 
bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if (pRoot1 == NULL && pRoot2 != NULL)
        return false;
    if (pRoot2 == NULL)
        return true;
    if (pRoot1->val != pRoot2->val)
        return false;
    return isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    bool result = false;
    if (pRoot1 != NULL && pRoot2 != NULL)
    {
        if (pRoot1->val == pRoot2->val) {
            result = isSubtree(pRoot1, pRoot2);
        }
        if (!result)
            result = HasSubtree(pRoot1->left, pRoot2);
        if (!result)
            result = HasSubtree(pRoot1->right, pRoot2);
    }
    return result;
}

链表

k个一组翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
ListNode * reverse(ListNode* head){
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur){
        ListNode* next;
        next = cur->next;
        cur->next =pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* newnode=new ListNode(0);
        //必须要
        newnode ->next = head;
        ListNode* pre = newnode;
        //先找需要翻转的前一个节点
        for(int i=0;i<left-1 ;i++){
            pre = pre->next;
        }
        ListNode* cur = pre->next;
        for(int i=0;i<right-left;i++){
            ListNode* next = cur->next;
            cur->next =next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return newnode->next;
    }
};

链表相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //哈希表
        unordered_map<ListNode*,int>mp;
        ListNode* cur1=headA;
        while(cur1){
            mp[cur1]++;
            cur1=cur1->next;
        }
        ListNode* cur2=headB;
        while(cur2){
            if(mp[cur2]) return cur2;
            cur2=cur2->next;
        }
        return nullptr;
    }
};

滑动窗口

无重复的最长子串/无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> appears;// 判断是否重复
        int res;
        int pos = 0,len = s.length();
        for (int left =0 ;left <len;left++){
            if(left!=0){ // 只要下面的循环扫描一遍，就会来这里left++
            //说明往右移走了一位，最左边字母删掉
                appears.erase(s[left-1]);
            }
            while(pos < len && !appears.count(s[pos])){
                appears.insert(s[pos]);
                pos++;
            }
            res = max(res,pos - left);
        }
        return res;
    }
};

判断s中是否有字符串st的排列

https://leetcode.cn/problems/permutation-in-string/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool checkInclusion(string s1, string s2) {
    int n = s1.length(), m = s2.length();
    if (n > m) {
        return false;
    }
    vector<int> cnt(26);
    for (int i = 0; i < n; ++i) {
        cnt[s1[i] - 'a'] -- ;
    }
    int left = 0;
    for (int right = 0; right < m; ++right) {
        int x = s2[right] - 'a';
        cnt[x]++;
        while (cnt[x] > 0) {
            cnt[s2[left] - 'a'] --;
            left++;
        }
        if (right - left + 1 == n) {
            return true;
        }
    }
    return false;
}

DP

最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLIS(vector<int>& nums) {//O(n^2)
    int n = nums.size();
    if(n==1) return 1;
    int dp[n];//dp[i]定义为num数组前i个里面最长的上升子序列长度
    // memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++) dp[i]=1;
    int ans=dp[0];
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){//比较i前所有的数，
            if(nums[j]<nums[i]){
                dp[i]=dp[j]+1 > dp[i] ? dp[j]+1 :dp[i];
            }
        }
        ans = ans > dp[i]? ans:dp[i];
    }
    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
int lengthOfLIS(vector<int>& nums) {//O(nlog2n) 抄的评论区
    /**
    dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
    由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度. 
    对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
    1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
        数组尾部, 并将最长递增序列长度maxL加1
    2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
    **/
    int maxL = 0;
    int n = nums.size();
    int dp[n];
    for(auto num : nums) {
        // 二分法查找, 也可以调用库函数如binary_search
        int low = 0, high = maxL;
        while(low < high) {
            int mid = low+(high-low)/2;
            if(dp[mid] < num)
                low = mid+1;
            else
                high = mid;
        }
        dp[low] = num;
        if(low == maxL)
            maxL++;
    }
    return maxL;
}

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(),n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(text1[i]==text2[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

最大子数组/子序和

1
2
3
4
5
6
7
8
9
10
11
12
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int dp[n];
    memset(dp,0,sizeof(dp));
    dp[0]=nums[0];
    int maxn = dp[0];
    for(int i=1;i<n;i++) {
        dp[i]=max(nums[i],dp[i-1]+nums[i]);
        maxn = max(maxn,dp[i]);
    }
    return maxn;
}

最长重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

打家劫舍【有限制的dp】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int rob(vector<int>& nums) {//dp[i] =max(dp[i-1]跳过这间，dp[i-2]+nums[i])
        int n = nums.size();
        if(n==0)return 0;
        if(n==1)return nums[0];
        int dp[n];
        memset(dp,0,sizeof(dp));
        dp[0]=nums[0];
        dp[1]=max(nums[1],nums[0]);
        for(int i=2;i<n ;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return max(dp[n-1],dp[n-2]);
    }
};

排序

第K个最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }
    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void merge_sort(vector<int>& nums, int left, int right){
    if(left>=right)
        return;
    int mid = (left+right)>>1;
    merge_sort(nums, left, mid);
    merge_sort(nums, mid+1, right);
    //递归调用完成后，[left,mid]和[mid+1,right]两个区间已经有序(升序)
    int i = left;
    int j = mid + 1;
    int count = 0;
    while(i<=mid && j<=right){
        //如果 nums[i] <= nums[j]那么就将nums[i]放入temp中，然后i++
        if(nums[i]<=nums[j]){
            temp[count] = nums[i];
            i++;
        }else{
            temp[count] = nums[j];
            j++;
        }
        count++;
    }
    while(i<=mid)
        temp[count++] = nums[i++];
    while(j<=right)
        temp[count++] = nums[j++];
    int interval_length = right-left+1;
    for(int i = 0; i<interval_length; i++)
        nums[i+left]=temp[i];
}

快排/快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    void quickSort(vector<int>&nums, int startIndex, int endIndex) {
        if (startIndex >= endIndex) return;
        int l = startIndex, r = endIndex;
        int pivot = rand() % (endIndex - startIndex + 1) + startIndex; // 基于随机的原则
        int pivotnum = nums[pivot];
        swap(nums[startIndex], nums[pivot]);
        while (l < r) {
            // 从后往前走，将比第一个小的移到前面
            while (l < r && nums[r] >= pivotnum) r--;
            if (l < r) {
                nums[l] = nums[r];
            }
            // 从前往后走，将比第一个大的移到后面
            while (l < r && nums[l] <= pivotnum) l++;
            if (l < r) {
                nums[r] = nums[l];
            }
            
        }
        nums[l] = pivotnum; 
        // 自顶向下
        quickSort(nums, startIndex, l - 1);
        quickSort(nums, l + 1, endIndex);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        quickSort(nums, 0, n - 1);
        return nums;
    }
};

归并

LRU

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 LRUCache {
    int capacity;
    list<pair<int,int>> cachelist;//实际缓存列表
    unordered_map<int,decltype(cachelist.begin())> cache;
    //保存的缓存的迭代器
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (!cache.count(key))
            return -1;
        // cout<<"cend:"<<  ->first;
        // 将缓存中的键值对移动到缓存列表的末尾，表示最近使用
        cachelist.splice(cachelist.cend(), cachelist, cache[key]);
        return cache[key]->second;
    }
    void put(int key, int value) {
        if(!cache.count(key)){//缓存列表里没有出现要进入的k
            //如果满了，就把最前删掉，然后加到链表尾
            if(cachelist.size()==capacity){
                // 移除最久未使用的键值对
                cache.erase(cachelist.front().first); 
                // 从缓存映射中删除对应的键
                cachelist.pop_front(); // 从缓存列表中删除最前面的元素
            }
            cache[key] = cachelist.emplace(cachelist.cend(),key,value);

        }else{//缓存列表里有这个新来的任务
            //根据key更新任务内容
            cache[key]->second = value;
            //把这个迭代器插入队尾
            cachelist.splice(cachelist.cend(),cachelist,cache[key]);
        }
    }
};

DFS

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool>visited(nums.size(),false);
        vector<int>perm;
        dfs(ans,nums,visited,perm);
        return ans;
    }
    void dfs(vector<vector<int>>& ans,vector<int>& nums, vector<bool>& visited,vector<int>& perm){
        if(nums.size()==perm.size()){
            ans.push_back(perm);
        }
        for(int i=0;i<nums.size();i++){
            if(!visited[i]){
                perm.push_back(nums[i]);
                visited[i]=true;
                dfs(ans,nums,visited,perm);
                perm.pop_back();
                visited[i]=false;
            } 
        }
    }
};

岛屿周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func islandPerimeter(grid [][]int) int {
	var land, border int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				land++
				if i < len(grid)-1 && grid[i+1][j] == 1 {
					border++
				}
				if j < len(grid[0])-1 && grid[i][j+1] == 1 {
					border++
				}
			}
		}
	}
	return 4*land - 2*border
}