久艹A V,久久爱五月在下

題目匯總：https://leetcode-cn.com/tag/stack/

1130. 葉值的最小代價生成樹中等（不打算做了）

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

1249. 移除無效的括號中等[?]

1381. 設(shè)計(jì)一個支持增量操作的棧中等（沒有做）

1410. HTML 實(shí)體解析器中等（不做了）

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

1541. 平衡括號字符串的最少插入次數(shù)中等(評論區(qū)的代碼)

1544. 整理字符串簡單[?]

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單[?]

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

給出一個字符串 s（僅含有小寫英文字母和括號）。
請你按照從括號內(nèi)到外的順序，逐層反轉(zhuǎn)每對匹配括號中的字符串，并返回最終的結(jié)果。注意，您的結(jié)果中 不應(yīng) 包含任何括號。
示例 1：
輸入：s = "(abcd)"，輸出："dcba"
示例 2：
輸入：s = "(ed(et(oc))el)"，輸出："leetcode"
示例 3：
輸入：s = "a(bcdefghijkl(mno)p)q"，輸出："apmnolkjihgfedcbq"
提示：

0 <= s.length <= 2000

s 中只有小寫英文字母和括號

我們確保所有括號都是成對出現(xiàn)的

思路：

使用棧去匹配左括號，不斷的反轉(zhuǎn)兩個括號之間的內(nèi)容，最后輸出的時候省略掉左括號和右括號。

class Solution {//執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了99.78%的用戶,2020/08/09
    public String reverseParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] ch = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(ch[i] == '('){
                stack.push(i);//遇到左括號就把左括號的索引入棧
            }else if(ch[i] == ')'){
                reverse(ch, stack.pop() + 1, i - 1);//反轉(zhuǎn)左右括號之間的內(nèi)容
            }
        }

        for(char c : ch){
            if(c != '(' && c != ')'){//忽略左括號和右括號輸出結(jié)果
                sb.append(c);
            }
        }
    return sb.toString();
    }

    public void reverse(char[] arr, int left, int right){
        while(right > left){
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        
    }
}

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

相似題目：1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)
給你一個字符串 s，「k 倍重復(fù)項(xiàng)刪除操作」將會從 s 中選擇 k 個相鄰且相等的字母，并刪除它們，使被刪去的字符串的左側(cè)和右側(cè)連在一起。
你需要對 s 重復(fù)進(jìn)行無限次這樣的刪除操作，直到無法繼續(xù)為止。
在執(zhí)行完所有刪除操作后，返回最終得到的字符串。
本題答案保證唯一。
示例 1：
輸入：s = "abcd", k = 2
輸出："abcd"
解釋：沒有要刪除的內(nèi)容。
示例 2：
輸入：s = "deeedbbcccbdaa", k = 3
輸出："aa"
解釋： 先刪除 "eee" 和 "ccc"，得到 "ddbbbdaa"，再刪除 "bbb"，得到 "dddaa"，最后刪除 "ddd"，得到 "aa"
示例 3：
輸入：s = "pbbcggttciiippooaais", k = 2
輸出："ps"
提示：

1 <= s.length <= 10^5

2 <= k <= 10^4

s 中只含有小寫英文字母。

思路：

將字符與該字符的計(jì)數(shù)都存儲在棧中，當(dāng)棧為空或者棧頂元素不等于當(dāng)前元素時，將該元素入棧，計(jì)數(shù)為1。如果當(dāng)前字符與棧頂元素相同，則棧頂元素計(jì)數(shù)加 1。如果棧頂元素計(jì)數(shù)等于 k，則彈出棧頂元素。最后根據(jù)留在棧中的元素及其計(jì)數(shù)構(gòu)建結(jié)果字符串。

//2020/08/09
class Solution {//執(zhí)行用時：14 ms, 在所有 Java 提交中擊敗了64.19%的用戶
     class Node{
        public char val;
        public int count;
        public Node(char val, int count){
            this.val = val;
            this.count = count;
        }
    }
    public String removeDuplicates(String s, int k) {
        Stack<Node> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(stack.isEmpty() || stack.peek().val != ch){
                stack.push(new Node(ch, 1));
            }else{
                if(++stack.peek().count == k){
                    stack.pop();
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            Node n = stack.pop();
            for(int j = 0; j < n.count; j++)
                sb.append(n.val);
        }
        return sb.reverse().toString();
    }
}

1249. 移除無效的括號中等[?]

給你一個由 '('、')' 和小寫字母組成的字符串 s。
你需要從字符串中刪除最少數(shù)目的 '(' 或者 ')' （可以刪除任意位置的括號)，使得剩下的「括號字符串」有效。
請返回任意一個合法字符串。
有效「括號字符串」應(yīng)當(dāng)符合以下 **任意一條 **要求：
空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號字符串」
可以被寫作 (A) 的字符串，其中 A 是一個有效的「括號字符串」
示例 1：
輸入：s = "lee(t(c)o)de)"
輸出："lee(t(c)o)de"
解釋："lee(t(co)de)" , "lee(t(c)ode)" 也是一個可行答案。
示例 2：
輸入：s = "a)b(c)d"
輸出："ab(c)d"
示例 3：
輸入：s = "))(("
輸出：""
解釋：空字符串也是有效的
示例 4：
輸入：s = "(a(b(c)d)"
輸出："a(b(c)d)"
提示：

1 <= s.length <= 10^5

s[i] 可能是 '('、')' 或英文小寫字母

思路：

移除無效的括號要先找到它，棧用來存放所有遍歷到的左括號的索引，數(shù)組用來標(biāo)記無效括號的索引。

//2020/08/09
class Solution {//執(zhí)行用時：18 ms, 在所有 Java 提交中擊敗了89.87%的用戶
    public String minRemoveToMakeValid(String s) {
        Deque<Integer> stack = new ArrayDeque<>();//存放所有遍歷到的左括號的索引
        boolean[] isInvalidIndex = new boolean[s.length()];//標(biāo)記無效括號的索引
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '('){
                stack.push(i);//左括號入棧
                isInvalidIndex[i] = true;//標(biāo)記為無效的
            }else if(ch == ')'){
                if(!stack.isEmpty()){
                    isInvalidIndex[stack.pop()] = false;//'('出棧，更新標(biāo)記為有效的
                }else{
                    isInvalidIndex[i] = true;//標(biāo)記為無效的
                }
            }else{
                isInvalidIndex[i] = false;//除了括號之外的字母標(biāo)記為有效的
            }
        }
        for (int i = 0; i < s.length(); i++) {
            if (!isInvalidIndex[i]) {//有效的索引最后才組合
                res.append(s.charAt(i));
            }
        }
        return res.toString();


    }
}

1381. 設(shè)計(jì)一個支持增量操作的棧中等

請你設(shè)計(jì)一個支持下述操作的棧。
實(shí)現(xiàn)自定義棧類 CustomStack ：

CustomStack(int maxSize)：用 maxSize 初始化對象，maxSize 是棧中最多能容納的元素?cái)?shù)量，棧在增長到 maxSize 之后則不支持 push 操作。

void push(int x)：如果棧還未增長到 maxSize ，就將 x 添加到棧頂。

int pop()：彈出棧頂元素，并返回棧頂?shù)闹?，或棧為空時返回 -1 。

void inc(int k, int val)：棧底的 k 個元素的值都增加 val 。如果棧中元素總數(shù)小于 k ，則棧中的所有元素都增加 val 。

示例：
輸入：
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
輸出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解釋：
CustomStack customStack = new CustomStack(3); // 棧是空的 []
customStack.push(1); // 棧變?yōu)?[1]
customStack.push(2); // 棧變?yōu)?[1, 2]
customStack.pop(); // 返回 2 --> 返回棧頂值 2，棧變?yōu)?[1]
customStack.push(2); // 棧變?yōu)?[1, 2]
customStack.push(3); // 棧變?yōu)?[1, 2, 3]
customStack.push(4); // 棧仍然是 [1, 2, 3]，不能添加其他元素使棧大小變?yōu)?4
customStack.increment(5, 100); // 棧變?yōu)?[101, 102, 103]
customStack.increment(2, 100); // 棧變?yōu)?[201, 202, 103]
customStack.pop(); // 返回 103 --> 返回棧頂值 103，棧變?yōu)?[201, 202]
customStack.pop(); // 返回 202 --> 返回棧頂值 202，棧變?yōu)?[201]
customStack.pop(); // 返回 201 --> 返回棧頂值 201，棧變?yōu)?[]
customStack.pop(); // 返回 -1 --> 棧為空，返回 -1
提示：

1 <= maxSize <= 1000

1 <= x <= 1000

1 <= k <= 1000

0 <= val <= 100

每種方法 increment，push 以及 pop 分別最多調(diào)用 1000 次

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

給你一個目標(biāo)數(shù)組 target 和一個整數(shù) n。每次迭代，需要從 list = {1,2,3..., n} 中依序讀取一個數(shù)字。
請使用下述操作來構(gòu)建目標(biāo)數(shù)組 target ：
Push：從 list 中讀取一個新元素，并將其推入數(shù)組中。
Pop：刪除數(shù)組中的最后一個元素。
如果目標(biāo)數(shù)組構(gòu)建完成，就停止讀取更多元素。
題目數(shù)據(jù)保證目標(biāo)數(shù)組嚴(yán)格遞增，并且只包含 1 到 n 之間的數(shù)字。
請返回構(gòu)建目標(biāo)數(shù)組所用的操作序列。
題目數(shù)據(jù)保證答案是唯一的。
示例 1：
輸入：target = [1,3], n = 3
輸出：["Push","Push","Pop","Push"]
解釋： 讀取 1 并自動推入數(shù)組 -> [1]，讀取 2 并自動推入數(shù)組，然后刪除它 -> [1]
，讀取 3 并自動推入數(shù)組 -> [1,3]
示例 2：
輸入：target = [1,2,3], n = 3
輸出：["Push","Push","Push"]
示例 3：
輸入：target = [1,2], n = 4
輸出：["Push","Push"]
解釋：只需要讀取前 2 個數(shù)字就可以停止。
提示：

1 <= target.length <= 100

1 <= target[i] <= 100

1 <= n <= 100

target 是嚴(yán)格遞增的

思路：

只有兩種情況：["Push","Pop"] 和 "Push"

class Solution {//執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶,//2020/08/09
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int j = 1;
        for(int i = 0; i < target.length; i++){
            while(j < target[i]){
                res.add("Push");
                res.add("Pop");
                j++;
            }
            if(target[i] == j){
                res.add("Push");
                j++;
            }
        }
    return res;
    }
}

1541. 平衡括號字符串的最少插入次數(shù)中等

給你一個括號字符串 s ，它只包含字符 '(' 和 ')' 。一個括號字符串被稱為平衡的當(dāng)它滿足：
任何左括號 '(' 必須對應(yīng)兩個連續(xù)的右括號 '))' 。
左括號 '(' 必須在對應(yīng)的連續(xù)兩個右括號 '))' 之前。
比方說 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
請你返回讓 s 平衡的最少插入次數(shù)。
示例 1：
輸入：s = "(()))"
輸出：1
解釋：第二個左括號有與之匹配的兩個右括號，但是第一個左括號只有一個右括號。我們需要在字符串結(jié)尾額外增加一個 ')' 使字符串變成平衡字符串 "(())))" 。
示例 2：
輸入：s = "())"
輸出：0
解釋：字符串已經(jīng)平衡了。
示例 3：
輸入：s = "))())("
輸出：3
解釋：添加 '(' 去匹配最開頭的 '))' ，然后添加 '))' 去匹配最后一個 '(' 。
示例 4：
輸入：s = "(((((("
輸出：12
解釋：添加 12 個 ')' 得到平衡字符串。
示例 5：
輸入：s = ")))))))"
輸出：5
解釋：在字符串開頭添加 4 個 '(' 并在結(jié)尾添加 1 個 ')' ，字符串變成平衡字符串 "(((())))))))" 。
提示：

1 <= s.length <= 10^5

s 只包含 '(' 和 ')' 。

思路：

class Solution {
    public int minInsertions(String s) {
        Stack<Character> stack = new Stack<>();
        int left = 0;
        int ans = 0;
        while(left < s.length()){
            while(left < s.length() && s.charAt(left) == '('){
                stack.push('(');
                left++;
            }
            int cnt = 0;
            while(left < s.length() && s.charAt(left) == ')'){
                cnt++;
                if(cnt >= 2 && !stack.isEmpty()){
                    cnt -= 2;
                    stack.pop();
                }
                left++;
            }
            if(cnt != 0){
                if(!stack.isEmpty()){
                    ans++;
                    stack.pop();
                }else{
                    if(cnt % 2 == 0) ans += cnt/2;
                    else ans += (cnt-1)/2+2;
                }
            }
        }
        ans += stack.size()*2;
        return ans;

    }
}

1544. 整理字符串簡單[?]

給你一個由大小寫英文字母組成的字符串 s 。
一個整理好的字符串中，兩個相鄰字符 s[i] 和 s[i + 1] 不會同時滿足下述條件：
0 <= i <= s.length - 2
s[i] 是小寫字符，但 s[i + 1] 是相同的大寫字符；反之亦然 。
請你將字符串整理好，每次你都可以從字符串中選出滿足上述條件的 兩個相鄰 字符并刪除，直到字符串整理好為止。
請返回整理好的 字符串 。題目保證在給出的約束條件下，測試樣例對應(yīng)的答案是唯一的。
注意：空字符串也屬于整理好的字符串，盡管其中沒有任何字符。
示例 1：
輸入：s = "leEeetcode"
輸出："leetcode"
解釋：無論你第一次選的是 i = 1 還是 i = 2，都會使 "leEeetcode" 縮減為 "leetcode" 。
示例 2：
輸入：s = "abBAcC"
輸出：""
解釋：存在多種不同情況，但所有的情況都會導(dǎo)致相同的結(jié)果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
提示：

1 <= s.length <= 100

s 只包含小寫和大寫英文字母

思路：棧

class Solution {//執(zhí)行用時：4 ms, 在所有 Java 提交中擊敗了100.00%的用戶,//2020/08/10
    public String makeGood(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            while(!stack.isEmpty() && i < s.length() && isSimilar(stack.peek(), s.charAt(i))){
                stack.pop();
                ++i;
            }
            if(i < s.length()){
                stack.push(s.charAt(i));
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
    return sb.reverse().toString();
    }

    public boolean isSimilar(Character c1, Character c2){
        return (c1 - 'a') == (c2 - 'A') || (c1 - 'A') == (c2 - 'a');
    }
}

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單

用兩個棧實(shí)現(xiàn)一個隊(duì)列。隊(duì)列的聲明如下，請實(shí)現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒有元素，deleteHead 操作返回 -1 )
示例 1：
輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：
輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000

最多會對 appendTail、deleteHead 進(jìn)行 10000 次調(diào)用

思路：

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()) return -1;
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            
        }
        return stack2.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

6.棧（六）

6.棧（六）

題目匯總：https://leetcode-cn.com/tag/stack/

1130. 葉值的最小代價生成樹中等（不打算做了）

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

1249. 移除無效的括號中等[?]

1381. 設(shè)計(jì)一個支持增量操作的棧中等（沒有做）

1410. HTML 實(shí)體解析器中等（不做了）

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

1541. 平衡括號字符串的最少插入次數(shù)中等(評論區(qū)的代碼)

1544. 整理字符串簡單[?]

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單[?]

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

思路：

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

思路：

1249. 移除無效的括號中等[?]

思路：

1381. 設(shè)計(jì)一個支持增量操作的棧中等

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

思路：

1541. 平衡括號字符串的最少插入次數(shù)中等

思路：

1544. 整理字符串簡單[?]

思路：棧

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單

思路：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

6.棧（六）

題目匯總：https://leetcode-cn.com/tag/stack/

1130. 葉值的最小代價生成樹中等（不打算做了）

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

1249. 移除無效的括號中等[?]

1381. 設(shè)計(jì)一個支持增量操作的棧中等（沒有做）

1410. HTML 實(shí)體解析器中等（不做了）

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

1541. 平衡括號字符串的最少插入次數(shù)中等(評論區(qū)的代碼)

1544. 整理字符串簡單[?]

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單[?]

1190. 反轉(zhuǎn)每對括號間的子串中等[?]

思路：

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II中等[?]

思路：

1249. 移除無效的括號中等[?]

思路：

1381. 設(shè)計(jì)一個支持增量操作的棧中等

1441. 用棧操作構(gòu)建數(shù)組簡單[?]

思路：

1541. 平衡括號字符串的最少插入次數(shù)中等

思路：

1544. 整理字符串簡單[?]

思路：棧

劍指 Offer 09. 用兩個棧實(shí)現(xiàn)隊(duì)列簡單

思路：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av