1.统计字符串字符频次 (1) def count_seq(seq): result = {word: seq.count(word) for word in seq} return result seq = 'abcdfedhfvjxgfhsfhdgasdfcg' print(count_seq(seq)) (2) def count_seq(seq): result = {} for letter in seq: if letter not in result.keys(): result[letter] = 1 else: result[letter] += 1 return result if __name__ == "__main__": seq = "askjdhgfahdjfhfgsj" result = count_seq(seq) print(result) 2.用python删除文件和利用cmd命令行删除文件 import os os.remove(r'D: est-1 est.doc') import subprocess subprocess.Popen(r'del D: est-1 est.doc',shell= True) 3.自定义异常代码 def assert_value(num): if num > 100: raise ValueError("num can not bigger than 100") else: return 'num is available' assert_value(200)#ValueError: num can not bigger than 100 4.异常模块try except else finally相关意义 def div(a,b): c=0 try: #需要检测的代码 c = a/b except ZeroDivisionError as e: #发生异常需要处理的代码 print(e) else: #m没引发异常需要执行的代码 return c finally: #不管是否引发错误均要执行的代码 print(c) if __name__ == "__main__": div(1,0) 5.给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. #Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ curry = new = ListNode() a = 0 while l1 or l2: if l1 == None: x=0 else: x = l1.val l1 = l1.next if l2 == None: y = 0 else: y = l2.val l2 = l2.next sum = x + y + a a = sum // 10 b = sum % 10 curry.next = ListNode(b) curry = curry.next if a != 0: curry.next = ListNode(a) return new.next def add_node_to_listnode(a): """ :type a: iter :rtype: ListNode """ l1 = curry =ListNode() for item in a: l1.next = ListNode(item) l1 = l1.next return curry.next a = [1,4,5,6] b = [1,3,5,6] l1 = add_node_to_listnode(a) l2 = add_node_to_listnode(b) result = addTwoNumbers(l1,l2) 6.给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 法1： def reverse_int(x:int) -> int: min = pow(-2,31) max = pow(2,31) - 1 x = str(x) string_list = list(x) flag = False if x[0] == '-': flag = True print(flag) num1 = len(x) // 2 num2 = len(x) % 2 for i in range(num1): string_list[i],string_list[2*num1+num2-1-i] = string_list[2*num1+num2-1-i],string_list[i] if flag == True: temp = string_list.pop() print(temp) temp_string = ''.join(item for item in string_list if item != 0) new_string = temp + temp_string else: new_string = ''.join(item for item in string_list if item != 0) result = int(new_string) if result > max or result < min: return 0 return result x = -153 print(reverse_int(x)) 法2： def reverse_int(x:int) -> int: result = 0 flag = False if x < 0: flag = True x = abs(x) while(x != 0): result = result*10 + x%10 x = x // 10 if flag==True: result = -result if result > 2**31-1 or result < -2**31: return 0 return result 7.给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 法1： def lengthOfLongestSubstring(seq:str) ->int: length = len(seq) result = [] temp_string_list = [] temp = 1 i = 0 if length==0: return 0 while(i < length-1): if seq[i] != seq[i+1] and seq[i] not in temp_string_list and seq[i+1] not in temp_string_list: temp_string_list.append(seq[i]) temp += 1 i += 1 elif seq[i] == seq[i+1]: i += 1 result.append(temp) temp_string_list.append(seq[i]) temp_string_list =[] temp =1 continue else: result.append(temp) i = i-temp+2 temp_string_list = [] temp = 1 result.append(temp) return max(result) 法2： #窗口移动法 def lengthOfLongestSubstring(seq:str) ->int: temp_seq_dict = {} seq_length_list = [] sub_seq_head = -1 for i,value in enumerate(seq): if value in temp_seq_dict and temp_seq_dict[value] >= sub_seq_head:#判断当前字符是否在字典中，且上次出现的下标大于当前子序列的起始下标 if sub_seq_head == -1: # 第一次进入循环单独处理 sub_seq_long = i else: sub_seq_long = i - sub_seq_head reaped_head = temp_seq_dict[value] sub_seq_head = reaped_head +1 seq_length_list.append(sub_seq_long) temp_seq_dict[value] = i else: temp_seq_dict[value] = i if seq and sub_seq_head != -1:#head后无重复字符的子序列 seq_length_list.append(i-sub_seq_head+1) if not seq_length_list:#特殊情况：无重复字符或空字符 seq_length_list.append(len(seq)) print(seq_length_list) return max(seq_length_list) #seq = 'aabcdbwertyuiop' #seq = 'abcdfa' #seq = 'abfgcdchchijklmqwyx' #seq ="cccc" #seq = 'abcdecac' print(lengthOfLongestSubstring(seq)) 8.给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式的数目。 示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 #法1：回溯法 class Solution: def findTargetSumWays(self, nums: list, target: int) -> int: self.result = 0 self.buildTree(nums,0,0,target) return self.result def buildTree(self,nums: list, index: int, sum: int , target: int): length = len(nums) if index == length-1: if sum + nums[index] == target: self.result += 1 if sum - nums[index] == target: self.result +=1 return else: self.buildTree(nums, index+1, sum+nums[index],target) self.buildTree(nums, index + 1, sum - nums[index], target) a = [1,1,1,1,1] target = 3 solution = Solution() result = solution.findTargetSumWays(a,target) print(result) 回归遍历动态过程： index=0 +1 -1 index=1 index=1 +1 -1 index=2 index =2 +1 -1 index=3 index=3 +1 -1 index=4 index=4 +1 -1 +1+1+1+1+1 +1+1+1+1-1 idex3 +1 +1+1+1-1+1 +1+1+1-1-1 idex3 -1 +1+1-1+1+1 +1+1-1+1-1 index2 -1 +1+1-1-1+1 +1+1-1-1-1 +1-1+1+1+1 +1-1+1+1-1 index1 -1 +1-1+1-1+1 +1-1+1-1-1 +1-1-1+1+1 +1-1-1+1-1 +1-1-1-1+1 +1-1-1-1-1 -1+1+1+1+1 -1+1+1+1-1 idex3 -1 -1+1+1-1+1 -1+1+1-1-1 -1+1-1+1+1 -1+1-1+1-1 -1+1-1-1+1 -1+1-1-1-1 -1-1+1+1+1 -1-1+1+1-1 -1-1+1-1+1 -1-1+1-1-1 -1-1-1+1+1 -1-1-1+1-1 -1-1-1-1+1 -1-1-1-1-1 #法2 动态规划法 class Solution: def findTargetSumWays(self, nums: list, target: int) -> int: #设目标和为target的正数集和为x，负数绝对值和为y #x+y=sum(nums),x-y=target, ==>x= (sum(nums) + target)//2 y = (sum(nums) - target)//2 #问题转换为在列表nums中选取若干元素，使这些元素和等于x==>转换为01背包问题:每个物品只取一次，装满承重为x的背包的总方案数 #定义二维数组dp，其中dp[i][j]表示在数组nums的前i个数中选取元素，使得这些元素之和等于j的方案数。j表示目前的背包承重。 # 假设nums的长度为n，则最终答案为dp[n][j]，物品的下标从i=1开始，i=0，表示目前无元素可以，这样设置是避免递推式中下标i-1的问题 #dp[0][0]，表示当没有元素可取时，元素和只能是0，对应的方案数为1，因此动态规划的边界条件是： #当j=0时，dp[0][0] = 1 ，当j>0时，dp[0][j] = 0 #当i<=1<=n时，对于数组nums中的第i个元素num=nums[i-1]，遍历0 <= j <= x，计算dp[i][j]的值 #如果nums[i]>j，则不能选nums[i]，此时有dp[i][j] = dp[i-1][j] #如果nums[i]<=j，则如果不选nums[i]，方案数是dp[i][j] = dp[i-1][j]，如果选num[i]，此时有dp[i][j]=dp[i-1][j-nums[i]] #由于列表都是正数，也可以求和为y的子集数，这样内循坏量少一些 x = (sum(nums) - target)//2 n = len(nums) if (sum(nums) - target)%2 == 1:#x不可能为奇数 return 0 if sum(nums)< target:#列表里所有数加起来都小于target，则永远不可能有表达式结果为target return 0 ##可以让dp第一行除dp[0][0] =1外，其余存0，物品的下标从1开始，这样不用单独赋值第一行，循环时下标i-1也不会出错 dp = [[0]*(x+1) for i in range(n+1)] dp[0][0] = 1 for i in range(1,n+1): num = nums[i-1] for j in range(x + 1): if num > j: dp[i][j] = dp[i-1][j] if num <= j: dp[i][j] = dp[i-1][j] + dp[i-1][j-num] print(dp) return dp[n][x] a = [1,1,1,1,1] target = 3 solution = Solution() result = solution.findTargetSumWays(a,target) print(result) 由于dp的每一行的计算只和上一行有关，因此可以使用滚动数组的方式,去掉dp的第一个维度，将空间复杂度优化到 O(y)。 class Solution: def findTargetSumWays(self, nums: list, target: int) -> int: x = (sum(nums) + target)//2 if (sum(nums) + target)%2 == 1:#x不可能为奇数 return 0 if sum(nums)< target:#列表里所有数加起来都小于target，则永远不可能有表达式结果为target return 0 dp = [0]*(x+1) dp[0] = 1 for num in nums: j = x while(j>=0): if num <= j: dp[j] = dp[j] + dp[j - num]#当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数 if num > j: dp[j] = dp[j] j = j - 1 return dp[-1] nums=[1,1,1,1,1],target=3时，x = 4，动态规划二维数组如下： j 0, 1, 2, 3, 4 i 0 1 0 0 0 0 1 1 1 1 0 0 0 2 1 1 2 1 0 0 3 1 1 3 3 1 0 4 1 1 4 6 4 1 5 1 1 5 10 10 5 nums=[1,2,3,4,5] target = 3时，x = 9，动态规划二维数组如下： j 0, 1, 2, 3, 4 5 6 7 8 9 i 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 2 2 1 1 1 1 0 0 0 0 0 0 3 3 1 1 1 2 1 1 1 0 0 0 4 4 1 1 1 2 2 2 2 1 1 1 5 5 1 1 1 2 2 3 3 3 3 3 4+3 4+2+1 2.给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 #重复背包问题 class Solution: def change(self, amount: int, coins: list) -> int: n = len(coins) dp = [[0] * (amount + 1) for i in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1): coin = coins[i - 1] for j in range(amount + 1): if coin > j: dp[i][j] = dp[i - 1][j] if coin <= j: temp = j//coin#看背包最多能放几个coin for k in range(temp+1): dp[i][j] += dp[i-1][j-k*coin] print(dp) return dp[n][amount] #当coins = [1,2,5],amout=[5]时，动态规划数组如下 amout j 0 1 2 3 4 5 i=0 coin=0 1, 0, 0, 0, 0, 0 i=1 coin=1 1, 1, 1, 1, 1, 1 i=2 coin=2 1, 1, 2, 2, 3, 3 i=3 coin=5 1, 1, 2, 2, 3, 4 #降维写法 class Solution: def change(self, amount: int, coins: list) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: j = amount while (j >= 0): if coin > j: dp[j] = dp[j] if coin <= j: temp = j // coin for k in range(1,temp + 1): dp[j] = dp[j] + dp[j - k * coin] j = j - 1 print(dp) return dp[-1]
1.给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1： 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 示例 2： 输入：n = 13 输出：2 解释：13 = 4 + 9 #法1：BFS方法：使用队列保存未被检测的节点，节点按照宽度优先的次序被访问（即先遍历层次）和进出队列 因为是广度优先遍历，顺序遍历每一行，所以当节点差出现0时，此时一定是最短的路径。 如绿色所示，若此时节点为0，表示根节点可以由路径上的平方数{1,1,9}构成，返回此时的路径长度3，后续不在执行。 如红色所示，若节点值在之前已经出现，则不需要再计算，一定不会是最短路径，最短路径还未出现。 借助队列实现广度优先遍历（层次遍历） 1.初始化队列queue=[n]，访问元组visited={}，初试化路径长度step=0 2.循环条件，队列不为空 step+=1，因为循环一次，意味着一层中的节点已经遍历完，所以路径长度需要加一 定义当前层中的节点数l=len(queue)，遍历当前层的所有节点 令curry_num为队首元素,遍历所有可能数i的平方数，遍历区间[1,int(sqrt{tmp})+1)] 定义x=tmp-i**2 当x=tmp-i**2=0时，返回step 若x not in visited，表示当前节点未出现过：将该节点入队并在访问数组中加入。 3.当找到第一个curry_num = 0时，对应的路径是最短路径 class Solution: def numSquares(self, n: int) -> int: from collections import deque queue = deque([n]) step = 0 visited = set()#装遍历过的节点 while (queue): step += 1#循环一次，该层的节点已经遍历完一次，路径长度加1 length = len(queue) for i in range(length): curry_num = queue.pop() for j in range(1,int(curry_num**0.5)+1): x = curry_num - j**2 if x == 0: return step else: if x not in visited:#表明当前节点未出现过 queue.appendleft(x)#保证先进的先出 visited.add(x) return step #法2.重复背包->动态规划 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 2 0 1 2 3 1 2 3 4 2 3 3 0 1 2 3 1 2 3 4 2 1 dp[2,8] = min( dp[1,8] ,dp[1,4]+1,dp[1,0]+2) dp[2,9] = min( dp[1,9] ,dp[1,5]+1,dp[1,1]+2) #二维数组 class Solution: def numSquares(self, n: int) -> int: num_list = [i for i in range(1,int(n**(0.5)+1))] dp = [[0]*(n+1) for i in range(len(num_list)+1)] for j in range(1,n+1): dp[0][j] = j for i in range(1,len(num_list)+1): num = num_list[i-1] for j in range(n+1): if num**2 > j: dp[i][j] = dp[i-1][j] if num**2 <= j: temp = j k = 0 while(temp >= num**2): k = k + 1 temp = temp - num**2 dp[i][j] = min(dp[i-1][j],dp[i-1][temp]+k) print(dp) return dp[len(num_list)][n] #一维数组动态规划 class Solution: def numSquares(self, n: int) -> int: num_list = [i for i in range(1,int(n**(0.5)+1))] dp = [i for i in range(n+1)] for num in num_list: j = n while(j>=0): if num**2 > j: dp[j] = dp[j] if num**2<=j: temp = j k = 0 while(temp>=num**2): k= k+1 temp = temp - num**2 dp[j] = min(dp[j],dp[temp]+k) j = j-1 return dp[n] 2.给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 示例 1: 输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 示例 2: 输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 提示： 被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 法1：倍增法 class Solution: def divide(self, dividend: int, divisor: int) -> int: if dividend == 0 and divisor!=0: return 0 flag = 1 if dividend*divisor < 0: flag = -1 dividend = abs(dividend) divisor = abs(divisor) remain = dividend # 余数 result = 0 # 商 while (remain >= divisor): curry = 1 # 倍增商 div = divisor # 倍增值 while div + div < remain: curry += curry div += div remain -= div # 余数递减 result += curry # 商值累计 if flag < 0: result = -result if result < pow(-2, 31): result = pow(-2,31) if result > pow(2, 31)-1: result = pow(2, 31)-1 return result
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。 示例 1: 输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 输出：6 解释： 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的， 因为当拨动到 "0102" 时这个锁就会被锁定。 示例 2: 输入: deadends = ["8888"], target = "0009" 输出：1 解释： 把最后一位反向旋转一次即可 "0000" -> "0009"。 示例 3: 输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" 输出：-1 解释： 无法旋转到目标数字且不被锁定。 示例 4: 输入: deadends = ["0000"], target = "8888" 输出：-1 class Solution: def openLock(self, deadends: List[str], target: str) -> int: from typing import List from collections import deque if target == "0000": return 0 dead = set(deadends) if "0000" in dead: return -1 def num_prev(x: str) -> str: return "9" if x == "0" else str(int(x) - 1) def num_succ(x: str) -> str: return "0" if x == "9" else str(int(x) + 1) def get(status: str) -> List[str]: s = list(status) status_list = [] for i in range(4): num = s[i] s[i] = num_prev(num) status_list.append(''.join(s)) s[i] = num_succ(num) status_list.append(''.join(s)) s[i] = num return status_list q = deque([('0000',0)]) checked = {'0000'} while(q): status,step = q.popleft() next_status_list = get(status) for next_status in next_status_list: if next_status not in checked and next_status not in dead: if next_status == target: return step+1 q.append((next_status,step+1)) checked.add(next_status) return -1 deadends = ["8888"] target = "0009" solution = Solution() result = solution.openLock(deadends,target) print(result)
1.三数之和 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 示例 2： 输入：nums = [] 输出：[] 示例 3： 输入：nums = [0] 输出：[] 提示： 0 <= nums.length <= 3000 -105 <= nums[i] <= 105 #法1：双指针 from typing import List class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: length = len(nums) if length < 3: return [] result = list(list()) nums_list = sorted(nums) print(nums_list) # 枚举 a for i in range(length-2): # 需要和上一次枚举的数不相同 if i > 0 and nums_list[i] == nums_list[i-1]: continue if nums_list[i] > 0: return result # b对应的指针初始 left = i+1 # c 对应的指针初始指向数组的最右端 right = length - 1 while(left < right): if nums_list[i] + nums_list[left] +nums_list[right] < 0: left = left + 1 elif nums_list[i] + nums_list[left] +nums_list[right] > 0: right = right -1 else: result.append([nums_list[i], nums_list[left],nums_list[right]]) while (left < right and nums_list[left] == nums_list[left + 1]): left = left + 1 while (left < right and nums_list[right] == nums_list[right - 1]): right = right - 1 left = left + 1 right = right - 1 return result #法2 暴力双重循环 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: length = len(nums) if length < 3: return [] result = list(list()) nums_list = sorted(nums) for i in range(length): if nums_list[i] > 0: return result if nums_list[i] in nums_list[:i]:#保证第一个加数唯一 continue target = -nums_list[i] cheacked_add_2 = [] for j in range(i+1,length): if nums_list[j] in cheacked_add_2: continue if target - nums_list[j] in nums_list[j+1:]: result.append([nums_list[i],nums_list[j],target-nums_list[j]]) cheacked_add_2.append(nums_list[j]) cheacked_add_2.append(target-nums_list[j]) return result 2.四数之和 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + 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 = [], target = 0 输出：[] 提示： 0 <= nums.length <= 200 -109 <= nums[i] <= 109 法1：双指针 nums_list = sorted(nums) print(nums_list) lentgh = len(nums) ans = list(list()) if lentgh < 4: return [] for i in range(lentgh-3): if i > 0 and nums_list[i] == nums_list[i-1]: continue if nums_list[i]+nums_list[i+1]+nums_list[i+2]+nums_list[i+3] > target: break for j in range(i+1,lentgh-2): target2 = target - nums_list[i] - nums_list[j] if j > i+1 and nums_list[j] == nums_list[j - 1]: continue if nums_list[i] + nums_list[j] + nums_list[j+1]+nums_list[j+2] > target: break left = j+1 right = lentgh-1 while(left < right): if nums_list[left] + nums_list[right] < target2: left = left + 1 elif nums_list[left] + nums_list[right] > target2: right = right - 1 else: ans.append([nums_list[i],nums_list[j],nums_list[left],nums_list[right]]) while(left < right and nums_list[left] == nums_list[left+1]): left = left + 1 while (left < right and nums_list[right] == nums_list[right-1]): right = right - 1 left = left + 1 right = right - 1 return ans
请实现两个函数，分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 示例： 输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5] from collections import deque # Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Codec: @staticmethod def serialize(root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "[]" ans = list() ans.append(str(root.val)) queue = deque([root]) while queue: node = queue.popleft() if node.val: if node.left: ans.append(str(node.left.val)) queue.append(node.left) else: ans.append('null') if node.right: ans.append(str(node.right.val)) queue.append(node.right) else: ans.append('null') ans_str = ','.join(ans) result = '[' + ans_str + ']' return result @staticmethod def deserialize(data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data == "[]": return data_list = data[1:-1].split(',') root = TreeNode(int(data_list[0])) queue = deque([root]) i = 1 while i < len(data_list): node = queue.popleft() if data_list[i] != 'null': node.left = TreeNode(int(data_list[i])) queue.append(node.left) i = i + 1 if data_list[i] != 'null': node.right = TreeNode(int(data_list[i])) queue.append(node.right) i = i + 1 return root data = "[1,2,3,null,null,4,5]" codec = Codec() root_node = codec.deserialize(data) result = codec.serialize(root_node) print(result)
1.给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。 示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2： 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5 示例 3： 输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000 示例 4： 输入：nums1 = [], nums2 = [1] 输出：1.00000 示例 5： 输入：nums1 = [2], nums2 = [] 输出：2.00000 提示： nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106 #双指针 class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n = len(nums1) m = len(nums2) k = (n+m+1) // 2 point_1 = 0 point_2 = 0 temp_list = [] if nums1 == [] or nums2 == []: num = nums1 + nums2 if (n+m) % 2 == 1: return num[k-1] else: return (num[k-1]+num[k]) / 2 while point_1 + point_2 <= k: if point_1 < n and point_2 < m: if nums1[point_1] <= nums2[point_2]: temp_list.append(nums1[point_1]) point_1 += 1 else: temp_list.append(nums2[point_2]) point_2 += 1 elif point_1 < n and point_2 == m: temp_list = temp_list + nums1[point_1:k-m+1] point_1 = k - m+1 elif point_1 == n and point_2 < m: temp_list = temp_list + nums2[point_2:k-point_1+1] point_2 = k - n + 1 print(temp_list) if (n + m) % 2 == 1: return temp_list[k-1] else: return (temp_list[k-1]+temp_list[k])/2 nums1 = [1,3] nums2 = [1,2] solution = Solution() result = solution.findMedianSortedArrays(nums1,nums2) print(result) 2.给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。 示例 1： 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 示例 2： 输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 提示： nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[i] <= 109 #双指针从左开始遍历 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ #数组1指针 point1 = 0 #数组2指针 point2 = 0 while point1 < m + n: if point2 < n and point1 < m + point2: if nums1[point1] <= nums2[point2]: point1 += 1 else: nums1.insert(point1,nums2[point2]) nums1.pop(-1) point2 += 1 point1 += 1 elif point2 < n and point1 >= m + point2: nums1[point1:] = nums2[point2:] point1 = m+n point2 = n elif point2 == n: break #双指针从右开始遍历 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ #数组1指针 point1 = m #数组2指针 point2 = n if m == 0: nums1[:] = nums2 while point2 >= 0 and point1 >= 0: if point1 > 0 and point2 > 0: if nums1[point1-1] <= nums2[point2-1]: nums1[point1+point2-1] = nums2[point2-1] point2 -= 1 else: nums1[point1+point2-1] = nums1[point1-1] point1 -= 1 elif point1 == 0 and point2 > 0: nums1[0:point2] = nums2[0:point2] break elif point2==0: break print(nums1)
1.给定一个化学式formula（作为字符串），返回每种原子的数量。 原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。 两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。 一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。 给定一个化学式 formula ，返回所有原子的数量。格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。 示例 1： 输入：formula = "H2O" 输出："H2O" 解释： 原子的数量是 {'H': 2, 'O': 1}。 示例 2： 输入：formula = "Mg(OH)2" 输出："H2MgO2" 解释： 原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。 示例 3： 输入：formula = "K4(ON(SO3)2)2" 输出："K4N2O14S4" 解释： 原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。 示例 4： 输入：formula = "Be32" 输出："Be32" #法1用队列:广度优先 class Solution: def countOfAtoms(self, formula: str) -> str: from collections import deque q = deque([(formula,1)])#将带括号的分子式及其数量存储于队列 atom_num = {}#存储原子及其数量 while q: string,num = q.popleft() length = len(string)#遍历每个队列的分子式 i = 0 while i < length: if string[i].isupper(): j = i + 1 while j < length and not string[j].isdigit() and string[j] != '(' and not string[j].isupper(): j = j+1 k = j #如果string最后一位是单个原子不带数量，K将与length同，需要单独处理，防止字符串下标溢出 if k == length: num1 = 1 else: #获取原子数量 if string[k].isdigit(): while k < length-1 and string[k+1].isdigit(): k = k + 1 if k == j: num1 = int(string[k]) else: num1 = int(string[j:k+1]) else: num1 = 1 #存储原子及其数量到atom_num 字典 if string[i:j] not in atom_num.keys(): atom_num[string[i:j]] = str(num1*num) else: atom_num[string[i:j]] = str(int(atom_num[string[i:j]]) + num1*num) i = k elif string[i] == '(': j = i+1 while string[i:j+1].count('(') != string[i:j+1].count(')'): j = j + 1 #获取分子数量 k = j + 1 #如果括号中的分子不带数量,将数量赋值为1，例如特殊形式如(H) if k == length: num2 = 1 else: #处理括号中分子在括号外有数量的情况 if string[k].isdigit(): while k < length - 1 and string[k + 1].isdigit(): k = k + 1 if k == j + 1: num2 = int(string[k]) else: num2 = int(string[j+1:k+1]) else: num2 = 1 #将分子及其数量以元组的形式存进队列 q.append((string[i+1:j],num*num2)) i = k else: i = i+1 result = '' for key in sorted(atom_num.keys()): if atom_num[key] == '1': result = result + key else: result = result + key + atom_num[key] return result
1.大餐是指恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。 你可以搭配任意两道餐品做一顿大餐。 给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。 示例 1： 输入：deliciousness = [1,3,5,7,9] 输出：4 解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。 它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。 示例 2： 输入：deliciousness = [1,1,1,3,3,3,7] 输出：15 解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。 提示： 1 <= deliciousness.length <= 105 0 <= deliciousness[i] <= 2**20 解析： 1.根据条件0 <= deliciousness[i] <= 2**20，可以知道所谓2的幂是有限的，即：target=[2**0, 2**1, 2**2, ..., 2**21],所以题目隐含的意思是，从数组中任选两个数，两数之和在上面的这个集合target中。 根据输入的deliciousness数组的最大值max_num，可以找到优化后的数组target的上线，为大于且最接近 2*max_num的2的幂。 可以表达为 max_i = int(math.log(2*max_num,2))，target = [2**i for i in range(max_i+1)] 2.统计数组，获取每一个数字出现的次数，得到一个次数字典hashmap，对于hashmap中的每一个数字x，遍历2的幂集合target，对于target中每一个值t，若t-x存在于hashmap中，则(x, t-x)符合题目要求。 如果 x = t - x,则表示两个加数相同，此时根据排列组合公式，餐品的组合数是 n*(n-2)/2，n为deliciousness中x的个数； 如果 x != t- x,则表示两个加数不同，此时根据排列组合公式，餐品的组合数是n*m， n和m分别代表deliciousness中 x 和 t-x的个数 3.遍历harshmap肯定会出现重复的记录，例如(1,3)和(3,1)，故当x 和 t-x不等时，(x,t-x)的大餐会重复计算，这部分组合方式数需要除以2，当x=t-x时，此时不会重复计算，因为hashmap里的数字x不会重复。 class Solution: def countPairs(self, deliciousness: List[int]) -> int: import math max_num = max(deliciousness) max_i = int(math.log(2*max_num,2)) target = [2**i for i in range(max_i+1)] hashmap = Counter(deliciousness) ans_same = 0 ans_diff = 0 for x in hashmap: for t in target: y = t - x if y in hashmap: if y == x: ans_same = ans_same + hashmap[x]*(hashmap[x] - 1) / 2 else: ans_diff = ans_diff + hashmap[x]*hashmap[y] ans = int(ans_same + ans_diff / 2) ans = ans % (10**9 + 7) print(ans) return ans
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。 子数组是数组的一段连续部分。 示例 1： 输入：nums = [1,0,1,0,1], goal = 2 输出：4 解释： 有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1] 示例 2： 输入：nums = [0,0,0,0,0], goal = 0 输出：15 提示： 1 <= nums.length <= 3 * 104 nums[i] 不是 0 就是 1 0 <= goal <= nums.length 一、暴力解法 class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: length = len(nums) ans = 0 for i in range(length): if nums[i] == goal: ans += 1 add_sum = nums[i] for j in range(i+1,length): add_sum = add_sum + nums[j] if add_sum == goal: ans = ans + 1 elif add_sum > goal: break print(ans) return ans 二、窗口移动 1.维持两个窗口：[left ... r1],[left ... r2] 2.窗口内累加和分别为sum1,sum2 3.r1、r2分别为以left为左端点且累加和等于goal的子数组右边界范围， 4.r2-r2即为以left为左边界满足条件的子数组个数 class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: length = len(nums) ans = left = r1 = r2 = sum1 = sum2 = 0 while left < length: if r1 < left: r1 = left if r2 < left: r2 = left while r1 < length and sum1 + nums[r1] < goal: sum1 += nums[r1] r1 += 1 while r2 < length and sum2 + nums[r2] <= goal: sum2 += nums[r2] r2 += 1 if left < r1: sum1 -= nums[left] sum2 -= nums[left] ans += r2 - r1 left += 1 return ans 三、hash法 1.题目需要找寻所有的子区间(i,j]，子区间满足nums[i+1] + ....nums[j]=goal ,记为Sum(i,j] = goal 2.如果区间[0,i] 和 区间[0,j]满足 Sum[0,j] - Sum[0,i] = goal，那么区间(i,j]就是符合要求的子区间 3.Sum[0,i]为前i个数的前缀和，记为presum(i),Sum[0,j]为前j个数的前缀和，记为presum[j],满足要求的 区间[i,j]的判断条件为presum[i] + goal = presum[j] 注意，为了能取到区间nums[0] + ...nums[j] = goal即Sum[i,j] = goal（包含nums首个数字）的子区间， 需要在前缀和列表中加入初始值[0] 4.因此题目转换为找满足条件Sum(i,j] = goal的所有左端点presum[i]个数总和或右端点presum[j]个数总和 5.如果是找满足条件的presum[j]的个数，由于对于区间[i,j]总有presum[i] <= presum[j]，故如果遍历前缀 和数组时，当前值作为区间左端点pre_l，那么需要先统计每个前缀和的次数存储于hashmap中，对应法1： 法1：需要先构造完整的hashmap字典 from typing import List class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: presum = 0 ans = 0 pre_sum = list() pre_sum.append(0)#预存0，是为了可以取到从nums第一位数开始和为goal的情况 for num in nums: presum += num pre_sum.append(presum) print(pre_sum) hashmap = Counter(pre_sum) for pre_l in pre_sum: pre_r = pre_l + goal if pre_r in hashmap: if goal != 0: ans += hashmap[pre_r] else: hashmap[pre_r] -= 1 ans += hashmap[pre_r] print(ans) return ans 6.如果是找满足条件的presum[i]的个数，由于对于区间[i,j]总有presum[i] <= presum[j]，故如果遍历前缀 和数组时，当前值作为区间左端点pre_r，那么不需要事前存储hashmap，实时更新即可，对应法2： 法2：动态更新hashmap from typing import List from collections import defaultdict class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: presum_cnt = defaultdict(int) presum_cnt[0] = 1 ans = 0 pre_r = 0 for x in nums: pre_r += x pre_l = pre_r - goal ans += presum_cnt[pre_l] presum_cnt[pre_r] += 1 return ans
给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 示例 3： 输入：s = "a" 输出："a" 示例 4： 输入：s = "ac" 输出："a" 1.暴力解法 class Solution: def longestPalindrome(self, s: str) -> str: if not s: return 0 n = len(s) i = 0 temp_long = 0 while i < n: j = i while j < n: sub_str = s[i:j+1] if sub_str == sub_str[::-1]: if j + 1 - i > temp_long: temp_long = j + 1 - i ans = sub_str j += 1 i += 1 return ans 2.滑动窗口 1）遍历s的每个字符，找出与以与首字符相同的所有子串，判断该子串是不是回文子串 2）因为回文子的首尾字符串肯定相等，以该条件去过滤子串 class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) left = 0 right = 1 temp_long = 0 if n == 1: return s ans = '' while left < n: while right < n: if s[right] != s[left]: right += 1 else: sub_str = s[left:right+1] if sub_str == sub_str[::-1]: if right - left + 1 > temp_long: temp_long = right - left + 1 ans = sub_str right += 1 left += 1 right = left + 1 if not ans: return s[0] return ans 3）状态转移 第 1 步：定义状态 dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。 第 2 步：思考状态 dp[i][j]为回文字的条件： j-1-(i+1)+1 >= 2时，即j-i >=3，s[i] = s[j]且dp[i+1][j-1]为回文字； j-i < 3时，s[i] = s[j]便为回文子 转移方程： dp[i][j] = Ture if dp[i+1][j-1]&&s[i] = s[j] j-i >=3 dp[i][j] = Ture if s[i] = s[j] j-i < 3 class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) #dp[i][j]表示s[i:j+1]是否是回文串 dp = [[False]*n for i in range(n)] if n < 2: return s # #单个字符肯定是回文串 # for i in range(n): # dp[i][i] = True ans = '' temp_long = 0 for j in range(n): for i in range(j): if j - i < 3: if s[i] == s[j]: dp[i][j] = True if j-i+1 > temp_long: temp_long = j-i+1 ans = s[i:j+1] else: if s[i] == s[j] and dp[i+1][j-1]: dp[i][j] = True if j-i+1 > temp_long: temp_long = j-i+1 ans = s[i:j+1] #只有单个字符是回文字 if not ans: return s[0] else: return ans
元素的频数是该元素在一个数组中出现的次数。 给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。 执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。 示例 1： 输入：nums = [1,2,4], k = 5 输出：3 解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。 4 是数组中最高频元素，频数是 3 。 示例 2： 输入：nums = [1,4,8,13], k = 5 输出：2 解释：存在多种最优解决方案： - 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。 - 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。 - 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。 示例 3： 输入：nums = [3,9,6], k = 2 输出：1 提示： 1 <= nums.length <= 105 1 <= nums[i] <= 105 1 <= k <= 105 法1：暴力双重循环 class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: n = len(nums) nums = sorted(nums) cur_step = 0 left = 0 ans = list() ans.append(1) while left < n: flag = False for i in range(left+1,n): cur_step = cur_step + (nums[i] - nums[i-1])*(i - left) if cur_step <= k: flag = True temp_ans = i - left + 1 else: break if flag == True: ans.append(temp_ans) cur_step = 0 left += 1 return max(ans) 法2：双指针去除重复计算 class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: n = len(nums) nums = sorted(nums) cur_step = 0 left = 0 right = 1 temp_ans = 1 while left < n-1 and right < n: flag = False#判断窗口右移一位后，temp_ans是否改变 for i in range(right,n): cur_step = cur_step + (nums[i] - nums[i-1])*(i - left) if cur_step <= k: flag = True if i - left + 1 > temp_ans: temp_ans = i - left + 1 else: break if flag: right = i cur_step = cur_step - (nums[right] - nums[left]) left += 1 right = right + 1 return temp_ans
>>待续