⑴ 103. leetcode筆記(1~60)
d1
https://leetcode-cn.com/problems/two-sum
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
【hashmap存儲】
給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。
請你找出這兩個有序數組的中位數，並且要求演算法的時間復雜度為 O(log(m + n))。
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5
【奇偶判斷】
給定一個字元串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
【雙循環貪心】
d2
判斷一個整數是否是迴文數。迴文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。
輸入: 121
輸出: true
【折半比較】
給定一個包含大寫字母和小寫字母的字元串，找到通過這些字母構造成的最長的迴文串。
在構造過程中，請注意區分大小寫。比如 "Aa" 不能當做一個迴文字元串。
注意:
假設字元串的長度不會超過 1010。
示例：
輸入:
"abccccdd"
輸出:
7
【集合更新與判空】(add remove, 放入可迴文的字元，無重復)
給你一個字元串 s 和一個字元規律 p ，請你來實現一個支持 '.' 和 '*' 的正則表達式匹配。
'.' 匹配任意單個字元
'*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 **整個 **字元串 s 的，而不是部分字元串。
說明:
【正則包與結果項】
d3
給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。
示例:
給定數組 nums = [1,1,2],
函數應該返回新的長度 2, 並且原數組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數組中超出新長度後面的元素。
【新計數索引】
給定一個數組 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
示例:
給定 nums = [3,2,2,3], val = 3,
函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。
你不需要考慮數組中超出新長度後面的元素。
【while val存在】
實現 strStr() 函數：
給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。
示例:
輸入: haystack = "hello", needle = "ll"
輸出: 2
【str.index(p)】
d4
【分支遞歸乘數】
給定一個整數數組 nums，求出數組從索引 i 到 j (i ≤ j) 范圍內元素的總和，包含 i, j 兩點。
給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數為 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
【緩存和】
給定一個二進制數組，你可以最多將 1 個 0 翻轉為 1，找出其中最大連續 1 的個數。
輸入：[1,0,1,1,0]
輸出：4
解釋：翻轉第一個 0 可以得到最長的連續 1。
當翻轉以後，最大連續 1 的個數為 4。
【最近0的出現位置】
d5
對於一個 正整數，如果它和除了它自身以外的所有正因子之和相等，我們稱它為「完美數」
輸出: True
解釋: 28 = 1 + 2 + 4 + 7 + 14
【折平根比較】
修改一個數，則變成非遞減數列，輸出True
【嵌套條件分支】
123456789101112...求出第N個數字對應的單字元數值
【while True中的數量級t和求解條件m】
d6
列表中存在最大長度為k的兩個相等的數，則返True
給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的絕對值最大為 k。如輸入: nums = [1,2,3,1], k = 3， 輸出: true
【集合表示滑動窗口】
【雙指針追蹤】
兩個數不是同一個數，存在某數2倍數的一個數則返回True
【判雙零】
d7
兩個數值型字元串，相加後返回結果字元串
【while中低位進位】
求節點與其祖先之間的最大差，如：
【左右遞歸dfs返回最大差】
一排人領糖果, 相鄰的人rating高的獲得較多糖，每人都有糖果。
老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分。
你需要按照以下要求，幫助老師給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果。
相鄰的孩子中，評分高的孩子必須獲得更多的糖果。
那麼這樣下來，老師至少需要准備多少顆糖果呢？如輸入: [1,0,2], 輸出: 5
解釋: 你可以分別給這三個孩子分發 2、1、2 顆糖果。
【左右規則】
d8
返回鏈表中倒數第k個節點值
【雙指針追蹤】
是否平衡二叉樹，即任意一個節點其兩顆子樹的高度差不超過一。
【遞歸返回是否平衡和樹高】
【三重while中低位進位】
d9
刪除鏈表中的節點
【製造偽頭結點】
之字形層次遍歷二叉樹，如:
【遞歸含層數的層次遍歷與折返判斷】
如果一個數的左邊數組和與右邊數組和相等，則返回此中間數的索引。
【從左累加與總和比較】
d10
輸出二叉樹的鏡像， 如：
【製造臨時節點的自身遞歸】
自底向上遍歷二叉樹，如：
【遞歸層次遍歷】
【含hashmap[depth]的dfs遞歸】
d11
返回除法結果，不越界[-2**31， 2**31-1]
【正負/零劃分】
一個數的二進製表示中1的個數
【帶奇偶判斷的逐右移位】
移除所有值為val的節點，返回鏈表。如輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
【含有目標比較的自身遞歸】
d12
實現int sqrt(int x)函數
【牛頓迭代】
【兩次判空與全存在的各自相加】
求出根到葉子節點路徑總和為固定值的所有路徑集
【目標遞減下葉子和當前更新的路徑和與目標值的比較】
d13
數組中是否有獨一無二的出現次數
【hashmap計數與值數組判重】
給定一個無序的整數數組，找到其中最長上升子序列的長度。如輸入: [10,9,2,5,3,7,101,18]
輸出: 4 ，解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
【雙循環動態規劃】
【遞歸判斷】
d14
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個演算法來計算你所能獲取的最大利潤。
注意你不能在買入股票前賣出股票。如輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格。
【最低股價與最大利潤同時更新】
輸入一個整型數組，數組里有正數也有負數。數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。
要求時間復雜度為O(n)。如輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6, 解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
【max0 sum0初始索引0賦值，與sum0>0判斷】
給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等於 n。你需要讓組成和的完全平方數的個數最少。如輸入: n = 12
輸出: 3 ，解釋: 12 = 4 + 4 + 4
【動態規劃雙循環解背包問題】
d15
統計所有小於非負整數 n 的質數的數量。如輸入: 10
輸出: 4，解釋: 小於 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。
【篩去法】
找出第 n 個丑數。
丑數就是只包含質因數 2, 3, 5 的正整數。如輸入: n = 10
輸出: 12， 解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數。
【三指針動態規劃】
給定一個整數數組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數 fee 代表了交易股票的手續費用。
你可以無限次地完成交易，但是你每次交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。
返回獲得利潤的最大值。如輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8，解釋: 能夠達到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
【買入賣出的動態規劃】
d16
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
如輸入: [7,1,5,3,6,4]
輸出: 7
解釋:
在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出,
這筆交易所能獲得利潤 = 5-1 = 4 。
隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出,
這筆交易所能獲得利潤 = 6-3 = 3 。
【同leet714 多次買賣的動態規劃】
是否是相同的樹
【同空、不同空判斷後的自身遞歸】
不特定根節點和葉子節點，返迴路徑總和為固定值的路徑數
【自身遞歸與dfs遞歸】
d17
找出右邊的值小於當前值的數的個數：
使用線段樹構建左右子樹，並從右到左計算前面的數小於當前值的數的個數，最終返回依次進入結果數組的list的倒置值。
【list復製法】
將遍歷到的前兩個和數都去掉，雙重遍歷T(n)= O(n)
規范的路徑表示寫法轉換為最簡路徑
【棧進棧出，判斷'' '.' '..'()】
d18
【復制字元庫，逐次後移匹配庫起始點】
按要求分一個數組為m份，求其中子數組的最大值中最小一個
【二分查找、設定子數組最大的和mid作劃分節點】
【二分思想，拆分數組遞歸】(不用判斷平衡)
d19(52%)
兩個字元串對應位置移動總次數在指定步數內(ascii值的差)，求字元串的最大可變換長
【滑窗記錄更新最初位置、不斷更新當前滑窗內移動步數最小值】
⑵ 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』 的個數（也被稱為 漢明重量 ）。
示例：
提示：
⑶ 豬喝毒水 信息熵
事情的起因是有這么一道題：
25桶水其中一桶有毒，豬喝水後會在15分鍾內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？
看到這個題，我直接就使用了二分法，25桶直接分成12桶+12桶+1桶，然後12分6，6分3，3分1，最終計算結果是需要5頭豬，反過來理解，也就是 ，現在就25桶水，當然答案是5頭豬。然而我這個答案是錯的……
網路了一下，發現是一道leecode題目，正確答案是2。解法也很容易理解，這里借用網路到的一張圖來幫助理解，如果我下面的解釋沒看懂，也可以去看一下博主原文： [leetcode]——哪桶水有毒
如圖，把25桶水分成5行5列，派兩頭豬，一個逐行喝( 注意是一次性喝掉這一行的5桶水的混合物 )，一個逐列喝。以逐列的豬為例，15分鍾後死了說明毒水在第1列，如果活著就繼續去喝第2列，然後分別等到30、45、60分鍾觀察是否死亡來鎖定是哪一列，如果60分鍾還沒死，說明前面4列都沒毒水，那麼用排除法就知道毒水只能在第5列。逐行豬同理，最終只要鎖定了行列數，那麼交叉點必然是毒水所在位置。
可以觀察到，這種解法的關鍵是，一頭豬充分利用了15分鍾的間隔，在1個小時內直接辨明了5大桶水(實際是5桶混合水)是否有毒。如果題目改成是10分鍾的間隔呢，那1個小時就能辨明7桶水了。此時7的2次方是49，仍然需要2頭豬。
再擴展一下，仍然是15分鍾間隔，但總共是1000桶水呢？實際上，一頭豬只能辨明5，兩個維度只能是5乘以5，再來一頭，就是5的3次方；很容易發現，問題實際變成求5的多少次方能大於1000，答案易得是5頭豬。其實這時候5的5次方是3125，也就是說即使是3000桶水，5頭豬也是夠的。
再擴展一下，如果是15分鍾間隔，但要求是15分鍾搞定，而不是一個小時呢？這時候會發現，15分鍾結束後，豬只有兩個狀態，要麼死要麼活。也就是每一行或每一列實際上只能放2桶水。那麼 問題就變成2的多少次方大於25，哎，此時的答案和我剛開始使用的二分法是完全一致的。這個時候，我才意識到，我的二分法，實際上不需要1小時，僅僅15分鍾就能搞定辨明毒水的目的。因為題目中說了，每桶水是無限多的，那我可以先按二分的思路，把25桶水全部都拆好，然後一聲令下，5頭豬同時上去喝對應的分組，當然是15分鍾後就知道結果了。
然而事情到現在，才剛剛開始……比如這個知乎3萬贊的回答：
1000桶水，其中一桶有毒，豬喝毒水後會在15分鍾內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？ - 苗華棟的回答 - 知乎
作者上來就丟出信息熵的定義和公式：
然後用這公式一頓計算，把我看懵逼了。這里建議先通過別的鏈接，來補一下基礎知識。
參考 信息熵是什麼？ - 運籌之學的回答 - 知乎
信息熵，信息熵，怎麼看怎麼覺得這個「熵」字不順眼，那就先不看。我們起碼知道這個概念跟信息有關系。而它又是個數學模型裡面的概念，一般而言是可以量化的。所以，第一個問題來了： 信息是不是可以量化？
起碼直覺上而言是可以的，不然怎麼可能我們覺得有些人說的廢話特別多，「沒什麼信息量」，有些人一語中的，一句話就傳達了很大的信息量。
有些事情本來不是很確定，例如明天股票是漲還是跌。如果你告訴我明天NBA決賽開始了，這兩者似乎沒啥關系啊，所以你的信息對明天股票是漲是跌帶來的信息量很少。但是假如NBA決賽一開始，大家都不關注股票了沒人坐莊股票有99%的概率會跌，那你這句話信息量就很大，因為本來不確定的事情變得十分確定。
而有些事情本來就很確定了，例如太陽從東邊升起，你再告訴我一百遍太陽從東邊升起，你的話還是絲毫沒有信息量的，因為這事情不能更確定了。
所以說信息量的大小跟事情不確定性的變化有關。
一，跟事情的可能結果的數量有關；二，跟概率有關。
先說一。例如我們討論太陽從哪升起。本來就只有一個結果，我們早就知道，那麼無論誰傳遞任何信息都是沒有信息量的。當可能結果數量比較大時，我們得到的新信息才有潛力擁有大信息量。
二，單看可能結果數量不夠，還要看初始的概率分布。例如一開始我就知道小明在電影院的有15*15個座位的A廳看電影。小明可以坐的位置有225個，可能結果數量算多了。可是假如我們一開始就知道小明坐在第一排的最左邊的可能是99%，坐其它位置的可能性微乎其微，那麼在大多數情況下，你再告訴我小明的什麼信息也沒有多大用，因為我們幾乎確定小明坐第一排的最左邊了。那麼，怎麼衡量不確定性的變化的大小呢？怎麼定義呢？這個問題不好回答，但是假設我們已經知道這個量已經存在了，不妨就叫做信息量，那麼你覺得信息量起碼該滿足些什麼特點呢？
那有什麼函數能滿足上面四個條件呢？
負的對數函數，也就是-log（x）！底數取大於1的數保證這個函數是非負的就行。前面再隨便乘個正常數也行。
a. 為什麼不是正的？因為假如是正的，由於x是小於等於1的數，log（x）就小於等於0了。第一個特點滿足。
b. 咱們再來驗證一下其他特點。三是最容易的。假如x是一個概率，那麼log（x）是連續依賴於x的。donec。
四呢？假如有n個可能結果，那麼出現任意一個的概率是1/n，而-log(1/n)是n的增函數，沒問題。
d。最後驗證二。由於-log(xy) = -log(x) -log(y)，所以也是對的。學數學的同學注意，這里的y可以是給定x的條件概率，當然也可以獨立於x。By the way，這個函數是唯一的（除了還可以多乘上任意一個常數），有時間可以自己證明一下，或者查書。
ok，所以我們知道一個事件的信息量就是這個事件發生的概率的負對數。最後終於能回到信息熵。信息熵是跟所有可能性有關系的。每個可能事件的發生都有個概率。信息熵就是平均而言發生一個事件我們得到的信息量大小。所以數學上，信息熵其實是信息量的期望。（表達式參考其它答案或者看下面）
參考 信息熵是什麼？ - D.Han的回答 - 知乎
賭馬比賽里，有4匹馬{A,B,C,D},獲勝概率為{1/2,1/4,1/8,1/8}。接下來，讓我們將哪一匹馬獲勝視為一個隨機變數X。
假定我們需要用盡可能少的二元問題來確定隨機變數 X 的取值。例如：問題1：A獲勝了嗎？問題2：B獲勝了嗎？問題3：C獲勝了嗎？最後我們可以通過最多3個二元問題，來確定X的取值，即哪一匹馬贏了比賽。
那麼很容易計算，在這種問法下，為確定X取值
當我們使用上述的信息熵公式，是這樣的：
-1/2*log(1/2) + -1/4*log(1/4) + -1/8*log(1/8) + -1/8*log(1/8)
這里很容易計算結果，比如： -1/2*log(1/2) = -1/2 * (log1 - log2) = 1/2 * log2 = 1/2 ，最終結果就是：
1/2+1/2+3/8+3/8 = 7/4
可以發現，信息熵公式計算結果與之前計算是一致的。在二進制計算機中，一個比特為0或1，其實就代表了一個二元問題的回答。也就是說，在計算機中，我們給哪一匹馬奪冠這個事件進行編碼，所需要的平均碼長為1.75個比特。
很顯然，為了盡可能減少碼長，我們要給發生概率較大的事件，分配較短的碼長 。這個問題深入討論，可以得出霍夫曼編碼的概念。
擴展閱讀可以參考 H264系列九 熱力學熵 信息熵 哈夫曼編碼 哥倫布編碼 ，在這篇文章里，也有一個很有意思的例子：
我要拋一次骰子，在觀測到結果之前，骰子六個面向上都有可能，而且概率完全一樣（都是1/6).這時，這一事件的信息熵為 。這個結果用之前的信息熵公式也很好計算，相當於累加6次 -1/6*log(1/6) ，即 -log(1/6)=-(log1-log6)=log6 ，注意這個演算法在之後算豬喝毒水時也會用到。
現在萬能的女神給了我一個提示，這次骰子的結果一定是偶數，於是可能的結果由6種降低為3種，事件的熵也就變成了 。也就是說，當我得到提示後，對於事件結果的不確定性降低了。我們把信息熵降低的量規定為信息量I。上面那條提示對我的信息量是 ，正好是1比特，相當於對一個完全未知的命題做一次是非判斷需要的信息量。而如果我要得到唯一確定的結果，P(x)就必須等於1，此時的信息熵為零。我們需要得到的信息量就是原本的熵 。
看到這里，聰明的你一定已經可以自己總結出另一個金光閃閃的結論：信息就是負熵。需要特別注意的是，這句話里的「熵」指而且僅指信息熵，試圖將這個結論擴大到熱力學熵的解釋往往都缺乏足夠的事實基礎，並且含義也經常是含混的。
是時候回到知乎3萬贊的回答了： 1000桶水，其中一桶有毒，豬喝毒水後會在15分鍾內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？ - 苗華棟的回答 - 知乎
1000桶水，其中一桶有毒，豬喝毒水後會在15分鍾內死去，想用15分鍾內找到這桶毒水，至少需要幾頭豬？
首先，」1000桶水其中有一桶有毒「這個隨機變數X的信息熵為： -(1/1000)*log(1/1000) 累加1千次。這個很容易理解吧，毒水出現在任意一桶之中是個等概率事件，累加起來的結果就是：
-log(1/1000) = log 1000 約等於9.966
1隻豬喝水以後的要麼活著，要麼死去，一共有兩種狀態，所以」1隻豬喝完水以後的狀態「這個隨機變數Y的信息熵為
n只豬喝完水會有2的n次方種狀態，即"n只豬喝完水以後的狀態"這個隨機變數Y的信息熵為
所以，按照題目要求，如果至少需要n頭豬能夠找到這桶毒水，那麼隨機變數Y的信息熵必須要大於隨機變數X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966，即 n = 10
當我們用信息熵算出來了n的最小值以後，我們就可以堅信，理論上n=10一定是最優解，任何想方設法想找到小於10的值都是徒勞的。
其實，上面的信息熵計算的簡化版本可以寫成如下更好理解的形式 ，同樣可以解得 n = 10 ，雖然形式簡單，但我們一定要記住它背後的原理是信息熵。
至於到底採用什麼方案，這涉及到術的層面，即使我們暫時想不到，我們也會有努力的方向，並且知道努力的邊界在哪裡，不會做類似尋找永動機的事情。
1000桶水，其中一桶有毒，豬喝毒水後會在15分鍾內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？
1000桶水其中有一桶有毒，和第一個問題相同，仍然是9.966。但是，豬的信息熵不同了。我們可以想像一下，一隻豬在一個小時內會有幾種狀態？
可見，1隻豬1個小時以後會有5種狀態，所以」1隻豬1個小時後的狀態「這個隨機變數Z的信息熵為
n只豬1個小時後會有 5的n次方 種狀態，即"n只豬1個小時以後的狀態"這個隨機變數Y的信息熵為
所以，按照題目要求，如果至少需要n頭豬能夠找到這桶毒水，那麼隨機變數Y的信息熵必須要大於隨機變
量X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966 / 2.3219 = 4.292，即 n = 5
事實上，對於 n = 5來說，不僅可以檢測1000桶水，甚至檢測3000桶水都是沒有問題的。有興趣的童鞋
可以試著計算一下。
到此，香農給了我們一個理論極限，但是具體的方案還是需要我們自己進行構造。得出n=5是依靠我們的
理論功底，而得出具體的方案就是我們的工程水平了。
還是知乎3萬贊的作者，參考 香農的資訊理論究竟牛在哪裡？ - 苗華棟的回答 - 知乎 ，老習慣，這里只介紹思路，具體方案看作者原文。
12個外表相同的球中有1個壞球，它的重量比其它11個好球要輕，現在有一台沒有砝碼的天平，問至少稱幾次能確保找出這個壞球？
我們可以思考一下，一個天平稱量1次後會有3種結果：
所以「天平稱量1次後的結果」這個隨機變數Z的信息熵是
如果將上述式子簡化，即
12個外表相同的球中有1個壞球，它的重量和其它11個球不同，現在有一台沒有砝碼的天平，問至少稱幾次能確保找出這個壞球？
這個問題和前面那個問題的不同之處在於不知道這個壞球的輕重。這對信息熵來說跟前面的已知壞球是輕的相比有什麼影響呢？
如果有2個球放在天平兩側。如果已知壞球比較輕，當天平不平衡時，我就可以立刻知道壞球是輕的那一側。而當不知道壞球是輕還是重時，如果天平不平衡，我無法判斷壞球是重的那一側還是輕的那一側，我只能夠知道壞球要麼是輕的那一個，要麼是重的那一個。所以，在不知道壞球是輕還是重時，每次測量多了一個壞球是輕還是重的不確定性。在上題的基礎上，在最高位增加一位表示球的輕重。其中0表示輕，1表示重，如下表所示。於是雖然12個球，但是因為多了一個輕重的不確定性，所以變成24種狀態。
於是「12個外表相同的球中確定1個不知輕重的球」這個隨機變數X的信息熵為
而「天平稱量n次後的結果」這個隨機變數Y的信息熵沒有變，因為天平每次還是只能確定三種狀態，所以
同樣，H(Y) >= H(X) ，即 n >= 2.893，即 n = 3可見，前面那道題並沒有充分發揮天平的信息優勢，3次還能測出不知輕重的壞球。這就是理論武裝頭腦的好處，先找到答案，再去想方案。這種自頂向下的思考方式的好處就是我們在思考方案之前有了目標，也有了努力的方向，而不是無頭蒼蠅一樣。
如果看了文章開頭1000桶水找毒葯那道題的童鞋可能會發現，這道題的解題思路幾乎是照搬那道題的解題思路，雖然表面上是不同類型的題目，但我們要像香農祖師爺學習，透過題目的表象直穿本質。
這兩道題目的底層邏輯都是信息熵，當我們掌握了理論工具以後，人之間的差距就在於是否有足夠的能力將現實問題抽象成數學或者其他問題，然後用我們熟知的理論工具去解決它。在這一點上，就和解方程式是一樣的。解方程本身非常簡單，難點是如何將現實的問題抽象成表達式，定義變數，列出方程式。關於這一點詳細的陳述在我的另一篇文章 《數學思維在生活中有多大用處？》 中有更詳細的描述。
參考 1000桶水，其中一桶有毒，豬喝毒水後會在15分鍾內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？ - PlanarG的回答 - 知乎
考慮這樣一個過程：假設現在給你兩個數a,b，只允許你進行一次比較，將這兩個數從小到大排序。你心想這個問題不是非常簡單嗎，直接拿這兩個數比較一次，哪個數小哪個就排在前面。
我們來分析一下這個看似簡單的問題的本質是什麼。
如果我們只能進行一次比較，那麼根據這一次比較，我們能夠得到的信息實際上只有兩種：要麼第一個數較小，要麼第二個數較小。而兩個數最終從小到大的關系也只有兩種情況：要麼是 a,b ，要麼是b,a 。也就是說，我們能夠根據這一次比較的結果建立一個結果-最終排列的雙射關系，每一種比較的結果都唯一地對應最終的一種大小關系。
現在考慮上面那個問題的升級版：如果現在給你四個數a,b,c,d 能否通過 4 次比較給它們從小到大排序？答案是否定的。因為通過四次比較我們能得到的信息最多隻有2的4次方，即16種。而這4個數的排列一共有4！=24種。因此不可能將詢問的結果與最終排列一一對應，我們就證明了 4 不可能是答案的下界。
我們再升級一次，考慮給n個數排序的情況。如果我們在最終的方案中使用了k次比較，那麼可能得到的信息有2的k次方種，而n個數的排列有n!種。要建立結果-最終排列的雙射關系，必須滿足 即：
現在讓我們用資訊理論的角度思考一下原問題。 1000桶水，只有一桶有毒，換言之，可能的答案只有 1000種。
每頭豬在中毒之後 15分鍾內死去，那麼我們可以從每頭豬獲得的信息一共有5種：在[0,15) [15,30) [30,45) [45,60)中的哪一個時間段死去，或者最終存活下來。如果最終有k只豬，我們能獲得的信息就有 種，換言之，k需要滿足 ，即 ，因此 k的下界為 5。
⑷ 【leetcode C語言實現】面試題 02.05-鏈表求和
給定兩個用鏈表表示的整數，每個節點包含一個數位。
這些數位是反向存放的，也就是個位排在鏈表首部。
編寫函數對這兩個整數求和，並用鏈表形式返回結果。
示例：
輸入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
輸出：2 -> 1 -> 9，即912
進階：假設這些數位是正向存放的，請再做一遍。
示例：
輸入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
輸出：9 -> 1 -> 2，即912
當兩個整數相加時，從個位開始，依次將兩個數的對應位置進行相加，將所得結果的個位數作為相加後對應位置的結果，若有進位將進位的值在更高一位進行相加。此處兩個數是以鏈表存儲，同樣的思路，依次將兩個數的對應位置進行相加，並將所得結果保存到一個鏈表中。
運行結果：
⑸ C C++ leetcode 總是說編譯錯誤，關鍵我連第77行都沒有，只有那麼幾行……
leetcode都不能自己定義主函數的
需要你構造一個Solution的類
77行redefine的main恰好就是leetcode用來測試你寫的Solution的main函數
⑹ LeetCode 力扣官方題解 - 1020. 飛地的數量
題目描述
給你一個大小為 m x n 的二進制矩陣 grid，其中 0 表示一個海洋單元格、1 表示一個陸地單元格。
一次 移動 是指從一個陸地單元格走到另一個相鄰（上、下、左、右）的陸地單元格或跨過 grid 的邊界。
返回網格中 無法 在任意次數的移動中離開網格邊界的陸地單元格的數量。
示例 1：
示例 2：
提示：
根據飛地的定義，如果從一個陸地單元格出發無法移動到網格邊界，則這個陸地單元格是飛地。因此可以將所有陸地單元格分成兩類：第一類陸地單元格和網格邊界相連，這些陸地單元格不是飛地；第二類陸地單元格不和網格邊界相連，這些陸地單元格是飛地。
我們可以從網格邊界上的每個陸地單元格開始深度優先搜索，遍歷完邊界之後，所有和網格邊界相連的陸地單元格就都被訪問過了。然後遍歷整個網格，如果網格中的一個陸地單元格沒有被訪問過，則該陸地單元格不和網格的邊界相連，是飛地。
代碼實現時，由於網格邊界上的單元格一定不是飛地，因此遍歷網格統計飛地的數量時只需要遍歷不在網格邊界上的單元格。
代碼
Java
C#
C++
C
Python3
Golang
JavaScript
復雜度分析
也可以通過廣度優先搜索判斷每個陸地單元格是否和網格邊界相連。
首先從網格邊界上的每個陸地單元格開始廣度優先搜索，訪問所有和網格邊界相連的陸地單元格，然後遍歷整個網格，統計飛地的數量。
代碼
Java
C#
C++
C
Python3
Golang
JavaScript
復雜度分析
除了深度優先搜索和廣度優先搜索的方法以外，也可以使用並查集判斷每個陸地單元格是否和網格邊界相連。
並查集的核心思想是計算網格中的每個陸地單元格所在的連通分量。對於網格邊界上的每個陸地單元格，其所在的連通分量中的所有陸地單元格都不是飛地。如果一個陸地單元格所在的連通分量不同於任何一個網格邊界上的陸地單元格所在的連通分量，則該陸地單元格是飛地。
並查集的做法是，遍歷整個網格，對於網格中的每個陸地單元格，將其與所有相鄰的陸地單元格做合並操作。由於需要判斷每個陸地單元格所在的連通分量是否和網格邊界相連，因此並查集還需要記錄每個單元格是否和網格邊界相連的信息，在合並操作時更新該信息。
在遍歷網格完成並查集的合並操作之後，再次遍歷整個網格，通過並查集中的信息判斷每個陸地單元格是否和網格邊界相連，統計飛地的數量。
代碼
Java
C#
C++
C
Python3
Golang
JavaScript
復雜度分析
BY /
本文作者：力扣
⑺ 為什麼LeetCode上C的解法很少
leetcode不支持C語言原因如下：
1、在ViewController.h添加事件代理和數據源代理<UICollectionViewDataSource,UICollectionViewDelegate>。
2、在ViewController.m創建UICollectionView。需要使用UICollectionViewFlowLayout來創建，使用方法- (instancetype)initWithFrame:(CGRect)frame collectionViewLayout:(UICollectionViewLayout *)layout;如果只用普通的init方法，是實現不了的。
4、代理授權並添加至視圖。
self.collectionView.delegate = self;
self.collectionView.dataSource = self;
[self.view addSubview:self.collectionView];
把UICollectionViewCell添加到UICollectionView內
1、注冊CollectionViewCell，添加cell需要在這里實現。方法：- (void)registerClass:(Class)cellClass forCellWithReuseIdentifier:(NSString *)identifier;
2、添加代理方法
//定義展示的UICollectionViewCell的個數
-(NSInteger)collectionView:(UICollectionView *)collectionView numberOfItemsInSection:(NSInteger)section;