11. 盛最多水的容器

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
說(shuō)明：你不能傾斜容器。

示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例 2：
輸入：height = [1,1]
輸出：1

提示：
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
通過次數(shù)917,591提交次數(shù)1,513,670

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/container-with-most-water
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

秀逗的腦袋不轉(zhuǎn)圈，為什么第一想法都是暴力運(yùn)算呢？

class Solution:def maxArea(self, height: List[int]) -> int:n = len(height)dp = [[0 for _ in range(n)] for _ in range(n)]for i in range(n):for j in range(i+1,n):dp[i][j] = min(height[i],height[j]) * (j - i)mx = [max(row) for row in dp]return max(mx)

這算法。。。按照用例范圍10萬(wàn)數(shù)據(jù)。。。能過才見鬼了

也沒多少用例數(shù)據(jù)嘛。。。才5屏半而已。。。。見鬼了。。。。

還是開始動(dòng)動(dòng)腦子吧。。。從兩邊往中間推，哪邊的柱子低，哪邊就往里推

class Solution:def maxArea(self, height: List[int]) -> int:mx = 0n = len(height)l = 0r = n - 1while True:c = min(height[l],height[r]) * (r - l)if c > mx:mx = cif height[l] > height[r]:r -= 1else:l += 1if l == r:breakreturn mx

額。。。居然通過了，我還說(shuō)萬(wàn)一中間有幾根高出天際的柱子，會(huì)影響計(jì)算，結(jié)果他沒這情況

竟然。。。有不到50ms的成績(jī)？趕緊學(xué)習(xí)！

一段時(shí)間過去了，程序看懂了，思路貌似也理解了，但絕對(duì)不會(huì)在以后能想起來(lái)。。。。。

這題基本都是雙指針，和雙指針優(yōu)化了，到此為止，繼續(xù)下一題。

12. 整數(shù)轉(zhuǎn)羅馬數(shù)字

羅馬數(shù)字包含以下七種字符： I， V， X， L，C，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II ，即為兩個(gè)并列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來(lái)表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來(lái)表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左邊，來(lái)表示 400 和 900。
給你一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。

示例 1:
輸入: num = 3
輸出: “III”
示例 2:
輸入: num = 4
輸出: “IV”
示例 3:
輸入: num = 9
輸出: “IX”
示例 4:
輸入: num = 58
輸出: “LVIII”
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: num = 1994
輸出: “MCMXCIV”
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

提示：
1 <= num <= 3999
通過次數(shù)362,078提交次數(shù)546,627

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/integer-to-roman
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這個(gè)題好像以前做過，很久以前很久以前。。。想不起來(lái)了！

算了，從新做一遍吧。

class Solution:def intToRoman(self, num: int) -> str:#num = 1994# MCMXCIVn = [1,5,10,50,100,500,1000]c = ['I','V','X','L','C','D','M']r = ''for i in range(7,0,-1):m = max((i // 2 - 1) * 2,0)v = n[i - 1]l = c[i - 1]#print(num,v)while num >= v:num -= vr += lif num > 0 and v - num <= n[m]:#print(v,num,n[m],r)r += c[m] + lnum -= v - n[m]#print(num,r)return r

額。。。。大佬這么多，看看分布，又是一群大佬集中？然后翻了翻頭部的答案。。。。各種奇葩的節(jié)省時(shí)間思路啊。。。。真是無(wú)語(yǔ)了。。。

13. 羅馬數(shù)字轉(zhuǎn)整數(shù)

羅馬數(shù)字包含以下七種字符: I， V， X， L，C，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II ，即為兩個(gè)并列的 1 。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來(lái)表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊，來(lái)表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左邊，來(lái)表示 400 和 900。
給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。

示例 1:
輸入: s = “III”
輸出: 3
示例 2:
輸入: s = “IV”
輸出: 4
示例 3:
輸入: s = “IX”
輸出: 9
示例 4:
輸入: s = “LVIII”
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:
輸入: s = “MCMXCIV”
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

提示：
1 <= s.length <= 15
s 僅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
題目數(shù)據(jù)保證 s 是一個(gè)有效的羅馬數(shù)字，且表示整數(shù)在范圍 [1, 3999] 內(nèi)
題目所給測(cè)試用例皆符合羅馬數(shù)字書寫規(guī)則，不會(huì)出現(xiàn)跨位等情況。
IL 和 IM 這樣的例子并不符合題目要求，49 應(yīng)該寫作 XLIX，999 應(yīng)該寫作 CMXCIX 。
關(guān)于羅馬數(shù)字的詳盡書寫規(guī)則，可以參考 羅馬數(shù)字 - Mathematics 。
通過次數(shù)776,067提交次數(shù)1,245,617

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/roman-to-integer
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這一題就是上一題的逆運(yùn)算，說(shuō)實(shí)話，這個(gè)比上一個(gè)還簡(jiǎn)單，碰到前邊數(shù)字小于后邊數(shù)字的，就減去前邊數(shù)字就好，其他都是加法，這個(gè)題，也不想拼什么執(zhí)行時(shí)間了，沒啥感覺

class Solution:def romanToInt(self, s: str) -> int:n = [1,5,10,50,100,500,1000]l = ['I','V','X','L','C','D','M']r = 0for i in range(len(s)):if i < len(s) - 1:if l.index(s[i]) >= l.index(s[i + 1]):r += n[l.index(s[i])]else:r -= n[l.index(s[i])]else:r+= n[l.index(s[i])]return r

14. 最長(zhǎng)公共前綴

編寫一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 “”。

示例 1：
輸入：strs = [“flower”,“flow”,“flight”]
輸出：“fl”
示例 2：
輸入：strs = [“dog”,“racecar”,“car”]
輸出：“”
解釋：輸入不存在公共前綴。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 僅由小寫英文字母組成
通過次數(shù)1,027,298提交次數(shù)2,377,782

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/longest-common-prefix
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這一題也很簡(jiǎn)單，暴力莽過去看看

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:r = ''n = min([len(n) for n in strs])for i in range(n):if ''.join([n[i] for n in strs]) != strs[0][i] * len(strs):breakr += strs[0][i]return r

額。。。雖然在預(yù)計(jì)內(nèi)，但還是沒想到大家應(yīng)該都是暴力莽的

15. 三數(shù)之和

給你一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0 。請(qǐng)
你返回所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。

示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

提示：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
通過次數(shù)1,264,583提交次數(shù)3,442,609

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/3sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

暴力，我們崇尚暴力！雖然知道肯定過不去，但還是要發(fā)泄一下暴力！

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:#nums = [-1,0,1,2,-1,-4,-2,-3,3,0,4]result = []nums.sort()n = len(nums)p = 0while p < n:t = nums[p]if t > 0:breakfor i in range(p + 1,n - 1):if (t + nums[i]) * -1 in nums[i + 1:]:c = [t,nums[i],(t + nums[i]) * -1]c.sort()if not c in result:result.append(c)p += 1result.sort()return result

一時(shí)半會(huì)的，也不知道怎么優(yōu)化，折騰了半天還是超時(shí)，先換個(gè)思路看看

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []if len(nums)==3 and sum(nums)==0:result.append(nums)return resulta,b,c=[n for n in nums if n<0],[n for n in nums if n==0],[n for n in nums if n>0]a.sort()c.sort()sa = set(a)sc = set(c)if len(b)>2:result.append([0,0,0])if len(b) > 0:for i in a:if abs(i) in c and [i,0,abs(i)] not in result:result.append([i,0,abs(i)])if len(a) == 0 or len(c) == 0:return resultif len(a)>1:mx = c[-1]n = len(a)for i in range(n - 1):for j in range(n - 1,i,-1):v = abs(a[i] + a[j])if v > mx:breakif v in sc and not [a[i],a[j],v] in result:result.append([a[i],a[j],v])if len(c)>1:mx = abs(a[0])n = len(c)for j in range(n - 1,0,-1):for i in range(j):v = c[i] + c[j]if v > mx:breakif v * -1 in sa and not [v * -1,c[i],c[j]] in result:result.append([v * -1,c[i],c[j]])result.sort()return result

好歹是通過了。。。這個(gè)就是把負(fù)數(shù)放一起，正數(shù)放一起，分開算，負(fù)數(shù)和取絕對(duì)值在正數(shù)里找對(duì)應(yīng)，反之亦然

但很明顯，這個(gè)算法也很土了，更不要說(shuō)成績(jī)了，總算自己完成一版，然后開始去看官方題解

抄了一遍官方題解，效率也就比我的好一些，但成績(jī)還是排不上號(hào)啊

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:n = len(nums)nums.sort()ans = list()# 枚舉 afor first in range(n):# 需要和上一次枚舉的數(shù)不相同if first > 0 and nums[first] == nums[first - 1]:continue# c 對(duì)應(yīng)的指針初始指向數(shù)組的最右端third = n - 1target = -nums[first]# 枚舉 bfor second in range(first + 1, n):# 需要和上一次枚舉的數(shù)不相同if second > first + 1 and nums[second] == nums[second - 1]:continue# 需要保證 b 的指針在 c 的指針的左側(cè)while second < third and nums[second] + nums[third] > target:third -= 1# 如果指針重合，隨著 b 后續(xù)的增加# 就不會(huì)有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)if second == third:breakif nums[second] + nums[third] == target:ans.append([nums[first], nums[second], nums[third]])return ans作者：LeetCode-Solution
鏈接：https://leetcode.cn/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

然后，我就想不明白了，為什么我的代碼就超時(shí)呢？下邊代碼和上邊代碼區(qū)別很大嗎？

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []nums.sort()n = len(nums)for i in range(n):if nums[i] > 0:breakif i > 0 and nums[i] == nums[i - 1]:continuet = abs(nums[i])for j in range(i+1,n):if j > i + 1 and nums[j] == nums[j - 1]:continuefor k in range(n - 1,j,-1):if k < n - 1 and nums[k] == nums[k + 1]:continueif nums[k] + nums[j] > t:continueif nums[k] < 0:breakif nums[i] + nums[j] + nums[k] == 0:result.append([nums[i],nums[j],nums[k]])if nums[i] + nums[j] + nums[k] < 0:breakreturn result

最后，還是按照題解的完整的抄了一遍，注意 k 賦值的位置

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []nums.sort()n = len(nums)for i in range(n - 2):if i > 0 and nums[i] == nums[i - 1]:continuet = -nums[i]k = n - 1for j in range(i+1,n):if j > i + 1 and nums[j] == nums[j - 1]:continuef = nums[j]while j < k and f + nums[k] > t:k -= 1if j == k:breakif f + nums[k] == t:#if [nums[i],nums[j],nums[k]] not in result:result.append([nums[i],nums[j],nums[k]])return result

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []nums.sort()n = len(nums)for i in range(n - 2):if i > 0 and nums[i] == nums[i - 1]:continuet = -nums[i]for j in range(i+1,n):if j > i + 1 and nums[j] == nums[j - 1]:continuef = nums[j]k = n - 1  # k賦值放到2層循環(huán)里，超時(shí)while j < k and f + nums[k] > t:k -= 1if j == k:breakif f + nums[k] == t:#if [nums[i],nums[j],nums[k]] not in result:result.append([nums[i],nums[j],nums[k]])return result

那么，里面第三層循環(huán)用 for 那就更沒跑的超時(shí)了。。。這題真難，比第10題正則的都難。。。55555

還有好多高分答案沒看呢，繼續(xù)學(xué)習(xí)吧。。。。bisect 是啥？頭部答案基本都用了這個(gè)。。。。也沒有 import 看一下，納悶了

然后，結(jié)合字典和我自己搞出的5000ms的思路，從新優(yōu)化出一版

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []d = Counter(nums)l = sorted(d)for x in range(len(l)):i = l[x]if i == 0 and d[i] > 2:result.append([0,0,0])if d[i] > 1 and (i * -2) in d and i != 0:result.append([i,i,i * -2])if i < 0 and -i in d and d[0] > 0:result.append([i,0,-i])if i < 0:for y in range(x + 1,len(l)):j = l[y]if j == 0:continuet = (i + j) * -1if t in d and t != 0:if i < t and j < t:result.append([i,j,t])return result

除了頭部的那個(gè)看不懂的 bisect ，其他的考前的都是雙指針操作，我就不嘗試了，思路學(xué)會(huì)了就繼續(xù)下一題

16. 最接近的三數(shù)之和

給你一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 nums 和 一個(gè)目標(biāo)值 target。請(qǐng)你從 nums 中選出三個(gè)整數(shù)，使它們的和與 target 最接近。
返回這三個(gè)數(shù)的和。
假定每組輸入只存在恰好一個(gè)解。

示例 1：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
輸入：nums = [0,0,0], target = 1
輸出：0

提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4
通過次數(shù)441,101提交次數(shù)976,526

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/3sum-closest
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這個(gè)題。。。。。和前邊的三數(shù)和的思路一樣啊，唯一不同的就是有一個(gè)不確定的 target，而且這個(gè) target 很飄逸，很有可能是比三個(gè)最大正數(shù)和還打上不少，或者比三個(gè)負(fù)數(shù)和小上不少，這里就出現(xiàn)了一個(gè)小問題，怎么確認(rèn)一個(gè)初始的 target 來(lái)記錄當(dāng)前最接近 target 的三數(shù)和呢？好在提示里有，target 的范圍，那就弄出一個(gè)超出這個(gè)范圍的數(shù)最為起始值好了

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:#nums = [4,0,5,-5,3,3,0,-4,-5]#target = -2nums.sort()n = len(nums)if n < 3:return Nonemn = 1e5for i in range(n):if i > 0 and nums[i] == nums[i - 1]:continuel,r = i + 1,n - 1while l < r:while l < r and l > i + 1 and nums[l] == nums[l - 1]:l += 1while r> l and r < n - 1 and nums[r] == nums[r + 1]:r -= 1if l >= r:breakc = nums[i] + nums[l] + nums[r]#print(n,i,l,r,'n:',nums[i],nums[l],nums[r],c)if abs(c - target) < abs(mn - target):mn = cif mn == target:break#if abs(nums[l] - target) < abs(nums[r] - target):if c < target:l += 1else:r -= 1return mn

額，提交的時(shí)候，有幾個(gè)用例錯(cuò)誤了，就是雙指針，是根據(jù)什么移動(dòng)左還是右的問題

這個(gè)成績(jī)一看就是基礎(chǔ)不穩(wěn)，之前的三數(shù)和沒做好，這個(gè)題就很難做好了，從新學(xué)習(xí)這兩題的大佬的答案吧，然后，還是一堆看不懂的東西。。。不過，有個(gè)思路倒是很合適，在開始循環(huán)前判斷前三后三的和與target比較，然后稍微調(diào)整了一下，執(zhí)行時(shí)間就。。。。哎。。。用例的問題

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:#nums = [4,0,5,-5,3,3,0,-4,-5]#target = -2nums.sort()n = len(nums)if n < 3:return Noneif sum(nums[:3]) >= target:return sum(nums[:3])if sum(nums[-3:]) <= target:return sum(nums[-3:])mn = 1e5for i in range(n):if mn == target:breakif i > 0 and nums[i] == nums[i - 1]:continuel,r = i + 1,n - 1while l < r:while l < r and l > i + 1 and nums[l] == nums[l - 1]:l += 1while r> l and r < n - 1 and nums[r] == nums[r + 1]:r -= 1if l >= r:breakc = nums[i] + nums[l] + nums[r]if abs(c - target) < abs(mn - target):mn = cif mn == target:breakif c < target:l += 1else:r -= 1return mn

既然知道用例有問題，那么久再調(diào)整一下

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:#nums = [4,0,5,-5,3,3,0,-4,-5]#target = -2nums.sort()n = len(nums)if n < 3:return Noneif sum(nums[:3]) >= target:return sum(nums[:3])if sum(nums[-3:]) <= target:return sum(nums[-3:])mn = 1e5for i in range(n - 2):if mn == target:breakif i > 0 and nums[i] == nums[i - 1]:continueif nums[i] + nums[-1] + nums[-2] < target:continuel,r = i + 1,n - 1while l < r:while l < r and l > i + 1 and nums[l] == nums[l - 1]:l += 1while r> l and r < n - 1 and nums[r] == nums[r + 1]:r -= 1if l >= r:breakc = nums[i] + nums[l] + nums[r]if abs(c - target) < abs(mn - target):mn = cif mn == target:breakif c < target:l += 1else:r -= 1return mn

https://leetcode.cn/submissions/detail/404423668/
竟然還有這評(píng)價(jià)？無(wú)敵了。。。。

17. 電話號(hào)碼的字母組合

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

示例 1：
輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
輸入：digits = “”
輸出：[]
示例 3：
輸入：digits = “2”
輸出：[“a”,“b”,“c”]

提示：
0 <= digits.length <= 4
digits[i] 是范圍 [‘2’, ‘9’] 的一個(gè)數(shù)字。
通過次數(shù)637,332提交次數(shù)1,097,933

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這個(gè)題目其實(shí)很簡(jiǎn)單，主要就是讀題，剛開始，老顧一下子挺蒙的，為什么23會(huì)出來(lái)這么多字母，后來(lái)才想明白，這不就是9鍵手機(jī)鍵盤的對(duì)應(yīng)字母么，然后求最大組合

class Solution:def letterCombinations(self, digits: str) -> List[str]:d = {2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}r = self.makeGroup(digits,d) if len(digits)>0 else []return rdef makeGroup(self,s,d):r = []l = int(s[0])s = s[1:]z = d[l]if len(s) == 0:return list(z)for n in z:r += [n+x for x in self.makeGroup(s,d)]return r

這題沒什么說(shuō)的，遞歸一下什么都有了，而且范圍也小

18. 四數(shù)之和

給你一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)值 target 。請(qǐng)你找出并返回滿足下述全部條件且不重復(fù)的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。

示例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]

提示：
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
通過次數(shù)417,575提交次數(shù)1,114,508

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/4sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

額。。。。本次刷題最難的應(yīng)該是這個(gè)吧？看了看提示，只有200個(gè)數(shù)，那么暴力應(yīng)該能通過吧？
那就暴力來(lái)一次看看

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()r = self.makeGroup(nums,target,[],4)return rdef makeGroup(self,arr,t,r,x):if x == 1:result = []d = set(arr)if t in d:result.append(r + [t])return resultreturn resultresult = []for i in range(len(arr) - x + 1):if i > 0 and arr[i] == arr[i - 1]:continueresult += self.makeGroup(arr[i + 1:],t - arr[i],r + [arr[i]],x - 1)return result

嘖嘖，還真通過了，那就繼續(xù)翻動(dòng)一下咸魚的腦干，答題思路不變，還是遞歸，稍微調(diào)整下跳出

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()r = self.makeGroup(nums,target,[],4)return rdef makeGroup(self,arr,t,r,x):if x == 1:if arr.count(t) > 0:return [r + [t]]return []result = []v = sum(arr[-x + 1:])for i in range(len(arr) - x + 1):if i > 0 and arr[i] == arr[i - 1]:continueif t- arr[i] > v:continueresult += self.makeGroup(arr[i + 1:],t - arr[i],r + [arr[i]],x - 1)return result

嘖嘖，用時(shí)少了一半，成績(jī)還是這個(gè)檔次，暫時(shí)用遞歸不知道怎么優(yōu)化了，開始抄作業(yè)。官方題解真沒啥作用。然后看了下答案分布。。。嘖嘖，名落孫山了

看了看大家的答案，貌似都是雙循環(huán)雙指針，感覺以后還有5數(shù)和，不定數(shù)量的數(shù)之和之類的，難道沒有一個(gè)通用的高效辦法嗎？這個(gè)問題先記下了，以后學(xué)明白了，單獨(dú)針對(duì)這個(gè)問題寫個(gè)學(xué)習(xí)經(jīng)歷。

最后調(diào)整一下，在遞歸里最后兩層循環(huán)改成雙指針

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()self.r = []self.makeGroup(nums,target,[],4)return self.rdef makeGroup(self,arr,t,r,x):if x == 2:m,n = 0,len(arr) - 1while m < n:while m > 0 and m < n and arr[m] == arr[m - 1]:m += 1while n > m and n < len(arr) - 1 and arr[n] == arr[n + 1]:n -= 1if m == n:breakif arr[m] + arr[n] > t:n -= 1elif arr[m] + arr[n] < t:m += 1else:self.r.append(r + [arr[m],arr[n]])m += 1n -= 1returnv = sum(arr[-x + 1:])for i in range(len(arr) - x + 1):if i > 0 and arr[i] == arr[i - 1]:continueif t- arr[i] > v:continueself.makeGroup(arr[i + 1:],t - arr[i],r + [arr[i]],x - 1)

這成績(jī)暫時(shí)能接受了，以后學(xué)有所得的時(shí)候再繼續(xù)優(yōu)化

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]

提示：
鏈表中結(jié)點(diǎn)的數(shù)目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？
通過次數(shù)1,037,729提交次數(shù)2,295,516

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

老顧對(duì)鏈表完全不了解啊，什么叫只掃描一趟？還是先做出來(lái)再考慮吧

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:arr = []while head:arr.append(head.val)head = head.nextarr.pop(-n)if len(arr) > 0:head = ListNode()r = headfor i in range(len(arr)):head.val = arr[i]if i < len(arr) - 1:head.next = ListNode()head = head.nextreturn rreturn None

這個(gè)辦法肯定是不對(duì)的，他重構(gòu)了一趟鏈表，看了看官方題解，三種方法大概理解了一點(diǎn)點(diǎn)，只是雙指針方式自己沒嘗試成功，還是對(duì)鏈表不熟悉的過，以后補(bǔ)課

20. 有效的括號(hào)

給定一個(gè)只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。

示例 1：
輸入：s = “()”
輸出：true
示例 2：
輸入：s = “()[]{}”
輸出：true
示例 3：
輸入：s = “(]”
輸出：false

提示：
1 <= s.length <= 10^4
s 僅由括號(hào) ‘()[]{}’ 組成
通過次數(shù)1,377,119提交次數(shù)3,105,792

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/valid-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這個(gè)。。。送分題，考隊(duì)列的，弄個(gè)隊(duì)列對(duì)上開始結(jié)束就ok

class Solution:def isValid(self, s: str) -> bool:d = len(s)if d == 0:return Trueif d % 2 == 1:return Falsed = {']':'[','}':'{',')':'('}l = ''for i in s:if len(l) == 0:if i in d:return Falseelse:l += ielif i in '[{(':l += ielif l[-1] != d[i]:return Falseelse:l = l[:-1]if len(l) > 0:return Falsereturn True

小結(jié)

三數(shù)和，四數(shù)和，不定數(shù)量數(shù)的和。。。真難啊，以后還要努力學(xué)習(xí)，除了這三個(gè)數(shù)和問題，其他問題相對(duì)簡(jiǎn)單，大家一起加油吧