[LeetCode]刷题记录

Introduction

去年刷了不到五十道题，也忘光了，现在接着吧，有些算法真的很奇妙，能用c就用c，不行就c++

小结

2021/9/30

月底了， 也不知道记录了多少道题，十月重新开始了

287. 寻找重复数

2021/9/30

这么简单的代码，第二个while循环想不明了

 1class Solution {
 2public:
 3    int findDuplicate(vector<int>& nums) {
 4        int slow = 0;
 5        int fast = 0;
 6        slow = nums[slow];
 7        fast = nums[nums[fast]];
 8        while(slow != fast){
 9            slow = nums[slow];
10            fast = nums[nums[fast]];
11        }
12        int pre1 = 0;
13        int pre2 = slow;
14        while(pre1 != pre2){
15            pre1 = nums[pre1];
16            pre2 = nums[pre2];
17        }
18        return pre1;
19    }
20};

198. 打家劫舍

2021/9/30

9月最后一天了，

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

215. 数组中的第K个最大元素

2021/9/29

自己写的不如库快

 1class Solution {
 2public:
 3    int findKthLargest(vector<int>& nums, int k) {
 4        int len = nums.size();
 5        //QuickSort(nums,0,len-1);
 6        sort(nums.begin(),nums.end());
 7        return nums[len-k];
 8    }
 9    int Paritition1(vector<int>& nums, int low, int high) {
10        int pivot = nums[low];
11        while (low < high) {
12            while (low < high && nums[high] >= pivot) {
13                --high;
14            }
15            nums[low] = nums[high];
16            while (low < high && nums[low] <= pivot) {
17                ++low;
18            }
19            nums[high] = nums[low];
20        }
21        nums[low] = pivot;
22        return low;
23    }
24
25    void QuickSort(vector<int>& nums, int low, int high) //快排母函数
26    {
27        if (low < high) {
28            int pivot = Paritition1(nums, low, high);
29            QuickSort(nums, low, pivot - 1);
30            QuickSort(nums, pivot + 1, high);
31        }
32    }
33};

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

2021/9/29

递归总是感觉会，总是感觉不会

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10 //递归思想博大精深，害
11class Solution {
12public:
13    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
14        if(!root)return NULL;
15        if(root == p || root == q)return root;
16        TreeNode* left = lowestCommonAncestor(root->left,p,q);
17        TreeNode* right = lowestCommonAncestor(root->right,p,q);
18        if(!left)return right;
19        if(!right)return left;
20        return root;
21    }
22};

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

2021/9/29

知道用什么解决，实现起来真难，这个题花的时间有点多了，自己的代码不能参考别人的= =

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
15        int len = preorder.size();
16        if(!len)return nullptr;
17        return build(preorder,inorder,0,len-1,0,len-1);
18
19    }
20    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int pre_left,int pre_right,int in_left,int in_right){
21        if(pre_right < pre_left)return nullptr;
22        TreeNode *root = new TreeNode(preorder[pre_left]);
23        int in_mid = 0;
24        for(int i = in_left ; i <= in_right ; ++i ){
25            if(inorder[i] == root->val)break;
26            ++in_mid;
27        }
28        root->left = build(preorder,inorder,pre_left+1,pre_left+in_mid,in_left,in_left+in_mid-1);
29        root->right = build(preorder,inorder,pre_left+in_mid+1,pre_right,in_left+in_mid+1,in_right);
30        return root;
31
32    }
33};
34

98. 验证二叉搜索树

2021/9/28

越来越熟练

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    vector<int> res;
15    bool isValidBST(TreeNode* root) {
16        if(!root)return false;
17        order(root);
18        for(int i = 1 ; i < res.size() ; ++i){
19            if(res[i-1]>=res[i])
20            return false;
21        }
22        return true;
23    }
24    void order(TreeNode* root){
25        if(root){
26            order(root->left);
27            res.push_back(root->val);
28            order(root->right);
29        }
30    }
31};

96. 不同的二叉搜索树

2021//28

这个用数学方法还是不错的，可惜想不到

 1class Solution {
 2public:
 3    int numTrees(int n) {
 4        vector<int> G(n + 1, 0);
 5        G[0] = 1;
 6        G[1] = 1;
 7        for (int i = 2; i <= n; ++i) {
 8            for (int j = 1; j <= i; ++j) {
 9                G[i] += G[j - 1] * G[i - j];
10            }
11        }
12        return G[n];
13    }
14};
15

75. 颜色分类

2021/9/28

这么简单怎么就是想不明白

 1class Solution {
 2public:
 3    void sortColors(vector<int>& nums) {
 4        int len = nums.size();
 5        int i = 0,p = 0, q = len-1;
 6        while(i <= q && i >= p){
 7            if(nums[i] == 2){
 8                swap(nums[i],nums[q]);
 9                --q;
10            }else if(nums[i] == 0){
11                swap(nums[i],nums[p]);
12                ++p;
13                if(i<p)i=p;
14            }else{
15                ++i;
16            }
17        }
18    }
19};

64. 最小路径和

2021/9/27

希望越来越熟悉

动态规划，记住思想

 1class Solution {
 2public:
 3    int minPathSum(vector<vector<int>>& grid) {
 4        int row = grid.size();
 5        int col = grid[0].size();
 6        for(int i = 0 ; i < row ; ++i){
 7            for(int j = 0 ; j < col ; ++j){
 8                if(i==0 && j==0)continue;
 9                if(i==0 && j!=0)grid[i][j] += grid[i][j-1];
10                if(i!=0 && j==0)grid[i][j] += grid[i-1][j];
11                if(i!=0 && j!=0)grid[i][j] += min(grid[i-1][j],grid[i][j-1]);
12            }
13        }
14        return grid[row-1][col-1];
15    }
16};

55. 跳跃游戏

2021/9/27

不配中等难度

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

56. 合并区间

2021/9/26

函数参数压栈问题，先后问题（无关算法本身）

 1class Solution {
 2public:
 3    vector<vector<int>> merge(vector<vector<int>>& intervals) {
 4        sort(intervals.begin(), intervals.end());
 5        int len = intervals.size();
 6        vector<vector<int>> ans;
 7        for(int i = 0; i < len;){
 8            int x = intervals[i][0];
 9            int y = intervals[i][1];
10            while(i < len && y >= intervals[i][0] ){
11                x = min(x,intervals[i][0]);
12                y = max(y,intervals[i][1]);
13                i++;
14            }
15            ans.push_back({x,y});
16        }
17        return ans;
18    }
19};

49. 字母异位词分组

2021/9/26

c++ 用的太不熟练了

 1class Solution {
 2public:
 3    vector<vector<string>> groupAnagrams(vector<string>& strs) {
 4        unordered_map<string,vector<string>> map;
 5        for(string& str:strs){
 6            string key = str;
 7            sort(key.begin(),key.end());
 8            map[key].emplace_back(str);
 9        }
10        vector<vector<string>> ans;
11        for(auto it = map.begin();it != map.end();it++){
12            ans.emplace_back(it->second);
13        }
14        return ans;
15    }
16};

347. 前k个高频元素

2021/9/25

想到办法了，可是实现不会，尴尬

 1class Solution {
 2public:
 3    vector<int> topKFrequent(vector<int>& nums, int k) {
 4        int len = nums.size();
 5        vector<pair<int,int>> res;
 6        unordered_map<int,int> hash;
 7        for(int i = 0 ; i < len ; i++){
 8            hash[nums[i]]++;
 9        }
10        for(auto it=hash.begin();it!=hash.end();it++)res.push_back({it->second,it->first});
11        sort(res.rbegin(),res.rend());
12        vector<int> ans;
13        for(int i=0;i<k;i++)ans.push_back(res[i].second);
14        return ans;
15    }
16};

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

2021/9/24

二分法

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

33. 搜索旋转排序数组

2021/9/24

二分法，细节处理不到位

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

394. 字符串解码

2021/9/23 周四

栈 ，不看递归了

 1class Solution {
 2public:
 3    string res = "";
 4    stack<int> ints;
 5    stack<string> strs;
 6    string decodeString(string s) {
 7        int num = 0 ;
 8        int len = s.size();
 9        for(int i = 0 ; i < len ; i++){
10            if(s[i] >= '0' && s[i] <= '9'){
11                num = num * 10 + s[i] - '0';
12            }else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')){
13                res += s[i];
14            }else if(s[i] == '['){
15                ints.push(num);
16                strs.push(res);
17                num = 0;
18                res = "";
19            }else{
20                for(int i = 0 ; i < ints.top() ; i++)strs.top() += res;
21                res = strs.top();
22                strs.pop();
23                ints.pop();
24            }
25        }
26        return res;
27    }
28};

416. 分割等和子集

2021/9/23 周四

算法真心不能盲目刷，搞懂原理比题更重要，一道题优化了好几遍

 1// 最终代码
 2class Solution {
 3public:
 4    bool canPartition(vector<int>& nums) {
 5        int len = nums.size();
 6        if(len < 2)return false;
 7        int sum = accumulate(nums.begin(),nums.end(),0);
 8        int max_num =  *max_element(nums.begin(), nums.end());
 9        if((sum&1) == 1)return false;
10  
11        int target = sum / 2;
12        if(max_num > target)return false;
13        vector<int> dp(target+1,0);
14        dp[0] = true;
15        if(nums[0] < target)dp[nums[0]] = true;
16        for(int i = 1 ; i < len ; i++){
17            for(int j = target ; j >= 0 && nums[i] <= j ; j--) dp[j] = dp[j]|dp[j-nums[i]];
18            if(dp[target])return true;
19        }
20        return dp[target];
21    }
22};
23//未优化前
24class Solution {
25public:
26    bool canPartition(vector<int>& nums) {
27        int len = nums.size();
28        int sum = 0;
29        for(int num : nums){
30            sum += num;
31        }
32        if((sum&1) == 1){
33            return false;
34        }
35        int target = sum / 2;
36        vector<vector<int>> dp(len,vector<int>(target+1,0));
37        for(int i = 0 ; i< len ;i++)dp[i][0] = true;
38        if(nums[0] < target)dp[0][nums[0]] = true;
39
40        for(int i = 1 ; i < len ; i++){
41            for(int j = 0 ; j <= target ; j++){
42                dp[i][j] = dp[i-1][j];
43
44                if(nums[i] == j){
45                    dp[i][j] = true;
46                    continue;
47                }
48                if(nums[i] < j)dp[i][j] = dp[i-1][j]|dp[i-1][j-nums[i]];
49            }
50        }
51        return dp[len-1][target];
52    }
53};

437. 路径总和 |||

2021/9/22

双递归，无敌

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int pathSum(TreeNode* root, int targetSum) {
15         if(!root)return 0;
16         return dfs(root,targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
17    }
18    int dfs(TreeNode* root,int sum){
19        if(!root)return 0;
20        sum -= root->val;
21        return sum == 0 ? 1 + dfs(root->left,sum)+dfs(root->right,sum):dfs(root->left,sum)+dfs(root->right,sum);
22    }
23};

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

2021/9/22

算法为什么自己想不到

 1class Solution {
 2public:
 3    vector<int> findAnagrams(string s, string p) {
 4        int M = s.size(),N = p.size(),i=0;
 5        if(N > M )return {};
 6        vector<int> res,S_vec(26),P_vec(26);
 7        for(;i < N;i++){
 8            S_vec[s[i]-'a']++;
 9            P_vec[p[i]-'a']++;
10        }
11        if(S_vec == P_vec)res.push_back(0);
12        for(;i < M ;i++){
13            S_vec[s[i]-'a']++;
14            S_vec[s[i - N]-'a']--;
15            if(S_vec == P_vec)res.push_back(i - N +1);
16        }
17        return res;
18    }
19};

494. 目标和

2021/9/22

动态规划不会了，深搜吧

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

560. 和为k的子数组

2021/9/20

前缀和，加上hash

 1class Solution {
 2public:
 3    int subarraySum(vector<int>& nums, int k) {
 4        unordered_map<int,int> mp;
 5        mp[0] = 1;
 6        int count = 0 , pre = 0;
 7        for(int& x : nums){
 8            pre += x;
 9            if (mp.find(pre - k) != mp.end()){
10                count += mp[pre-k];
11            }
12            mp[pre]++;
13        }
14        return count;
15    }
16};

581. 最短无序连续子数组

2021/9/20

题目都开始看不懂要干什么了，为什么别人的方法都这么好

 1class Solution {
 2public:
 3    int findUnsortedSubarray(vector<int>& nums) {
 4        int len = nums.size();
 5        int max = nums[0];
 6        int min = nums[len - 1];
 7        int l = 0,r = len -1;
 8        for(int i = 0 ; i < len ; i++){
 9            if(max <= nums[i]){
10                max = nums[i];
11            }else{
12                l = i;
13            }
14        }
15        for(int i = len -1  ; i >= 0 ; i--){
16            if(min >= nums[i]){
17                min = nums[i];
18            }else{
19                r = i;
20            }
21        }
22        if(l == 0 && r == len-1)return 0;
23        return l-r+1;
24    }
25};

621. 任务调度器

2021/9/19

桶，分析题目太重要

 1class Solution {
 2public:
 3    int leastInterval(vector<char>& tasks, int n) {
 4        int len = tasks.size(),j=1;
 5        vector<int> vec(26);
 6        for(char c : tasks)++vec[c-'A'];
 7        sort(vec.rbegin(),vec.rend());
 8        while(j<vec.size()&&vec[j]==vec[0])++j;
 9        return max(len,j+(n+1)*(vec[0]-1));
10    }
11};
12

114. 二叉树展开为链表

2021/9/19

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    void flatten(TreeNode* root) {
15        vector<TreeNode *> st;
16        pre_order(root,st);
17        for(int i = 1 ; i < st.size() ; i++){
18            TreeNode *prev = st.at(i - 1), *curr = st.at(i);
19            prev->left = nullptr;
20            prev->right = curr;
21        }
22    }
23    void pre_order(TreeNode *root,vector<TreeNode*> &st){
24        if(root){
25            st.push_back(root);
26            pre_order(root->left,st);
27            pre_order(root->right,st);
28        }
29    }
30};

739. 每日温度

2021/9/18

暴力法可以解，堆栈解决O(n) c++基础忘记的太多了

 1class Solution {
 2public:
 3    vector<int> dailyTemperatures(vector<int>& temperatures) {
 4        int n = temperatures.size();
 5        vector<int> res (n,0);
 6        stack<int> st;
 7        for(int i = 0 ; i < n ; ++i){
 8            while(!st.empty() && temperatures[i] > temperatures[st.top()]){
 9                int t = st.top();
10                st.pop();
11                res[t] = i - t;
12            }
13            st.push(i);
14        }
15        return res;
16    }
17};

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

2021/9/18

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int sum = 0;
15    TreeNode* convertBST(TreeNode* root) {
16        if(root){
17            convertBST(root->right);
18            sum += root->val;
19            root->val = sum ;
20            convertBST(root->left);
21        }
22        return root;
23    }
24};

647. 回文子串

2021/9/17

 1class Solution {
 2private:
 3    int res=0;
 4public:
 5    int countSubstrings(string s) {
 6        if(!s.size())return 0;
 7        for(int i = 0 ; i < s.length();i++){
 8            aen(s,i,i);
 9            aen(s,i,i+1);
10        }
11        return res;
12    }
13    void aen(string s,int left,int right ){
14        while(left >= 0 && right < s.length()&& s[left--] == s[right++]){
15            ++res;
16        }   
17    }
18};

337. 打家劫舍|||

2021/9/17

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13private:
14    unordered_map <TreeNode*, int> q,p; // p 父节点不偷
15public:
16    int rob(TreeNode* root) {
17        rob_max(root);
18        return max(p[root],q[root]);
19    }
20    void rob_max(TreeNode *node){
21        if(!node)return ;
22        rob_max(node->left);
23        rob_max(node->right);
24        q[node] = node->val + p[node->left]+p[node->right];
25        p[node] = max(p[node->left],q[node->left])+ max(p[node->right],q[node->right]);
26    }
27};

208. 实现Trie 前缀树

2021/9/17

 1class Trie {
 2private:
 3    vector<Trie*> children;
 4    bool isEnd;
 5
 6    Trie* search_Aen(string word){
 7        Trie* node = this;
 8        for(char ch : word){
 9            if(node->children[ch-'a'] == nullptr)return nullptr;
10            node = node->children[ch-'a'];
11        }
12        return node;
13    }
14public:
15    /** Initialize your data structure here. */
16    Trie():children(26),isEnd(false) {}
17    /** Inserts a word into the trie. */
18    void insert(string word) {
19        Trie *node = this;
20        for(char ch : word){
21            if(node->children[ch-'a'] == nullptr)node->children[ch-'a'] = new Trie();
22            node = node->children[ch-'a'];
23        }
24        node->isEnd = true;
25    }
26    /** Returns if the word is in the trie. */
27    bool search(string word) {
28        Trie *node = this->search_Aen(word);  
29        return node != nullptr && node->isEnd;
30    }
31  
32    /** Returns if there is any word in the trie that starts with the given prefix. */
33    bool startsWith(string prefix) {
34        return this->search_Aen(prefix)!= nullptr;
35    }
36};
37
38/**
39 * Your Trie object will be instantiated and called as such:
40 * Trie* obj = new Trie();
41 * obj->insert(word);
42 * bool param_2 = obj->search(word);
43 * bool param_3 = obj->startsWith(prefix);
44 */

Algorithms

279. 完全平方数

2021/9/16

背包问题，半懂不懂的，动态规划，脑子真是个好东西忘干净了

 1class Solution {
 2public:
 3    int numSquares(int n) {
 4        vector<int> f(n+1);
 5        for(int i = 1; i <= n ; i++){
 6            int min_num = INT_MAX;
 7            for (int j = 1 ; j*j <= i; j++){
 8                min_num = min(min_num,f[i-j*j]);
 9            }
10            f[i] = min_num + 1;
11        }
12        return f[n];
13    }
14};

146. LRU缓存机制

2021/9/15

双向链表，哈希表，这都不重要重要的是重新了解了LRU的缓存机制

 1struct Aen_link_node{
 2    int key;
 3    int value;
 4    Aen_link_node *prev;
 5    Aen_link_node *next;
 6    Aen_link_node():key(0),value(0),prev(nullptr),next(nullptr){}
 7    Aen_link_node(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
 8};
 9
10class LRUCache {
11private:
12    unordered_map<int, Aen_link_node*> cache;
13    Aen_link_node* head;
14    Aen_link_node* tail;
15    int size;
16    int capacity;
17public:
18    LRUCache(int _capacity):capacity(_capacity),size(0) {
19        head = new Aen_link_node();
20        tail = new Aen_link_node();
21        head->next = tail;
22        tail->prev = head;
23    }
24    int get(int key) {
25        if(!cache.count(key))return -1;
26        return move_to_head(cache[key])->value;
27    }
28  
29    void put(int key, int value) {
30        if(!cache.count(key)){
31            Aen_link_node *node = new Aen_link_node(key,value);
32            cache[key] = node;
33            add_data_to_head(node);
34            ++size;
35            if(size > capacity){
36                Aen_link_node *del_node = delete_tail_node();
37                cache.erase(del_node->key);
38                delete(del_node);
39                --size;
40            }
41        }else{
42            Aen_link_node *node = cache[key];
43            node->value = value;
44            move_to_head(node);
45        }
46    }
47
48    void add_data_to_head(Aen_link_node *node){
49        node->prev = head;
50        node->next = head->next;
51        head->next->prev = node;
52        head->next = node;
53    }
54    void delete_node(Aen_link_node *node){
55        node->prev->next = node->next;
56        node->next->prev = node->prev;
57    }
58    Aen_link_node* move_to_head(Aen_link_node *node){
59        delete_node(node);
60        add_data_to_head(node);
61        return node;
62    }
63    Aen_link_node* delete_tail_node(){
64        Aen_link_node *node = tail->prev;
65        delete_node(node);
66        return node;
67    }
68};
69/**
70 * Your LRUCache object will be instantiated and called as such:
71 * LRUCache* obj = new LRUCache(capacity);
72 * int param_1 = obj->get(key);
73 * obj->put(key,value);
74 */

148.排序链表

2021/9/14

归并排序，代码有个小错误真的烦，没有错误的那种 = 写成 ==

 1/**
 2 * Definition for singly-linked list.
 3 * struct ListNode {
 4 *     int val;
 5 *     ListNode *next;
 6 *     ListNode() : val(0), next(nullptr) {}
 7 *     ListNode(int x) : val(x), next(nullptr) {}
 8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9 * };
10 */
11class Solution {
12public:
13    ListNode* sortList(ListNode* head) {
14        return sortA(head,nullptr);
15    }
16
17    ListNode* sortA(ListNode *head,ListNode *tmp){
18        if(head == nullptr)return head;
19        if(head->next == tmp){
20            head->next = nullptr;
21            return head;
22        }
23        ListNode *fast = head,*low = head;
24        while(fast != tmp){
25            fast = fast->next;
26            low = low->next;
27            if(fast != tmp){
28                fast = fast->next;
29            }
30        }
31        return merge(sortA(head,low),sortA(low,tmp));
32    }
33
34    ListNode* merge(ListNode *p,ListNode *q){
35        ListNode* resHead = new ListNode(0);
36        ListNode *res = resHead,*pp = p,*qq = q;
37        while(pp != nullptr && qq != nullptr){
38            if(pp->val <= qq->val){
39                res->next = pp;
40                pp = pp->next;
41            }else{
42                res->next = qq;
43                qq = qq->next;
44            }
45            res = res->next;
46        }
47        if(pp)res->next = pp;
48        if(qq )res->next = qq;
49        return resHead->next;
50    }
51};

78.子集

2021/9/13

二进制思想

回溯算法 也挺好

 1class Solution {
 2public:
 3    vector<int> tmp;
 4    vector<vector<int>> res;
 5    vector<vector<int>> subsets(vector<int>& nums) {
 6        int length = nums.size();
 7        for(int i = 0 ; i < (1 << length ) ; ++i){
 8            tmp.clear();
 9            for(int j = 0 ; j < length ; ++j){
10                if( i & (1 << j)){
11                    tmp.push_back(nums[j]);
12                }
13            }
14            res.push_back(tmp);
15        }
16        return res;
17    }
18};

39.组和总和

2021/9/12

 1class Solution {
 2public:
 3    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx){
 4        if (idx == candidates.size()) {
 5            return;
 6        }
 7        if (target == 0) {
 8            ans.emplace_back(combine);
 9            return;
10        }
11  
12        dfs(candidates, target, ans, combine, idx + 1);
13  
14        if (target - candidates[idx] >= 0) {
15            combine.emplace_back(candidates[idx]);
16            dfs(candidates, target - candidates[idx], ans, combine, idx);
17            combine.pop_back();
18        }
19    }
20
21    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
22        vector<vector<int>> ans;
23        vector<int> combine;
24        dfs(candidates, target, ans, combine, 0);
25        return ans;
26    }
27
28};

46.全排列

2021/9/11

c++ 真的忘干净了

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

31.下一个排列

2021/9/10

c++ 开始练练手

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