字节跳动挂经

tanj 发表于 2020/05/14 07:21:46
他的解法好像没什么问题吧, 用他的方法解cbacbc的话先是 cba -> bac -> acb ->...

好像是…不过前面cdacd也过不了

补充内容 (2020-5-13 18:24):
cda - cda - cad ❌
正确答案acd

xzx111 发表于 2020-5-14 07:50
How about cdacd

Follow the algorithm, result = acd

ozox 发表于 2020/05/14 09:43:04
Follow the algorithm, result = acd

老哥 你的解法跑出来是cda - cda - cad

第一题是刷题网316

qiaofengmarco 发表于 2020-5-14 10:18
老哥 你的解法跑出来是cda - cda - cad

sorry, the algorithm is not correct. turns out to be a hard one at lc

guzhiyan 发表于 2020-5-14 11:19
第一题是刷题网316

谢谢，我才发现这题我做过，呵呵。。。

第一题https://leetcode.com/problems/re ... 99-Stack-Dictionary
第二题也是刷题网原题，
我面的也是相同的题2轮，请问楼主下一轮有消息了吗

18321738697 发表于 2020/05/16 05:38:48
第一题https://leetcode.com/problems/remove-duplicate-letters/di...

被拒了🤦‍♀️
第二题方便告知一下题号吗？谢谢了

第一题真是不容易bug free啊：

    string removeDuplicateLetters(string s) {
        
        if (s.empty() || s.size() == 1)
            return s;
        
        vector<int>  count(26, 0); // Count each char in the string
        vector<int>  used (26, 0); // 1 if used, 0 otherwise
        
        // Preprocess: get the count of each char and num of unique chars
        int unique = 0;
        for(char c: s)
        {
            if (count[c-'a'] == 0)
            {
                unique ++;
            }
            
            count[c-'a'] ++;
        }
        
        // Result vector
        vector<char> result(unique, 0);
        int cur = 0;
        for(char c: s)
        {
            while(cur > 0 && (used[c-'a'] == 0) && (c < result[cur-1]) && (count[result[cur-1] - 'a'] >= 1))
            {
                used[result[cur-1] - 'a'] = 0; // Unuse this char
                result[--cur] = c;
            }
            
            if (used[c-'a'] == 0)
            {
                used[c-'a'] = 1;
                result[cur++] = c;
            }
            
            count[c-'a'] --;   
        }
        
        string ret_s(result.begin(), result.end());
        return ret_s;      
    }
};

遇见 楼上们的答案可以 但是这么想 删除 然后保留下来的 最小最大或者 字典序最小最大 马上要反映到 这个一个匹配的问题从而想到单调栈
贴代码
class Solution {
    public String smallestSubsequence(String text) {
        Deque<Integer> stack = new LinkedList<>();
        int[] last =  new int[26];
        boolean[] used = new boolean[26];
        for (int i = 0; i < text.length(); i++) {
            last[text.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < text.length(); i++) {
            int ch = text.charAt(i) - 'a';
            if (used[ch]) {
                continue;
            }
            used[ch] = true;
            while (!stack.isEmpty() && stack.peekLast() > ch
                   && i < last[stack.peekLast()]) {
                int released = stack.pollLast();
                used[released] = false;
            }
            stack.offerLast(ch);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append((char) (stack.pollFirst() + 'a'));
        }
        return sb.toString();
    }
}

还有一道比较好的单调栈 是LC 409 楼主可以感受一下 这里面的套路

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (n == k) {
            return "0";
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peekLast() > num.charAt(i) && k > 0) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(num.charAt(i));
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() && stack.peekFirst() == '0') {
                stack.pollFirst();
        }
        while (!stack.isEmpty() && k > 0) {
            stack.pollLast();
            k--;
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pollFirst());
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

第二题国内高频题
https://zhuanlan.zhihu.com/p/65065359

希望能帮到lz