[LeetCode]刷题记录2

2021-10-01 / 2021-12-27 / Algorithm

[LeetCode]刷题记录2

introduction

十月一号了，国庆快乐，题不能停

algorithm

没更新的日子里也没有偷懒，剑指offer的有些题太简单了

剑指offer II 23

12/27

 1class Solution {
 2public:
 3    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
 4        if (headA == nullptr || headB == nullptr) return nullptr;   
 5
 6        ListNode *pA = headA, *pB = headB;
 7        while (pA != pB)
 8        {
 9            if (pA) pA = pA->next;      
10            else pA = headB;            
11            if (pB) pB = pB->next;
12            else pB = headA;            
13        }
14
15        return pA;
16    }
17};

328. 奇偶链表

12/18

 1class Solution {
 2public:
 3    ListNode* oddEvenList(ListNode* head) {
 4        if(!head)return nullptr;
 5        deque<ListNode*> dq_head,dq_tail;
 6        ListNode *p = head;
 7        while(p){
 8            if(p)dq_head.push_back(p);
 9            p = p -> next;
10            if(p)dq_tail.push_back(p);
11            if(p)p = p -> next;
12        }
13        while(!dq_head.empty()){
14            p = dq_head.front();
15            dq_head.pop_front();
16            if(!dq_head.empty())p -> next = dq_head.front();
17        }
18        p -> next = dq_tail.front();
19        while(!dq_tail.empty()){
20            p = dq_tail.front();
21            dq_tail.pop_front();
22            if(!dq_tail.empty())p -> next = dq_tail.front();
23        }
24        p -> next = nullptr;
25        return head;
26    }
27};

445. 两数相加

12/17

 1class Solution {
 2public:
 3    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 4        stack<ListNode*> st1;
 5        stack<ListNode*> st2;
 6        ListNode *p = l1,*q = l2;
 7        while(l1){
 8            st1.push(l1);
 9            l1 = l1 -> next;
10        }
11        while(l2){
12            st2.push(l2);
13            l2 = l2 -> next;
14        }
15  
16        int flag = st1.size() > st2.size() ? 1 : 0;
17        int ca = 0;
18        while(!st1.empty() || !st2.empty()){
19            int a = st1.empty() ? 0 : st1.top()->val;
20            int b = st2.empty() ? 0 : st2.top()->val;
21            int res = a + b + ca;
22            ca = res / 10 ;
23            int b_2 = res % 10 ;
24            if(flag)st1.top()->val = b_2;
25            else st2.top()->val = b_2;
26            if(!st1.empty())st1.pop();
27            if(!st2.empty())st2.pop();
28    
29        }
30        if(ca != 0){
31            ListNode *hh = new ListNode(ca);
32            if(flag){
33                hh -> next = p;
34                p = hh;
35            }
36            else {
37                hh -> next =q;  
38                q = hh;
39            }   
40        }
41        return flag == 1 ? p : q;
42    }
43};

725. 分隔链表

12/16

 1class Solution {
 2public:
 3    vector<ListNode*> splitListToParts(ListNode* head, int k) {
 4        vector<ListNode*> res(k,nullptr);
 5        deque<ListNode*> qu;
 6        ListNode *p = head;
 7        while(p){
 8            qu.push_back(p);
 9            p = p -> next;
10        }
11        int size = qu.size();
12        int per = size / k ,ready = 0, kk = 0;
13        ListNode *end = nullptr;
14        while(!qu.empty()){
15            res[kk] = qu.front();
16            end = qu.front();
17            ++kk;  
18            for(int i = 0 ; i < per ; ++i){
19                ++ready;
20                end = qu.front();
21                qu.pop_front();
22            }
23            if(ready + (k - kk) * per < size ){
24                ++ready;
25                end = qu.front();
26                qu.pop_front();
27            }
28            end -> next = nullptr;
29        }
30        return res;
31    }
32};

86. 分隔链表

12/15

 1class Solution {
 2public:
 3    ListNode* partition(ListNode* head, int x) {
 4        ListNode *small = new ListNode();
 5        ListNode *large = new ListNode();
 6        ListNode *s_head = small,*l_head = large;
 7        while(head){
 8            if(head->val < x){
 9                small->next = head;
10                small = small->next;
11            }else{
12                large->next = head;
13                large = large->next;
14            }
15            head = head->next;
16        }
17        large -> next = nullptr;
18        small->next = l_head -> next;
19        return s_head->next;
20    }
21};

61. 旋转链表

12/14

 1class Solution {
 2public:
 3    ListNode* rotateRight(ListNode* head, int k) {
 4        if(!head)return nullptr;
 5        deque<ListNode*> dq;
 6        ListNode *p = head;
 7        while(p->next){
 8            dq.push_back(p);
 9            p = p -> next;
10        }
11        dq.push_back(p);
12        p->next =head;
13        k %= dq.size();
14        while(k--){
15            dq.push_front(dq.back());
16            dq.pop_back();
17        }
18        head = dq.front();
19        dq.back()->next = nullptr;
20        return head;
21    }
22};

817. 链表组件

12/13

 1class Solution {
 2public:
 3    int numComponents(ListNode* head, vector<int>& nums) {
 4        vector<bool> exists(10000,false);
 5        for (int num : nums)exists[num] = true;
 6        int res = 0;
 7        ListNode* curr = head;
 8        while (curr != nullptr)
 9        {
10            if (exists[curr->val] && (curr->next == nullptr || !exists[curr->next->val]))
11            {
12                ++res;
13            }
14            curr = curr->next;
15        }
16        return res;
17    }
18};

剑指offer || 28

12/12

 1class Solution {
 2public:
 3    Node* flatten(Node* head) {
 4        dfs(head);
 5        return head;
 6    }
 7    Node* dfs(Node *head){
 8        Node *p = head,*tail = nullptr;
 9        while(p){
10            Node *next = p->next;
11            if(p->child){
12                Node *child = p->child;
13                Node *child_tail = dfs(child);
14
15                p->child = nullptr;
16                p->next = child;
17                child->prev = p;
18                child_tail->next = next;
19                if(next)next->prev = child_tail;
20
21                tail = child_tail;
22            }else{
23                tail = p;
24            }
25            p = p->next;
26        }
27        return tail;
28    }
29};

剑指offer || 78

12/11

 1class Solution {
 2public:
 3    ListNode* merge(ListNode* left,ListNode* right){
 4        ListNode *res = new ListNode(0);
 5        ListNode *p=left,*q=right,*tmp=res;
 6        while(p && q){
 7            if(p->val <= q->val){
 8                tmp->next = p;
 9                p = p->next;
10                tmp = tmp->next;
11            }else{
12                tmp->next = q;
13                q = q->next;
14                tmp = tmp->next;
15            }
16        }
17        if(p)tmp->next = p;
18        if(q)tmp->next = q;
19        return res->next;
20    }
21    ListNode* merge_lists(vector<ListNode*>& lists,int st,int end) {
22        if(st == end)return lists[st];
23        int mid = st + ((end - st)>>1);
24        ListNode *sr1 = merge_lists(lists,st,mid);
25        ListNode *sr2 = merge_lists(lists,mid+1,end);
26        return merge(sr1,sr2);
27    }
28    ListNode* mergeKLists(vector<ListNode*>& lists) {
29        if(lists.size() == 0)return nullptr;
30        return merge_lists(lists,0,lists.size()-1);
31    }
32};

剑指offer || 27 回文链表

12/11

随手写

 1class Solution {
 2public:
 3    bool isPalindrome(ListNode* head) {
 4        deque<ListNode*> dq;
 5        ListNode *p = head;
 6        while(p){
 7            dq.push_back(p);
 8            p = p->next;
 9        }
10        while(!dq.empty()){
11            if(dq.front()->val == dq.back()->val){
12                if(dq.size()==1){
13                    dq.pop_front();
14                }else{
15                    dq.pop_front();
16                    dq.pop_back();
17                }
18            }else{
19                return false;
20            }
21        }
22        return true;
23    }
24};

剑指offer || 26

思路没毛病，一个野指针找了好久，曹了

12/10

 1class Solution {
 2public:
 3    void reorderList(ListNode* head) {
 4        if(!head->next)return;
 5        deque<ListNode*> L,R;
 6        ListNode *left=head,*right=head,*mid = head;
 7        while(right && right->next){
 8            mid = left;
 9            left = left->next;
10            right = right->next->next;
11        }
12        mid->next = nullptr;
13        right = head;
14        while(right){
15            L.push_back(right);right = right->next;
16        }
17        while(left){
18            R.push_front(left);left = left->next;
19        }
20        right = L.front();
21        L.pop_front();
22        while(true){
23            if(R.empty() && L.empty())break;
24            if(!R.empty()){
25                R.front()->next = nullptr;
26                right->next = R.front();
27                R.pop_front();
28                right = right->next;
29            }
30            if(!L.empty()){
31                L.front()->next = nullptr;
32                right->next = L.front();
33                L.pop_front();
34                right = right->next;
35            }
36        }
37    }
38
39};

剑指offer II 77

一个简单的没有错误的错误找了好久

12/9

 1class Solution {
 2public:
 3    ListNode* merge_sort(ListNode *l1,ListNode *l2){
 4        ListNode *head = new ListNode();
 5        ListNode *node = head;
 6        while(l1 && l2){
 7            if(l1->val < l2->val){
 8                node->next = l1;
 9                l1 = l1->next;
10            }else{
11                node->next = l2;
12                l2 = l2->next;
13            }
14            node = node->next;
15        }
16        node->next = (l1 == nullptr) ? l2 : l1;
17        return head->next;
18    }
19    ListNode* sortList(ListNode* head) {
20        if(!head  || !head->next )return head;
21        ListNode *pre = head,*low = head,*fast=head;
22        while(fast && fast->next){
23            pre = low;
24            low = low->next;
25            fast = fast->next->next;
26        }
27        pre->next = nullptr;
28        return merge_sort(sortList(head), sortList(low));
29    }
30};

1669 合并两个链表

与链表有关的要全部刷完，很简单

12/8

 1class Solution {
 2public:
 3    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
 4        ListNode* left = list1,*right = list1,*p=list2;
 5        int k=a-1;
 6        while(k--)left = left->next;
 7        while(b--)right = right->next;
 8        while(p->next != nullptr)p = p->next;
 9        left->next = list2;
10        p->next = right->next;
11        return list1;
12    }
13};

剑指offer II 21 删除倒数第k个节点

12/7

 1class Solution {
 2public:
 3    ListNode* removeNthFromEnd(ListNode* head, int n) {
 4        if(head->next == nullptr)return nullptr;
 5        ListNode* fast=head,*low = head,*tmp=head;
 6        while(n--)fast = fast->next;
 7        if(!fast)return head->next;
 8        while(fast){
 9            fast = fast->next;
10            tmp=low;
11            low = low ->next;
12        }
13        tmp->next = low->next;
14        return head;
15    }
16};

2095 删除链表中的中间节点

2021/12/7

一搞linux 就忘记了，以后专注链表排序嵌入式算法

 1class Solution {
 2public:
 3    ListNode* deleteMiddle(ListNode* head) {
 4        if(head->next == nullptr)return nullptr;
 5        ListNode* fast = head,*low = head,*pre = head;
 6        while(fast->next){
 7            if(fast->next->next)
 8                fast = fast->next->next;
 9            else
10                fast = fast->next;
11            pre = low;
12            low = low->next;
13        }
14        pre->next = low ->next;
15        return head;
16    }
17};

118

11/24

 1class Solution {
 2public:
 3    vector<vector<int>> generate(int numRows) {
 4        vector<vector<int>> res;
 5        res.push_back({1});
 6        if(numRows==1)return res;
 7        res.push_back({1,1});
 8        for(int i = 2 ; i < numRows ; ++i){
 9            vector<int> tmp(i+1,1);
10            for(int j = 1 ; j < i ; ++j){
11                tmp[j] = res[i-1][j]+res[i-1][j-1];
12            }
13            res.push_back(tmp);
14        }
15        return res;
16    }
17};

108

11/24

 1class Solution {
 2public:
 3    TreeNode* sortedArrayToBST(vector<int>& nums) {
 4        return dfs(nums,0,nums.size()-1);
 5    }
 6    TreeNode* dfs(vector<int>&nums,int left,int right){
 7        if(left > right) return nullptr;
 8        int mid = left + (right - left)/2 ;
 9        TreeNode* node = new TreeNode(nums[mid]);
10        node->left = dfs(nums,left,mid-1);
11        node->right = dfs(nums,mid+1,right);
12        return node;
13    }
14};

剑指offer II 24

11/23

反转链表，就非要用别的方式

 1class Solution {
 2public:
 3    ListNode* reverseList(ListNode* head) {
 4        if(!head)return nullptr;
 5        ListNode* p = head;
 6        stack<ListNode*> st;
 7        while(p){
 8            st.push(p);
 9            p = p->next;
10        }
11        head = st.top();
12        ListNode* q = st.top();
13        st.pop();
14        while(!st.empty()){
15            q->next = st.top();
16            st.pop();
17            q = q->next;
18        }
19        q->next = nullptr;
20        return head;
21
22        // ListNode* prev = nullptr;
23        // ListNode* curr = head;
24        // while (curr) {
25        //     ListNode* next = curr->next;
26        //     curr->next = prev;
27        //     prev = curr;
28        //     curr = next;
29        // }
30        // return prev;
31    }
32};

剑指offer II 41

2021/11/23

200道题了

 1class MovingAverage {
 2public:
 3    /** Initialize your data structure here. */
 4    int size;
 5    queue<int> q;
 6    int res;
 7    MovingAverage(int val) {
 8        size = val;
 9        res = 0;
10    }  
11    double next(int val) {
12        q.push(val);
13        res += val;
14        if(q.size() > size){
15            res -= q.front();
16            q.pop();
17            return (double)res/size;
18        }
19        return (double)res/q.size();
20    }
21};

剑指offer 59

2021/11/21

 1class Solution {
 2public:
 3    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
 4        vector<int> res;
 5        deque<int> q;
 6        for(int right = 0 ; right < nums.size() ; ++ right){
 7            while(!q.empty() && nums[right] > nums[q.back()])
 8                q.pop_back();
 9            q.push_back(right);
10            int left = right - k + 1;
11            if(left > q.front())
12                q.pop_front();
13            if(right + 1 >= k)
14                res.push_back(nums[q.front()]);
15        }
16        return res;
17    }
18};

剑指offer 51

2021/11/20

 1class Solution {
 2public:
 3    int reversePairs(vector<int>& nums) {
 4        vector<int> tmp(nums.size());
 5        return merge_sort(0,nums.size()-1,nums,tmp);
 6    }
 7    int merge_sort(int left,int right,vector<int>& nums,vector<int>& tmp){
 8        if(left >= right)return 0;
 9        int mid = ( left + right ) / 2;
10        int res = merge_sort(left,mid,nums,tmp) + merge_sort(mid+1,right,nums,tmp);
11        //tmp.assign(nums.begin(),nums.end());  超出时间限制
12        for (int k = left; k <= right; k++)
13            tmp[k] = nums[k];
14        int i = left,j = mid + 1;
15        for(int k = left ; k <= right ; ++k){
16            if(i == mid + 1)nums[k] = tmp[j++];
17            // else if(j == right + 1)nums[k] = tmp[i++];
18            // else if(tmp[i] <= tmp[j])nums[k] = tmp[i++];
19            else if(j == right + 1 || tmp[i] <= tmp[j])nums[k] = tmp[i++];
20            else{
21                nums[k] = tmp[j++];
22                res += mid - i + 1;
23            }
24        }
25        return res;
26    }
27};

剑指offer 41

 1class MedianFinder {
 2public:
 3    priority_queue<int> small;
 4    priority_queue<int, vector<int>, greater<int> > big;
 5    int num_size;
 6    /** initialize your data structure here. */
 7    MedianFinder() {
 8        num_size = 0;
 9    }
10  
11    void addNum(int num) {
12        small.push(num);
13        big.push(small.top());
14        small.pop();
15        small.push(big.top());
16        big.pop();
17        ++num_size;
18        if(small.size() - big.size() == 2){big.push(small.top());small.pop();}
19    }
20  
21    double findMedian() {
22        if(num_size%2){
23            return small.top();
24        }else{
25            return (double)(small.top() + big.top())/2;
26        }
27    }
28};

剑指offer 20

又是看答案的一天，这题eeee

 1class Solution {
 2public:
 3    bool isNumber(string s) {
 4        vector<vector<pair<char,int>>> state = {
 5            {make_pair(' ',0),make_pair('s',1),make_pair('d',2),make_pair('.',4)},
 6            {make_pair('d',2),make_pair('.',4)},
 7            {make_pair('d',2),make_pair('.',3),make_pair('e',5),make_pair(' ',8)},
 8            {make_pair('d', 3), make_pair('e', 5), make_pair(' ', 8)},
 9            {make_pair('d', 3)},
10            {make_pair('s', 6), make_pair('d', 7) },
11            {make_pair('d', 7) },
12            {make_pair('d', 7) , make_pair(' ', 8)},
13            {make_pair(' ', 8)}
14        };
15        int p = 0 ;
16        char t;
17        for(auto& c : s){
18            if('0' <= c && c <= '9')t = 'd';
19            else if(c == '+' || c == '-') t = 's';
20            else if(c == 'e' || c == 'E') t = 'e';
21            else if(c == '.' || c == ' ') t = c;
22            else t = '?';
23            int flag = 0;
24            for(auto& st :state[p]){
25                if(st.first == t){
26                    flag = 1;
27                    p = st.second;
28                }
29            }
30            if(!flag) return false;
31        }
32        return p == 2 || p == 3 || p == 7 || p == 8;
33    }
34};

剑指offer 44

11/15

自己有点傻逼了

 1class Solution {
 2public:
 3    int findNthDigit(int n) {
 4        int digit = 1;
 5        long start = 1;
 6        long count = 9;
 7        while (n > count) { 
 8            n -= count;
 9            digit += 1;
10            start *= 10;
11            count = digit * start * 9;
12        }
13        long num = start + (n - 1) / digit; 
14        return to_string(num)[(n - 1) % digit]-'0';
15    }
16};

剑指offer 26

11/11

 1class Solution {
 2public:
 3    bool isSubStructure(TreeNode* A, TreeNode* B) {
 4        if(!A||!B)return false;
 5        return check(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
 6    }
 7    bool check(TreeNode* A, TreeNode* B){
 8        if(!B)return true;
 9        if(!A || A->val != B->val)return false;
10        return check(A->right,B->right)&&check(A->left,B->left);
11    }
12};

剑指offer 46

11/10

不知不觉就快双十一了

 1class Solution {
 2public:
 3    int translateNum(int num) {
 4        string s = to_string(num); 
 5        int n = s.size();
 6        int p_i_2 = 0,p_i_1 = 0,p_i = 1;
 7        for(int i = 1; i <= n; i++){
 8            p_i_2 = p_i_1;
 9            p_i_1 = p_i;
10           // p_i = p_i_1;
11            if(i > 1){ 
12                int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
13                if(t >= 10 && t <= 25)  
14                    p_i += p_i_2; 
15            }   
16        }
17        return p_i;
18    }
19};
20// class Solution {
21// public:
22//     int translateNum(int num) {
23//         string s = to_string(num); 
24//         int n = s.size();
25//         vector<int> f(n + 1);
26//         f[0] = 1;
27  
28//         for(int i = 1; i <= n; i++){
29//             f[i] = f[i - 1]; 
30//             if(i > 1){ 
31//                 int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
32//                 if(t >= 10 && t <= 25)  
33//                     f[i] += f[i - 2];   
34//             }   
35//         }
36//         return f[n];
37//     }
38// };

剑指offer 59

11/9

 1class MaxQueue {
 2public:
 3    queue<int> _queue;
 4    deque<int> _deque;
 5    MaxQueue() {
 6
 7    }
 8  
 9    int max_value() {
10        if(!_deque.empty())
11            return _deque.front();
12        return -1;
13    }
14  
15    void push_back(int value) {
16        _queue.push(value);
17        while(!_deque.empty()&&(_deque.back()< value))_deque.pop_back();
18        _deque.push_back(value);
19    }
20  
21    int pop_front() {
22        if(_queue.empty())return -1;
23        if(_queue.front() == _deque.front())_deque.pop_front();
24        int res = _queue.front();
25        _queue.pop();
26        return res;
27    }
28};

剑指offer 60

11/8

 1class Solution {
 2public:
 3    vector<double> dicesProbability(int n) {
 4        vector<double> pre(6);
 5        for(int i=0;i<6;++i) pre[i]=1.0/6;
 6        for(int i = 2 ; i <= n ; ++i){
 7            vector<double> tmp(5*i+1,0);
 8            for(int k = 0 ; k < pre.size() ;k++){
 9                for(int j = 0 ; j < 6 ;j++){
10                    tmp[k+j] += pre[k]/6;
11                }
12            }
13            pre = tmp;
14        }
15        return pre;
16    }
17};

剑指offer 34

11/7

 1class Solution {
 2public:
 3    vector<vector<int>> res;
 4    vector<int> res_tmp;
 5    int target_tmp = 0;
 6    vector<vector<int>> pathSum(TreeNode* root, int target) {
 7        dfs(root,target);
 8        return res;
 9    }
10    void dfs(TreeNode* root,int target){
11        if(!root)return;
12        target_tmp += root->val;
13        res_tmp.push_back(root->val);
14        if((target == target_tmp) && !(root->left) && !(root->right))res.push_back(res_tmp);
15        dfs(root->left,target);
16        dfs(root->right,target);
17        target_tmp -= root->val;
18        res_tmp.pop_back();
19    }
20};

剑指offer 32 |||

11/5

 1class Solution {
 2public:
 3    vector<vector<int>> levelOrder(TreeNode* root) {
 4        if(!root)return {};
 5        vector<vector<int>> res;
 6        deque<TreeNode*> dq;
 7        int layer = 1;
 8        dq.push_back(root);
 9        while(!dq.empty()){
10            vector<int> tmp;
11            int len = dq.size();
12            while(len--){
13                if(layer & 1){
14                    tmp.push_back(dq.front()->val);
15                    if(dq.front()->left)dq.push_back(dq.front()->left);
16                    if(dq.front()->right)dq.push_back(dq.front()->right); 
17                    dq.pop_front();
18                }else{
19                    tmp.push_back(dq.back()->val);
20                    if(dq.back()->right)dq.push_front(dq.back()->right);
21                    if(dq.back()->left)dq.push_front(dq.back()->left);
22                    dq.pop_back();
23                }
24            }
25            res.push_back(tmp);
26            ++layer;
27        }
28        return res;
29    }
30};

剑指offer 32

11/4

 1class Solution {
 2public:
 3    vector<int> levelOrder(TreeNode* root) {
 4        if(!root)return {};
 5        queue<TreeNode*> q;
 6        vector<int> res;
 7        q.push(root);
 8        while(!q.empty()){
 9            if(q.front()->left)q.push(q.front()->left);
10            if(q.front()->right)q.push(q.front()->right);
11            res.push_back(q.front()->val);
12            q.pop();
13        }
14        return res;
15    }
16};

剑指offer 49

11/4

 1class Solution {
 2public:
 3    int nthUglyNumber(int n) {
 4        int a = 0,b = 0,c = 0;
 5        vector<int> dp(n);
 6        dp[0] = 1;
 7        for(int i = 1 ; i < n ; ++i){
 8            int tmp2 = dp[a]*2,tmp3 = dp[b]*3,tmp5 = dp[c]*5;
 9            dp[i] = min(tmp2,min(tmp3,tmp5));
10            if(dp[i] == tmp2)++a;
11            if(dp[i] == tmp3)++b;
12            if(dp[i] == tmp5)++c;
13        }
14        return dp[n-1];
15    }
16};

剑指offer 47

11/3

 1class Solution {
 2public:
 3    // 动态规划
 4    int maxValue(vector<vector<int>>& grid) {
 5        vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size(),0));
 6        for(int i = 0 ; i < grid.size() ; ++i){
 7            for(int j = 0 ; j < grid[0].size() ; ++j){
 8                if(i == 0 && j == 0)dp[i][j] = grid[i][j];
 9                else if(i == 0 && j != 0)dp[i][j] = dp[i][j-1] + grid[i][j];
10                else if(i != 0 && j == 0)dp[i][j] = dp[i-1][j] + grid[i][j];
11                else dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) + grid[i][j];
12            }
13        }
14        return dp[grid.size()-1][grid[0].size()-1];
15    }
16};

剑指offer 56

11/2

 1class Solution {
 2public:
 3    vector<int> singleNumbers(vector<int>& nums) {
 4        int tmp = 0, m = 1,x = 0, y = 0;
 5        for(auto& c : nums)tmp ^= c;
 6        while((tmp & m) == 0) m <<= 1;
 7        for(auto& c : nums){
 8            if((c & m))x ^= c;
 9            else y ^= c;
10        }
11        return {x,y};
12    }
13};

剑指offer 35

11/1

 1/*
 2// Definition for a Node.
 3class Node {
 4public:
 5    int val;
 6    Node* next;
 7    Node* random;
 8  
 9    Node(int _val) {
10        val = _val;
11        next = NULL;
12        random = NULL;
13    }
14};
15*/
16class Solution {
17public:
18    Node* copyRandomList(Node* head) {
19        if(!head) return nullptr;
20        Node* cur = head;
21        unordered_map<Node*, Node*> map;
22        while(cur){
23            map[cur] = new Node(cur->val);
24            cur = cur->next;
25        }
26        cur = head;
27        while(cur){
28            map[cur]->next = map[cur->next];
29            map[cur]->random = map[cur->random];
30            cur = cur->next;
31        }
32        return map[head];
33
34    }
35};

剑指offer 58

10/30

 1class Solution {
 2public:
 3    string reverseWords(string s) {
 4        if(!s.size())return "";
 5        int i = 0,j = 0 , n = s.size()-1;
 6        stack<string> word;
 7        string res = "";
 8        if(!n && s != " ")return s;
 9        if(!n)return "";
10        while(i < n){
11            while(i < n && s[i] == ' ')++i;
12            j = i;
13            while(j <= n && s[j] != ' ')++j;
14            if(s.substr(i,j-i) != "")word.push(s.substr(i,j-i));
15            i = j;
16        }
17        while(!word.empty()){
18            res += word.top();
19             if(word.size() != 1)res += ' ';
20            word.pop();
21   
22        }
23        return res;
24    }
25};

剑指offer 57

10/25

 1class Solution {
 2public:
 3    vector<int> twoSum(vector<int>& nums, int target) {
 4        int i = 0 , j = nums.size()-1,sum = 0;
 5        while(true){
 6            sum = nums[i]+nums[j];
 7            if(sum == target)break;
 8            if(sum < target)++i;
 9            if(sum > target)--j;
10        }
11        return {nums[i],nums[j]};
12    }
13};

剑指offer 32

10/25

 1class Solution {
 2public:
 3    vector<vector<int>> levelOrder(TreeNode* root) {
 4        queue<TreeNode*> q;
 5        vector<vector<int>> res;
 6        if(!root)return res;
 7        q.push(root);
 8        while(!q.empty()){
 9            vector<int> tmp;
10            int s = q.size();
11            for(int i = 0 ; i < s ; ++i){
12                tmp.push_back(q.front()->val);
13                if(q.front()->left)q.push(q.front()->left);
14                if(q.front()->right)q.push(q.front()->right);
15                q.pop();
16            }
17            res.push_back(tmp);
18        }
19        return res;
20    }
21};

剑指offer 39

10/24/

 1class Solution {
 2public:
 3    int majorityElement(vector<int>& nums) {
 4        unordered_map<int,int> hash;
 5        int res_num = 0, max_num = 0 ;
 6        for(auto& i : nums){
 7            ++hash[i];
 8            if(hash[i] > max_num){
 9                res_num = i;
10                max_num = hash[i];
11            }
12        }
13        return res_num;
14    }
15};

剑指offer

10/24

 1class Solution {
 2public:
 3    vector<vector<int>> findContinuousSequence(int target) {
 4        vector<vector<int>> res;
 5        int left = 1, right = 2, sum = 3;
 6        while(left < right){
 7            if(sum == target){
 8                vector<int> r;
 9                for(int i = left ; i <= right ; ++i) r.push_back(i);
10                res.push_back(r);
11            }
12            if(sum < target){
13                ++right;
14                sum += right;
15            }else if (sum >= target){
16                sum -= left;
17                ++left;
18            }
19        }
20        return res;
21    }
22};

剑指offer 68

10/23

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

剑指offer 17

21/10/23

 1class Solution {
 2public:
 3    vector<int> res;
 4    vector<int> printNumbers(int n) {
 5        string path(n,'0');
 6        dfs(n,0,path);
 7        return res;
 8    }
 9    void dfs(int n,int x,string str){
10        if(x == n){
11            int val = std::stoi(str);
12            if(val)res.push_back(val);
13            return;
14        }
15        for(int i = 0 ; i < 10 ; ++i ){
16            str[x] = i + '0';
17            dfs(n,x+1,str);
18        }
19    }
20};

剑指offer 29

21/10/22

 1class Solution {
 2public:
 3    vector<int> spiralOrder(vector<vector<int>>& matrix) {
 4        if(!matrix.size()) return {};
 5        vector<int> res;
 6        int left = 0,right = matrix[0].size()-1,top = 0,bottom = matrix.size()-1;
 7        while(true){
 8            for(int i = left ; i <= right;++i)res.push_back(matrix[top][i]);
 9            if(++top > bottom)break;
10            for(int i = top ; i <= bottom;++i)res.push_back(matrix[i][right]);
11            if(--right < left)break;
12            for(int i = right ; i >= left;--i)res.push_back(matrix[bottom][i]);
13            if(--bottom < top)break;
14            for(int i = bottom ; i >= top;--i)res.push_back(matrix[i][left]);
15            if(++left > right)break;
16        }
17        return res;
18    }
19};

剑指offer54

10/22

 1class Solution {
 2public:
 3    int count = 0,res = 0;
 4    int kthLargest(TreeNode* root, int k) {
 5        dfs(root,k);
 6        return res;
 7    }
 8    void dfs(TreeNode* node,int k){
 9        if(!node)return;
10        dfs(node->right,k);
11        ++count;
12        if(count == k) res = node->val;
13        dfs(node->left,k);
14    }
15};

剑指offer21

2021/10/21

 1class Solution {
 2public:
 3    vector<int> exchange(vector<int>& nums) {
 4        int i = 0 , j = nums.size()-1,p=0;
 5        while(i < j){
 6            while(i<j && nums[i]%2 == 1)++i;
 7            while(i<j && nums[j]%2 == 0)--j;
 8            swap(nums[i++],nums[j--]);
 9        }
10        return nums;
11    }
12};

剑指offer27

2021/10/21

 1class Solution {
 2public:
 3    TreeNode* mirrorTree(TreeNode* root) {
 4        if(!root)return nullptr;
 5        TreeNode* tmp = root->right;
 6        root->right = mirrorTree(root->left);
 7        root->left = mirrorTree(tmp);
 8        return root;
 9    }
10};

10. 正则表达式匹配

2021/10/20

热题 hot 100结束了

 1class Solution {
 2public:
 3    //犯了一个错误，最后才想明白，就是被注释的代码，竟然想到用for循环找单个字符
 4    bool isMatch(string s, string p) {
 5        vector<vector<bool>> dp(s.size()+1,vector<bool>(p.size()+1,false));
 6        dp[0][0] = true;
 7        for(int i = 1 ; i < dp[0].size() ; ++i){
 8            // for(auto &c : p){
 9            char c = p[i-1];
10            if(c == '*' && i > 1)
11                dp[0][i] = dp[0][i-2];
12            if(i == 1 && c == '*')
13                dp[0][i] = true;
14            // }
15        }
16        for(int i = 1 ; i < dp.size() ; ++i){
17            //for(auto &c : s){
18            char c = s[i-1];
19            for(int j = 1 ; j < dp[i].size() ; ++j){
20                char m = p[j-1];
21                if(c == m || m == '.'){
22                    dp[i][j] = dp[i-1][j-1];
23                }else if(m == '*'){
24                    if(j > 1){
25                        if(dp[i][j-2] == true)
26                            dp[i][j] = true;
27                        else{
28                            char m_prv = p[j-2];
29                            if(m_prv == c || m_prv == '.')
30                                dp[i][j] = dp[i-1][j];
31                        }
32                    }
33                }  
34            }
35            //}
36        }
37        return dp[s.size()][p.size()];
38    }
39};

32. 最长有效括号

2021/10/19

 1class Solution {
 2public:
 3    int longestValidParentheses(string s) {
 4        int longest_len = 0 ;
 5        stack<int> l_stack;
 6        l_stack.push(-1);
 7        for(int i = 0 ; i < s.size() ; ++i){
 8            if(s[i] == '('){
 9                l_stack.push(i);
10            }else{
11                l_stack.pop();
12                if(l_stack.empty()){
13                    l_stack.push(i);
14                }else{
15                    longest_len = max(longest_len,i-l_stack.top());
16                }
17            }
18        }
19        return longest_len;
20    }
21};

76. 最小覆盖子串

2021/10/18

 1class Solution {
 2public:
 3    string minWindow(string s, string t) {
 4        int cnt= 0 ,count = t.size();
 5        unordered_map<char, int> tt,ss;
 6        string res;
 7        for(auto& c : t)++tt[c];
 8        for(int i = 0 , j = 0 ; i < s.size() ; ++i){
 9            ++ss[s[i]];
10            if(ss[s[i]] <= tt[s[i]])++cnt;
11            while(ss[s[j]] > tt[s[j]])--ss[s[j++]];
12            if(cnt == count){
13                if(res.empty() || i-j+1 < res.size()){
14                    res = s.substr(j,i-j+1);
15                }
16            }
17        }
18        return res;
19    }
20};

239. 滑动窗口最大值

2021/10/18

用对队列

 1class MyQueue {
 2private:
 3    deque<int> data;
 4public:
 5    void push(int n) {
 6        while (!data.empty() && data.back() < n) 
 7            data.pop_back();
 8        data.push_back(n);
 9    }
10  
11    int max() { return data.front(); }
12  
13    void pop(int n) {
14        if (!data.empty() && data.front() == n)
15            data.pop_front();
16    }
17};
18class Solution {
19public:
20    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
21        MyQueue window;
22        vector<int> res;
23        for(int i = 0 ; i < k-1 ; ++i) window.push(nums[i]);
24        for (int i = k-1; i < nums.size(); i++) {  
25            window.push(nums[i]);
26            res.push_back(window.max());
27            window.pop(nums[i - k + 1]);  
28        }
29        return res;
30    }
31};

85. 最大矩形

2021/10/17

用84题解决

 1class Solution {
 2public:
 3    int largestRectangleArea(vector<int>& heights) {
 4        int res = 0 ,len = heights.size();
 5        stack<int> my_stack;
 6        vector<int> new_heights(len+2,0);
 7        for(int i = 1 ; i < len + 1 ; ++i)new_heights[i] = heights[i-1];
 8        for(int i = 0 ; i < len+2 ; ++i){
 9            while(!my_stack.empty() && new_heights[i] < new_heights[my_stack.top()]){
10                int cur = my_stack.top();
11                my_stack.pop();
12                int cur_height = new_heights[cur];
13                int left = my_stack.top();
14                int right = i;
15                int width = right - left - 1;
16                res = max(res,cur_height*width);
17            }
18            my_stack.push(i);
19        } 
20        return res; 
21    }
22    int maximalRectangle(vector<vector<char>>& matrix) {
23        if(matrix.size() == 0)return 0;
24        int row = matrix.size(),col = matrix[0].size();
25        vector<int> tmp(col,0);
26        //for(int i = 0 ; i < col ; ++i)tmp[i] = atoi(matrix[0][i]);
27        //此处char 转int 不知道为什么这个函数说没有，换了写法
28        int res = largestRectangleArea(tmp);
29        for(int i = 0 ; i < row ; ++i){
30            for(int j = 0 ; j < col ; ++j){
31                //tmp[j] += atoi(matrix[i][j]);
32                if(matrix[i][j] == '1'){
33                    ++tmp[j];
34                }else{
35                    tmp[j] = 0;
36                }
37            }
38            res = max(res,largestRectangleArea(tmp));
39        }
40        return res;
41    }
42};

84. 柱状图中最大的矩形

2021/10/16

单调栈

 1class Solution {
 2public:
 3    int largestRectangleArea(vector<int>& heights) {
 4        int res = 0 ,len = heights.size();
 5        stack<int> my_stack;
 6        vector<int> new_heights(len+2,0);
 7        for(int i = 1 ; i < len + 1 ; ++i)new_heights[i] = heights[i-1];
 8        for(int i = 0 ; i < len+2 ; ++i){
 9            while(!my_stack.empty() && new_heights[i] < new_heights[my_stack.top()]){
10                int cur = my_stack.top();
11                my_stack.pop();
12                int cur_height = new_heights[cur];
13                int left = my_stack.top();
14                int right = i;
15                int width = right - left - 1;
16                res = max(res,cur_height*width);
17            }
18            my_stack.push(i);
19        } 
20        return res; 
21    }
22};

301. 删除无效的括号

2021/10/15

有点难

 1class Solution {
 2public:
 3    bool Is_Valid(const string& s){
 4        int count = 0;
 5        for( char c : s){
 6            if(c == '(')++count;
 7            if(c == ')')--count;
 8            if(count < 0)return false;
 9        }
10        return count == 0 ;
11    }
12    vector<string> removeInvalidParentheses(string s) {
13        unordered_set<string> word{s};
14        while(true){
15            unordered_set<string> res;
16            for(auto& w : word){
17                if(Is_Valid(w))
18                    res.insert(w);
19            }
20            if(!res.empty())   
21                return vector<string>(res.begin(),res.end());
22            unordered_set<string> next_word;
23            for (const string& t : word) {
24                for (int i = 0; i < t.length(); ++i) {
25                    if (t[i] == '(' || t[i] == ')') {
26                        next_word.insert(t.substr(0, i) + t.substr(i+1,t.size()-i-1));
27                    }
28                }
29            }
30            word = next_word;
31        }
32        return {};
33    }
34};

312. 戳气球

2021/10/14

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

72. 编辑距离

2021/10/13

动态规划

 1class Solution {
 2public:
 3    int minDistance(string word1, string word2) {
 4        int row = word1.size(),col = word2.size();
 5        vector<vector<int>> dp(row+1,vector<int>(col+1));
 6        for(int i = 0 ; i <= row ; ++i)dp[i][0] = i;
 7        for(int i = 0 ; i <= col ; ++i)dp[0][i] = i;
 8        for(int i = 1 ; i <= row ; ++i){
 9            for(int j = 1 ; j <= col ; ++j){
10                if(word1[i-1] == word2[j-1]){
11                    dp[i][j] = dp[i-1][j-1];
12                }else{
13                    dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
14                }
15            }
16        }
17        return dp[row][col];
18    }
19};

297. 二叉树的序列化与反序列化

2021/10/12

中等级别

 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 */
10class Codec {
11public:
12 
13    // Encodes a tree to a single string.
14    string serialize(TreeNode* root) {
15        if(!root)return "None";
16        return to_string(root->val)+","+ serialize(root->left)+","+serialize(root->right);
17    }
18 
19    // Decodes your encoded data to tree.
20    TreeNode* deserialize(string data) {
21        list<string> array;
22        string tmp;
23        for(auto& ch :data){
24            if(ch != ','){
25                tmp.push_back(ch);
26            }else{
27                array.push_back(tmp);
28                tmp.clear();
29            }
30        }
31        array.push_back(tmp);
32        return dfs(array);
33    }
34    TreeNode* dfs(list<string>& array){
35        if(array.front() == "None"){
36             array.erase(array.begin());
37             return nullptr;
38        }
39        TreeNode* root = new TreeNode(stoi(array.front()));
40        array.erase(array.begin());
41        root->left = dfs(array);
42        root->right = dfs(array);
43        return root;
44    }
45 
46};
47 
48// Your Codec object will be instantiated and called as such:
49// Codec ser, deser;
50// TreeNode* ans = deser.deserialize(ser.serialize(root));

42. 接雨水

2021/10/11

 1//author : Aen
 2//blog   : https://aeneag.xyz
 3//公众号  : 技术乱舞
 4class Solution {
 5public:
 6    int trap(vector<int>& height) {
 7        int n = height.size();
 8        if (!n) return 0;
 9        vector<int> leftMax(n),rightMax(n);
10        leftMax[0] = height[0];
11        rightMax[n - 1] = height[n - 1];
12        for (int i = 1,j = n-2; i < n, j >= 0; ++i,--j) {
13            leftMax[i] = max(leftMax[i - 1], height[i]);
14            rightMax[j] = max(rightMax[j + 1], height[j]);
15        }
16        int ans = 0;
17        for (int i = 0; i < n; ++i)ans += min(leftMax[i], rightMax[i]) - height[i];
18        return ans;
19    }
20};

152. 乘积最大子数组

2021/10/10

动态规划思想

 1class Solution {
 2public:
 3    int maxProduct(vector<int>& nums) {
 4        int len = nums.size(),res = nums[0];
 5        vector<int> f(len+1,0),g(len+1,0);
 6        f[0] = nums[0],g[0] = nums[0];
 7        for(int i = 1 ; i < len ; ++i){
 8            f[i] = max(nums[i], max(f[i - 1] * nums[i], g[i - 1] * nums[i])); 
 9            g[i] = min(nums[i], min(g[i - 1] * nums[i], f[i - 1] * nums[i])); 
10            res = max(res,f[i]);
11        }
12        return res;
13    }
14};
15class Solution {
16public:
17    int maxProduct(vector<int>& nums) {
18        int len = nums.size(),res = nums[0];
19        int max_num= nums[0] , min_num = nums[0],max_tmp = nums[0],min_tmp = nums[0];
20        for(int i = 1 ; i < len ; ++i){
21            max_tmp = max_num,min_tmp = min_num;
22            max_num = max(nums[i], max(max_tmp * nums[i], min_tmp * nums[i])); 
23            min_num = min(nums[i], min(max_tmp * nums[i], min_tmp * nums[i])); 
24            res = max(res,max_num);
25        }
26        return res;
27    }
28};
29/*
30* [2 3 -2 4]
31* 动态规划
32* f[i] g[i] 表示以当前节点结尾的连续子数组的max，min值
33* 首先我们不知道最大值是否是正数还是负数
34* 1) 计算最大值
35*       当nums[i] >= 0 时
36*                       1.把当前节点的值看作子数组，
37*                       2.当前节点与前一个最大连续子数组(f[i-1])相乘，组成该节点的子数组  
38*       当nums[i] <  0 时
39*                       1.把当前节点的值看作子数组，
40*                       2.当前节点与前一个最小连续子数组(g[i-1])相乘，组成该节点的子数组  
41*       最后比较最大值
42*                       nums[i] nums[i]*f[i-1] nums[i]*g[i-1]
43* 2) 计算最小值
44*      当nums[i] >= 0 时
45*                       1.把当前节点的值看作子数组，
46*                       2.当前节点与前一个最小连续子数组(g[i-1])相乘，组成该节点的子数组  
47*      当nums[i] <  0 时
48*                       1.把当前节点的值看作子数组，
49*                       2.当前节点与前一个最小连续子数组(f[i-1])相乘，组成该节点的子数组  
50*      最后比较最大值
51*                       nums[i] nums[i]*f[i-1] nums[i]*g[i-1]
52*/

221. 最大正方形

2021/10/10

什么时候可以自己想到方法

 1class Solution {
 2public:
 3    int maximalSquare(vector<vector<char>>& matrix) {
 4        int row = matrix.size(),col = matrix[0].size(),res = 0;
 5        if(!row || !col)return 0;
 6        vector<vector<int>> dp(row,vector<int>(col,0));
 7        for(int i = 0 ; i < row ; ++i){
 8            for(int j = 0 ; j < col ; ++j){
 9                if(matrix[i][j] == '1'){
10                    if(!i || !j){
11                        dp[i][j] = 1;
12                    }else{
13                        dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
14                    }
15                    res = max(res,dp[i][j]);
16                }
17            }
18        }
19        return res*res;
20    }
21};

238. 除自身以外数组的乘积

2021/10/9

第二题

 1class Solution {
 2public:
 3    vector<int> productExceptSelf(vector<int>& nums) {
 4        int len = nums.size();
 5        vector<int> res(len,0);
 6        int left = 1 , right = 1;
 7        for(int i = 0 ; i < len ; ++i){
 8            res[i] = left;
 9            left *= nums[i];
10        }
11        for(int i = len - 1 ; i > 0 ; --i){
12            right *= nums[i];
13            res[i-1] *= right;
14        }
15        return res;
16    }
17};

240. 搜索二维矩阵 II

2021/10/9

刷题记录会在csdn同步更新

算法真的妙

 1class Solution {
 2public:
 3    bool searchMatrix(vector<vector<int>>& matrix, int target) {
 4        int col = matrix[0].size(),row = matrix.size();
 5        int i = 0 ,j = col - 1 ;
 6        if(!row&&!col)return false;
 7        while(i < row && j >= 0){
 8            if(matrix[i][j] == target)return true;
 9            else if(matrix[i][j] < target)++i;
10            else if(matrix[i][j] > target)--j;
11        }
12        return false;
13  
14    }
15};

300. 最长递增子序列

2021/10/8

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

139. Word Break 单词拆分

2021/10/7

今天又做了一个决策，算法输出到csdn，要更专业

动态规划

 1class Solution {
 2public:
 3    bool wordBreak(string s, vector<string>& wordDict) {
 4        int len = s.size();
 5        auto wordDictSet = unordered_set <string>();//新建一个无序集合
 6        for(auto word : wordDict)wordDictSet.insert(word);//子单词插入到这个无序集合中
 7        auto dp = vector<bool> (len+1);//动态规划dp数组
 8        dp[0] = true;//第一项说明空串是true
 9        for(int i = 1 ; i <= len ; ++i){ // for循序，dp[i]如果是true意思是说前i个串匹配到
10            for(int j = 0 ; j < i ; ++j){
11                if(dp[j] && wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end()){
12                    dp[i] = true;
13                    break;//如果匹配到就跳出这个循环，继续下一个i
14                }
15            }
16        }
17        return dp[len];
18    }
19};

322. 零钱兑换

2021/10/6

 1class Solution {
 2public:
 3    int coinChange(vector<int>& coins, int amount) {
 4        int len = coins.size();
 5        vector<int> dp(amount+1,amount+1);
 6        dp[0] = 0;
 7        for(int i = 1 ; i <= amount ; ++i){
 8            for(int j = 0 ; j < len ; ++j){
 9                if(coins[j] <= i){
10                    dp[i] = min(dp[i],dp[i - coins[j]]+1);
11                }
12            }
13        }
14        return dp[amount] > amount ? -1 : dp[amount];
15    }
16};

309. 最佳买卖股票时机含冷冻期

2021/10/5

动态规划什么时候自己可以完全想到

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

399. 除法求值

2021/10/5

这个有点难，不是自己写的，别人怎么能想到 = =，理解代码

 1class Solution {
 2public:
 3    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
 4        int nvars = 0;
 5        unordered_map<string, int> variables;
 6
 7        int n = equations.size();
 8        for (int i = 0; i < n; i++) {
 9            if (variables.find(equations[i][0]) == variables.end()) {
10                variables[equations[i][0]] = nvars++;
11            }
12            if (variables.find(equations[i][1]) == variables.end()) {
13                variables[equations[i][1]] = nvars++;
14            }
15        }
16        vector<vector<double>> graph(nvars, vector<double>(nvars, -1.0));
17        for (int i = 0; i < n; i++) {
18            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
19            graph[va][vb] = values[i];
20            graph[vb][va] = 1.0 / values[i];
21        }
22
23        for (int k = 0; k < nvars; k++) {
24            for (int i = 0; i < nvars; i++) {
25                for (int j = 0; j < nvars; j++) {
26                    if (graph[i][k] > 0 && graph[k][j] > 0) {
27                        graph[i][j] = graph[i][k] * graph[k][j];
28                    }
29                }
30            }
31        }
32
33        vector<double> ret;
34        for (const auto& q: queries) {
35            double result = -1.0;
36            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
37                int ia = variables[q[0]], ib = variables[q[1]];
38                if (graph[ia][ib] > 0) {
39                    result = graph[ia][ib];
40                }
41            }
42            ret.push_back(result);
43        }
44        return ret;
45    }
46};

207. 课程表

2021/10/3

菜狗就是自己

 1class Solution {
 2public:
 3    vector<vector<int>> edges;
 4    vector<int> visited;
 5    bool res = true;
 6    void dfs(int u){
 7        visited[u] = 1;
 8        for(auto v: edges[u]){
 9            if(!visited[v]){
10                dfs(v);
11                if(!res)return;
12            }else if(visited[v] == 1){
13                res = false;
14                return;
15            }
16        }
17        visited[u] = 2;
18    }
19    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
20        edges.resize(numCourses);
21        visited.resize(numCourses);
22        for(auto& info:prerequisites){
23            edges[info[1]].push_back(info[0]);
24        }
25        for(int i = 0 ; i < numCourses && res; ++i){
26            if(!visited[i])dfs(i);
27        }
28        return res;
29    }
30};

128. 最长连续序列

2021/10/2

自己总是想不到，c用习惯了想不到用库

 1class Solution {
 2public:
 3    int longestConsecutive(vector<int>& nums) {
 4        unordered_set<int> hash;
 5        for(auto x : nums)hash.insert(x);
 6        int res = 0,y = 0;
 7        for(auto x :nums){
 8            if(!hash.count(x-1)){
 9                y = x;
10                while(hash.count(y+1))y++;
11                res = max(res,y-x+1);
12            }
13        }
14        return res;
15    }
16};

200. 岛屿数量

2021/10/1

为什么自己想不到这个

 1class Solution {
 2public:
 3    int numIslands(vector<vector<char>>& grid) {
 4        int res = 0;
 5        int row = grid.size(),col = grid[0].size();
 6        for(int i = 0 ; i < row ; ++i){
 7            for(int j = 0 ; j < col ; ++j){
 8                if(grid[i][j] == '1'){
 9                    dfs(grid,i,j,row,col);
10                    ++res;
11                }
12            }
13        }
14        return res;
15    }
16    void dfs(vector<vector<char>>& grid,int i , int j,int row,int col){
17        if(i<0 || i >= row|| j<0 || j >= col || grid[i][j] == '0')return;
18        grid[i][j] = '0';
19        dfs(grid,i+1,j,row,col);
20        dfs(grid,i-1,j,row,col);
21        dfs(grid,i,j+1,row,col);
22        dfs(grid,i,j-1,row,col);
23    }
24};