<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 第一期講義-雙指針 # 【91算法-基礎篇】05.雙指針 力扣加加,一個努力做西湖區最好的算法題解的團隊。就在今天它給大家帶來了《91 天學算法》,幫助大家擺脫困境,征服算法。 ![](https://img.kancloud.cn/69/70/6970cc286e4e129916d46ce2e0c43d15_1087x1080.jpg) ## 什么是雙指針 顧名思議,雙指針就是**兩個指針**,但是不同于 C,C++中的指針, 其是一種**算法思想**。 如果說,我們迭代一個數組,并輸出數組每一項,我們需要一個指針來記錄當前遍歷的項,這個過程我們叫單指針(index)的話。 ``` <pre class="calibre18">``` <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>;i < nums.size(); i++) { 輸出(nums[i]); } ``` ``` ![](https://img.kancloud.cn/17/8c/178cf0629fa1dfa1c6e12aee899a5a75_370x633.jpg) (圖 1) 那么雙指針實際上就是有兩個這樣的指針,最為經典的就是二分法中的左右雙指針啦。 ``` <pre class="calibre18">``` <span class="hljs-keyword">int</span> l = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> r = nums.size() - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (l < r) { <span class="hljs-keyword">if</span>(一定條件) <span class="hljs-keyword">return</span> 合適的值,一般是 l 和 r 的中點 <span class="hljs-keyword">if</span>(一定條件) l++ <span class="hljs-keyword">if</span>(一定條件) r-- } <span class="hljs-title">// 因為 l == r,因此返回 l 和 r 都是一樣的</span> <span class="hljs-keyword">return</span> l ``` ``` ![](https://img.kancloud.cn/c5/95/c595c4acf44f3dfdb09d07e554735454_257x174.jpg) (圖 2) 讀到這里,你發現雙指針是一個很寬泛的概念,就好像數組,鏈表一樣,其類型會有很多很多, 比如二分法經常用到`左右端點雙指針`。滑動窗口會用到`快慢指針和固定間距指針`。 因此雙指針其實是一種綜合性很強的類型,類似于數組,棧等。 但是我們這里所講述的雙指針,往往指的是某幾種類型的雙指針,而不是“只要有兩個指針就是雙指針了”。 > 有了這樣一個**算法框架**,或者算法思維,有很大的好處。它能幫助你理清思路,當你碰到新的問題,在腦海里進行搜索的時候,**雙指針**這個詞就會在你腦海里閃過,閃過的同時你可以根據**雙指針**的所有套路和這道題進行**窮舉匹配**,這個思考解題過程本來就像是算法,我會在進階篇《搜索算法》中詳細闡述。 那么究竟我們算法中提到的雙指針指的是什么呢?我們一起來看下算法中雙指針的常見題型吧。 ## 常見題型有哪些? 這里我將其分為三種類類型,分別是: 1. 快慢指針(兩個指針步長不同) 2. 左右端點指針(兩個指針分別指向頭尾,并往中間移動,步長不確定) 3. 固定間距指針(兩個指針間距相同,步長相同) > 上面是我自己的分類,沒有參考別人。可以發現我的分類標準已經覆蓋了幾乎所有常見的情況。 大家在平時做題的時候一定要養成這樣的習慣,將題目類型進行總結,當然這個總結可以是別人總結好的,也可以是自己獨立總結的。不管是哪一種,都要進行一定的消化吸收,把它們變成真正屬于自己的知識。 不管是哪一種雙指針,只考慮雙指針部分的話 ,由于最多還是會遍歷整個數組一次,因此時間復雜度取決于步長,如果步長是 1,2 這種常數的話,那么時間復雜度就是 O(N),如果步長是和數據規模有關(比如二分法),其時間復雜度就是 O(logN)。并且由于不管規模多大,我們都只需要最多兩個指針,因此空間復雜度是 O(1)。下面我們就來看看雙指針的常見套路有哪些。 ## 常見套路 ### 快慢指針 1. 判斷鏈表是否有環 這里給大家推薦兩個非常經典的題目,一個是力扣 287 題,一個是 142 題。其中 142 題我在我的 LeetCode 題解倉庫中的每日一題板塊出過,并且給了很詳細的證明和解答。而 287 題相對不直觀,比較難以想到,這道題曾被官方選定為每日一題,也是相當經典的。 - [287. 尋找重復數](https://leetcode-cn.com/problems/find-the-duplicate-number/) - [【每日一題】- 2020-01-14 - 142. 環形鏈表 II · Issue #274 · azl397985856/leetcode](https://github.com/azl397985856/leetcode/issues/274) - 讀寫指針。典型的是`刪除重復元素` 這里推薦我倉庫中的一道題, 我這里寫了一個題解,橫向對比了幾個相似題目,并剖析了這種題目的本質是什么,讓你看透題目本質,推薦閱讀。 - [80.刪除排序數組中的重復項 II](https://github.com/azl397985856/leetcode/blob/master/problems/80.remove-duplicates-from-sorted-array-ii.md) ## 左右端點指針 1. 二分查找。 二分查找會在專題篇展開,這里不多說,大家先知道就行了。 1. 暴力枚舉中“從大到小枚舉”(剪枝) 一個典型的題目是我之前參加官方每日一題的時候給的一個解法,大家可以看下。這種解法是可以 AC 的。同樣地,這道題我也給出了三種方法,幫助大家從多個緯度看清這個題目。強烈推薦大家做到一題多解。這對于你做題很多幫助。除了一題多解,還有一個大招是多題同解,這部分我們放在專題篇介紹。 [find-the-longest-substring-containing-vowels-in-even](https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/qian-zhui-he-zhuang-tai-ya-suo-pythonjava-by-fe-lu/) 1. 有序數組。 區別于上面的二分查找,這種算法指針移動是連續的,而不是跳躍性的,典型的是 LeetCode 的`兩數和`,以及`N數和`系列問題。 ## 固定間距指針 1. 一次遍歷(One Pass)求鏈表的中點 2. 一次遍歷(One Pass)求鏈表的倒數第 k 個元素 3. 固定窗口大小的滑動窗口 ## 模板(偽代碼) 我們來看下上面三種題目的算法框架是什么樣的。這個時候我們沒必要糾結具體的語言,這里我直接使用了偽代碼,就是防止你掉進細節。 當你掌握了這種算法的細節,就應該找幾個題目試試。一方面是檢測自己是否真的掌握了,另一方面是“細節”,”細節“是人類,尤其是軟件工程師最大的敵人,畢竟我們都是`差不多先生`。 1. 快慢指針 ``` <pre class="calibre18">``` l = <span class="hljs-params">0</span> r = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> 沒有遍歷完 <span class="hljs-keyword">if</span> 一定條件 l += <span class="hljs-params">1</span> r += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> 合適的值 ``` ``` 1. 左右端點指針 ``` <pre class="calibre18">``` l = <span class="hljs-params">0</span> r = n - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> l < r <span class="hljs-keyword">if</span> 找到了 <span class="hljs-keyword">return</span> 找到的值 <span class="hljs-keyword">if</span> 一定條件<span class="hljs-params">1</span> l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> 一定條件<span class="hljs-params">2</span> r -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> 沒找到 ``` ``` 1. 固定間距指針 ``` <pre class="calibre18">``` l = <span class="hljs-params">0</span> r = k <span class="hljs-keyword">while</span> 沒有遍歷完 自定義邏輯 l += <span class="hljs-params">1</span> r += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> 合適的值 ``` ``` ## 題目推薦 如果你`差不多`理解了上面的東西,那么可以拿下面的題練練手。Let's Go! ### 左右端點指針 - 16.3Sum Closest (Medium) - 713.Subarray Product Less Than K (Medium) - 977.Squares of a Sorted Array (Easy) - Dutch National Flag Problem > 下面是二分類型 - 33.Search in Rotated Sorted Array (Medium) - 875.Koko Eating Bananas(Medium) - 881.Boats to Save People(Medium) ### 快慢指針 - 26.Remove Duplicates from Sorted Array(Easy) - 141.Linked List Cycle (Easy) - 142.Linked List Cycle II(Medium) - 287.Find the Duplicate Number(Medium) - 202.Happy Number (Easy) ### 固定間距指針 - 1456.Maximum Number of Vowels in a Substring of Given Length(Medium) > 固定窗口大小的滑動窗口見專題篇的滑動窗口專題(暫未發布) ## 其他 有時候也不能太思維定式,比如 <https://leetcode-cn.com/problems/consecutive-characters/> 這道題根本就沒必要雙指針什么的。 再比如:<https://lucifer.ren/blog/2020/05/31/101.symmetric-tree/>
                  <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>

                              哎呀哎呀视频在线观看