leetcode 11~20 学习经历

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1

提示：
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
通过次数917,591提交次数1,513,670

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

秀逗的脑袋不转圈，为什么第一想法都是暴力运算呢？

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万数据。。。能过才见鬼了

也没多少用例数据嘛。。。才5屏半而已。。。。见鬼了。。。。

还是开始动动脑子吧。。。从两边往中间推，哪边的柱子低，哪边就往里推

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

额。。。居然通过了，我还说万一中间有几根高出天际的柱子，会影响计算，结果他没这情况

竟然。。。有不到50ms的成绩？赶紧学习！

一段时间过去了，程序看懂了，思路貌似也理解了，但绝对不会在以后能想起来。。。。。

这题基本都是双指针，和双指针优化了，到此为止，继续下一题。

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

示例 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
通过次数362,078提交次数546,627

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题好像以前做过，很久以前很久以前。。。想不起来了！

算了，从新做一遍吧。

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

额。。。。大佬这么多，看看分布，又是一群大佬集中？然后翻了翻头部的答案。。。。各种奇葩的节省时间思路啊。。。。真是无语了。。。

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

示例 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’)
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
通过次数776,067提交次数1,245,617

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这一题就是上一题的逆运算，说实话，这个比上一个还简单，碰到前边数字小于后边数字的，就减去前边数字就好，其他都是加法，这个题，也不想拼什么执行时间了，没啥感觉

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. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

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

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
通过次数1,027,298提交次数2,377,782

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这一题也很简单，暴力莽过去看看

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

额。。。虽然在预计内，但还是没想到大家应该都是暴力莽的

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 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
通过次数1,264,583提交次数3,442,609

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力，我们崇尚暴力！虽然知道肯定过不去，但还是要发泄一下暴力！

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

一时半会的，也不知道怎么优化，折腾了半天还是超时，先换个思路看看

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

好歹是通过了。。。这个就是把负数放一起，正数放一起，分开算，负数和取绝对值在正数里找对应，反之亦然

但很明显，这个算法也很土了，更不要说成绩了，总算自己完成一版，然后开始去看官方题解

抄了一遍官方题解，效率也就比我的好一些，但成绩还是排不上号啊

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:n = len(nums)nums.sort()ans = list()# 枚举 afor first in range(n):# 需要和上一次枚举的数不相同if first > 0 and nums[first] == nums[first - 1]:continue# c 对应的指针初始指向数组的最右端third = n - 1target = -nums[first]# 枚举 bfor second in range(first + 1, n):# 需要和上一次枚举的数不相同if second > first + 1 and nums[second] == nums[second - 1]:continue# 需要保证 b 的指针在 c 的指针的左侧while second < third and nums[second] + nums[third] > target:third -= 1# 如果指针重合，随着 b 后续的增加# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

然后，我就想不明白了，为什么我的代码就超时呢？下边代码和上边代码区别很大吗？

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层循环里，超时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

那么，里面第三层循环用 for 那就更没跑的超时了。。。这题真难，比第10题正则的都难。。。55555

还有好多高分答案没看呢，继续学习吧。。。。bisect 是啥？头部答案基本都用了这个。。。。也没有 import 看一下，纳闷了

然后，结合字典和我自己搞出的5000ms的思路，从新优化出一版

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

除了头部的那个看不懂的 bisect ，其他的考前的都是双指针操作，我就不尝试了，思路学会了就继续下一题

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 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
通过次数441,101提交次数976,526

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题。。。。。和前边的三数和的思路一样啊，唯一不同的就是有一个不确定的 target，而且这个 target 很飘逸，很有可能是比三个最大正数和还打上不少，或者比三个负数和小上不少，这里就出现了一个小问题，怎么确认一个初始的 target 来记录当前最接近 target 的三数和呢？好在提示里有，target 的范围，那就弄出一个超出这个范围的数最为起始值好了

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

额，提交的时候，有几个用例错误了，就是双指针，是根据什么移动左还是右的问题

这个成绩一看就是基础不稳，之前的三数和没做好，这个题就很难做好了，从新学习这两题的大佬的答案吧，然后，还是一堆看不懂的东西。。。不过，有个思路倒是很合适，在开始循环前判断前三后三的和与target比较，然后稍微调整了一下，执行时间就。。。。哎。。。用例的问题

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

既然知道用例有问题，那么久再调整一下

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/
竟然还有这评价？无敌了。。。。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 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’] 的一个数字。
通过次数637,332提交次数1,097,933

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题目其实很简单，主要就是读题，刚开始，老顾一下子挺蒙的，为什么23会出来这么多字母，后来才想明白，这不就是9键手机键盘的对应字母么，然后求最大组合

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

这题没什么说的，递归一下什么都有了，而且范围也小

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
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
通过次数417,575提交次数1,114,508

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

额。。。。本次刷题最难的应该是这个吧？看了看提示，只有200个数，那么暴力应该能通过吧？
那就暴力来一次看看

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

啧啧，还真通过了，那就继续翻动一下咸鱼的脑干，答题思路不变，还是递归，稍微调整下跳出

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

啧啧，用时少了一半，成绩还是这个档次，暂时用递归不知道怎么优化了，开始抄作业。官方题解真没啥作用。然后看了下答案分布。。。啧啧，名落孙山了

看了看大家的答案，貌似都是双循环双指针，感觉以后还有5数和，不定数量的数之和之类的，难道没有一个通用的高效办法吗？这个问题先记下了，以后学明白了，单独针对这个问题写个学习经历。

最后调整一下，在递归里最后两层循环改成双指针

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)

这成绩暂时能接受了，以后学有所得的时候再继续优化

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 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]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？
通过次数1,037,729提交次数2,295,516

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

老顾对链表完全不了解啊，什么叫只扫描一趟？还是先做出来再考虑吧

# 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

这个办法肯定是不对的，他重构了一趟链表，看了看官方题解，三种方法大概理解了一点点，只是双指针方式自己没尝试成功，还是对链表不熟悉的过，以后补课

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

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

提示：
1 <= s.length <= 10^4
s 仅由括号 ‘()[]{}’ 组成
通过次数1,377,119提交次数3,105,792

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个。。。送分题，考队列的，弄个队列对上开始结束就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

小结

三数和，四数和，不定数量数的和。。。真难啊，以后还要努力学习，除了这三个数和问题，其他问题相对简单，大家一起加油吧