leetcode 41~50 学习经历

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1

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

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:d = set(nums)c = {n + 1 for n in range(len(nums) + 1)}return sorted(c-d)[0]

啊这。。。。。。常数级别额外空间是啥意思？？就说，我这个内存消耗肯定不过关了呗
然后。。。。看大佬们的答案，全都是一个算法，引用这里的说法https://blog.csdn.net/kexuanxiu1163/article/details/103209554

嗯。。。这样就排除了重复数字的干扰。。。。好办法，又学废了一招

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

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

额。。。。这个题目就是考每个坐标点上的最高可与两侧持平的点事多高，那么，简单暴力的来一次

class Solution:def trap(self, height: List[int]) -> int:if len(height) < 3: # 少于3个柱子，存不住水return 0n = len(height)arr = [0 for _ in range(n)] # 临时数组，保存每个位置可保持的最高位置arr[0] = height[0] # 记录上第一个柱子的高度mx = 0for i in range(n - 1): # 从第一个柱子开始测量最高点arr[i + 1] = max(height[i],height[i + 1],arr[i])mx = max(height[i],mx,height[i + 1])  # 并记录下最高点for i in range(n - 1,-1,-1): # 将最高点之后的数据清掉，因为要从新计算if height[i] == mx:breakarr[i] = 0for i in range(n - 1,-1,-1): # 将最高点之后的最高位置从后向前再计算一遍if height[i] == mx:breakarr[i - 1] = max(height[i],height[i - 1],arr[i])arr[-1] = height[-1] # 记录上最后一根柱子的高度return sum([arr[i] - height[i] for i in range(n)]) # 将最高点与原柱子高度相减后求和，就是存量

明显成绩不佳，继续努力

class Solution:def trap(self, height: List[int]) -> int:if len(height) < 3:return 0n,mx = len(height) , max(height)arr = [height[_] for _ in range(n)]total,first,last = 0 , height.index(mx) , n - height[::-1].index(mx) - 1for i in range(first,last + 1):total += mx - height[i]for i in range(n - 1):if height[i] == mx: breakarr[i + 1] = max(height[i],height[i + 1],arr[i])total += arr[i] - height[i]for i in range(n - 1,-1,-1):if height[i] == mx: breakarr[i - 1] = max(height[i],height[i - 1],arr[i])total += arr[i] - height[i]return total

然后就没思路了，接着抄作业。。。好吧，第11题白做了。。。闹心。。。。

class Solution:def trap(self, height: List[int]) -> int:if len(height) < 3:return 0lh,rh,total = height[0],height[-1],0l,r = 1,len(height) - 1while l <= r:if lh < height[l]:lh = height[l]l += 1continueif rh < height[r]:rh = height[r]r -= 1continueif lh < rh:total += lh - height[l]l += 1elif lh >= rh:total += rh - height[r]r -= 1return total

从新写得双指针的确块一点了，内存消耗也小一些，ε=(´ο｀*)))唉，咋就没想起来呢

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”

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

。。。。不转成正数怎么搞？？？用ascii码计算算不算转整数？这题目考的是啥？

class Solution:def multiply(self, num1: str, num2: str) -> str:return str(eval('{}*{}'.format(num1,num2)))

别喷我，我也知道这是作弊了。。。问题是，不转数字，到底怎么算？忍不住看了题解。。。。果然用ascii减出来数字了。。然后，除了没整个数相乘，乘法除法取余都没少用。。。这算什么？后来想了想，也许是乘数被乘数都很大很大，嗯，天文数字那种，计算机肯定溢出的，只好用字符串来保存数据的，也就这种能用到这算法了吧，所以，不是限制乘法除法，是不能直接乘。。。好吧，理解了这个，就从新做吧，难怪评论里全是竖式的说法

class Solution:def add(self,x,y):if x == '' or x == '0':return yif y == '' or y == '0':return xx = x[::-1]y = y[::-1]r = ''n = 0for i in range(max(len(x),len(y))):a = int(x[i]) if i < len(x) else 0b = int(y[i]) if i < len(y) else 0r += str((a + b + n) % 10)n = (a + b + n) // 10if n == 1:r += '1'return r[::-1]def multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0's1 = list(num1)s2 = list(num2)s = ''for i in range(len(s1),0,-1):x = int(s1[i - 1])xn = len(s1) - ifor j in range(len(s2),0,-1):y = int(s2[j - 1])yn = len(s2) - js = self.add(s,str(x * y) + '0' * (xn + yn))return s

。。。。。这是马上超时的节奏了吧。。。。赶紧调整一下进位的计算，不要每次都从个位开始计算

class Solution:def add(self,x,y,z):if x == '' or x == '0':return y + '0' * zif y == '' or y == '0':return x_x = x[::-1] + '0' * (z - len(x))y = y[::-1]x = _x[z:]r = _x[:z]n = 0for i in range(max(len(x),len(y))):a = int(x[i]) if i < len(x) else 0b = int(y[i]) if i < len(y) else 0r += str((a + b + n) % 10)n = (a + b + n) // 10if n == 1:r += '1'return r[::-1]def multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0's1 = list(num1)s2 = list(num2)s = ''for i in range(len(s1),0,-1):x = int(s1[i - 1])xn = len(s1) - ifor j in range(len(s2),0,-1):y = int(s2[j - 1])yn = len(s2) - js = self.add(s,str(x * y),xn + yn)return s

总算不会超时边缘疯狂试探了，继续优化

class Solution:def add(self,x,y,z):if x == '' or x == '0':return y + '0' * zif y == '' or y == '0':return xx = '0' * (z - len(x)) + xr = x[-z:]x = x[:-z]x = 0 if len(x) == 0 else xreturn str(int(x)+int(y)) + rdef multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0's1 = list(num1)s2 = list(num2)s = ''for i in range(len(s1),0,-1):x = int(s1[i - 1])xn = len(s1) - ifor j in range(len(s2),0,-1):y = int(s2[j - 1])yn = len(s2) - js = self.add(s,str(x * y),xn + yn)return s

考虑到每次都是个位数相乘，那么弄一个数组，存放每个位上的乘积之和，最后在数组里再进行进位

class Solution:def multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0's = []for i in range(len(num1),0,-1):x = ord(num1[i - 1]) - 48xn = len(num1) - ifor j in range(len(num2),0,-1):y = ord(num2[j - 1]) - 48yn = len(num2) - jwhile len(s) < xn + yn + 1:s.append(0)s[xn + yn] += x * yn = len(s)for i in range(n):if s[i] > 9:if len(s) == i + 1:s.append(0)s[i + 1] += s[i] // 10s[i] = s[i] % 10return ''.join([str(n) for n in s][::-1])

终于从新杀进100ms的成绩了。。。。可惜刚刚及格，还得继续

class Solution:def multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0'l1,l2 = len(num1),len(num2)s = [0 for _ in range(l1 + l2 + 1)]for i in range(l1,0,-1):x = ord(num1[i - 1]) - 48for j in range(l2,0,-1):y = ord(num2[j - 1]) - 48s[l1 - i + l2 - j] += x * yfor i in range(l1 + l2 + 1):if s[i] > 9:s[i + 1] += s[i] // 10s[i] = s[i] % 10while s[-1] == 0:s.pop(-1)return ''.join([str(n) for n in s][::-1])

额额额。做到这个份上了，还是刚及格的成绩？大佬这么多的么，看我千里眼之术！

然后，只想爆粗口了，这TNND的20ms到60ms全体掩耳盗铃啊，你 10 ** n，这和直接弄出来 num1*num2有区别么？还是我太实在了。更不要说，eval的，int的更多。。。日了哈士奇了

得嘞，这个题用python完全没有意义，他本身支持的整数范围太离谱了，换个c#的玩

嗯，这就舒服了。。。。

44. 通配符匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

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

之前第十题做了个正则匹配的 . 和*，还以为这次会简单点，结果拿第十题的内容直接改了改，一提交都超时了。。。看来思路不能这么简单的延续过来，从新考虑下

在此记录，2023年2月26日写了一地 bug 把老顾自己吞没了，大侠我准备休息一下，回头再来一次

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

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

这个题目不能算中等吧，就是在后边范围内找个能跳的最远的点落地就可以了啊

class Solution:def jump(self, nums: List[int]) -> int:r,i,j,n = 0,0,nums[0],len(nums)if n == 1:return 0while i + j < n - 1:mx,pos = 0,0for x in range(j):if nums[i + x + 1] + x >= mx:mx = nums[i + x + 1] + xpos = x + 1i += posj = nums[i]r += 1return r + 1

水题，没什么好说的

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

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

额。。。。这个就是穷举了吧，还有其他办法？

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def makeGroup(arr,lst):for i in range(len(arr)):makeGroup(arr[:i] + arr[i+1:],lst + [arr[i]])if len(arr) == 0:if lst not in r:r.append(lst)r = []makeGroup(nums,[])return r

嗯，题里说了，每个数不相同。。。不用 not in 判断。。。

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

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

嗯，和46题一样，不过这次有重复数字了

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def makeGroup(arr,lst):i = 0if len(arr) == 0:if lst not in r:r.append(lst)while i < len(arr):makeGroup(arr[:i] + arr[i + 1:],lst + [arr[i]])i += 1nums.sort()r = []makeGroup(nums,[])return r

呦。。。意外啊，多了连个用例，用时超出这么多？

那么，这个题的目的就是怎么优化排重了

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def makeGroup(arr,lst):i = 0if len(arr) == 1:r.append(lst + [arr[0]])while i < len(arr):while i > 0 and i < len(arr) and arr[i] == arr[i - 1]:i += 1if i == len(arr):breakmakeGroup(arr[:i] + arr[i + 1:],lst + [arr[i]])i += 1nums.sort()r = []makeGroup(nums,[])return r

这个排重，前边各类双指针都用的很多了，就没什么可说得了

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

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

额。。。。矩阵旋转。。。。说实话，别考虑坐标对应问题。。。那会死人的，直接按列读，然后把列变成行就差不多了

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""n = len(matrix)r = [[x[c] for x in matrix] for c in range(n)]for i in range(n):matrix[i][:] = r[i][::-1]

python 也就是这个reverse方便，其他语言自己实现一下也一样

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]

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

脑筋急转弯，把单词字母排序，作为字典键，然后再往字典里存数组就好

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:s = {}for i in strs:a = ''.join(sorted(list(i)))if a in s:s[a].append(i)else:s[a] = [i]return [s[n] for n in s]

/*** @param {string[]} strs* @return {string[][]}*/
var groupAnagrams = function(strs) {o = {}for(var i = 0;i < strs.length;i++){s = strs[i]sr = []for (var j = 0;j < s.length;j++){sr.push(s[j])}sr.sort()k = sr.join('')if (o[k]){o[k].push(s)}else{o[k] = [s]}}r = []for (var k in o){r.push(o[k])}return r
};

。。。。成绩有点差啊，估计是箭头函数不熟的问题，抄大佬答案去

// 一下内容抄自leetcode第49题JavaScript 80ms答案
var groupAnagrams = function(strs) {let map = new Map()for(let str of strs){let key = [...str].sort().join('')let list = map.get(key) ? map.get(key) : new Array()list.push(str)map.set(key, list)}return Array.from(map.values())
};

好吧。。。。没得说，落伍就是落伍了，吃灰都吃不上了

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

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

黑人问号？这个，是个啥章程？不用 ** 运算？不用 math库？老顾从95年接触计算机就没想过这东西怎么实现，最多就是自己乘个n次。。。。优化？不存在的！

嗯，各个版本都提交了一个最简单的版本，让语言环境自己计算的，我只是好奇，大佬们都怎么做的

# python
class Solution:def myPow(self, x: float, n: int) -> float:return x ** n

// javascript
var myPow = function(x, n) {return x ** n
};

// c#
public class Solution {public double MyPow(double x, int n) {return Math.Pow(x,n);}
}

leetcode 有一点不好，你没有提交记录，就不能抄答案，而且，你提交哪个语言环境的，就只能看哪个语言环境的答案，为了抄作业，也得多提交几个语言版本的啊

然后发现，原来是自己写递归算幂运算，比这个环境自带的块一点点？额。。。有必要么。。。既然都是自己乘n次，那就没必要继续研究了

小结

这次10道题有三个评价苦难。
第一个是41，缺失的正数，这个是没思路，纯粹用语言特性进行的作弊，还好后边找到资料能学习。
42接雨水，自己脑袋有坑，做了这么多双指针题，楞是想不起来用一下，第一版已经从前向后，从后向前推数据了，结果还是没用双指针。。。
最后就是44题，通配符题，本来以为会很快做出来，结果自己写了一地 bug，脑袋就浆糊了。等我缓两天再回来灭了他。
然后中等难度的 43 题，字符串相乘，这。。。。才是一步一步做下来的，结果还是错付了