[LeetCode]刷题记录

[LeetCode]刷题记录

Introduction

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

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};

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

2021/9/10

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

 1/**
 2 * Note: The returned array must be malloced, assume caller calls free().
 3 */
 4int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
 5    for(int i = 0; i < numsSize; i++){
 6        int x = (nums[i] - 1) % numsSize;
 7        nums[x] += numsSize;
 8    }
 9    int* ret = malloc(sizeof(int) * numsSize);
10    *returnSize = 0;
11    for (int i = 0; i < numsSize; i++) {
12        if (nums[i] <= numsSize) {
13            ret[(*returnSize)++] = i + 1;
14        }
15    }
16    return ret;
17}

543.二叉树的直径

2021/9/8

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

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

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     struct TreeNode *left;
 6 *     struct TreeNode *right;
 7 * };
 8 */
 9int mDepth(struct TreeNode* root,int *res){
10    if(!root){
11        return 0;
12    }
13    int leftDepth = mDepth(root->left,res);
14    int rightDepth = mDepth(root->right,res);
15    *res = *res > (leftDepth + rightDepth) ? *res : (leftDepth + rightDepth);
16    return (leftDepth > rightDepth ? leftDepth:rightDepth)+1 ;
17}
18
19int diameterOfBinaryTree(struct TreeNode* root){
20    int res = 0;
21    if(!root){
22        return 0;
23    }
24    mDepth(root,&res);
25    return res;
26}

461.汉明距离

2021/9/7

搞嵌入式的二进制还行

1int hammingDistance(int x, int y){
2    int cal = x^y,res = 0;
3    while(cal){
4        res += (cal &1);
5        cal >>= 1;
6    }
7    return res;
8}

617.合并二叉树

2021/9/7

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     struct TreeNode *left;
 6 *     struct TreeNode *right;
 7 * };
 8 */
 9
10struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
11    struct TreeNode* merged = malloc(sizeof(struct TreeNode));
12    if(!root1)return root2;
13    if(!root2)return root1;
14    merged->val = root1->val + root2->val ;
15    merged->left = mergeTrees(root1->left,root2->left);
16    merged->right = mergeTrees(root1->right,root2->right);
17    return merged;
18}

338.比特位计数

2021/9/7

 1/**
 2 * Note: The returned array must be malloced, assume caller calls free().
 3 */
 4int* countBits(int n, int* returnSize){
 5    int *res = malloc(sizeof(int)*(n+1));
 6    *returnSize = n+1;
 7    res[0] = 0;
 8    for(int i = 1;i<=n;i++){
 9        if(!(i%2))
10            res[i] = res[i/2];
11        else 
12            res[i] = res[i-1]+1;
13    }
14    return res;
15}

283.移动零

2021/9/6

 1void swap(int *a, int *b) {
 2    int t = *a;
 3    *a = *b, *b = t;
 4}
 5void moveZeroes(int *nums, int numsSize) {
 6    int left = 0, right = 0;
 7    while (right < numsSize) {
 8        if (nums[right]) {
 9            swap(nums + left, nums + right);
10            left++;
11        }
12        right++;
13    }
14}

226.翻转二叉树

2021/9/6

比较简单

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     struct TreeNode *left;
 6 *     struct TreeNode *right;
 7 * };
 8 */
 9struct TreeNode* invertTree(struct TreeNode* root){
10    if(!root)return root;
11    struct TreeNode *tmp = root->left;
12    root->left = root->right;
13    root->right = tmp;
14    invertTree(root->left);
15    invertTree(root->right);
16    return root;
17}

121.买卖股票的最佳时机

 1int maxProfit(int* prices, int pricesSize){
 2    // int i = 0,j=0,ans=0,tmp=90000;
 3    // for(i=0;i<(pricesSize-1);i++){
 4    //     for(j=i;j<(pricesSize);j++){
 5    //         tmp = prices[i] - prices[j];
 6    //         if(tmp<ans){
 7    //             ans =tmp;
 8    //         }
 9    //     }
10    // }
11    // if(ans<0){
12    // return -ans;}
13    // else{
14    // return 0;}
15    // 暴力法不好用
16    int min = 165323;
17    for (int i = 0; i < pricesSize; ++i) {
18        if (min > prices[i]) min = prices[i];
19        else ans = (ans - (prices[i] - min))>0 ? ans : (prices[i] - min);
20    }
21    return ans;
22
23}

169.多数元素

2021/9/4

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

155.最小栈

2021/9/3

 1#define MAX_SIZE 10000
 2
 3typedef struct {
 4    int *p_stack;
 5    int top;
 6    int *p_min;
 7} MinStack;
 8
 9/** initialize your data structure here. */
10
11MinStack* minStackCreate() {
12    MinStack *obj=(MinStack *)malloc(sizeof(MinStack));
13    obj->p_stack=(int *)malloc(MAX_SIZE*sizeof(int));
14    obj->top=-1;
15    obj->p_min=(int *)malloc(MAX_SIZE*sizeof(int));
16    return obj;
17}
18
19void minStackPush(MinStack* obj, int val) {
20  if(obj->top == (MAX_SIZE-1)){
21  
22  }else if(obj->top==-1){
23      obj->top++;
24      obj->p_stack[obj->top]=val;
25      obj->p_min[obj->top]=val;
26  }else{
27      int tmp=obj->p_min[obj->top];
28      obj->top++;
29      obj->p_stack[obj->top]=val;
30      if(tmp<val){
31        obj->p_min[obj->top]=tmp;
32      }else{
33        obj->p_min[obj->top]=val;
34      }
35  }
36}
37
38void minStackPop(MinStack* obj) {
39  if(obj->top==-1){
40  
41  }else{
42      obj->top--;
43  }
44}
45
46int minStackTop(MinStack* obj) {
47   if(obj->top==-1){
48      return;
49  }
50  return obj->p_stack[obj->top];
51}
52
53int minStackGetMin(MinStack* obj) {
54    return obj->p_min[obj->top];
55}
56
57void minStackFree(MinStack* obj) {
58    free(obj->p_stack);
59    obj->p_stack=NULL;
60    free(obj->p_min);
61    obj->p_min = NULL;
62    free(obj);
63    obj=NULL;
64}
65
66/**
67 * Your MinStack struct will be instantiated and called as such:
68 * MinStack* obj = minStackCreate();
69 * minStackPush(obj, val);
70 
71 * minStackPop(obj);
72 
73 * int param_3 = minStackTop(obj);
74 
75 * int param_4 = minStackGetMin(obj);
76 
77 * minStackFree(obj);
78*/

70.爬楼梯

2021/5/28

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

 1int climbStairs(int n){
 2    int a=1,b=1,res=0;
 3    if(n == 1) return 1;
 4    for(int i = 2; i <= n; i++) {
 5        res = a + b;
 6        a = b ;
 7        b = res;
 8    }
 9    return res;
10}

48.旋转头像

2021/5/27

 1void swap(int* a, int* b) {
 2    int t = *a;
 3    *a = *b, *b = t;
 4}
 5/*
 6* 水平翻转,对角线互换
 7*/
 8void rotate(int** matrix, int matrixSize, int* matrixColSize) {
 9    for (int i = 0; i < matrixSize / 2; ++i) {
10        for (int j = 0; j < matrixSize; ++j) {
11            swap(&matrix[i][j], &matrix[matrixSize - i - 1][j]);
12        }
13    }
14    for (int i = 0; i < matrixSize; ++i) {
15        for (int j = 0; j < i; ++j) {
16            swap(&matrix[i][j], &matrix[j][i]);
17        }
18    }
19}

142.环形链表II

2021/5/26

 1struct ListNode *detectCycle(struct ListNode *head) {
 2     struct ListNode *slow = head, *fast = head;
 3    while (fast != NULL) {
 4        slow = slow->next;
 5        if (fast->next == NULL) {
 6            return NULL;
 7        }
 8        fast = fast->next->next;
 9        if (fast == slow) {
10            struct ListNode* ptr = head;
11            while (ptr != slow) {
12                ptr = ptr->next;
13                slow = slow->next;
14            }
15            return ptr;
16        }
17    }
18    return NULL;
19}

206.反转链表

2021/5/25

 1struct ListNode* reverseList(struct ListNode* head){
 2    struct ListNode* prev = NULL;
 3    struct ListNode* curr = head;
 4    while (curr) {
 5        struct ListNode* next = curr->next;
 6        curr->next = prev;
 7        prev = curr;
 8        curr = next;
 9    }
10    return prev;
11}

160.相交链表

2021/5/24

双指针法

 1struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
 2    if ((!headA) && (!headB))return NULL;
 3    struct ListNode *A = headA;
 4    struct ListNode *B = headB;
 5    while(A != B){
 6        if(A){
 7            A = A->next;
 8        }else{
 9            A = headB;
10        }
11        if(B){
12            B = B->next;
13        }else{
14            B = headA;
15        }
16    }
17    return A;
18}

98.验证二叉搜索树

2021/5/22

1bool fun(struct TreeNode* root, long low, long high) {
2    if (root == NULL) return true;
3    long num = root->val;
4    if (num <= low || num >= high) return false;
5    return fun(root->left, low, num) && fun(root->right, num, high);
6}
7bool isValidBST(struct TreeNode* root){
8    return fun(root, LONG_MIN, LONG_MAX);
9}

101.对称二叉树

2021/5/21

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

1bool checkIsSymmetric(struct TreeNode* p,struct TreeNode* q){
2    if(!p && !q)return true;
3    if(!p || !q)return false;
4    return (p->val==q->val)&&(checkIsSymmetric(p->left,q->right))&&(checkIsSymmetric(q->left,p->right));
5}
6bool isSymmetric(struct TreeNode* root){
7   return checkIsSymmetric(root,root);
8}

104.二叉树的最大深度

2021/5/20

DFS思想

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

22.括号生成

2021/5/19

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

 1// 回溯法求解
 2#define MAX_SIZE 1430  // 卡特兰数: 1, 1, 2, 5, 14, 42, 132, 429, 1430
 3void generate(int left, int right, int n, char *str, int index, char **result, int *returnSize) {
 4    if (index == 2 * n) { // 当前长度已达2n
 5        result[(*returnSize)] =  (char*)calloc((2 * n + 1), sizeof(char));
 6        strcpy(result[(*returnSize)++], str);
 7        return;
 8    }
 9    // 如果左括号数量不大于 n,可以放一个左括号
10    if (left < n) {
11        str[index] = '(';
12        generate(left + 1, right, n, str, index + 1, result, returnSize);
13    }
14    // 如果右括号数量小于左括号的数量,可以放一个右括号
15    if (right < left) {
16        str[index] = ')';
17        generate(left, right + 1, n, str, index + 1, result, returnSize);
18    }
19}
20/**
21 * Note: The returned array must be malloced, assume caller calls free().
22 */
23char** generateParenthesis(int n, int *returnSize) {
24    char *str = (char*)calloc((2 * n + 1), sizeof(char));
25    char **result = (char **)malloc(sizeof(char *) * MAX_SIZE);
26    *returnSize = 0;
27    generate(0, 0, n, str, 0, result, returnSize);
28    return result;
29}

136.只出现一次的数字

2021/5/18

这个确实太简单了

1int singleNumber(int* nums, int numsSize){
2    int i,res = 0;
3    for(i = 0 ;i < numsSize;i++){
4        res ^= *nums;
5        nums++;
6    }
7    return res;
8}

102.二叉树的层序遍历

2021/5/17

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

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     struct TreeNode *left;
 6 *     struct TreeNode *right;
 7 * };
 8 */
 9
10 #define NODE_SIZE 10000
11int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
12    int **rslt = NULL;
13    int *columnSize = NULL;
14    struct TreeNode *queue[NODE_SIZE] = {0};                    /* 做队列使用 */
15    struct TreeNode *pNode = NULL;
16    int front = 0, rear = 0, pre_rear;
17    int i = 0, j = 0;                                           /* i用来索引行,即层数,j用来索引列,即每层的结点个数 */
18
19    if (!root) {
20        *returnSize = 0;
21        return NULL;
22    }
23    queue[rear++] = root;                                       /* 先把root结点入队 */
24    while (front < rear) {                                      /* 外层循环:用来处理队列,队列不为空就循环处理 */
25        pre_rear = rear;                                        /* 备份上一层的队尾指针 */
26        rslt = realloc(rslt, (i + 1)*sizeof(int *));            /* 外层循环实际就是层数,每次扩充1 */
27        rslt[i] = calloc(pre_rear - front, sizeof(int));
28        while(front < pre_rear) {                               /* 内层循环:遍历每一层结点,每次出队一个结点,同时并把该结点的孩子入队 */
29            pNode = queue[front++];                             /* 出队 */
30            rslt[i][j++] = pNode->val;                          /* 存储结点值 */
31            if (pNode->left)                                    /* 当前结点左、右孩子存在则将他们入队 */
32                queue[rear++] = pNode->left;
33            if (pNode->right)
34                queue[rear++] = pNode->right;
35        }
36        columnSize = realloc(columnSize, (i + 1)*sizeof(int));  /* columnSize数组用来存储每层结点个数 */
37        columnSize[i++] = j;
38        j = 0;
39    }
40
41    *returnSize = i;                                            /* 如上注释,这个参数用来“带回”层数 */
42    *returnColumnSizes = columnSize;                            /* 这个参数用来“带回”每层的结点个数 */
43
44    return rslt;                                                /* 返回值存储了遍历的结果,上面两个参数用来描述这个结果,以便调用者打印树的形态 */
45}

62.不同路径

2021/5/16

1int uniquePaths(int m, int n) {
2    long long ans = 1;
3    for (int x = n, y = 1; y < m; ++x, ++y) {
4        ans = ans * x / y;
5    }
6    return ans;
7}

53.最大子序和

2021/5/15

贪心算法

1int maxSubArray(int* nums, int numsSize){
2    int temp = 0, ret = nums[0];
3    for(int i = 0; i < numsSize; i++){
4        temp = fmax(temp + nums[i], nums[i]);
5        ret = fmax(temp, ret);
6    }
7    return ret;  
8}

94.二叉树的中序遍历

2021/5/14

 1void inorder(struct TreeNode* node, int* res, int* resSize) {
 2    if (!node) {
 3        return;
 4    }
 5    inorder(node->left, res, resSize);
 6    res[(*resSize)++] = node->val;
 7    inorder(node->right, res, resSize);
 8}
 9
10int* inorderTraversal(struct TreeNode* root, int* returnSize) {
11    int* res = malloc(sizeof(int) * 501);
12    *returnSize = 0;
13    inorder(root, res, returnSize);
14    return res;
15}

141.环形链表

2021/513

 1bool hasCycle(struct ListNode *head) {
 2    if (head == NULL || head->next == NULL) {
 3        return false;
 4    }
 5    struct ListNode* slow = head;
 6    struct ListNode* fast = head->next;
 7    while (slow != fast) {
 8        if (fast == NULL || fast->next == NULL) {
 9            return false;
10        }
11        slow = slow->next;
12        fast = fast->next->next;
13    }
14    return true;
15}

20.有效的括号

2021/5/12

 1char pairs(char a) {
 2    if (a == '}') return '{';
 3    if (a == ']') return '[';
 4    if (a == ')') return '(';
 5    return 0;
 6}
 7
 8bool isValid(char* s) {
 9    int n = strlen(s);
10    if (n % 2 == 1) {
11        return false;
12    }
13    int stk[n + 1], top = 0;
14    for (int i = 0; i < n; i++) {
15        char ch = pairs(s[i]);
16        if (ch) {
17            if (top == 0 || stk[top - 1] != ch) {
18                return false;
19            }
20            top--;
21        } else {
22            stk[top++] = s[i];
23        }
24    }
25    return top == 0;
26}

17.电话号码的字母组合

2021/5/11

别人的代码怎么就这么好

 1/**
 2 * Note: The returned array must be malloced, assume caller calls free().
 3 */
 4char phoneMap[11][5] = {"\0", "\0", "abc\0", "def\0", "ghi\0", "jkl\0", "mno\0", "pqrs\0", "tuv\0", "wxyz\0"};
 5
 6char* digits_tmp;
 7int digits_size;
 8
 9char** combinations;
10int combinations_size;
11
12char* combination;
13int combination_size;
14
15void backtrack(int index) {
16    if (index == digits_size) {
17        char* tmp = malloc(sizeof(char) * (combination_size + 1));
18        memcpy(tmp, combination, sizeof(char) * (combination_size + 1));
19        combinations[combinations_size++] = tmp;
20    } else {
21        char digit = digits_tmp[index];
22        char* letters = phoneMap[digit - '0'];
23        int len = strlen(letters);
24        for (int i = 0; i < len; i++) {
25            combination[combination_size++] = letters[i];
26            combination[combination_size] = 0;
27            backtrack(index + 1);
28            combination[--combination_size] = 0;
29        }
30    }
31}
32
33char** letterCombinations(char* digits, int* returnSize) {
34    combinations_size = combination_size = 0;
35    digits_tmp = digits;
36    digits_size = strlen(digits);
37    if (digits_size == 0) {
38        *returnSize = 0;
39        return combinations;
40    }
41    int num = 1;
42    for (int i = 0; i < digits_size; i++) num *= 4;
43    combinations = malloc(sizeof(char*) * num);
44    combination = malloc(sizeof(char*) * digits_size);
45    backtrack(0);
46    *returnSize = combinations_size;
47    return combinations;
48}

11.盛最多水的容器

2021/5/10

我觉得LeetCode编译器sd

 1#define MAX(a,b) (a>b)?(a):(b)
 2int maxArea(int* height, int heightSize){
 3    int i = 0, j = heightSize - 1, res = 0;
 4    while(i < j){
 5      //  res = height[i] < height[j] ?  MAX(res, (j - i) * height[i++]):  MAX(res, (j - i) * height[j--]); 
 6        if( height[i] < height[j] ){
 7            res =  MAX(res, (j - i) * height[i]);
 8            i++;
 9        }else{
10            res =  MAX(res, (j - i) * height[j]);
11            j--;
12        }
13    }
14    return res;
15}

5.最长回文子串

2021/5/9

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

 1char * longestPalindrome(char * s){
 2    char* left,* right,* now,* tar;
 3    int dist,length;
 4    now=tar=s;
 5    length=1;
 6    while(*now){
 7        right=now;
 8        left=now-1;
 9        do{
10            right++;
11        }while((*right)==(*now));
12        now=right;
13        while(left>=s&&(*right)&&((*left)==(*right))){
14            left--;
15            right++;
16        }
17        dist=right-left-1;
18        if(dist>length){
19            length=dist;
20            tar=left+1;
21        }
22    }
23    tar[length]=0;
24    return tar;
25}

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

2021/5/8

 1double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
 2    int size = nums2Size+nums1Size;
 3    int   all_nums[size];
 4    int n1 = 0;
 5    int n2 = 0;
 6    int index = 0;
 7    while(n1<nums1Size || n2<nums2Size){
 8        if(n1<nums1Size && n2<nums2Size){
 9            if(nums1[n1]<= nums2[n2]){
10                all_nums[index++] = nums1[n1++];
11 
12            }else{
13                all_nums[index++] = nums2[n2++];
14            }
15        }
16        else if(n1 == nums1Size && n2 <nums2Size) {
17            all_nums[index++] = nums2[n2++];
18        }
19        else{
20            all_nums[index++] = nums1[n1++];
21        }
22    }
23    if(size%2 == 0){
24        return ((double)all_nums[size/2-1]+(double)all_nums[size/2])/2;
25    }else{
26        return (double)all_nums[size/2];
27    }
28}

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

2021/5/7

 1int lengthOfLongestSubstring(char * s) {
 2    char hash[128] = {0};
 3    int start = 0;
 4    int len = strlen(s);
 5    int max = 0;
 6    for (int i = 0; i < len; i++) {
 7        hash[s[i]]++;
 8        while (hash[s[i]] > 1) {
 9            hash[s[start]]--;
10            start++;
11        }
12        max = fmax(max, i - start + 1);
13    }
14    return max;
15}
    吾心信其可行,
          则移山填海之难,
                  终有成功之日!
                                  ——孙文
    评论
    1 评论
    2021-09-27 10:25 回复»

    坚持

avatar

取消