Python200道leetcode编程题

1、Python200道leetcode编程题在leetcode刷200道题，完成学校2020年96号到920号的学期任务，特此记录， 同时也供家学习交流。【 表数值的字符串】请实现个函数来判断字符串是否表数值（包括整数和数）。例如，字符串+100、5e2、-123、3.1416、-1E-16、0123都表数值，但12e、1a3.14、1.2.3、+-5及12e+5.4都不是。import reclass Solution(object): def isNumber(self, s):type s: str:rtype: bool matchObj=re.match(s*+-0,1(d)+(.)(

2、d)+)0,1|(.)(d)+)|(d)+(.)(eE+-0,1d+)0,1s*$,s) if matchObj:print (match - matchObj.group() : , matchObj.group() return Trueelse:print (No match!) return False【两数之和】给定个整数数组 nums 和个标值 target，请你在该数组中找出和为标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输只会对应个答案。但是，数组中同个元素不能使两遍。例:给定 nums = 2, 7, 11, 15, target = 9因为 nums0 + n

3、ums1 = 2 + 7 = 9 所以返回 0, 1第1种最耗时，思路：拿数组的第个数字和后的数字分别相加，看是否等于target；如果不等于target，那么就继续拿数组的第个数字和后的数字相加；不停的去个前置知识：nums = 11, 2，15，7，的数字对应的下标分别是0,1,2,3for循环嵌套执顺序：如果个for循环还有个for循环，如果条件不满，那么的for循环会先执完，外的for循环才会执class Solution:def twoSum(self,nums,target):n = len(nums) # 获取nums的长度，是4for x in range(n): # 外层循环

4、先取出下标0，对应着数组的第个数字for y in range(x+1,n): # 内层循环取出下标1，对应着数组的第个数字if numsx + numsy = target: # 如果第个数字+第个数字=target return x,y # 上的判断是对的话，那么就返回下标break # 并停程序else: # 如果上的条件不满的话，内层for循环就会继续取出下标2进判断.如果都不满，那么外层for循环就会取出下标1.依次类推continue第2种，1个for循环直接target 减去 取出的数字，看结果有没有在数组class Solution:def twoSum(self,nums,t

5、arget):n = len(nums) for x in range(n):a = target - numsxif a in nums: # 判断a有没有在nums数组y = nums.index(a) # 有的话，那么index获取到该数字的下标if x = y:continue # 同样的数字不能重复，所以这如果是样的数字，那么就不满条件，跳过else: # 否则就返回结果return x,y breakelse:continue # 上的条件都不满就跳过，进下次循环第3种，字典提速度这个是看了别的图解答案才知道的（/problems/two-sum/solution/tu-jie-h

6、a-xi-biao-by-ml-zimingmeng/），把原先的数组转化成字class Solution:def twoSum(self,nums,target):d = n = len(nums) for x in range(n):dnumsx = x # 把数组的数字作为key，下标作为value存到d字典中if target - numsx in d: # 看另外个数字有没有在字典return dtarget-numsx,x # 有的话直接就可以返回value了;没有的话会继续循环经群友指出，上的写法是错误的。如果先把数组转化成字典的话，target-numsx的值很有可能会等于nu

7、msx，正确的如下：class Solution:def twoSum(self,nums,target): d = n = len(nums) for x in range(n):if target - numsx in d: return dtarget-numsx,x else:dnumsx = x【叉树的层次遍历 II】给定个叉树，返回其节点值底向上的层次遍历。 （即按从叶节点所在层到根节点所在的层，逐层从左向右遍历）BFS实现class Solution(object):def levelOrderBottom(self, root): if not root:return # 创建

8、个队列，将根节点放其中queue = root# 来存放最终结果res = while queue:# 每次遍历的数量为队列的长度size = len(queue) tmp = # 将这层的元素全部取出，放到临时数组中，如果节点的左右孩不为空，继续放队列for _ in xrange(size): node = queue.pop(0) tmp.append(node.val) if node.left:queue.append(node.left) if node.right:queue.append(node.right) res.append(tmp)# 翻转最终结果并返回return

9、res:-1BFS实现-2第种式中，我们将最终结果集定义成数组，等所有元素都放置完后，再翻转下数组。我们可以将其结构改成链表，以后每层遍历完将结果放到链表的第位，这样就动完成了翻转的功能了class Solution(object):def levelOrderBottom(self, root): if not root:return queue = root# 改双端队列实现，每次都插到第位res = collections.deque() while queue:size = len(queue) tmp = for _ in xrange(size): node = queue.pop

10、(0) tmp.append(node.val) if node.left:queue.append(node.left) if node.right:queue.append(node.right)# 每次插到第位，这样带了翻转的功能res.appendleft(tmp) return list(res)DFS实现class Solution(object):def levelOrderBottom(self, root): if not root:return # 来存放最终结果res = def dfs(root,index):if not root: return# 如果index于r

11、es，说明这层没有对应的集合，需要新创建if indexlen(res): res.append()# 将当前层的元素直接放到对应层的末尾即可resindex-1.append(root.val)# 继续遍历左右节点，同时将层+1 dfs(root.left,index+1) dfs(root.right,index+1)dfs(root,1) return res:-1【两数相加】给出两个 空 的链表来表两个负的整数。其中，它们各的位数是按照 逆序 的式存储的，并且它们的每个节点只能存储 位 数字。如果，我们将这两个数相加起来，则会返回个新的链表来表它们的和。 您可以假设除了数字 0 之外，

12、这两个数都不会以 0 开头。# Definition for singly-linked list. # class ListNode:#def _init_(self, x):#self.val = x#self.next = Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode:# 创建个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 来最后返回, p 来遍历dummy = p = ListNode(None)s = 0# 初始化进位 s 为 0 wh

13、ile l1 or l2 or s:# 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下有进位1, 下次加上) s += (l1.val if l1 else 0) + (l2.val if l2 else 0)p.next = ListNode(s % 10)# p.next 指向新链表, 来创建个新的链表p = p.next# p 向后遍历s /= 10# 有进位情况则取模, eg. s = 18, 18 / 10 = 1 l1 = l1.next if l1 else None # 如果l1存在, 则向后遍历, 否则为 None l2 = l2.ne

14、xt if l2 else None # 如果l2存在, 则向后遍历, 否则为 Nonereturn dummy.next # 返回 dummy 的下个节点, 因为 dummy 指向的是空的头结点, 下个节点才是新建链表的后序节点【重复字符的最长串】给定个字符串，请你找出其中不含有重复字符的 最长串 的长度思路：这道题主要到思路是：滑动窗什么是滑动窗？其实就是个队列,如例题中的 abcabcbb，进这个队列（窗）为 abc 满题要求，当再进 a，队列变成了 abca，这时候不满要求。所以，我们如何移动？我们只要把队列的左边的元素移出就了，直到满题要求！直维持这样的队列，找出队列出现最长的长度时

15、候，求出解！ 时间复杂度：O(n)O(n)class Solution:def lengthOfLongestSubstring(self, s: str) - int: if not s:return 0left = 0 lookup = set() n = len(s) max_len = 0cur_len = 0for i in range(n): cur_len += 1while si in lookup: lookup.remove(sleft) left += 1cur_len -= 1if cur_len max_len:max_len = cur_len lookup.add

16、(si)return max_len【前k个频元素】给定个空的整数数组，返回其中出现频率前 k 的元素。提：你可以假设给定的 k 总是合理的，且 1 k 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的。题数据保证答案唯，换句话说，数组中前 k 个频元素的集合是唯的。你可以按任意顺序返回答案。先利哈希表，再对字典排序。class Solution:def topKFrequent(self, nums, k): Hash = for i in nums:Hashi = Hash.get(i, 0) + 1keyvalues = sorted(Has

17、h.items(), key = lambda x: (x1, x0), reverse=True) return keyvaluesj0 for j in range(k)【组合】给定两个整数 n 和 k，返回 1 . n 中所有可能的 k 个数的组合。回溯算法 剪枝class Solution:def combine(self, n, k): all_combination=def backtracking(remain_selection,unfinished_count,prefix): if unfinished_count=0:all_combination.append(pref

18、ix:) tmp_length=len(remain_selection) for i in range(tmp_length):#此处代码优化可以显著提运的效率if unfinished_count=tmp_length-i+1: backtracking(remain_selectioni+1:,unfinished_count-1,prefix+remain_selectioni)else:breakif nk or n=0 or k=0: return backtracking(i for i in range(1,n+1),k,) return all_combination【组合总

19、和】给定个重复元素的数组 candidates 和个标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。回溯算法from typing import Listclass Solution:def combinationSum(self, candidates, target):def dfs(candidates, begin, size, path, res, target): if target 0:returnif targe

20、t = 0: res.append(path) returnfor index in range(begin, size):dfs(candidates, index, size, path + candidatesindex, res, target - candidatesindex)size = len(candidates) if size = 0:return path = res = dfs(candidates, 0, size, path, res, target) return res剪枝提速from typing import Listclass Solution:def

21、combinationSum(self, candidates, target):def dfs(candidates, begin, size, path, res, target): if target = 0:res.append(path) returnfor index in range(begin, size): residue = target - candidatesindex if residue 0:breakdfs(candidates, index, size, path + candidatesindex, res, residue) size = len(candi

22、dates)if size = 0: return candidates.sort() path = res = dfs(candidates, 0, size, path, res, target) return res【寻找两个正序数组的中位数】给定两个为 m 和 n 的正序（从到）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n)。你可以假设 nums1 和 nums2 不会同时为空。解题思路length=m+n 如果是奇数中间值的下标就是 length/2,偶数就是 mid=length/2, 也就是mid-1和mid

23、的下标所对应的值/2 2.i,j 分别对应两个数组对应的下标，将的值插到new_Arry3.当new_Arry的长度等于mid的时候就停循环。class Solution(object):def findMedianSortedArrays(self, nums1, nums2): :type nums1: Listint:type nums2: Listint:rtype: float res = 0.0 new_array = m = len(nums1) n = len(nums2) length = m + n mid = 0if length & 1:mid = int(length

24、/2) else:mid = int(length/2) i,j = 0,0while len(new_array) -1 mid: if i m and j n :if nums1i = nums2j: new_array.append(nums2j) j+=1continueif i = m and j n:while j n and len(new_array) -1 mid: new_array.append(nums2j)j+=1if i m and j = n:while i m and len(new_array) -1 = len(s): breakif l = 0:dpij

25、= True elif l = 1:dpij = (si = sj) else:dpij = (dpi + 1j - 1 and si = sj) if dpij and l + 1 len(ans):ans = si:j+1 return ans【z字形变换】将个给定字符串根据给定的数，以从上往下、从左到右进 Z 字形排列。如输字符串为 LEETCODEISHIRING 数为 3 时，排列如下： L C I RE T O E S I I G E D H N之后，你的输出需要从左往右逐读取，产出个新的字符串，如：LCIRETOESIIGEDHN。请你实现这个将字符串进指定数变换的函数：stri

26、ng convert(string s, int numRows);class Solution:def convert(self, s, numRows): if numRows 2: return sres = for _ in range(numRows) i, flag = 0, -1for c in s: resi += cif i = 0 or i = numRows - 1: flag = -flag i += flagreturn .join(res)【整数反转】给出个 32 位的有符号整数，你需要将这个整数中每位上的数字进反转。注意: 假设我们的环境只能存储得下 32 位的有

27、符号整数，则其数值范围为 2*31, 2*31 1。请根据这个假设，如果反转后整数溢出那么就返回 0。class Solution(object): def reverse(self, x):type x: int:rtype: int if -10 x 10:return x str_x = str(x)if str_x0 != -: str_x = str_x:-1 x = int(str_x)else:str_x = str_x:0:-1 x = int(str_x)x = -xreturn x if -2147483648 x int:y, res = abs(x), 0# 则其数值范

28、围为 231, 231 1 boundry = (10 else 1 boundry :return 0 y /=10return res if x 0 else -res【字符串转换整数（ atoi）】请你来实现个 atoi 函数，使其能将字符串转换成整数。先，该函数会根据需要丢弃的开头空格字符，直到寻找到第个空格的字符为。接下来的转化规则如下：如果第个空字符为正或者负号时，则将该符号与之后尽可能多的连续数字字符组合起来，形成个有符号整数。 假如第个空字符是数字，则直接将其与之后连续的数字字符组合起来，形成个整数。该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它

29、们对函数不应该造成影响。注意：假如该字符串中的第个空格字符不是个有效整数字符、字符串为空或字符串仅包含空字符时，则你的函数不需要进转换， 即法进有效转换。在任何情况下，若函数不能进有效的转换时，请返回 0 。提：本题中的空字符只包括空格字符 。假设我们的环境只能存储 32 位的有符号整数，那么其数值范围为 2*31, 2*31 1。如果数值超过这个范围，请返回 INT_MAX (2*31 1) 或 INT_MIN (2*31) 。import reclass Solution:def myAtoi(self, str: str) - int: INT_MAX = 2147483647INT_M

30、IN = -2147483648str = str.lstrip()#清除左边多余的空格num_re = pile(r+-?d+) #设置正则规则num = num_re.findall(str) #查找匹配的内容num = int(*num) #由于返回的是个列表，解包并且转换成整数return max(min(num,INT_MAX),INT_MIN) #返回值：匹配字符串开头+-：代表个+字符或-字符?：前个字符可有可d：个数字+：前个字符的个或多个D：个数字字符*：前个字符的0个或多个简洁版本：class Solution:def myAtoi(self, s: str) - int:

31、return max(min(int(*re.findall(+-?d+, s.lstrip(), 2*31 - 1), -2*31)【回数】判断个整数是否是回数。回数是指正序（从左向右）和倒序（从右向左）读都是样的整数。class Solution(object):def isPalindrome(self, x): return str(x)=str(x):-1【正则表达式匹配】给你个字符串 s 和个字符规律 p，请你来实现个持 . 和 * 的正则表达式匹配。. 匹配任意单个字符* 匹配零个或多个前的那个元素所谓匹配，是要涵盖 整个 字符串 s的，不是部分字符串。说明:s 可能为空，且只包

32、含从 a-z 的写字母。p 可能为空，且只包含从 a-z 的写字母，以及字符 . 和 *思路先判断s和p的第个字符是否匹配处理p1为*号的情况：匹配0个或多个字符处理.号的情况：匹配个字符class Solution:def isMatch(self, s: str, p: str) - bool:if not p: return not s # 结束条件first_match = (len(s) 0) and p0 in s0, . # 先处理 *if len(p) =2 and p1 = *:# 匹配0个 | 多个return self.isMatch(s, p2:) or (first_

33、match and self.isMatch(s1:, p)# 处理 . ，匹配个return first_match and self.isMatch(s1:, p1:)【盛最多的容器】给你 n 个负整数 a1，a2，.，an，每个数代表坐标中的个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和(i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的。说明：你不能倾斜容器，且 n 的值少为 2。双指针class Solution:def maxArea(self, height: Listint) - int: l, r

34、= 0, len(height) - 1ans = 0 while l r:area = min(heightl, heightr) * (r - l) ans = max(ans, area)if heightl = heightr: l += 1else:r -= 1return ans【整数转罗马数字】罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符数值I1V5X10L50C100D500M1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下

35、，罗马数字中的数字在的数字的右边。但也存在特例，例如 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 到 3999 的范围内。贪算法class Solution:def intToRoman(se

36、lf, num):# 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中# 并且按照阿拉伯数字的降序排列，这是贪选择思想nums = 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1romans = M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, Iindex = 0 res = while index = numsindex:res += romansindex num -= numsindexindex += 1 return res【罗马数字转整数】罗马数字包含以下七种字符: I，

37、 V， X， L，C，D 和 M。字符数值I1V5X10L50C100D500M1000例如， 罗马数字 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

38、) 的左边，来表 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表 400 和 900。给定个罗马数字，将其转换成整数。输确保在 1 到 3999 的范围内。class Solution:def romanToInt(self, s):d = I:1, IV:3, V:5, IX:8, X:10, XL:30, L:50, XC:80, C:100, CD:300, D:500, CM:800, M:1000return sum(d.get(smax(i-1, 0):i+1, dn) for i, n in enumerate(s)【最长公共前缀】编写个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 。取个单词 s，和