php网站开发数据列表排重,网站内容是什么,惠州网站推广,织梦如何制作静态网站模板leetcode 41~50 学习经历41. 缺失的第一个正数42. 接雨水43. 字符串相乘44. 通配符匹配45. 跳跃游戏 II46. 全排列47. 全排列 II48. 旋转图像49. 字母异位词分组50. Pow(x, n)小结41. 缺失的第一个正数 给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的…
leetcode 41~50 学习经历41. 缺失的第一个正数42. 接雨水43. 字符串相乘44. 通配符匹配45. 跳跃游戏 II46. 全排列47. 全排列 II48. 旋转图像49. 字母异位词分组50. Pow(x, n)小结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 1return r[::-1]def multiply(self, num1: str, num2: str) - str:if num1 0 or num2 0:return 0s1 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 1return r[::-1]def multiply(self, num1: str, num2: str) - str:if num1 0 or num2 0:return 0s1 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 0s1 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 0s []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 0l1,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[i1:],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 题字符串相乘这。。。。才是一步一步做下来的结果还是错付了
