[LeetCode]刷题记录

2021-05-07 / 2021-09-30 / leetcode

[LeetCode]刷题记录

Introduction

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

小结

2021/9/30

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

287. 寻找重复数

2021/9/30

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

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int pre1 = 0;
        int pre2 = slow;
        while(pre1 != pre2){
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
};

198. 打家劫舍

2021/9/30

9月最后一天了，

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if(len == 1)return nums[0];
        vector<int> dp(len,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2 ; i < len ; ++i){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[len-1];
    }
};

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

2021/9/29

自己写的不如库快

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        //QuickSort(nums,0,len-1);
        sort(nums.begin(),nums.end());
        return nums[len-k];
    }
    int Paritition1(vector<int>& nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) {
                --high;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) {
                ++low;
            }
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    void QuickSort(vector<int>& nums, int low, int high) //快排母函数
    {
        if (low < high) {
            int pivot = Paritition1(nums, low, high);
            QuickSort(nums, low, pivot - 1);
            QuickSort(nums, pivot + 1, high);
        }
    }
};

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

2021/9/29

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //递归思想博大精深，害
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)return NULL;
        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;
        return root;
    }
};

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

2021/9/29

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

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = preorder.size();
        if(!len)return nullptr;
        return build(preorder,inorder,0,len-1,0,len-1);

    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int pre_left,int pre_right,int in_left,int in_right){
        if(pre_right < pre_left)return nullptr;
        TreeNode *root = new TreeNode(preorder[pre_left]);
        int in_mid = 0;
        for(int i = in_left ; i <= in_right ; ++i ){
            if(inorder[i] == root->val)break;
            ++in_mid;
        }
        root->left = build(preorder,inorder,pre_left+1,pre_left+in_mid,in_left,in_left+in_mid-1);
        root->right = build(preorder,inorder,pre_left+in_mid+1,pre_right,in_left+in_mid+1,in_right);
        return root;

    }
};

98. 验证二叉搜索树

2021/9/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:
    vector<int> res;
    bool isValidBST(TreeNode* root) {
        if(!root)return false;
        order(root);
        for(int i = 1 ; i < res.size() ; ++i){
            if(res[i-1]>=res[i])
            return false;
        }
        return true;
    }
    void order(TreeNode* root){
        if(root){
            order(root->left);
            res.push_back(root->val);
            order(root->right);
        }
    }
};

96. 不同的二叉搜索树

2021//28

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

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
};

75. 颜色分类

2021/9/28

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

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int i = 0,p = 0, q = len-1;
        while(i <= q && i >= p){
            if(nums[i] == 2){
                swap(nums[i],nums[q]);
                --q;
            }else if(nums[i] == 0){
                swap(nums[i],nums[p]);
                ++p;
                if(i<p)i=p;
            }else{
                ++i;
            }
        }
    }
};

64. 最小路径和

2021/9/27

希望越来越熟悉

动态规划，记住思想

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        for(int i = 0 ; i < row ; ++i){
            for(int j = 0 ; j < col ; ++j){
                if(i==0 && j==0)continue;
                if(i==0 && j!=0)grid[i][j] += grid[i][j-1];
                if(i!=0 && j==0)grid[i][j] += grid[i-1][j];
                if(i!=0 && j!=0)grid[i][j] += min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[row-1][col-1];
    }
};

55. 跳跃游戏

2021/9/27

不配中等难度

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        int max_location = 0;
        for(int i = 0 ; i <= len - 1 ; ++i){
            if(i <= max_location){
                max_location = max(max_location,i + nums[i]);
                if(max_location >= len -1)return true;
            }
        }
        return false;
    }
};

56. 合并区间

2021/9/26

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int len = intervals.size();
        vector<vector<int>> ans;
        for(int i = 0; i < len;){
            int x = intervals[i][0];
            int y = intervals[i][1];
            while(i < len && y >= intervals[i][0] ){
                x = min(x,intervals[i][0]);
                y = max(y,intervals[i][1]);
                i++;
            }
            ans.push_back({x,y});
        }
        return ans;
    }
};

49. 字母异位词分组

2021/9/26

c++ 用的太不熟练了

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        for(string& str:strs){
            string key = str;
            sort(key.begin(),key.end());
            map[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for(auto it = map.begin();it != map.end();it++){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

347. 前k个高频元素

2021/9/25

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

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int len = nums.size();
        vector<pair<int,int>> res;
        unordered_map<int,int> hash;
        for(int i = 0 ; i < len ; i++){
            hash[nums[i]]++;
        }
        for(auto it=hash.begin();it!=hash.end();it++)res.push_back({it->second,it->first});
        sort(res.rbegin(),res.rend());
        vector<int> ans;
        for(int i=0;i<k;i++)ans.push_back(res[i].second);
        return ans;
    }
};

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

2021/9/24

二分法

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result ={-1,-1};
        int len = nums.size();
        for(int i = 0 ; i < len; i++){
            if(nums[i] == target){
                result[0] = i;
                break;
            }
        }
        for(int i = len-1; i >= 0 ; i --){
            if(nums[i] == target){
                result[1] = i;
                break;
            }
        }
        return result;
    }
};

33. 搜索旋转排序数组

2021/9/24

二分法，细节处理不到位

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(!n)return -1;
        if(n==1)return nums[0]==target?0:-1;
        int left = 0 , right = n - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] == target) return mid;
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            else{
                if(nums[mid] < target && target <= nums[n-1]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

394. 字符串解码

2021/9/23 周四

栈，不看递归了

class Solution {
public:
    string res = "";
    stack<int> ints;
    stack<string> strs;
    string decodeString(string s) {
        int num = 0 ;
        int len = s.size();
        for(int i = 0 ; i < len ; i++){
            if(s[i] >= '0' && s[i] <= '9'){
                num = num * 10 + s[i] - '0';
            }else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')){
                res += s[i];
            }else if(s[i] == '['){
                ints.push(num);
                strs.push(res);
                num = 0;
                res = "";
            }else{
                for(int i = 0 ; i < ints.top() ; i++)strs.top() += res;
                res = strs.top();
                strs.pop();
                ints.pop();
            }
        }
        return res;
    }
};

416. 分割等和子集

2021/9/23 周四

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

// 最终代码
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        if(len < 2)return false;
        int sum = accumulate(nums.begin(),nums.end(),0);
        int max_num =  *max_element(nums.begin(), nums.end());
        if((sum&1) == 1)return false;
  
        int target = sum / 2;
        if(max_num > target)return false;
        vector<int> dp(target+1,0);
        dp[0] = true;
        if(nums[0] < target)dp[nums[0]] = true;
        for(int i = 1 ; i < len ; i++){
            for(int j = target ; j >= 0 && nums[i] <= j ; j--) dp[j] = dp[j]|dp[j-nums[i]];
            if(dp[target])return true;
        }
        return dp[target];
    }
};
//未优化前
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if((sum&1) == 1){
            return false;
        }
        int target = sum / 2;
        vector<vector<int>> dp(len,vector<int>(target+1,0));
        for(int i = 0 ; i< len ;i++)dp[i][0] = true;
        if(nums[0] < target)dp[0][nums[0]] = true;

        for(int i = 1 ; i < len ; i++){
            for(int j = 0 ; j <= target ; j++){
                dp[i][j] = dp[i-1][j];

                if(nums[i] == j){
                    dp[i][j] = true;
                    continue;
                }
                if(nums[i] < j)dp[i][j] = dp[i-1][j]|dp[i-1][j-nums[i]];
            }
        }
        return dp[len-1][target];
    }
};

437. 路径总和 |||

2021/9/22

双递归，无敌

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
         if(!root)return 0;
         return dfs(root,targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
    }
    int dfs(TreeNode* root,int sum){
        if(!root)return 0;
        sum -= root->val;
        return sum == 0 ? 1 + dfs(root->left,sum)+dfs(root->right,sum):dfs(root->left,sum)+dfs(root->right,sum);
    }
};

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

2021/9/22

算法为什么自己想不到

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int M = s.size(),N = p.size(),i=0;
        if(N > M )return {};
        vector<int> res,S_vec(26),P_vec(26);
        for(;i < N;i++){
            S_vec[s[i]-'a']++;
            P_vec[p[i]-'a']++;
        }
        if(S_vec == P_vec)res.push_back(0);
        for(;i < M ;i++){
            S_vec[s[i]-'a']++;
            S_vec[s[i - N]-'a']--;
            if(S_vec == P_vec)res.push_back(i - N +1);
        }
        return res;
    }
};

494. 目标和

2021/9/22

动态规划不会了，深搜吧

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums,0,0,target);
    }

    int dfs(vector<int>& nums,int index,int sum,int target){
        if(nums.size() == index){
            if(sum == target){
                return 1;
            }else{
                return 0;
            }
        }
        return dfs(nums,index+1,sum+nums[index],target)+ dfs(nums,index+1,sum-nums[index],target);
    }
};

560. 和为k的子数组

2021/9/20

前缀和，加上hash

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0] = 1;
        int count = 0 , pre = 0;
        for(int& x : nums){
            pre += x;
            if (mp.find(pre - k) != mp.end()){
                count += mp[pre-k];
            }
            mp[pre]++;
        }
        return count;
    }
};

581. 最短无序连续子数组

2021/9/20

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

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int len = nums.size();
        int max = nums[0];
        int min = nums[len - 1];
        int l = 0,r = len -1;
        for(int i = 0 ; i < len ; i++){
            if(max <= nums[i]){
                max = nums[i];
            }else{
                l = i;
            }
        }
        for(int i = len -1  ; i >= 0 ; i--){
            if(min >= nums[i]){
                min = nums[i];
            }else{
                r = i;
            }
        }
        if(l == 0 && r == len-1)return 0;
        return l-r+1;
    }
};

621. 任务调度器

2021/9/19

桶，分析题目太重要

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size(),j=1;
        vector<int> vec(26);
        for(char c : tasks)++vec[c-'A'];
        sort(vec.rbegin(),vec.rend());
        while(j<vec.size()&&vec[j]==vec[0])++j;
        return max(len,j+(n+1)*(vec[0]-1));
    }
};

114. 二叉树展开为链表

2021/9/19

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode *> st;
        pre_order(root,st);
        for(int i = 1 ; i < st.size() ; i++){
            TreeNode *prev = st.at(i - 1), *curr = st.at(i);
            prev->left = nullptr;
            prev->right = curr;
        }
    }
    void pre_order(TreeNode *root,vector<TreeNode*> &st){
        if(root){
            st.push_back(root);
            pre_order(root->left,st);
            pre_order(root->right,st);
        }
    }
};

739. 每日温度

2021/9/18

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

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res (n,0);
        stack<int> st;
        for(int i = 0 ; i < n ; ++i){
            while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                int t = st.top();
                st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }
};

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

2021/9/18

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(root){
            convertBST(root->right);
            sum += root->val;
            root->val = sum ;
            convertBST(root->left);
        }
        return root;
    }
};

647. 回文子串

2021/9/17

class Solution {
private:
    int res=0;
public:
    int countSubstrings(string s) {
        if(!s.size())return 0;
        for(int i = 0 ; i < s.length();i++){
            aen(s,i,i);
            aen(s,i,i+1);
        }
        return res;
    }
    void aen(string s,int left,int right ){
        while(left >= 0 && right < s.length()&& s[left--] == s[right++]){
            ++res;
        }   
    }
};

337. 打家劫舍|||

2021/9/17

/**
 * 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 {
private:
    unordered_map <TreeNode*, int> q,p; // p 父节点不偷
public:
    int rob(TreeNode* root) {
        rob_max(root);
        return max(p[root],q[root]);
    }
    void rob_max(TreeNode *node){
        if(!node)return ;
        rob_max(node->left);
        rob_max(node->right);
        q[node] = node->val + p[node->left]+p[node->right];
        p[node] = max(p[node->left],q[node->left])+ max(p[node->right],q[node->right]);
    }
};

208. 实现Trie 前缀树

2021/9/17

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* search_Aen(string word){
        Trie* node = this;
        for(char ch : word){
            if(node->children[ch-'a'] == nullptr)return nullptr;
            node = node->children[ch-'a'];
        }
        return node;
    }
public:
    /** Initialize your data structure here. */
    Trie():children(26),isEnd(false) {}
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *node = this;
        for(char ch : word){
            if(node->children[ch-'a'] == nullptr)node->children[ch-'a'] = new Trie();
            node = node->children[ch-'a'];
        }
        node->isEnd = true;
    }
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *node = this->search_Aen(word);  
        return node != nullptr && node->isEnd;
    }
  
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return this->search_Aen(prefix)!= nullptr;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Algorithms

279. 完全平方数

2021/9/16

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

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n+1);
        for(int i = 1; i <= n ; i++){
            int min_num = INT_MAX;
            for (int j = 1 ; j*j <= i; j++){
                min_num = min(min_num,f[i-j*j]);
            }
            f[i] = min_num + 1;
        }
        return f[n];
    }
};

146. LRU缓存机制

2021/9/15

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

struct Aen_link_node{
    int key;
    int value;
    Aen_link_node *prev;
    Aen_link_node *next;
    Aen_link_node():key(0),value(0),prev(nullptr),next(nullptr){}
    Aen_link_node(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};

class LRUCache {
private:
    unordered_map<int, Aen_link_node*> cache;
    Aen_link_node* head;
    Aen_link_node* tail;
    int size;
    int capacity;
public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head = new Aen_link_node();
        tail = new Aen_link_node();
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        if(!cache.count(key))return -1;
        return move_to_head(cache[key])->value;
    }
  
    void put(int key, int value) {
        if(!cache.count(key)){
            Aen_link_node *node = new Aen_link_node(key,value);
            cache[key] = node;
            add_data_to_head(node);
            ++size;
            if(size > capacity){
                Aen_link_node *del_node = delete_tail_node();
                cache.erase(del_node->key);
                delete(del_node);
                --size;
            }
        }else{
            Aen_link_node *node = cache[key];
            node->value = value;
            move_to_head(node);
        }
    }

    void add_data_to_head(Aen_link_node *node){
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    void delete_node(Aen_link_node *node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    Aen_link_node* move_to_head(Aen_link_node *node){
        delete_node(node);
        add_data_to_head(node);
        return node;
    }
    Aen_link_node* delete_tail_node(){
        Aen_link_node *node = tail->prev;
        delete_node(node);
        return node;
    }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

148.排序链表

2021/9/14

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

/**
 * 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* sortList(ListNode* head) {
        return sortA(head,nullptr);
    }

    ListNode* sortA(ListNode *head,ListNode *tmp){
        if(head == nullptr)return head;
        if(head->next == tmp){
            head->next = nullptr;
            return head;
        }
        ListNode *fast = head,*low = head;
        while(fast != tmp){
            fast = fast->next;
            low = low->next;
            if(fast != tmp){
                fast = fast->next;
            }
        }
        return merge(sortA(head,low),sortA(low,tmp));
    }

    ListNode* merge(ListNode *p,ListNode *q){
        ListNode* resHead = new ListNode(0);
        ListNode *res = resHead,*pp = p,*qq = q;
        while(pp != nullptr && qq != nullptr){
            if(pp->val <= qq->val){
                res->next = pp;
                pp = pp->next;
            }else{
                res->next = qq;
                qq = qq->next;
            }
            res = res->next;
        }
        if(pp)res->next = pp;
        if(qq )res->next = qq;
        return resHead->next;
    }
};

78.子集

2021/9/13

二进制思想

回溯算法也挺好

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        int length = nums.size();
        for(int i = 0 ; i < (1 << length ) ; ++i){
            tmp.clear();
            for(int j = 0 ; j < length ; ++j){
                if( i & (1 << j)){
                    tmp.push_back(nums[j]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};

39.组和总和

2021/9/12

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx){
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
  
        dfs(candidates, target, ans, combine, idx + 1);
  
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

};

46.全排列

2021/9/11

c++ 真的忘干净了

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]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

31.下一个排列

2021/9/10

c++ 开始练练手

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while(i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        if(i >= 0){
            int j =nums.size()-1;
            while(j >= 0 && nums[i]>=nums[j]){
                j--;
            }
            swap(nums[i],nums[j]);
        }
        reverse(nums.begin()+i+1,nums.end());
    }
};

448.找到所有数组中消失的数字

2021/9/10

用C语言写算法不能再写了

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
    for(int i = 0; i < numsSize; i++){
        int x = (nums[i] - 1) % numsSize;
        nums[x] += numsSize;
    }
    int* ret = malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] <= numsSize) {
            ret[(*returnSize)++] = i + 1;
        }
    }
    return ret;
}

543.二叉树的直径

2021/9/8

原理很简单，敲代码费劲了，用C敲真心考虑的太多，代码明明很对，结果就是不对，侵淫C也有6年了，还是没有好好考虑指针的用出

错误：定义全局变量 int res，结果不对，需要定义成指针型，int * res

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int mDepth(struct TreeNode* root,int *res){
    if(!root){
        return 0;
    }
    int leftDepth = mDepth(root->left,res);
    int rightDepth = mDepth(root->right,res);
    *res = *res > (leftDepth + rightDepth) ? *res : (leftDepth + rightDepth);
    return (leftDepth > rightDepth ? leftDepth:rightDepth)+1 ;
}

int diameterOfBinaryTree(struct TreeNode* root){
    int res = 0;
    if(!root){
        return 0;
    }
    mDepth(root,&res);
    return res;
}

461.汉明距离

2021/9/7

搞嵌入式的二进制还行

int hammingDistance(int x, int y){
    int cal = x^y,res = 0;
    while(cal){
        res += (cal &1);
        cal >>= 1;
    }
    return res;
}

617.合并二叉树

2021/9/7

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    struct TreeNode* merged = malloc(sizeof(struct TreeNode));
    if(!root1)return root2;
    if(!root2)return root1;
    merged->val = root1->val + root2->val ;
    merged->left = mergeTrees(root1->left,root2->left);
    merged->right = mergeTrees(root1->right,root2->right);
    return merged;
}

338.比特位计数

2021/9/7

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int n, int* returnSize){
    int *res = malloc(sizeof(int)*(n+1));
    *returnSize = n+1;
    res[0] = 0;
    for(int i = 1;i<=n;i++){
        if(!(i%2))
            res[i] = res[i/2];
        else 
            res[i] = res[i-1]+1;
    }
    return res;
}

283.移动零

2021/9/6

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}
void moveZeroes(int *nums, int numsSize) {
    int left = 0, right = 0;
    while (right < numsSize) {
        if (nums[right]) {
            swap(nums + left, nums + right);
            left++;
        }
        right++;
    }
}

226.翻转二叉树

2021/9/6

比较简单

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root){
    if(!root)return root;
    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

121.买卖股票的最佳时机

int maxProfit(int* prices, int pricesSize){
    // int i = 0,j=0,ans=0,tmp=90000;
    // for(i=0;i<(pricesSize-1);i++){
    //     for(j=i;j<(pricesSize);j++){
    //         tmp = prices[i] - prices[j];
    //         if(tmp<ans){
    //             ans =tmp;
    //         }
    //     }
    // }
    // if(ans<0){
    // return -ans;}
    // else{
    // return 0;}
    // 暴力法不好用
    int min = 165323;
    for (int i = 0; i < pricesSize; ++i) {
        if (min > prices[i]) min = prices[i];
        else ans = (ans - (prices[i] - min))>0 ? ans : (prices[i] - min);
    }
    return ans;

}

169.多数元素

2021/9/4

int cmpfunc(const void* a,const void* b){
    return *(int *)a - *(int *)b;
}
int majorityElement(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmpfunc);
    return nums[numsSize/2];
}

155.最小栈

2021/9/3

#define MAX_SIZE 10000

typedef struct {
    int *p_stack;
    int top;
    int *p_min;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack *obj=(MinStack *)malloc(sizeof(MinStack));
    obj->p_stack=(int *)malloc(MAX_SIZE*sizeof(int));
    obj->top=-1;
    obj->p_min=(int *)malloc(MAX_SIZE*sizeof(int));
    return obj;
}

void minStackPush(MinStack* obj, int val) {
  if(obj->top == (MAX_SIZE-1)){
  
  }else if(obj->top==-1){
      obj->top++;
      obj->p_stack[obj->top]=val;
      obj->p_min[obj->top]=val;
  }else{
      int tmp=obj->p_min[obj->top];
      obj->top++;
      obj->p_stack[obj->top]=val;
      if(tmp<val){
        obj->p_min[obj->top]=tmp;
      }else{
        obj->p_min[obj->top]=val;
      }
  }
}

void minStackPop(MinStack* obj) {
  if(obj->top==-1){
  
  }else{
      obj->top--;
  }
}

int minStackTop(MinStack* obj) {
   if(obj->top==-1){
      return;
  }
  return obj->p_stack[obj->top];
}

int minStackGetMin(MinStack* obj) {
    return obj->p_min[obj->top];
}

void minStackFree(MinStack* obj) {
    free(obj->p_stack);
    obj->p_stack=NULL;
    free(obj->p_min);
    obj->p_min = NULL;
    free(obj);
    obj=NULL;
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/

70.爬楼梯

2021/5/28

好讨厌这种用数学的，爬楼梯

int climbStairs(int n){
    int a=1,b=1,res=0;
    if(n == 1) return 1;
    for(int i = 2; i <= n; i++) {
        res = a + b;
        a = b ;
        b = res;
    }
    return res;
}

48.旋转头像

2021/5/27

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}
/*
* 水平翻转，对角线互换
*/
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    for (int i = 0; i < matrixSize / 2; ++i) {
        for (int j = 0; j < matrixSize; ++j) {
            swap(&matrix[i][j], &matrix[matrixSize - i - 1][j]);
        }
    }
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < i; ++j) {
            swap(&matrix[i][j], &matrix[j][i]);
        }
    }
}

142.环形链表II

2021/5/26

struct ListNode *detectCycle(struct ListNode *head) {
     struct ListNode *slow = head, *fast = head;
    while (fast != NULL) {
        slow = slow->next;
        if (fast->next == NULL) {
            return NULL;
        }
        fast = fast->next->next;
        if (fast == slow) {
            struct ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return NULL;
}

206.反转链表

2021/5/25

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

160.相交链表

2021/5/24

双指针法

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if ((!headA) && (!headB))return NULL;
    struct ListNode *A = headA;
    struct ListNode *B = headB;
    while(A != B){
        if(A){
            A = A->next;
        }else{
            A = headB;
        }
        if(B){
            B = B->next;
        }else{
            B = headA;
        }
    }
    return A;
}

98.验证二叉搜索树

2021/5/22

bool fun(struct TreeNode* root, long low, long high) {
    if (root == NULL) return true;
    long num = root->val;
    if (num <= low || num >= high) return false;
    return fun(root->left, low, num) && fun(root->right, num, high);
}
bool isValidBST(struct TreeNode* root){
    return fun(root, LONG_MIN, LONG_MAX);
}

101.对称二叉树

2021/5/21

这解题思路，与印象中的不一样

bool checkIsSymmetric(struct TreeNode* p,struct TreeNode* q){
    if(!p && !q)return true;
    if(!p || !q)return false;
    return (p->val==q->val)&&(checkIsSymmetric(p->left,q->right))&&(checkIsSymmetric(q->left,p->right));
}
bool isSymmetric(struct TreeNode* root){
   return checkIsSymmetric(root,root);
}

104.二叉树的最大深度

2021/5/20

DFS思想

int maxDepth(struct TreeNode* root){
if (root == NULL) return 0;
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

22.括号生成

2021/5/19

DFS思想，排除不需要的，大佬就是大佬

// 回溯法求解
#define MAX_SIZE 1430  // 卡特兰数: 1, 1, 2, 5, 14, 42, 132, 429, 1430
void generate(int left, int right, int n, char *str, int index, char **result, int *returnSize) {
    if (index == 2 * n) { // 当前长度已达2n
        result[(*returnSize)] =  (char*)calloc((2 * n + 1), sizeof(char));
        strcpy(result[(*returnSize)++], str);
        return;
    }
    // 如果左括号数量不大于 n，可以放一个左括号
    if (left < n) {
        str[index] = '(';
        generate(left + 1, right, n, str, index + 1, result, returnSize);
    }
    // 如果右括号数量小于左括号的数量，可以放一个右括号
    if (right < left) {
        str[index] = ')';
        generate(left, right + 1, n, str, index + 1, result, returnSize);
    }
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** generateParenthesis(int n, int *returnSize) {
    char *str = (char*)calloc((2 * n + 1), sizeof(char));
    char **result = (char **)malloc(sizeof(char *) * MAX_SIZE);
    *returnSize = 0;
    generate(0, 0, n, str, 0, result, returnSize);
    return result;
}

136.只出现一次的数字

2021/5/18

这个确实太简单了

int singleNumber(int* nums, int numsSize){
    int i,res = 0;
    for(i = 0 ;i < numsSize;i++){
        res ^= *nums;
        nums++;
    }
    return res;
}

102.二叉树的层序遍历

2021/5/17

用c写太难了，又是别人家的code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 #define NODE_SIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int **rslt = NULL;
    int *columnSize = NULL;
    struct TreeNode *queue[NODE_SIZE] = {0};                    /* 做队列使用 */
    struct TreeNode *pNode = NULL;
    int front = 0, rear = 0, pre_rear;
    int i = 0, j = 0;                                           /* i用来索引行，即层数，j用来索引列，即每层的结点个数 */

    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    queue[rear++] = root;                                       /* 先把root结点入队 */
    while (front < rear) {                                      /* 外层循环：用来处理队列，队列不为空就循环处理 */
        pre_rear = rear;                                        /* 备份上一层的队尾指针 */
        rslt = realloc(rslt, (i + 1)*sizeof(int *));            /* 外层循环实际就是层数，每次扩充1 */
        rslt[i] = calloc(pre_rear - front, sizeof(int));
        while(front < pre_rear) {                               /* 内层循环：遍历每一层结点，每次出队一个结点，同时并把该结点的孩子入队 */
            pNode = queue[front++];                             /* 出队 */
            rslt[i][j++] = pNode->val;                          /* 存储结点值 */
            if (pNode->left)                                    /* 当前结点左、右孩子存在则将他们入队 */
                queue[rear++] = pNode->left;
            if (pNode->right)
                queue[rear++] = pNode->right;
        }
        columnSize = realloc(columnSize, (i + 1)*sizeof(int));  /* columnSize数组用来存储每层结点个数 */
        columnSize[i++] = j;
        j = 0;
    }

    *returnSize = i;                                            /* 如上注释，这个参数用来“带回”层数 */
    *returnColumnSizes = columnSize;                            /* 这个参数用来“带回”每层的结点个数 */

    return rslt;                                                /* 返回值存储了遍历的结果，上面两个参数用来描述这个结果，以便调用者打印树的形态 */
}

62.不同路径

2021/5/16

int uniquePaths(int m, int n) {
    long long ans = 1;
    for (int x = n, y = 1; y < m; ++x, ++y) {
        ans = ans * x / y;
    }
    return ans;
}

53.最大子序和

2021/5/15

贪心算法

int maxSubArray(int* nums, int numsSize){
    int temp = 0, ret = nums[0];
    for(int i = 0; i < numsSize; i++){
        temp = fmax(temp + nums[i], nums[i]);
        ret = fmax(temp, ret);
    }
    return ret;  
}

94.二叉树的中序遍历

2021/5/14

void inorder(struct TreeNode* node, int* res, int* resSize) {
    if (!node) {
        return;
    }
    inorder(node->left, res, resSize);
    res[(*resSize)++] = node->val;
    inorder(node->right, res, resSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

141.环形链表

2021/513

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

20.有效的括号

2021/5/12

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}

17.电话号码的字母组合

2021/5/11

别人的代码怎么就这么好

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char phoneMap[11][5] = {"\0", "\0", "abc\0", "def\0", "ghi\0", "jkl\0", "mno\0", "pqrs\0", "tuv\0", "wxyz\0"};

char* digits_tmp;
int digits_size;

char** combinations;
int combinations_size;

char* combination;
int combination_size;

void backtrack(int index) {
    if (index == digits_size) {
        char* tmp = malloc(sizeof(char) * (combination_size + 1));
        memcpy(tmp, combination, sizeof(char) * (combination_size + 1));
        combinations[combinations_size++] = tmp;
    } else {
        char digit = digits_tmp[index];
        char* letters = phoneMap[digit - '0'];
        int len = strlen(letters);
        for (int i = 0; i < len; i++) {
            combination[combination_size++] = letters[i];
            combination[combination_size] = 0;
            backtrack(index + 1);
            combination[--combination_size] = 0;
        }
    }
}

char** letterCombinations(char* digits, int* returnSize) {
    combinations_size = combination_size = 0;
    digits_tmp = digits;
    digits_size = strlen(digits);
    if (digits_size == 0) {
        *returnSize = 0;
        return combinations;
    }
    int num = 1;
    for (int i = 0; i < digits_size; i++) num *= 4;
    combinations = malloc(sizeof(char*) * num);
    combination = malloc(sizeof(char*) * digits_size);
    backtrack(0);
    *returnSize = combinations_size;
    return combinations;
}

11.盛最多水的容器

2021/5/10

我觉得LeetCode编译器sd

#define MAX(a,b) (a>b)?(a):(b)
int maxArea(int* height, int heightSize){
    int i = 0, j = heightSize - 1, res = 0;
    while(i < j){
      //  res = height[i] < height[j] ?  MAX(res, (j - i) * height[i++]):  MAX(res, (j - i) * height[j--]); 
        if( height[i] < height[j] ){
            res =  MAX(res, (j - i) * height[i]);
            i++;
        }else{
            res =  MAX(res, (j - i) * height[j]);
            j--;
        }
    }
    return res;
}

5.最长回文子串

2021/5/9

思想是中心扩展法，这个代码指针用的太好了

char * longestPalindrome(char * s){
    char* left,* right,* now,* tar;
    int dist,length;
    now=tar=s;
    length=1;
    while(*now){
        right=now;
        left=now-1;
        do{
            right++;
        }while((*right)==(*now));
        now=right;
        while(left>=s&&(*right)&&((*left)==(*right))){
            left--;
            right++;
        }
        dist=right-left-1;
        if(dist>length){
            length=dist;
            tar=left+1;
        }
    }
    tar[length]=0;
    return tar;
}

4.寻找两个正序数组的中位数

2021/5/8

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int size = nums2Size+nums1Size;
    int   all_nums[size];
    int n1 = 0;
    int n2 = 0;
    int index = 0;
    while(n1<nums1Size || n2<nums2Size){
        if(n1<nums1Size && n2<nums2Size){
            if(nums1[n1]<= nums2[n2]){
                all_nums[index++] = nums1[n1++];
 
            }else{
                all_nums[index++] = nums2[n2++];
            }
        }
        else if(n1 == nums1Size && n2 <nums2Size) {
            all_nums[index++] = nums2[n2++];
        }
        else{
            all_nums[index++] = nums1[n1++];
        }
    }
    if(size%2 == 0){
        return ((double)all_nums[size/2-1]+(double)all_nums[size/2])/2;
    }else{
        return (double)all_nums[size/2];
    }
}

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

2021/5/7

int lengthOfLongestSubstring(char * s) {
    char hash[128] = {0};
    int start = 0;
    int len = strlen(s);
    int max = 0;
    for (int i = 0; i < len; i++) {
        hash[s[i]]++;
        while (hash[s[i]] > 1) {
            hash[s[start]]--;
            start++;
        }
        max = fmax(max, i - start + 1);
    }
    return max;
}

公众号'艾恩凝'