LeetCode 316 Remove Duplicate Letters

Tag: 数组类题目 LeetCode Posted on 2022-02-13 17:26:51 Edited on 2022-02-13 19:09:04 Views: 144

概述

https://leetcode.com/problems/remove-duplicate-letters/

直接法

首先遍历一遍用哈希表存一下各个字母的出现次数。

然后从头开始遍历开始删除字母,对于每个字母:

  1. 如果其就存在了一次,不能删,下一个;
  2. 如果存在了多次,
    1. 且之前已经保留了一次,则删,
    2. 尚未被保留,则查看其后面的字母是否字典序大于等于它:
      1. 如果其后面的字母字典序更小,则删;(要是后面的字母被删了怎么办?所以我们当遇到过一次且保留后就该删掉所有其他值,起码标记一下)
      2. 否则保留。

对应代码:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> m;
        for (auto c : s) m[c] ++;
        unordered_map<char, bool> alreadyKept;
        string ans;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (m[c] == 1) {
                cout << c << endl;
                ans += c;
                continue;
            }
            if (alreadyKept[c]) continue;
            
            bool hasSmallerAfterThis = false;
            int j = i + 1;
            while (j < s.size()) {
                if (!alreadyKept[s[j]] && s[j] < s[i]) {
                    hasSmallerAfterThis = true;
                    break;
                }
                j ++;
            }
            if (!hasSmallerAfterThis) {
                ans += c;
                alreadyKept[c] = true;
            }
        }
        return ans;
    }
};

上面的思路是有问题的,例如输入为 "cbacdcbc" 时,输出为 "adbc",实际应为 "acdb"

所以当遇到必须保留的值时,while 循环需要结束。

另外就是,当字符只剩下一个时,也必须保留。

改进到这里,已经是 278 / 289 test cases passed 了,但是一下情况难以应对:

  • Input: "bccab"
  • Output: "cab"
  • Expected: "bca"

虽然也可以继续改,但我感觉现在的解法已经是过于杂乱了,充满了判断。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> m;
        for (auto c : s) m[c] ++;
        unordered_map<char, bool> alreadyKept;
        string ans;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            cout << "i " << i << " c " << c << endl;
            if (alreadyKept[c]) continue;
            if (m[c] == 1) {
                ans += c;
                continue;
            }
            
            bool hasSmallerAfterThis = false;
            int j = i + 1;
            
            while (j < s.size()) {
                if (m[s[j]] == 1 && !alreadyKept[s[j]]) {
                    if (s[j] < s[i]) {
                        cout << s[j] << " vs " << s[i] << endl;
                        hasSmallerAfterThis = true;
                    }
                    break;
                }
                if (!alreadyKept[s[j]] && s[j] < s[i]) {
                    hasSmallerAfterThis = true;
                    break;
                }
                j ++;
            }
            cout << "hasSmallerAfterThis " << hasSmallerAfterThis << endl;
            if (!hasSmallerAfterThis) {
                ans += c;
                alreadyKept[c] = true;
            }
            m[c] --;
        }
        return ans;
    }
};

基于栈的解法

https://mp.weixin.qq.com/s/Yq49ZBEW3DJx6nXk1fMusw

大致思路:

  1. 首先遍历一遍维护一个记录字符个数的哈希表,
  2. 构造一个堆栈开始遍历字符,遍历过的字符更新哈希表,使其表示剩余未遍历部分的字符存在情况。

大体思想就是,如果合适就先压入栈,之后压入新元素时就弹出能弹掉的。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<char> ans;
        unordered_map<char, bool> inStack;
        unordered_map<char, int> count;
        for (auto c : s) count[c] ++;
        for (auto c : s) {
            count[c] --;  // 此行不能放到循环体的最后,因为有时候循环体未必能执行到最后
            if (inStack[c]) continue;
            while (!ans.empty() && ans.back() >= c) {
                if (count[ans.back()] == 0) break;
                inStack[ans.back()] = false;
                ans.pop_back();
            }
            ans.push_back(c);
            inStack[c] = true;
        }
        string res(ans.begin(), ans.end());
        return res;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/