WRY

Where Are You?
You are on the brave land,
To experience, to remember...

0%

算法随记 【2024年01月】

Posted on Edited on In
随手做的算法题

练习收获

1

联想思考

有序，单调栈，双指针

2

C++中unordered_map和map的对比

unordered_map, 哈希表，无序，\(O(1)\)，最差性能可能会退化成\(O(lgn)\)。适合查找场景。

map, 红黑树，有序，\(O(lgn)\), 存储空间大，适合有序场景。

同理unordered_set和set的对比。

练习题目

2487. Remove Nodes From Linked List

题目描述

Version 1

递归程序实现，如果当前节点比递归回退出来的最大值还小，删除当前节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int removeNodesWithVal(ListNode* head, ListNode* hsl) {
        int max_val = 0;
        if(head->next){
            max_val = removeNodesWithVal(head->next, head);
        }
        if(head->val < max_val) { // remove head node.
            hsl->next = head->next;
        } else { // update max_val
            max_val = head->val;
        }
        return max_val;
    }
    ListNode* removeNodes(ListNode* head) {
        ListNode* fhead = new ListNode(INT_MAX, head);
        removeNodesWithVal(head, fhead);
        return fhead->next;
    }
};

Version 2

使用栈来代替递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode* fhead = new ListNode(INT_MAX, head);
        stack<pair<ListNode*, ListNode*>> st;
        while(head){
            st.push(pair(head, fhead));
            fhead = head;
            head = head->next;
        }
        int max_right_val = fhead->val;
        while(!st.empty()){
            pair<ListNode*, ListNode*> ele = st.top();
            st.pop();
            if(ele.first->val < max_right_val) {
                ele.second->next = ele.first->next;
            } else {
                max_right_val = ele.first->val;
            }
            fhead = ele.second;
        }
        return fhead->next;
    }
};

Version 3

精简栈的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode* fhead = new ListNode(INT_MAX, head);
        stack<ListNode*> st;
        while(head){
            st.push(fhead);
            fhead = head;
            head = head->next;
        }
        int max_right_val = fhead->val;
        while(!st.empty()){
            ListNode* left = st.top();
            ListNode* cur = left->next;
            st.pop();
            if(cur->val < max_right_val) {
                left->next = cur->next;
            } else {
                max_right_val = cur->val;
            }
            fhead = left;
        }
        return fhead->next;
    }
};

Version 4

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode* fhead = new ListNode(INT_MAX, head);
        stack<ListNode*> st;
        st.push(fhead);
        while(head) {
            while(st.top()->val < head->val) st.pop();
            st.top()->next = head;
            st.push(head);
            head = head->next;
        }
        return fhead->next;
    }
};

Version 5

反转链表之后，删除右边更小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = nullptr;
        ListNode* nn = nullptr;
        while(head) {
            nn = head->next;
            head->next = new_head;
            new_head = head;
            head = nn;
        }
        return new_head;
    }
    ListNode* removeNodes(ListNode* head) {
        head = reverseList(head);
        ListNode* lt = head;
        ListNode* t = lt->next;
        int maxv = lt->val;
        while(t) {
            if(t->val < maxv) {
                lt->next = t->next;
                t = t->next;
            } else {
                maxv = t->val;
                lt = t;
                t = t->next;
            }
        }
        return reverseList(head);
    }
};

Version 6

简化Version 5的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = nullptr;
        ListNode* nn = nullptr;
        while(head) {
            nn = head->next;
            head->next = new_head;
            new_head = head;
            head = nn;
        }
        return new_head;
    }
    ListNode* removeNodes(ListNode* head) {
        head = reverseList(head);
        ListNode* t = head;
        while(t->next) {
            if(t->next->val < t->val) {
                t->next = t->next->next;
            } else {
                t = t->next;
            }
        }
        return reverseList(head);
    }
};

1944. Number of Visible People in a Queue

题目描述

Version 1

单调栈

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

2807. Insert Greatest Common Divisors in Linked List

题目描述

Version 1

最大公约数的计算方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int gcb(int x, int y){
        if(y == 0) return x;
        return gcb(y, x % y);
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode *t = head, *tn;
        int x, y;
        while(t->next) {
            x = t->val, y = t->next->val;
            tn = t->next;
            t->next = new ListNode(gcb(x, y), tn);
            t = tn;
        }
        return head;
    }
};

83. Remove Duplicates from Sorted List

Version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        vector<bool> m = vector<bool>(201, false);
        ListNode *t = head;
        m[t->val+100] = true;
        while(t->next){
            if(m[t->next->val + 100] == true){
                t->next = t->next->next;
            }else{
                m[t->next->val + 100] = true;
                t = t->next;
            }
        }
        return head;
    }
};

1. Two Sum

Version 1

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j, n = nums.size();
        vector<int> ans = vector<int>(2, 0);
        for(i=0;i<n;++i){
            for(j=i+1;j<n;++j){
                if(nums[i]+nums[j]==target){
                    ans[0] = i, ans[1] = j;
                    return ans;
                }
            }
        }
        return ans;
    }
};

Version 2

排序之后，双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j, k, n = nums.size();
        vector<int> on = nums;
        sort(on.begin(), on.end());
        vector<int> ans = vector<int>(2, -1);
        i=0, j=n-1;
        while(i<j){
            if(on[i]+on[j]==target){
                for(k=0;k<n;++k){
                    if(nums[k]==on[i]&&ans[0]<0){
                        ans[0]=k;
                    } else if(nums[k]==on[j]){
                        ans[1]=k;
                    }
                }
                break;
            } else if(on[i]+on[j]>target) {
                --j;
            } else {
                ++i;
            }
        }
        return ans;
    }
};

Version 3

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        int i, n = nums.size();
        vector<int> ans = vector<int>(2, -1);
        for(i=0;i<n;++i){
            if(mp.find(target-nums[i])!=mp.end()){
                ans[0]=mp.find(target-nums[i])->second;
                ans[1]=i;
                break;
            } else {
                mp.insert(pair(nums[i], i));
            }
        }
        return ans;
    }
};

升级一下使用unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        int i, n = nums.size();
        for(i=0;i<n;++i){
            auto it = mp.find(target-nums[i]);
            if(it!=mp.end()){
                return {it->second, i};
            } else {
                mp.emplace(nums[i], i);
            }
        }
        return {0, 0};
    }
};

49. Group Anagrams

Version 1

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size(), i, j;
        map<vector<short>, vector<string>> mp;
        for(i=0;i<n;++i){
            vector<short> r = vector<short>(26, 0);
            for(j=0;j<strs[i].size();++j){
                // cout<<strs[i][j]-'a'<<endl;
                ++r[strs[i][j]-'a'];
            }
            auto t = mp.find(r);
            if(t!=mp.end()){
                t->second.push_back(strs[i]);
            } else{
                mp[r] = {strs[i]};
            }
        }
        vector<vector<string>> ans;
        for(auto t=mp.begin();t!=mp.end();){
            ans.push_back(t->second);
            ++t;
        }
        return ans;
    }
};

Version 2

在暴力的基础上，优化存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size(), i, j;
        map<vector<short>, int> mp;
        vector<vector<string>> ans;
        for(i=0;i<n;++i){
            vector<short> r = vector<short>(26, 0);
            for(j=0;j<strs[i].size();++j){
                // cout<<strs[i][j]-'a'<<endl;
                ++r[strs[i][j]-'a'];
            }
            auto t = mp.find(r);
            if(t!=mp.end()){
                ans[t->second].push_back(strs[i]);
            } else{
                mp[r] = ans.size();
                ans.push_back({strs[i]});
            }
        }
        return ans;
    }
};

Version 3

继续简化存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size(), i, j;
        vector<short> rd = vector<short>(26, 0);
        unsigned long long r;
        unordered_map<long, int> mp;
        vector<vector<string>> ans;
        for(i=0;i<n;++i){
            r = 0;
            rd.assign(26, 0);
            for(j=0;j<strs[i].size();++j){
                rd[strs[i][j]-'a']++;
            }
            for(j=0;j<26;++j){
                r += rd[j];
                r *= 101;
            }
            auto t = mp.find(r);
            if(t!=mp.end()){
                ans[t->second].push_back(strs[i]);
            } else{
                mp[r] = ans.size();
                ans.push_back({strs[i]});
            }
        }
        return ans;
    }
};

128. Longest Consecutive Sequence

Version1

  1. 关键点：找到每个序列的起始元素
  2. unordered_set的应用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st(nums.begin(), nums.end());
        int ans=0, j, k;
        for(int&x:nums){
            if(st.find(x-1)==st.end()){ // x是序列的起始位置
                for(j=x+1,k=1;st.find(j)!=st.end();++k,++j);
                ans=max(ans, k);
            }
        }
        return ans;
    }
};

283. Move Zeroes

Version 1

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i, j, n=nums.size();
        for(i=0,j=0;j<n;++j)
            if(nums[j]!=0)
                nums[i++]=nums[j];
        while(i<n) nums[i++]=0;
    }
};

11. Container With Most Water

Version 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0, j=height.size()-1, ans=0;
        while(i<j){
            ans = max(ans, min(height[i], height[j]) * (j-i));
            if(height[i]<height[j]) ++i;
            else --j;
        }
        return ans;
    }
};

56. Merge Intervals

Version 1

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    void p(vector<vector<int>>& vec, int n){
        cout << " ## "<<endl;
        for(int i=0;i<n;++i){
            cout<<i<<": "<<vec[i][0]<<" "<<vec[i][1]<<endl;
        }
        cout << " ## "<<endl;
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int i, j, op;
        int k = intervals.size();
        while(true){
            op=0;
            for(i=0;i<k;++i){
                for(j=0;j<k;){
                    // cout << i << " " << j << " " << k << endl;
                    if(i!=j && i<k && j<k && (
                            (intervals[i][0]>=intervals[j][0]&&intervals[i][0]<=intervals[j][1])
                            || (intervals[i][1]>=intervals[j][0]&&intervals[i][1]<=intervals[j][1])
                            || (intervals[j][0]>=intervals[i][0]&&intervals[j][0]<=intervals[i][1])
                            || (intervals[j][1]>=intervals[i][0]&&intervals[j][1]<=intervals[i][1])
                        )
                    ){
                        // cout << "merge " << i << " " << j << endl;
                        intervals[i][0]=min(intervals[i][0], intervals[j][0]);
                        intervals[i][1]=max(intervals[i][1], intervals[j][1]);
                        swap(intervals[j], intervals[k-1]);
                        --k, ++op;
                        // p(intervals, k);
                    }else{
                        ++j;
                    }
                }
            }
            if(op==0) break;
        }
        return vector<vector<int>>(intervals.begin(), intervals.begin() + k);
    }
};

Version 2

排序之后，逐个排序处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int i, j, n=intervals.size();
        vector<vector<int>> ans;
        for(i=0;i<n;++i){
            if(ans.empty()||ans.back()[1]<intervals[i][0]){
                ans.push_back(intervals[i]);
            }else if(!ans.empty()&&ans.back()[1]>=intervals[i][0]){
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            }
        }
        return ans;
    }
};

Version 3

在version2的基础上，优化空间存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int i, j, n=intervals.size();
        for(j=-1,i=0;i<n;++i){
            if(j==-1||intervals[j][1]<intervals[i][0]){
                intervals[++j] = intervals[i];
            }else if(j!=-1&&intervals[j][1]>=intervals[i][0]){
                intervals[j][1] = max(intervals[j][1], intervals[i][1]);
            }
        }
        for(;j<n-1;++j) intervals.pop_back();
        return intervals;
    }
};


// 一些语言技巧上的优化
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 自定义用于排序的比较函数
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b){
                if(a[0]!=b[0]) return a[0] < b[0];
                else {
                    return a[1] < b[1];
                }
            });
        int i, j, n=intervals.size();
        for(j=-1,i=0;i<n;++i){
            if(j==-1||intervals[j][1]<intervals[i][0]){
                intervals[++j] = intervals[i];
            }else if(j!=-1&&intervals[j][1]>=intervals[i][0]){
                intervals[j][1] = max(intervals[j][1], intervals[i][1]);
            }
        }
        intervals.resize(j+1);  // 快速扩容或者缩容数组大小
        return intervals;
    }
};

73. Set Matrix Zeroes

Version 1

用边界进行记忆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int i, j, m = matrix.size(), n = matrix[0].size();
        bool x = false, y = false;
        for(i=0;i<m;++i)if(matrix[i][0]==0) x = true;
        for(j=0;j<n;++j)if(matrix[0][j]==0) y = true;
        for(i=1;i<m;++i)
            for(j=1;j<n;++j)
                if(matrix[i][j]==0)
                    matrix[i][0]=0, matrix[0][j]=0;
        for(j=1;j<n;++j)
            if(matrix[0][j]==0)
                for(i=1;i<m;++i)
                    matrix[i][j]=0;
        for(i=1;i<m;++i)
            if(matrix[i][0]==0)
                for(j=1;j<n;++j)
                    matrix[i][j]=0;
        if(x) for(i=0;i<m;++i) matrix[i][0]=0;
        if(y) for(j=0;j<n;++j) matrix[0][j]=0;
    }
};

763. Partition Labels

Version 1

记录每个跨度的起始位置，排序之后，如果后一个跨度和前一个不相交的话，生成一段可以截断的段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<pair<short, short>> m(26, {1000, -1});
        int i, j, n=s.size(), x, y;
        for(i=0;i<n;++i){
            if(m[s[i]-'a'].first==1000) m[s[i]-'a'].first=i;
            m[s[i]-'a'].second=i;
        }
        for(i=0,j=-1;i<26;++i){
            if(m[i].first<1000) m[++j]=m[i];
        }
        m.resize(j+1);
        sort(m.begin(), m.end());
        vector<int> ans;
        for(i=0,x=-1,y=-1;i<=j;++i){
            // cout<<i<<" "<<x<<" "<<y<<" "<<m[i].first<<" "<<m[i].second<<endl;
            if(y==-1||m[i].first<y){
                if(m[i].second>y) y=m[i].second;
            }else{
                ans.push_back(y-x);
                x=y, y=m[i].second;
            }
        }
        ans.push_back(y-x);
        return ans;
    }
};

Version 2

不断更新最晚可以截断的位置，如果当前坐标和可以截断的坐标一致，就表示可以截断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<short> m(26, -1);
        vector<int> ans;
        int i, n=s.size(), x=-1, y=-1;
        for(i=0;i<n;++i) m[s[i]-'a'] = i;
        for(i=0;i<n;++i){
            if(m[s[i]-'a']>x)x=m[s[i]-'a'];
            // cout<<i<<" "<<x<<endl;
            if(x==i){
                ans.push_back(x-y);
                y=x, x=-1;
            }
        }
        return ans;
    }
};

1143. Longest Common Subsequence

Version 1

动态规划

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

Version 2

优化存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
        int i,j,m=a.size(),n=b.size(), cur;
        int dp[2][m];
        memset(dp, 0, 2*m*sizeof(int));
        for(j=0;j<n;++j){
            cur=j%2;
            for(i=0;i<m;++i){
                if(a[i]==b[j]){
                    dp[cur][i]=(i>0?dp[1-cur][i-1]:0)+1;
                }else{
                    dp[cur][i]=max(dp[1-cur][i], i>0?dp[cur][i-1]:0);
                }
            }
        }
        return dp[cur][m-1];
    }
};

2859. Sum of Values at Indices With K Set Bits

Version 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int sum=0, i, n=nums.size(), x, y;
        for(i=0;i<n;++i){
            x=0,y=i;
            while(y) x += (y&1), y>>=1;
            if(x==k) sum+=nums[i];
        }
        return sum;
    }
};

994. Rotting Oranges

Version 1

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int orangesRotting(vector<vector<int>>& x) {
        int times=0, cn=1, i, j, k, fn=0, m=x.size(), n=x[0].size(), xi, xj;
        int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
        vector<vector<int>> y=x;
        for(i=0;i<m;++i)for(j=0;j<n;++j)if(x[i][j]==1)++fn;
        if(fn==0) return 0;
        while(cn){
            cn=0;
            // y is a new state
            for(i=0;i<m;++i){
                for(j=0;j<n;++j){
                    if(x[i][j]==2){// to rotten
                        for(k=0;k<4;++k){
                            xi=i+dir[k][0], xj=j+dir[k][1];
                            if(xi<0||xi>=m||xj<0||xj>=n) continue; 
                            if(x[xi][xj]!=1) continue;
                            ++cn;
                            y[xi][xj]=2;
                            // cout<<i<<" "<<j<<", "<<xi<<" "<<xj<<endl;
                        }
                    }
                }
            }
            x=y, ++times;
            // for(i=0;i<m;++i){for(j=0;j<n;++j)cout<<"  "<<x[i][j]<<" "; cout<<endl;}
        }
        for(fn=0,i=0;i<m;++i)for(j=0;j<n;++j)if(x[i][j]==1)++fn;
        if(fn==0) return times-1;
        else return -1;
    }
};

108. Convert Sorted Array to Binary Search Tree

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