三颗猫饼干算法 leetcode

Monday, October 2, 2023

Leetcode 316. Remove Duplicate Letters

这道题表面问的是如何删除重复，实际在问如何从多个字符选取一个保留，从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a'，就要选靠前位置的保留，而低顺位字符如’z'则应该尽量选取靠后位置保留。

算法大概思路：每看到一个字符，我们要决定是否保留

1. 如果改字符已经被保留过，那么就跳过无需处理

2. 如果没有被保留，而且该字符是高顺位字符，那么我们要看能不能删掉前面已经保留的字符从而让该字符更靠前

2a. 如果前面的字符顺位更高，那就停止删除

2b. 前面字符顺位更低，但能否删除前面字符取决于之后是不是还会看到该字符；因此我们事先要建一个表，存储每个字符最晚出现的位置，如果当前位置小于最晚出现位置，那么我们可以删除之

3. 重复2a-2b直到停止，加入新字符

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<char> stack;
        unordered_map<char,int> lastSeen;
        unordered_set<char> seen;
        for(int i=0; i<s.size(); i++){
            lastSeen[s[i]]=i;
        }

        for(int i=0; i<s.size(); i++){
            if(seen.count(s[i])==0) {
                while(stack.size()>0 && canRemove(lastSeen, stack.back(), s[i], i)){
                    seen.erase(stack.back());
                    stack.pop_back();
                }
                stack.push_back(s[i]);
                seen.insert(s[i]);
            }  
        }
        string res="";
        for(char c: stack){
            res+=c;
        }

        return res;
    }

    bool canRemove(unordered_map<char,int> lastSeen, char c, char cur, int i){
        if(c < cur){
            return false;
        }
        if(lastSeen[c]<=i){
            return false;
        }

        return true;
    }
};

Leetcode 670. Maximum Swap

第一感就是从最左边数位开始查找，如果该数位的右边有更大的数，那么我们应该交换；进而想到应该维护一个数组，表示该数位右边的最大数字，这个数组可以通过由右向坐遍历一遍得到；再进一步想到，如果有多个相同的最大值，那么应该记录最靠右的那个index，这样交换之后的数更大。最后如果该数位本身已经是最大值了就不用交换。

时间复杂度： O(N)

空间复杂度: O(N) ，因为额外数组

class Solution {
public:
    int maximumSwap(int num) {
        string numStr = to_string(num);
        vector<int> rightLargest(numStr.size());
        int curMaxIndex = numStr.size()-1;
        for(int i=numStr.size()-1; i>=0; i--){
            if(numStr[i]-'0'>numStr[curMaxIndex]-'0'){
                rightLargest[i] = i;
                curMaxIndex = i;
            }else{
                rightLargest[i] = curMaxIndex;
            }
        }

        string res = numStr;
        for(int i=0; i<numStr.size(); i++){
            //this is critical, only swap if number in right max index is larger than current number
            if(numStr[rightLargest[i]]-'0' > numStr[i]-'0'){
                res[i] = numStr[rightLargest[i]];
                res[rightLargest[i]] = numStr[i];
                return stoi(res);
            }
        }


        return num;
    }
};

Leetcode 662. Maximum Width of Binary Tree

这道题和314 Binary Tree Vertical Order Traversal类似，区别就是纵坐标的计算不同，这道题不存在有多个节点重合到一个纵坐标的情况。如果某个节点的位置是X，那么它的左子节点应该是2X,右子节点位置是2X+1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(root==nullptr) return 0;
        queue<pair<TreeNode*,long long int>> q;
        q.push(make_pair(root,0));
        long long int minCol=0;
        long long int maxCol=0;
        int maxWidth=1;

        while(q.size()>0){
            int size = q.size();
            for(int i=0; i<size; i++){
                pair<TreeNode*,int> cur = q.front();
                q.pop();
                TreeNode* node = cur.first;
                long long int col = cur.second;
                if(i==0){
                    minCol = col;
                }
                if(i==size-1){
                    maxCol = col;
                    maxWidth = max(maxWidth, maxCol-minCol+1);
                }

                if(node->left != nullptr){
                    q.push({node->left, col*2});
                }
                if(node->right != nullptr){
                    q.push({node->right, col*2+1});
                }
            }
        }

        return maxWidth;
    }
};

Leetcode 886. Possible Bipartition

这一类的题目可以用union find也可以用普通的dfs，bfs来做。这里就用比较简单的着色法加bfs。思路就是给出发节点着蓝色，然后给该节点的子节点都着红色，子节点的子节点着蓝色，以此往复。如果在这个过程中发现矛盾，例如本该给一个节点着红色却发现它已经被着蓝色，说明必然有两个相邻节点要着同一种颜色。需要注意的是题目给的图不一定是联通的，因此可能需要遍历多次，以免遗漏。

时间复杂度：O(V+E)，其中V是节点数，E 是连接数

空间复杂度: O(V+E)，队列的大小是O(V), 邻接表的大小是O(E)

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        if(n<=1) return true;
        vector<vector<int>> adjs(n+1);
        vector<int> color(n+1);

        for(auto dislike: dislikes){
            adjs[dislike[0]].push_back(dislike[1]);
            adjs[dislike[1]].push_back(dislike[0]);
        }

        for(auto dislike: dislikes){
            if(color[dislike[0]]==0){
                if(!bfs(dislike[0], adjs, color)){
                    return false;
                }
            }
        }

        return true;
    }

    bool bfs(int start, vector<vector<int>> adjs, vector<int>& color) {
        queue<int> q;
        q.push(start);
        color[start]=1;

        while(q.size()>0){
            for(int i=q.size()-1; i>=0; i--){
                int cur = q.front();
                q.pop();
                for(int next: adjs[cur]){
                    if(color[cur]==color[next]){
                        return false;
                    }else if(color[next]==0){
                        color[next]=-color[cur];
                        q.push(next);
                    }
                }
            }
        }

        return true;
    }
};

Leetcode 386. Lexicographical Numbers

这道题没什么特别巧妙的算法，就是纯考代码能力。对于当前数字的下一个数，我们首先考虑能否在后面加0，也就是下x10，如果可以就一直加；如果加不了，那么就在当前位置+1；如果还加不了，比如当前位置是9，或者当前数字已经等于最大值，就要退回前一位尝试+1, 如此不断尝试直到可以加到下一个数。这道题的难点在于分析出所有下一个数的可能性以及退出循环的条件。

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        std::vector<int> result;
        int curr = 1;

        for (int i = 1; i <= n; ++i) {
            result.push_back(curr);
        
            if (curr * 10 <= n) {
                curr *= 10;
            } else if (curr % 10 != 9 && curr + 1 <= n) {
                curr++;
            } else {
                while ((curr / 10) % 10 == 9) {
                    curr /= 10;
                }
                curr = curr / 10 + 1;
            }
        }

        return result;
    }
};

Leetcode 1249. Minimum Remove to Make Valid Parentheses

Valid Parentheses这个系列如果熟悉的话就知道非法的右括号‘）’是很容易分辨的，可以用栈也可以用简单计数找出。困难的地方在于左括号‘（’是没法在当时判定是否合法的。那么我们就需要记录下所有的左括号位置，当match的时候划掉合法的左括号，最后剩下的就是非法的。

这个题还有个不容易想到的方法，既然右括号很容易辨别合法性，我们可以反转字符串然后用同样的方法判定左括号。这样可以做到O(1)空间复杂度。这里贴上这种算法的代码。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string s1 = buildString(s, '(',')');
        reverse(s1.begin(), s1.end());
        string s2 = buildString(s1, ')','(');
        reverse(s2.begin(), s2.end());
        return s2;
    }

    string buildString(string s, char open, char close){
        int count=0;
        string res="";
        for(int i=0; i<s.size(); i++){
            if(s[i]==open){
                count++;
            }else if(s[i]==close){
                if(count==0){
                    continue;
                }
                count--;
            }
            res+=s[i];
        }

        return res;
    } 
};