<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 字典序列刪除 # 一招吃遍力扣四道題,媽媽再也不用擔心我被套路啦~ 我花了幾天時間,從力扣中精選了四道相同思想的題目,來幫助大家解套,如果覺得文章對你有用,記得點贊分享,讓我看到你的認可,有動力繼續做下去。 這就是接下來要給大家講的四個題,其中 1081 和 316 題只是換了說法而已。 - [316. 去除重復字母](https://leetcode-cn.com/problems/remove-duplicate-letters/)(困難) - [321. 拼接最大數](https://leetcode-cn.com/problems/create-maximum-number/)(困難) - [402. 移掉 K 位數字](https://leetcode-cn.com/problems/remove-k-digits/)(中等) - [1081. 不同字符的最小子序列](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/)(中等) ## 402. 移掉 K 位數字(中等) 我們從一個簡單的問題入手,識別一下這種題的基本形式和套路,為之后的三道題打基礎。 ### 題目描述 ``` <pre class="calibre18">``` 給定一個以字符串表示的非負整數 num,移除這個數中的 k 位數字,使得剩下的數字最小。 注意: num 的長度小于 10002 且 ≥ k。 num 不會包含任何前導零。 示例 1 : 輸入: num = "1432219", k = 3 輸出: "1219" 解釋: 移除掉三個數字 4, 3, 和 2 形成一個新的最小的數字 1219。 示例 2 : 輸入: num = "10200", k = 1 輸出: "200" 解釋: 移掉首位的 1 剩下的數字為 200. 注意輸出不能有任何前導零。 示例 3 : 輸入: num = "10", k = 2 輸出: "0" 解釋: 從原數字移除所有的數字,剩余為空就是 0。 ``` ``` ### 前置知識 - 數學 ### 思路 這道題讓我們從一個字符串數字中刪除 k 個數字,使得剩下的數最小。也就說,我們要保持原來的數字的相對位置不變。 以題目中的 `num = 1432219, k = 3` 為例,我們需要返回一個長度為 4 的字符串,問題在于: 我們怎么才能求出這四個位置依次是什么呢? ![](https://img.kancloud.cn/c1/0d/c10dfc795da7afd8aaeb2e75fd4d9b99_1234x626.jpg) (圖 1) 暴力法的話,我們需要枚舉`C_n^(n - k)` 種序列(其中 n 為數字長度),并逐個比較最大。這個時間復雜度是指數級別的,必須進行優化。 一個思路是: - 從左到右遍歷 - 對于每一個遍歷到的元素,我們決定是**丟棄**還是**保留** 問題的關鍵是:我們怎么知道,一個元素是應該保留還是丟棄呢? 這里有一個前置知識:**對于兩個數 123a456 和 123b456,如果 a > b, 那么數字 123a456 大于 數字 123b456,否則數字 123a456 小于等于數字 123b456**。也就說,兩個**相同位數**的數字大小關系取決于第一個不同的數的大小。 因此我們的思路就是: - 從左到右遍歷 - 對于遍歷到的元素,我們選擇保留。 - 但是我們可以選擇性丟棄前面相鄰的元素。 - 丟棄與否的依據如上面的前置知識中闡述中的方法。 以題目中的 `num = 1432219, k = 3` 為例的圖解過程如下: ![](https://img.kancloud.cn/49/a1/49a11aeef217d86033acaa297064f464_1061x1186.jpg) (圖 2) 由于沒有左側相鄰元素,因此**沒辦法丟棄**。 ![](https://img.kancloud.cn/c8/64/c864541061c6c25abcf1050ff5c66229_911x1186.jpg) (圖 3) 由于 4 比左側相鄰的 1 大。如果選擇丟棄左側的 1,那么會使得剩下的數字更大(開頭的數從 1 變成了 4)。因此我們仍然選擇**不丟棄**。 ![](https://img.kancloud.cn/7b/4e/7b4e55fc93fc35d59895391140e5c680_913x1186.jpg) (圖 4) 由于 3 比左側相鄰的 4 小。 如果選擇丟棄左側的 4,那么會使得剩下的數字更小(開頭的數從 4 變成了 3)。因此我們選擇**丟棄**。 。。。 后面的思路類似,我就不繼續分析啦。 然而需要注意的是,如果給定的數字是一個單調遞增的數字,那么我們的算法會永遠**選擇不丟棄**。這個題目中要求的,我們要永遠確保**丟棄** k 個矛盾。 一個簡單的思路就是: - 每次丟棄一次,k 減去 1。當 k 減到 0 ,我們可以提前終止遍歷。 - 而當遍歷完成,如果 k 仍然大于 0。不妨假設最終還剩下 x 個需要丟棄,那么我們需要選擇刪除末尾 x 個元素。 上面的思路可行,但是稍顯復雜。 ![](https://img.kancloud.cn/c6/55/c655f36b495bfd3b6b0cbca7c72044ae_1280x648.jpg)(圖 5) 我們需要把思路逆轉過來。剛才我的關注點一直是**丟棄**,題目要求我們丟棄 k 個。反過來說,不就是讓我們保留 n?kn - kn?k 個元素么?其中 n 為數字長度。 那么我們只需要按照上面的方法遍歷完成之后,再截取前**n - k**個元素即可。 按照上面的思路,我們來選擇數據結構。由于我們需要**保留**和**丟棄相鄰**的元素,因此使用棧這種在一端進行添加和刪除的數據結構是再合適不過了,我們來看下代碼實現。 ### 代碼(Python) ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeKdigits</span><span class="hljs-params">(self, num, k)</span>:</span> stack = [] remain = len(num) - k <span class="hljs-keyword">for</span> digit <span class="hljs-keyword">in</span> num: <span class="hljs-keyword">while</span> k <span class="hljs-keyword">and</span> stack <span class="hljs-keyword">and</span> stack[<span class="hljs-params">-1</span>] > digit: stack.pop() k -= <span class="hljs-params">1</span> stack.append(digit) <span class="hljs-keyword">return</span> <span class="hljs-string">''</span>.join(stack[:remain]).lstrip(<span class="hljs-string">'0'</span>) <span class="hljs-keyword">or</span> <span class="hljs-string">'0'</span> ``` ``` ***復雜度分析*** - 時間復雜度:雖然內層還有一個 while 循環,但是由于每個數字最多僅會入棧出棧一次,因此時間復雜度仍然為 O(N)O(N)O(N),其中 NNN 為數字長度。 - 空間復雜度:我們使用了額外的棧來存儲數字,因此空間復雜度為 O(N)O(N)O(N),其中 NNN 為數字長度。 > 提示: 如果題目改成求刪除 k 個字符之后的最大數,我們只需要將 stack\[-1\] > digit 中的大于號改成小于號即可。 ## 316. 去除重復字母(困難) ### 題目描述 ``` <pre class="calibre18">``` 給你一個僅包含小寫字母的字符串,請你去除字符串中重復的字母,使得每個字母只出現一次。需保證返回結果的字典序最小(要求不能打亂其他字符的相對位置)。 示例 1: 輸入: "bcabc" 輸出: "abc" 示例 2: 輸入: "cbacdcbc" 輸出: "acdb" ``` ``` ## 前置知識 - 字典序 - 數學 ### 思路 與上面題目不同,這道題沒有一個全局的刪除次數 k。而是對于每一個在字符串 s 中出現的字母 c 都有一個 k 值。這個 k 是 c 出現次數 - 1。 沿用上面的知識的話,我們首先要做的就是計算每一個字符的 k,可以用一個字典來描述這種關系,其中 key 為 字符 c,value 為其出現的次數。 具體算法: - 建立一個字典。其中 key 為 字符 c,value 為其出現的剩余次數。 - 從左往右遍歷字符串,每次遍歷到一個字符,其剩余出現次數 - 1. - 對于每一個字符,如果其對應的剩余出現次數大于 1,我們**可以**選擇丟棄(也可以選擇不丟棄),否則不可以丟棄。 - 是否丟棄的標準和上面題目類似。如果棧中相鄰的元素字典序更大,那么我們選擇丟棄相鄰的棧中的元素。 還記得上面題目的邊界條件么?如果棧中剩下的元素大于 n?kn - kn?k,我們選擇截取前 n?kn - kn?k 個數字。然而本題中的 k 是分散在各個字符中的,因此這種思路不可行的。 不過不必擔心。由于題目是要求只出現一次。我們可以在遍歷的時候簡單地判斷其是否在棧上即可。 代碼: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicateLetters</span><span class="hljs-params">(self, s)</span> -> int:</span> stack = [] remain_counter = collections.Counter(s) <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s: <span class="hljs-keyword">if</span> c <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> stack: <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> c < stack[<span class="hljs-params">-1</span>] <span class="hljs-keyword">and</span> remain_counter[stack[<span class="hljs-params">-1</span>]] > <span class="hljs-params">0</span>: stack.pop() stack.append(c) remain_counter[c] -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-string">''</span>.join(stack) ``` ``` ***復雜度分析*** - 時間復雜度:由于判斷當前字符是否在棧上存在需要 O(N)O(N)O(N) 的時間,因此總的時間復雜度就是 O(N2)O(N ^ 2)O(N2),其中 NNN 為字符串長度。 - 空間復雜度:我們使用了額外的棧來存儲數字,因此空間復雜度為 O(N)O(N)O(N),其中 NNN 為字符串長度。 查詢給定字符是否在一個序列中存在的方法。根本上來說,有兩種可能: - 有序序列: 可以二分法,時間復雜度大致是 O(N)O(N)O(N)。 - 無序序列: 可以使用遍歷的方式,最壞的情況下時間復雜度為 O(N)O(N)O(N)。我們也可以使用空間換時間的方式,使用 NNN的空間 換取 O(1)O(1)O(1)的時間復雜度。 由于本題中的 stack 并不是有序的,因此我們的優化點考慮空間換時間。而由于每種字符僅可以出現一次,這里使用 hashset 即可。 ### 代碼(Python) ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicateLetters</span><span class="hljs-params">(self, s)</span> -> int:</span> stack = [] seen = set() remain_counter = collections.Counter(s) <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s: <span class="hljs-keyword">if</span> c <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen: <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> c < stack[<span class="hljs-params">-1</span>] <span class="hljs-keyword">and</span> remain_counter[stack[<span class="hljs-params">-1</span>]] > <span class="hljs-params">0</span>: seen.discard(stack.pop()) seen.add(c) stack.append(c) remain_counter[c] -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-string">''</span>.join(stack) ``` ``` ***復雜度分析*** - 時間復雜度:O(N)O(N)O(N),其中 NNN 為字符串長度。 - 空間復雜度:我們使用了額外的棧和 hashset,因此空間復雜度為 O(N)O(N)O(N),其中 NNN 為字符串長度。 > LeetCode 《1081. 不同字符的最小子序列》 和本題一樣,不再贅述。 ## 321. 拼接最大數(困難) ### 題目描述 ``` <pre class="calibre18">``` 給定長度分別為 m 和 n 的兩個數組,其元素由 0-9 構成,表示兩個自然數各位上的數字。現在從這兩個數組中選出 k (k <= m + n) 個數字拼接成一個新的數,要求從同一個數組中取出的數字保持其在原數組中的相對順序。 求滿足該條件的最大數。結果返回一個表示該最大數的長度為 k 的數組。 說明: 請盡可能地優化你算法的時間和空間復雜度。 示例 1: 輸入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 輸出: [9, 8, 6, 5, 3] 示例 2: 輸入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 輸出: [6, 7, 6, 0, 4] 示例 3: 輸入: nums1 = [3, 9] nums2 = [8, 9] k = 3 輸出: [9, 8, 9] ``` ``` ### 前置知識 - 分治 - 數學 ### 思路 和第一道題類似,只不不過這一次是兩個**數組**,而不是一個,并且是求最大數。 最大最小是無關緊要的,關鍵在于是兩個數組,并且要求從兩個數組選取的元素個數加起來一共是 k。 然而在一個數組中取 k 個數字,并保持其最小(或者最大),我們已經會了。但是如果問題擴展到兩個,會有什么變化呢? 實際上,問題本質并沒有發生變化。 假設我們從 nums1 中取了 k1 個,從 num2 中取了 k2 個,其中 k1 + k2 = k。而 k1 和 k2 這 兩個子問題我們是會解決的。由于這兩個子問題是相互獨立的,因此我們只需要分別求解,然后將結果合并即可。 假如 k1 和 k2 個數字,已經取出來了。那么剩下要做的就是將這個長度分別為 k1 和 k2 的數字,合并成一個長度為 k 的數組合并成一個最大的數組。 以題目的 `nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5` 為例。 假如我們從 num1 中取出 1 個數字,那么就要從 nums2 中取出 4 個數字。 運用第一題的方法,我們計算出應該取 nums1 的 \[6\],并取 nums2 的 \[9,5,8,3\]。 如何將 \[6\] 和 \[9,5,8,3\],使得數字盡可能大,并且保持相對位置不變呢? 實際上這個過程有點類似`歸并排序`中的**治**,而上面我們分別計算 num1 和 num2 的最大數的過程類似`歸并排序`中的**分**。 ![](https://img.kancloud.cn/23/4e/234e62bdde8d564c63dce9b7783f5956_1586x493.jpg)(圖 6) 代碼: > 我們將從 num1 中挑選的 k1 個數組成的數組稱之為 A,將從 num2 中挑選的 k2 個數組成的數組稱之為 B, ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">merge</span><span class="hljs-params">(A, B)</span>:</span> ans = [] <span class="hljs-keyword">while</span> A <span class="hljs-keyword">or</span> B: bigger = A <span class="hljs-keyword">if</span> A > B <span class="hljs-keyword">else</span> B ans.append(bigger[<span class="hljs-params">0</span>]) bigger.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> ans ``` ``` 這里需要說明一下。 在很多編程語言中:**如果 A 和 B 是兩個數組,當前僅當 A 的首個元素字典序大于 B 的首個元素,A > B 返回 true,否則返回 false**。 比如: ``` <pre class="calibre18">``` A = [1,2] B = [2] A < B # True A = [1,2] B = [1,2,3] A < B # False ``` ``` 以合并 \[6\] 和 \[9,5,8,3\] 為例,圖解過程如下: ![](https://img.kancloud.cn/fe/0a/fe0aea24c716cce401685d9d55f7515a_1586x974.jpg)(圖 7) 具體算法: - 從 nums1 中 取 min(i,len(nums1))min(i, len(nums1))min(i,len(nums1)) 個數形成新的數組 A(取的邏輯同第一題),其中 i 等于 0,1,2, ... k。 - 從 nums2 中 對應取 min(j,len(nums2))min(j, len(nums2))min(j,len(nums2)) 個數形成新的數組 B(取的邏輯同第一題),其中 j 等于 k - i。 - 將 A 和 B 按照上面的 merge 方法合并 - 上面我們暴力了 k 種組合情況,我們只需要將 k 種情況取出最大值即可。 ### 代碼(Python) ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxNumber</span><span class="hljs-params">(self, nums1, nums2, k)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pick_max</span><span class="hljs-params">(nums, k)</span>:</span> stack = [] drop = len(nums) - k <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums: <span class="hljs-keyword">while</span> drop <span class="hljs-keyword">and</span> stack <span class="hljs-keyword">and</span> stack[<span class="hljs-params">-1</span>] < num: stack.pop() drop -= <span class="hljs-params">1</span> stack.append(num) <span class="hljs-keyword">return</span> stack[:k] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">merge</span><span class="hljs-params">(A, B)</span>:</span> ans = [] <span class="hljs-keyword">while</span> A <span class="hljs-keyword">or</span> B: bigger = A <span class="hljs-keyword">if</span> A > B <span class="hljs-keyword">else</span> B ans.append(bigger[<span class="hljs-params">0</span>]) bigger.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> ans <span class="hljs-keyword">return</span> max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(k+<span class="hljs-params">1</span>) <span class="hljs-keyword">if</span> i <= len(nums1) <span class="hljs-keyword">and</span> k-i <= len(nums2)) ``` ``` ***復雜度分析*** - 時間復雜度:pick\_max 的時間復雜度為 O(M+N)O(M + N)O(M+N) ,其中 MMM 為 nums1 的長度,NNN 為 nums2 的長度。 merge 的時間復雜度為 O(k)O(k)O(k),再加上外層遍歷所有的 k 中可能性。因此總的時間復雜度為 O(k2?(M+N))O(k^2 \* (M + N))O(k2?(M+N))。 - 空間復雜度:我們使用了額外的 stack 和 ans 數組,因此空間復雜度為 O(max(M,N,k))O(max(M, N, k))O(max(M,N,k)),其中 MMM 為 nums1 的長度,NNN 為 nums2 的長度。 ## 總結 這四道題都是刪除或者保留若干個字符,使得剩下的數字最小(或最大)或者字典序最小(或最大)。而解決問題的前提是要有一定**數學前提**。而基于這個數學前提,我們貪心地刪除棧中相鄰的字符。如果你會了這個套路,那么這四個題目應該都可以輕松解決。 `316. 去除重復字母(困難)`,我們使用 hashmap 代替了數組的遍歷查找,屬于典型的空間換時間方式,可以認識到數據結構的靈活使用是多么的重要。背后的思路是怎么樣的?為什么想到空間換時間的方式,我在文中也進行了詳細的說明,這都是值得大家思考的問題。然而實際上,這些題目中使用的棧也都是空間換時間的思想。大家下次碰到**需要空間換取時間**的場景,是否能夠想到本文給大家介紹的**棧**和**哈希表**呢? `321. 拼接最大數(困難)`則需要我們能夠對問題進行分解,這絕對不是一件簡單的事情。但是對難以解決的問題進行分解是一種很重要的技能,希望大家能夠通過這道題加深這種**分治**思想的理解。 大家可以結合我之前寫過的幾個題解練習一下,它們分別是: - [【簡單易懂】歸并排序(Python)](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-dan-yi-dong-gui-bing-pai-xu-python-by-azl3979/) - [一文看懂《最大子序列和問題》](https://lucifer.ren/blog/2019/12/11/LSS/) 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的 LeetCode 題解 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看