位元組跳動leetcode演算法題

A. leetcode演算法—[面試題 05.02]二進制數轉字元串（中等）

問題難點一：了解小數轉換為二進制的定義。

思路： 循環操作，每次num*2，判斷是否大於等於1？true：則填充1，false則填充0，直至num為0時終止循環！

遇到的難題：

按照題目分析，0.1是無法轉換為二進制的。因為 0.1->0.2->0.4->0.8->0.6->0.2->0.4....會一直循環下去。

那麼不能轉換為二進制的小數有什麼規律呢？思維卡在這個誤區。

結題思路： 將循環的num變數均緩存起來，然後判斷num變數是否出現重復的情況。若出現重復則直接返回ERROR。

但是實際運行起來， 出現了double精度的問題 ，導致num並不是0.6而是無限接近0.6，故使用緩存的思路是行不通的。

題目中明確表示，若無法使用32位二進製表示，則列印error。

那麼結束循環的條件：num為0或者循環的次數為32次。

B. 位元組跳動筆試通過率

1、一道演算法題，位元組跳動非常看重演算法，演算法的難度大概在LeetCode中等難度且通過率在30%以上的，比重40分，如果你想靠背答案來過關，那麼最好是打消這個念頭，因為做出來只是前面，後面會有更深入的問題，比如：時間復雜度、空間復雜度和優化點等；

3、iOS基礎，基本上就是一些面經和源碼級別問題什麼的，比重40分，如果真的問到了你不會的，那麼回答的模板是：這個問題呢我沒有深入的去了解，我只能說一下我的觀點，然後把你掌握的相關的知識說一遍，然後推出一個可能的結果。

C. 演算法筆記之前綴樹——字典序的第K小數字

前綴樹（字典樹）的一種應用場景，和傳統的前綴樹使用不太一樣，但是使用了其中的思想。

LeetCode 440. 字典序的第K小數字

定整數 n 和 k，找到 1 到 n 中字典序第 k 小的數字。

題目描述比較簡單，據說這是位元組跳動面試喜歡出的一道題。

首先簡單解釋下，字典序就是1、10、11、12這樣按照類似字典一樣的字元順序排序數字。

既然要用前綴樹的思想，那麼我們先把前綴樹畫出來。

我們可以看到相同前綴的數字可以放到一個子樹里，子樹的每個層級依次有1、10、100...個節點。

我們可以先判斷數字k屬於哪個子樹，然後在當前子樹往下一層級移動。然後重復找子樹和往下層移動的過程，直到找到節點（也就是數字）。

D. leetcode演算法

*最近在做一些 leetcode 的演算法題，我會將自己做過的演算法題記錄下來以供大家參考，如果查找不方便請看 油猴插件實現網站左側目錄生成。

給定一個排序數組，你需要在 原地 刪除重復出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在 原地修改輸入數組 並在使用 O(1) 額外空間的條件下完成。

示例：

解答：

     

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例：

提示：

解答：

     

給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。

示例：

說明:

解答：

     

給定一個整數數組，判斷是否存在重復元素。
如果任意一值在數組中出現至少兩次，函數返回 true 。如果數組中每個元素都不相同，則返回 false 。

示例：

解答：

     

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

說明：
你的演算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？

示例：

解答：

     

給定兩個數組，編寫一個函數來計算它們的交集。

示例：

說明：

進階:

解答：

     

給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。
最高位數字存放在數組的首位， 數組中每個元素只存儲單個數字。
你可以假設除了整數 0 之外，這個整數不會以零開頭。

示例：

解答：

     

給定一個數組 nums ，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

示例:

說明:

     

給定一個整數數組 nums 和一個目標值 target ，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例：

解答：

     

判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。

數獨部分空格內已填入了數字，空白格用 '.' 表示。

示例：

說明:

解答：

     

給定一個 *n *× *n* 的二維矩陣表示一個圖像。
將圖像順時針旋轉 90 度。

說明：
你必須在 原地 旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。 請不要 使用另一個矩陣來旋轉圖像。

示例：

解答：

     

編寫一個函數，其作用是將輸入的字元串反轉過來。輸入字元串以字元數組 char[] 的形式給出。
不要給另外的數組分配額外的空間，你必須 原地修改輸入數組 、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字元都是 ASCII 碼表中的可列印字元。

示例：

解答：

     

給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉。

示例：

注意:
假設我們的環境只能存儲得下 32 位的有符號整數，則其數值范圍為 [−231, 231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就返回 0。

解答：

     

給定一個字元串，找到它的第一個不重復的字元，並返回它的索引。如果不存在，則返回 -1。

示例：

解答：

     

給定兩個字元串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
長度一樣，包含的字母都一樣，每個字元出現的頻率也一樣，只是順序不同而已，這就屬於異位詞，

示例：

說明:
你可以假設字元串只包含小寫字母。

進階:
如果輸入字元串包含 unicode 字元怎麼辦？你能否調整你的解法來應對這種情況？

解答：

     

給定一個字元串，驗證它是否是迴文串，只考慮字母和數字字元，可以忽略字母的大小寫。
說明 ：本題中，我們將空字元串定義為有效的迴文串。

示例：

解答：

     

請你來實現一個 atoi 函數，使其能將字元串轉換成整數。

首先，該函數會根據需要丟棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。接下來的轉化規則如下：

注意 ：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換，即無法進行有效轉換。

在任何情況下，若函數不能進行有效的轉換時，請返回 0 。

提示 ：

示例：

解答：

     

實現 strStr() 函數。
給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始) 。如果不存在，則返回 -1 。

示例：

說明:
當 needle 是空字元串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。
對於本題而言，當 needle 是空字元串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符

解答：

     

「外觀數列」是一個整數序列，從數字 1 開始，序列中的每一項都是對前一項的描述。前五項如下：

1 被讀作 "one 1" ("一個一") , 即 11 。
11 被讀作 "two 1s" ("兩個一") , 即 21 。
21 被讀作 "one 2", "one 1" ("一個二" , "一個一") , 即 1211 。
給定一個正整數 n（1 ≤ n ≤ 30），輸出外觀數列的第 n 項。

注意 ：整數序列中的每一項將表示為一個字元串。

示例：

解答：

     

編寫一個函數來查找字元串數組中的最長公共前綴。
如果不存在公共前綴，返回空字元串 "" 。

示例：

說明:
所有輸入只包含小寫字母 a-z 。

解答：

     

請編寫一個函數，使其可以刪除某個鏈表中給定的（非末尾）節點，你將只被給定要求被刪除的節點。
現有一個鏈表 -- head = [4,5,1,9]，它可以表示為:

示例：

說明：

解答：

     

給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。

示例：

說明：
給定的 n 保證是有效的。

進階：
你能嘗試使用一趟掃描實現嗎？

解答：

     

反轉一個單鏈表。

示例：

解答：

     

將兩個升序鏈表合並為一個新的升序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

解答：

     

請判斷一個鏈表是否為迴文鏈表。

示例：

解答：

     

給定一個鏈表，判斷鏈表中是否有環。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1 ，則在該鏈表中沒有環。

示例：

解答：

     

給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明 : 葉子節點是指沒有子節點的節點。

示例：
給定二叉樹 [3,9,20,null,null,15,7] ，

返回它的最大深度 3 。

解答：

     

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特徵：

示例：

解答：

     

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

解答：

     

給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。 （即逐層地，從左到右訪問所有節點）。

示例：
二叉樹： [3,9,20,null,null,15,7] ,

返回其層次遍歷結果：

解答：

     

將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。
本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。

示例：
給定有序數組: [-10,-3,0,5,9] ,
一個可能的答案是: [0,-3,9,-10,null,5] ，它可以表示下面這個高度平衡二叉搜索樹：

解答：

     

給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合並到 nums1 中，使 nums1 成為一個有序數組。

說明:

示例:

解答：

     

你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由於每個版本都是基於之前的版本開發的，所以錯誤的版本之後的所有版本都是錯的。
假設你有 n 個版本 [1, 2, ..., n] ，你想找出導致之後所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。

示例：

解答：

     

假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意 ：給定 n 是一個正整數。

示例：

解答：

     

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤。
注意 ：你不能在買入股票前賣出股票。

示例：

解答：

     

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例:

解答：

     

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例：

解答：

     

打亂一個沒有重復元素的數組。

示例：

解答：

     

設計一個支持 push ， pop ， top 操作，並能在常數時間內檢索到最小元素的棧。

示例：

解答：

     

寫一個程序，輸出從 1 到 n 數字的字元串表示。

示例：

解答：

     

統計所有小於非負整數 n 的質數的數量。

示例：

解答：

     

給定一個整數，寫一個函數來判斷它是否是 3 的冪次方。

示例：

解答：

     

羅馬數字包含以下七種字元: I ， V ， X ， L ， C ， D 和 M 。

例如，羅馬數字 2 寫做 II ，即為兩個並列的 1 。 12 寫做 XII ，即為 X + II 。 27 寫做 XXVII , 即為 XX + V + II 。

通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII ，而是 IV 。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX 。這個特殊的規則只適用於以下六種情況：

示例：

解答：

     

編寫一個函數，輸入是一個無符號整數，返回其二進製表達式中數字位數為 『1』 的個數（也被稱為 漢明重量 ）。

示例：

提示：

E. leetcode演算法-給定兩個字元串形式的非負整數 num1 和num2 ，計算它們的和

初次看到這個題目，沒有考慮到大數相加問題，所以直接的思路是：

具體實現如下：

但是執行leetcode的測試用例，沒有通過，掛在了 addStrings('9333852702227987', '85731737104263') 這兩個數據的計算上。如下圖所示：

看到這里，讓我想到了這應該是大數相加的問題，那我們一起再學習一下大數相加的問題吧，然後我們再解題：

因為 JavaScript 的 Number 類型是遵循 IEEE 754 規范表示的，這就意味著 JavaScript 能精確表示的數字是有限的， JavaScript 可以精確到個位的最大整數是9007199254740992，也就是2的53次方，超過這個范圍就會精度丟失，造成 JavaScript 無法判斷大小，從而會出現下面的現象

在網上找了一張圖，表示的比較形象，也不知道來源是哪裡的，很多人的博客里都有這張圖，我們也借來參考下：

解決方案思路其實比較簡單，就是將字元串轉換為數組，末尾對齊，數組的兩兩元素相加得到total，如果total大於10的話，就往下一位進1，本次計算這一位對10求余數(temp % 10) + res做拼接。最後得到的結果就是精確的。通過這個思路，可以實現下leetcode這道題，本質也是大數相加問題：

執行效率如下圖所示：

F. 位元組交叉面試會考演算法嗎

會的。
1.位元組跳動並不會特別關心候選人使用什麼編程語言，邏輯很簡單，你Java特別厲害，那轉Go語言肯定不難。當然，如果你覺得難，那大概率也通不過後面的面試。
2.在整個的面試流程中，至少會有3輪技術面，並且每一輪面試都會考演算法。不管你是工程師，還是架構師。
3.為什麼要考這么多演算法？其實核心是看候選人是不是足夠聰明。和Netflix一樣，位元組跳動招聘工程師的必要條件就是聰明。
4.怎麼考演算法呢？一般會分兩步，第一步是直接讓你說思路，第二步是讓你直接上手寫代碼。位元組跳動的演算法題一般對應的是LeetCode中級模式，要通過面試，你肯定得花時間好好准備。
5.寫演算法代碼的時候，你可以用白板，也可以用電腦，都行。常見的模式是給你20分鍾時間，讓你寫出來某道題的解法。當然，肯定是越快做出來越好，這能說明你的熟練程度。

G. LeetCode題解：跳躍游戲II

給你一個非負整數數組nums，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
假設你總是可以到達數組的最後一個位置。

輸入： nums = [2,3,1,1,4]
輸出： 2
解釋： 跳到最後一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。

這道題是典型的貪心演算法，通過局部最優解得到全局最優解。以下兩種方法都是使用貪心演算法實現，只是貪心的策略不同。

我們的目標是到達數組的最後一個位置，因此我們可以考慮最後一步跳躍前所在的位置，該位置通過跳躍能夠到達最後一個位置。
如果有多個位置通過跳躍都能夠到達最後一個位置，那麼我們應該如何進行選擇呢？直觀上來看，我們可以使用貪心的選擇距離最後一個位置最遠的那個位置，也就是對應下標最小的那個位置。因此我們可以從左到右遍歷數組，選擇第一個滿足要求的位置。
找到最後一步跳躍前所在的位置之後，以此類推，直到找到數組的開始的位置。

復雜度分析

方法一雖然直觀，但是時間復雜度比較高，有沒有辦法降低時間復雜度呢？
如果我們貪心地進行正向查找，每次找到可到達的最遠位置，就可以在線性時間內得到最少的跳躍次數。
例如，對於數組 [2,3,1,2,4,2,3]，初始位置是下標 0，從下標 0 出發，最遠可到達下標 2。下標 0 可到達的位置中，下標 1 的值是 3，從下標 1 出發可以達到更遠的位置，因此第一步到達下標 1。
從下標 1 出發，最遠可到達下標 4。下標 1 可到達的位置中，下標 4 的值是 4 ，從下標 4 出發可以達到更遠的位置，因此第二步到達下標 4。

復雜度分析

H. 耗時7天我終於把LeetCode刷通關：數組十七連，真是不簡單

大家好，我是老三，一個刷題困難戶，接下來我們開始數組類型演算法的刷題之旅！

數組

數組基本上是我們最熟悉的數據結構了，剛會寫「Hello World」不久，接著就是「楊輝三角」之類的練習。

數組結構

上圖是一個字元數組的例子。

因為內存空間連續，所以可以直接通過下標獲取對應的元素。

但是刪除就麻煩一點，相當於填坑，一個元素被移走，留下的坑，需要其它元素來填上。

刪除元素

在Java中，多維數組的存儲本質上也是一個行優先的一維數組。

我們都知道，在Java中的 「=」 用在基本數據類型上，是值傳遞，用在引用數據類型上，是引用傳遞。

這一塊展開可以寫一篇文章，我們只簡單看個例子：

大家可以看到，newArray改變了，array也跟著變了。

為什麼呢？

在Java中，數組是引用數組類型。array、newArray都是存儲在棧中的引用，它們指向堆中真正存儲的數組對象。

所以改變了newArray，實際是改變了newArray指向的數組。

數組引用傳遞

這一點是我們刷題需要注意的，復制數組需要在循環中一個個復制。

題目：704. 二分查找 (https://leetcode-cn.com/problems/binary-search/)

難度：簡單

描述：

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

題目示例

思路：

二分查找可以說我們都很熟了。

因為數組是有序的，所以定義三個指針，low、high、mid，每次與中間指針指向的元素nums[mid]比較，

二分查找

但是這個代碼還有一處問題，在哪呢？

int mid = (left + right) / 2;

這個地方可能會因為left和right數值太大導致內存溢出，所以應該寫為 int mid = left + ((right - left) >> 1);

修改之後代碼如下：

時間復雜度：O(logn)

題目：35. 搜索插入位置 (https://leetcode-cn.com/problems/search-insert-position/)

難度：簡單

描述：

給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為 O(log n) 的演算法。

題目示例

思路：

二分查找比較簡單，但寫對還要費點功夫，再做一道基本一樣的題鞏固一下。

這道題基本一樣，插入的位置可能有四種情況：

二叉樹插入位置

代碼如下：

時間復雜度：O(logn)

題目：34. 在排序數組中查找元素的第一個和最後一個位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

難度：中等

描述：

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值 target，返回 [-1, -1]。

進階：

題目示例

思路：

看到時間復雜度 O(log n) ，數組有序，我們知道，二分查找該上場了。

但是這道題有點不一樣，它需要尋找邊界。

那我們怎麼辦呢？

這就引入了尋找邊界的二分查找。

這道題的思路是什麼呢？

我們分別用二分查找來尋找左邊界和右邊界。

一般的二分查找：

注意，我們這里的返回條件是 nums[mid] == target ，但是尋找邊界的時候就不能這樣了，因為我們不能確定mid是不是我們的邊界。

以尋找左邊界為例，條件是 target <= nums[mid] 的時候，我們接著往左移動。

尋找右邊界也類似。

代碼如下：

時間復雜度：O(logn)

題目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

難度：簡單

描述：

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等於 val 的元素，並返回移除後數組的新長度。

不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

說明:

為什麼返回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。

你可以想像內部操作如下:

思路

「暴力解法」

暴力解法沒什麼好說的，和上道題類似，找到要刪除的元素，把它後面的元素全部向前移動一位。

暴力解法

這里有兩點需要注意：

代碼如下：

時間復雜度：O(n²)。

「雙指針法」

雙指針法，是數組和鏈表題中非常常用的一種方法。

這道題用雙指針法怎麼解決呢？

定義兩個指針，一個前，一個後。沒有找到目標的時候front和after一起移動，找到目標的時候，after停下來，front接著移動，把front指向的值賦給after指向的值。

這樣一來，雙指針就通過一個循環完成了雙循環完成的事情。

雙指針法

代碼如下：

時間復雜度：O(n)。

題目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

難度：簡單

描述：

給你一個有序數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。

不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。

說明:

為什麼返回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。

你可以想像內部操作如下:

題目示例

思路

趁著上一道題勁兒還沒緩過來，趕緊做一道基本一樣的鞏固一下。

直接上代碼：

時間復雜度：O(n)。

題目：283. 移動零 (https://leetcode-cn.com/problems/move-zeroes/)

難度：簡單

描述：

給定一個數組 nums ，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

「示例:」

「說明」 :

思路

繼續沿著上一道題的思路。

移動零

代碼如下：

時間復雜度：O(n)。

題目：977. 有序數組的平方 (https://leetcode-cn.com/problems/squares-of-a-sorted-array/)

難度：簡單

描述：

給你一個按 「非遞減順序」 排序的整數數組 nums ，返回 「每個數字的平方」 組成的新數組，要求也按 「非遞減順序」 排序。

題目示例

思路

「暴力排序法」

這道題一看，最直觀的做法是什麼呢？

先求數字平方的數組，然後再把新數組排序。

代碼也好寫：

時間復雜度：遍歷時間復雜度O(n)，快排時間復雜度O(nlogn)，所以時間復雜度O(n+nlogn)。

思路

「雙指針法」

我們連寫幾道雙指針了，這道題能不能用雙指針實現呢？

我們分析一下，這個數組在取平方之前，是有序的，那麼它絕對值最大的數一定是在兩端的。

所以我們可以定義兩個指針，一個指向最左端，一個指向最右端，比較兩者平方的大小，大的平方放入結果數組，並移動指針。

有序數組的平方

代碼如下：

時間復雜度：O(n)。

題目：1. 兩數之和 (https://leetcode-cn.com/problems/two-sum/)

難度：簡單

描述：給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。

你可以按任意順序返回答案。

題目示例

思路：

「暴力解法」

上來我們先來個最簡單的暴力解法，大家應該都知道冒泡排序吧，類似的兩層循環。

兩層循環

代碼寫起來也很簡單：

時間復雜度：看到這個雙循環，就知道時間復雜度O(n²)。

「哈希輔助法」

時間復雜度O(n²)多少有點過了，這道題的重點是兩個元素相加之和的判斷。

我們可以用一個Hash集合把元素存起來，這樣一來遍歷一遍就夠了，例如目標和9，當前元素2，只需要判斷集合里是否有元素7就行了。

時間復雜度：從Hash查詢和取值時間復雜度都是O(1)，所以整體時間復雜度是O(1)。

題目：15. 三數之和 (https://leetcode-cn.com/problems/3sum/)

難度：簡單

描述：

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為0且不重復的三元組。

注意：答案中不可以包含重復的三元組。

題目示例

思路：

「哈希法」

做完兩數之和以後，我們首先想到的就是哈希法。

兩層循環，取到a，b，再通過 0-(a+b) 來確定c。

但是這里還有一個問題， 答案中不可以包含重復的三元組。

所以，我們還要想辦法去掉Hash里的重復元素。

可以加入一個約束，第三個數的索引大於第二個數才存入。

時間復雜度：雙循環，O(n²)。

雖然這么也寫出來了，但是，說實話，很難寫出沒有問題的代碼。

我們寫了這么多雙指針，那麼有沒有可能用雙指針的方式呢？

「雙指針法」

首先對數組進行排序，然後遍歷數組。

然後再在當前節點後面取左右指針，判斷左右指針的值是否等於0-nums[i]，然後分別左右移動。

怎麼去重呢？

滿足條件時，看左指針的值是否和前一個位置相等，右指針的值是否和和它後一個位置的值相等。

雙指針法

代碼如下：

時間復雜度：O(n²)

題目：18. 四數之和 (https://leetcode-cn.com/problems/4sum/)

難度：簡單

描述：

給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。

注意：答案中不可以包含重復的四元組。

題目示例

思路：

我們延續三數之和的思路，在三數之和外面再套一層循環。

時間復雜度：O(n³)

題目：209. 長度最小的子數組(https://leetcode-cn.com/problems/minimum-size-subarray-sum/)

難度：中等

描述：

給定一個含有 n 個正整數的數組和一個正整數 target 。

找出該數組中滿足其和 target 的長度最小的 連續子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，並返回其長度。如果不存在符合條件的子數組，返回 0 。

題目示例

思路

這道題是一道經典的滑動窗口問題[4]。

image-20210801164436322

代碼如下：

時間復雜度：O(n)，雖然循環里套循環了，但是starrt和end各自被移動了n次，所以時間復雜度是O(n)。

題目：219. 存在重復元素 II (https://leetcode-cn.com/problems/contains-plicate-ii/)

難度：簡單

描述：

給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的 絕對值 至多為 k。

題目示例

思路：

上面我們做了一道滑動窗口的題，我們接著再做一道也可以用滑動窗口解決的問題。

這道題的滑動窗口略有區別，上一道題的窗口是活動的，這個是 固定的滑動窗口 ,維護一個長度為k的固定窗口，如果窗口內含有目標值，返回。如果窗口進入新的元素，就需要把頭部的元素移除掉，保持窗口的長度。

固定窗口

代碼如下：

時間復雜度：O(n)。

題目：1052. 愛生氣的書店老闆(https://leetcode-cn.com/problems/grumpy-bookstore-owner/)

難度：中等

描述：

今天，書店老闆有一家店打算試營業 customers.length 分鍾。每分鍾都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鍾結束後離開。

在某些時候，書店老闆會生氣。如果書店老闆在第 i 分鍾生氣，那麼 grumpy[i] = 1，否則 grumpy[i] = 0。當書店老闆生氣時，那一分鍾的顧客就會不滿意，不生氣則他們是滿意的。

書店老闆知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續 X 分鍾不生氣，但卻只能使用一次。

請你返回這一天營業下來，最多有多少客戶能夠感到滿意。

「示例：」

思路：

這道題是一道固定窗口的問題。

整體思路就是把不生氣的部分作為固定窗口，固定窗口把customers分成了三部分，最後求三部分的最大和。

固定窗口

時間復雜度：O(n)。

空間復雜度：O(1)。

題目：面試題3. 數組中重復的數字 (https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

難度：復雜

描述：

找出數組中重復的數字。

在一個長度為 n 的數組 nums 里的所有數字都在 0 n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。

「示例 1：」

思路：

「哈希法」

這種找重復的數字問題，我們腦子里第一下就想起來，用Hash存儲元素，然後進行比對。

代碼實現也很簡單：

時間復雜度：O(n)。

空間復雜度：O(n)

但今天的主角不是它，而是

「原地置換法」

我們注意到一個條件 所有數字都在 0 n-1 的范圍內 ,那就在這方面進行操作，我們可以把元素放到它的值對應的下標的位置。

例如 num[2]=1，那我們就把它放到下標1的位置。

接著遍歷，元素發現它應該待的坑已經被它的雙胞胎兄弟給佔了，它就知道，它是多餘的那個。

原地置換

代碼如下：

時間復雜度：O(n)。

空間復雜度：O(1)

題目：41. 缺失的第一個正數 (https://leetcode-cn.com/problems/first-missing-positive/)

難度：復雜

描述：

給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。

請你實現時間復雜度為 O(n) 並且只使用常數級別額外空間的解決方案。

題目示例

思路

「輔助數組」

這道題有一個非常巧妙地的辦法！[1]

可以引入一個輔助數組，從1開始，在對應的位置存入原數組對應的元素。如原數組num[0]=1，那麼這個元素就應該存入輔助數組 helper[1]。

然後遍歷輔助數組，發現的第一個坑就是缺失的第一個正數。

輔助數組

代碼如下：

時間復雜度：O(n)。

空間復雜度：O(n)。

「原地置換法」

我們上面用了原地置換法解決了一個問題，降低了空間復雜度，我們這道題是不是也可以呢？

原地置換沒法修改數組長度，我們肯定不能nums[i] 存 i 了，我們左移一下，num[i-1]存i。

原地置換

代碼實現如下：

時間復雜度：O(n)。

空間復雜度：O(1)。

題目：54. 螺旋矩陣 (https://leetcode-cn.com/problems/spiral-matrix/)

難度：中等

描述：

給你一個 m 行 n 列的矩陣 matrix ，請按照 「順時針螺旋順序」 ，返回矩陣中的所有元素。

示例 1：

示例2

思路

這道題，思路比較容易想，就是上右下左四個方向順時針遍歷數組。

順時針遍歷數組

但是這道題的細節是魔鬼。

有兩種，一種是一圈遍歷完成，上下左右的位置移動，遍歷是左閉右開[的條件。

我們採用的是第二種，每遍歷完一條邊，就移動對應的位置，遍歷就是左閉右閉的條件。

還有一點細節就是值得注意的是，遍歷過程中可能會出現出現 top > bottom || left > right ，其中一對邊界彼此交錯了。

這意味著此時所有項都遍歷完了，如果沒有及時 break ，就會重復遍歷。

代碼如下：

時間復雜度：O(mn)，其中 m 和 n 分別是輸入矩陣的行數和列數。

題目：59. 螺旋矩陣 II (https://leetcode-cn.com/problems/spiral-matrix-ii/)

難度：中等

描述：

給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。

示例

思路

和上面一道題基本一模一樣，我們往裡面套就行了。

代碼如下：

時間復雜度：O(n²)

劍指 Offer 29. 順時針列印矩陣 也是一道類似的題目。

寫了個順口溜總結一下：

I. 這道題能解釋一下嗎

可以，
假設除以4的商為a余數為j，初一3的商為b余數為k
那麼可得
n=4a+j
n=3b+k
可以換算成
3n=12a+3j
4n=12b+4k
兩式相減得
n=12b+4k-12a-3j
n=12(b-a)+(4k-3j)
即能除以12餘4k-3j，所以除以6必定也餘4k-3j，如果算出來是負數或者大於6，取正值或者再除以6即可

J. LeetCode演算法題-29. 兩數相除（Swift）

給定兩個整數，被除數 dividend 和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。

返回被除數 dividend 除以除數 divisor 得到的商。

示例 1:

示例 2:

說明:

之前 的方法都超時了，這個方法也只擊敗了70%的用戶。但是我實在想不起來，不使用乘法、除法和 mod 運算符還能怎麼優化。先這樣吧。