python3的各种经典案例，总共299个案例，直接可以运行（后：99个案例）

一. python3的各种经典案例，总共299个案例，直接可以运行（前：100个案例）

二. python3的各种经典案例，总共299个案例，直接可以运行（中：100个案例）

三. python3的各种经典案例，总共299个案例，直接可以运行（后：99个案例））

【例201】多米诺和三格骨牌铺瓦问题 难度等级★★
3.代码实现

class Solution:#参数N为整数#返回整数def numTilings(self, N):if N < 3:return NMOD = 1000000007f = [[0, 0, 0] for i in range(N + 1)]f[0][0] = f[1][0] = f[1][1] = f[1][2] = 1for i in range(2, N + 1):f[i][0] = (f[i - 1][0] + f[i - 2][0] + f[i - 2][1] + f[i - 2][2]) % MOD;f[i][1] = (f[i - 1][0] + f[i - 1][2]) % MOD;f[i][2] = (f[i - 1][0] + f[i - 1][1]) % MOD;return f[N][0]
if __name__ == '__main__':solution=Solution()inputnum=3print("输入为：",inputnum)print("输出为：",solution.numTilings(inputnum))

【例202】逃离幽灵 难度等级★★
3.代码实现

class Solution:#参数ghosts为数组#参数target为数组#返回布尔类型def escapeGhosts(self, ghosts, target):target_dist = abs(target[0]) + abs(target[1])for r, c in ghosts:ghost_target = abs(target[0] - r) + abs(target[1] - c)if ghost_target <= target_dist:return Falsereturn True
if __name__ == '__main__':solution=Solution()inputnum1=[[1, 0], [0, 3]]inputnum2=[0, 1]print("输入幽灵为：",inputnum1)print("输入目标为：",inputnum2)print("输出为：",solution.escapeGhosts(inputnum1,inputnum2))

【例203】寻找最便宜的航行旅途（最多经过k个中转站）难度等级★★
1.问题描述
有n个城市由航班连接，每个航班 (u,v,w)表示从城市u出发，到达城市v，价格为w。给定城市数目n，所有的航班flights。找到从起点src到终点站dst线路最便宜的价格，而旅途中最多只能中转K次。如果没有找到合适的线路，返回-1。
2.问题示例
输入n = 3，flights = [[0,1,100],[1,2,100],[0,2,500]]，src = 0，dst = 2，K = 0，输出500，即不中转的条件下，最便宜的价格为500。
3.代码实现

import sys
class Solution:#参数n为整数#参数flights为矩阵#参数src为整数#参数dst为整数#参数K为整数#返回整数def findCheapestPrice(self, n, flights, src, dst, K):distance = [sys.maxsize for i in range(n)]distance[src] = 0for i in range(0, K + 1):dN = list(distance)for u, v, c in flights:dN[v] = min(dN[v], distance[u] + c)distance = dNif distance[dst] != sys.maxsize:return distance[dst]else:return -1
if __name__ == '__main__':solution=Solution()n=3flights=[[0, 1, 100], [1, 2, 100], [0, 2, 500]]src=0dst=2K=0print("输入城市为：",n)print("输入航班为：",flights)print("输入出发地：",src)print("输入目的地：",dst)print("输入中转数：",K)print("输出价格为：",solution.findCheapestPrice(n, flights, src, dst, K))

4.运行结果
输入城市为：3
输入航班为：[[0, 1, 100], [1, 2, 100], [0, 2, 500]]
输入出发地：0
输入目的地：2
输入中转数：0
输出价格为：500
【例204】图是否可以被二分 难度等级★★
3.代码实现

class Solution:#参数graph为无向图#返回布尔类型def isBipartite(self, graph):n = len(graph)self.color = [0] * nfor i in range(n):if self.color[i] == 0 and not self.colored(i, graph, 1):return Falsereturn Truedef colored(self, now, graph, c):self.color[now] = cfor nxt in graph[now]:if self.color[nxt] == 0 and not self.colored(nxt, graph, -c):return Falseelif self.color[nxt] == self.color[now]:return Falsereturn True
if __name__ == '__main__':solution=Solution()inputnum=[[1,3],[0,2],[1,3],[0,2]]print("输入为：",inputnum)print("输出为：",solution.isBipartite(inputnum))

4.运行结果
输入为：[[1, 3], [0, 2], [1, 3], [0, 2]]
输出为：True
【例205】森林中的兔子 难度等级★★
3.代码实现

import math
class Solution:#参数answers为数组#返回整数def numRabbits(self, answers):hsh = {}for i in answers:if i + 1 in hsh:hsh[i + 1] += 1else:hsh[i + 1] = 1ans = 0for i in hsh:ans += math.ceil(hsh[i] / i) * ireturn ans
if __name__ == '__main__':solution=Solution()inputnum=[1,1,2]print("输入为：",inputnum)print("输出为：",solution.numRabbits(inputnum))

4.运行结果
输入为：[1, 1, 2]
输出为：5

【例206】最大分块排序 难度等级★★
3.代码实现

class Solution(object):def maxChunksToSorted(self, arr):def dfs(cur, localmax):visited[cur] = Truelocalmax = max(localmax, cur)if not visited[arr[cur]]:return dfs(arr[cur], localmax)return localmaxvisited = [False] * len(arr)count = 0i = 0while i < len(arr):localmax = dfs(i, -1)i += 1while i < localmax + 1:if not visited[i]:localmax = dfs(i, localmax)i += 1count += 1return count
if __name__ == '__main__':solution=Solution()arr = [1,0,2,3,4]print("输入为：",arr)print("输出为：",solution.maxChunksToSorted(arr))

4.运行结果
输入为：[1, 0, 2, 3, 4]
输出为：4
【例207】分割标签 难度等级★★
3.代码实现

class Solution(object):def partitionLabels(self, S):last = {c: i for i, c in enumerate(S)}right = left = 0ans = []for i, c in enumerate(S):right = max(right, last[c])if i == right:ans.append(i - left + 1)left = i + 1return ans
if __name__ == '__main__':solution=Solution()s = "ababcbacadefegdehijhklij"print("输入为：",s)print("输出为：",solution.partitionLabels(s))

4.运行结果
输入为：ababcbacadefegdehijhklij
输出为：[9, 7, 8]
【例208】网络延迟时间 难度等级★★
3.代码实现

class Solution:#参数times为数组#参数N为整数#参数K为整数#返回整数def networkDelayTime(self, times, N, K):INF = 0x3f3f3f3fG = [[INF for i in range(N + 1)] for j in range(N + 1)]for i in range(1, N + 1):G[i][i] = 0for i in range(0, len(times)):G[times[i][0]][times[i][1]] = times[i][2]dis = G[K][:]vis = [0] * (N + 1)for i in range(0, N - 1):Mini = INFp = Kfor j in range(1, N + 1):if vis[j] == 0 and dis[j] < Mini:Mini = dis[j]p = jvis[p] = 1for j in range(1, N + 1):if vis[j] == 0 and dis[j] > dis[p] + G[p][j]:dis[j] = dis[p] + G[p][j]ans = 0for i in range(1, N + 1):ans = max(ans, dis[i])if ans == INF:return -1return ans
if __name__ == '__main__':solution=Solution()times=[[2,1,1],[2,3,1],[3,4,1]]N=4K=2print("时间矩阵为：",times)print("网络大小为：",N)print("起始节点为：",K)print("最小花费为：",solution.networkDelayTime(times,N,K))

【例209】洪水填充 难度等级★★
3.代码实现

class Solution(object):def floodFill(self, image, sr, sc, newColor):rows, cols, orig_color = len(image), len(image[0]), image[sr][sc]def traverse(row, col):if (not (0 <= row < rows and 0 <= col < cols)) or image[row][col] != orig_color:returnimage[row][col] = newColor[traverse(row + x, col + y) for (x, y) in ((0, 1), (1, 0), (0, -1), (-1, 0))]if orig_color != newColor:traverse(sr, sc)return image
if __name__ == '__main__':solution=Solution()image = [[1,1,1],[1,1,0],[1,0,1]]sr = 1sc = 1newColor = 2print("输入图像为：",image)print("输入坐标为： [",sr,",",sc,"]")print("输入颜色为：",newColor)print("输出图像为：",(solution.floodFill(image,sr,sc,newColor)))

【例210】映射配对之和 难度等级★★
3.代码实现

class TrieNode:def __init__(self):self.son = {}self.val = 0
class Trie:root = TrieNode()def insert(self, s, val):cur = self.rootfor i in range(0, len(s)):if s[i] not in cur.son:cur.son[s[i]] = TrieNode()cur = cur.son[s[i]]cur.val += valdef find(self, s):cur = self.rootfor i in range(0, len(s)):if s[i] not in cur.son:return 0cur = cur.son[s[i]]return cur.val
class MapSum:def __init__(self):self.d = {}self.trie = Trie()def insert(self, key, val):#参数key为字符串#参数val为整数#无返回值if key in self.d:self.trie.insert(key, val - self.d[key])else:self.trie.insert(key, val)self.d[key] = valdef sum(self, prefix):#参数prefix为字符串#返回整型return self.trie.find(prefix)
if __name__ == '__main__':mapsum=MapSum()print("插入方法：")print(mapsum.insert("apple", 3))print("求和方法：")print(mapsum.sum("ap"))print("插入方法：")print(mapsum.insert("app", 2))print("求和方法：")print(mapsum.sum("ap"))

4.运行结果
插入方法：None
求和方法：3
插入方法：None
求和方法：5
【例211】最长升序子序列的个数 难度等级★★
3.代码实现

import collections
class Solution(object):def findNumberOfLIS(self, nums):ans = [0, 0]l = len(nums)dp = collections.defaultdict(list)for i in range(l):dp[i] = [1, 1]for i in range(l):for j in range(i):if nums[i] > nums[j]:if dp[j][0] + 1 > dp[i][0]:dp[i] = [dp[j][0] + 1, dp[j][1]]elif dp[j][0] + 1 == dp[i][0]:dp[i] = [dp[i][0], dp[i][1] + dp[j][1]]for i in dp.keys():if dp[i][0] > ans[0]:ans = [dp[i][0], dp[i][1]]elif dp[i][0] == ans[0]:ans = [dp[i][0], ans[1] + dp[i][1]]return ans[1]
if __name__ == '__main__':solution=Solution()nums=[1,3,5,4,7]print("输入为：",nums)print("输出为：",solution.findNumberOfLIS(nums))

【例212】最大的交换 难度等级★★
3.代码实现

class Solution:def maximumSwap(self, num):res, num = num, list(str(num))for i in range(len(num) - 1):for j in range(i + 1, len(num)):if int(num[j]) > int(num[i]):tmp = int("".join(num[:i] + [num[j]] + num[i + 1:j] + [num[i]] + num[j + 1:]))res = max(res, tmp)return res
if __name__ == '__main__':solution=Solution()num=2736print("输入为：",num)print("输出为：",solution.maximumSwap(num))

【例213】将数组拆分成含有连续元素的子序列 难度等级★★
3.代码实现

class Solution:#参数nums为整数列表#返回布尔类型def isPossible(self, nums):cnt, tail = {}, {}for num in nums:cnt[num] = cnt[num] + 1 if num in cnt else 1for num in nums:if not num in cnt or cnt[num] < 1:continueif num - 1 in tail and tail[num - 1] > 0:tail[num - 1] -= 1tail[num] = tail[num] + 1 if num in tail else 1elif num + 1 in cnt and cnt[num + 1] > 0 and num + 2 in cnt and cnt[num + 2] > 0:cnt[num + 1] -= 1cnt[num + 2] -= 1tail[num + 2] = tail[num + 2] + 1 if num + 2 in tail else 1else:return Falsecnt[num] -= 1return True
if __name__ == '__main__':solution=Solution()nums=[1,2,3,3,4,5]print("输入为：",nums)print("输出为：",solution.isPossible(nums))

【例214】Dota2参议院 难度等级★★
3.代码实现

from collections import deque
class Solution():def predictPartyVictory(self,senate):senate = deque(senate)while True:try:thisGuy = senate.popleft()if thisGuy == 'R':senate.remove('D')else:senate.remove('R')senate.append(thisGuy)except:return 'Radiant' if thisGuy == 'R' else 'Dire'
if __name__ == '__main__':solution=Solution()senate="RD"print("输入为：",senate)print("输出为：",solution.predictPartyVictory(senate))

【例215】合法的三角数 难度等级★★
3.代码实现

class Solution:#参数nums为数组#返回整数def triangleNumber(self, nums):nums = sorted(nums)total = 0for i in range(len(nums)-2):if nums[i] == 0:continueend = i + 2for j in range(i+1, len(nums)-1):while end < len(nums) and nums[end] < (nums[i] + nums[j]):end += 1total += end - j - 1return total
if __name__ == '__main__':solution = Solution()nums=[2,2,3,4]print("输入为：",nums)print("输出为：",solution.triangleNumber(nums))

【例216】在系统中找到重复文件 难度等级★★
3.代码实现

import collections
class Solution:def findDuplicate(self, paths):dic = collections.defaultdict(list)for path in paths:root, *f = path.split(" ")for file in f:txt, content = file.split("(")dic[content] += root + "/" + txt,return [dic[key] for key in dic if len(dic[key]) > 1]
if __name__ == '__main__':paths=["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]solution=Solution()print("输入为：",paths)
print("输出为：",solution.findDuplicate(paths))

【例217】两个字符串的删除操作 难度等级★★
3.代码实现

class Solution:#word1为字符串#参数word2为字符串#返回整数def minDistance(self, word1, word2):m, n = len(word1), len(word2)dp = [[0] * (n + 1) for i in range(m + 1)]for i in range(m):for j in range(n):dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + (word1[i] == word2[j]))return m + n - 2 * dp[m][n]
if __name__ == '__main__':solution=Solution()word1="sea"word2="eat"print("输入1为：",word1)print("输入2为：",word2)
print("输出为：",solution.minDistance(word1,word2))

【例218】下一个更大的元素 难度等级★★
3.代码实现

class Solution:#n为整数#返回整数def nextGreaterElement(self, n):n_array = list(map(int, list(str(n))))if len(n_array) <= 1:return -1if len(n_array) == 2:if n_array[0] < n_array[1]:return int("".join(map(str, n_array[::-1])))else:return -1if n_array[-2] < n_array[-1]:n_array[-2], n_array[-1] = n_array[-1], n_array[-2]new_n = int("".join(map(str, n_array)))else:i = len(n_array) - 1while i > 0 and n_array[i - 1] >= n_array[i]:i -= 1if i == 0:return -1else:new_array = n_array[:i - 1]for j in range(len(n_array) - 1, i - 1, -1):if n_array[j] > n_array[i - 1]:breaknew_array.append(n_array[j])n_array[j] = n_array[i - 1]new_array.extend(reversed(n_array[i:]))new_n = int("".join(map(str, new_array)))return new_n if new_n <= 2 ** 31 else -1
if __name__ == '__main__':solution = Solution()n=123print("输入为：",n)print("输出为：",solution.nextGreaterElement(n))

【例219】最优除法 难度等级★★
3.代码实现

class Solution(object):def optimalDivision(self, nums):joinDivision = lambda l: '/'.join(list(map(str,l)))if len(nums) == 1: return str(nums[0])if len(nums) == 2: return joinDivision(nums)return str(nums[0]) if len(nums) == 1 else str(nums[0]) + '/(' + joinDivision(nums[1:]) +')'
if __name__ == '__main__':nums=[1000,100,10,2]solution=Solution()print("输入为：",nums)
print("输出为：",solution.optimalDivision(nums))

【例220】通过删除字母匹配到字典里最长单词 难度等级★★
3.代码实现

class Solution:#参数s为字符串#参数d为列表#返回字符串def findLongestWord(self, s, d):for x in sorted(d, key=lambda x: (-len(x), x)):it = iter(s)if all(c in it for c in x):return xreturn ''
if __name__ == '__main__':s = "abpcplea"d = ["ale", "apple", "monkey", "plea"]solution=Solution()print("输入为：",s)print("输入为：",d)print("输出为：",solution.findLongestWord(s,d))

【例221】寻找树中最左下结点的值 难度等级★★
3.代码实现

class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
class Solution:#参数root为二叉树根#返回整数def findBottomLeftValue(self, root):self.max_level = 0self.val = Noneself.helper(root, 1)return self.valdef helper(self, root, level):if not root: returnif level > self.max_level:self.max_level = levelself.val = root.valself.helper(root.left, level + 1)self.helper(root.right, level + 1)
if __name__ == '__main__':node=TreeNode(1)node.left=TreeNode(2)node.right=TreeNode(3)node.left.left=TreeNode(4)solution=Solution()print("输入为：[{1,2 3,4 # # #}")]print("输出为：",solution.findBottomLeftValue(node))

【例222】出现频率最高的子树和 难度等级★★
3.代码实现

import collections
class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
class Solution:def findFrequentTreeSum(self, root):#root为树根节点#返回列表if not root:return []counter = collections.Counter()def sumnode(node):if not node:return 0ret = node.valif node.left:ret += sumnode(node.left)if node.right:ret += sumnode(node.right)counter[ret] += 1return retsumnode(root)arr = []for k in counter:arr.append((k, counter[k]))arr.sort(key=lambda x: x[1], reverse=True)i = 0while i + 1 < len(arr) and arr[i + 1][1] == arr[0][1]:i += 1return [x[0] for x in arr[:i + 1]]
if __name__ == '__main__':node=TreeNode(5)node.right=TreeNode(-3)node.left=TreeNode(2)solution=Solution()print("输入为：{5，3 2}")print("输出为：",solution.findFrequentTreeSum(node))

【例223】寻找BST的modes 难度等级★★
3.代码实现

class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
class Solution:#参数root为根节点#返回整数def helper(self, root, cache):if root == None:returncache[root.val] += 1self.helper(root.left, cache)self.helper(root.right, cache)returndef findMode(self, root):from collections import defaultdictif root == None:return []cache = defaultdict(int)self.helper(root, cache)max_freq = max(cache.values())result = [k for k,v in cache.items() if v == max_freq]return result
#主函数
if __name__ == '__main__':T = TreeNode(1)T.left = NoneT2 = TreeNode(2)T.right = T2T3 = TreeNode(2)T2.left = T3s = Solution()print("输入为：[1,#,2,2]")print("输出为：",s.findMode(T))

【例224】对角线遍历 难度等级★★
3.代码实现

class Solution:#参数matrix为矩阵#返回整数列表def findDiagonalOrder(self, matrix):import collectionsresult = [ ]dd = collections.defaultdict(list)if not matrix:return resultfor i in range(0, len(matrix)):for j in range(0, len(matrix[0])):dd[i+j+1].append(matrix[i][j])for k, v in dd.items():if k%2==1: dd[k].reverse()result += dd[k]return result
#主函数
if __name__ == '__main__':m = [
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]s = Solution()print("输入为：",m)print("输出为：",s.findDiagonalOrder(m))

【例225】提莫攻击 难度等级★★
3.代码实现

class Solution:#参数timeSeries为整数数组#参数duration为整数#返回整数def findPoisonedDuration(self, timeSeries, duration):ans = duration * len(timeSeries)for i in range(1,len(timeSeries)):ans -= max(0, duration - (timeSeries[i] - timeSeries[i-1]))return ans
#主函数
if __name__ == '__main__':s = Solution()time =2timws = [1,4]print("输入攻击序列：",timws)print("输入持续时间：",time)print("输出中毒时间：",s.findPoisonedDuration(timws,time))

【例226】目标和 难度等级★★
3.代码实现

class Solution(object):def findTargetSumWays(self, nums, S):if not nums:return 0dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0: 2}for i in range(1, len(nums)):tdic = {}for d in dic:tdic[d + nums[i]] = tdic.get(d + nums[i], 0) + dic.get(d, 0)tdic[d - nums[i]] = tdic.get(d - nums[i], 0) + dic.get(d, 0)dic = tdicreturn dic.get(S, 0)
#主函数
if __name__ == '__main__':s = Solution()time =3timws = [1,1,1,1,1]print("输入目标值：",time)print("输入序列值：",timws)print("输出方法为：",s.findTargetSumWays(timws,time))

【例227】升序子序列 难度等级★★
3.代码实现

class Solution(object):def findSubsequences(self, nums):#参数nums为列表#返回列表res = []self.subsets(nums, 0, [], res)return resdef subsets(self, nums, index, temp, res):if len(nums) >= index and len(temp) >= 2:res.append(temp[:])used = {}for i in range(index, len(nums)):if len(temp) > 0 and temp[-1] > nums[i]: continueif nums[i] in used: continueused[nums[i]] = Truetemp.append(nums[i])self.subsets(nums, i+1, temp, res)temp.pop()
#主函数
if __name__ == '__main__':s = Solution()series =[4,6,7,7]print("输入序列为：",series)print("输出序列为：",s.findSubsequences(series))

【例228】神奇字符串 难度等级★★
3.代码实现

class Solution(object):def magicalString(self, n):#参数n为整数#返回整数if n == 0:return 0elif n <= 3:return 1else:so_far, grp, ones =[1,2,2], 2, 1while len(so_far) < n:freq, item = so_far[grp], 1 if grp % 2 == 0 else 2for _ in range(freq):so_far.append(item)ones, grp = ones + freq if item == 1 else ones, grp + 1if len(so_far) == n:return oneselse:return ones-1 if so_far[-1] == 1 else ones
#主函数
if __name__ == '__main__':s = Solution()n = 6print("输入为：",n)print("输出为：",s.magicalString(n))

【例229】爆破气球的最小箭头数 难度等级★★
3.代码实现

class Solution(object):def findMinArrowShots(self, points):#参数points为整数列表#返回整数if points == None or not points:return 0points.sort(key = lambda x : x[1]);ans = 1lastEnd = points[0][1]for i in range(1, len(points)):if points[i][0] > lastEnd:ans += 1lastEnd = points[i][1]return ans
#主函数
if __name__ == '__main__':s = Solution()n = [[10,16], [2,8], [1,6], [7,12]]print("输入为：",n)print("输出为：",s.findMinArrowShots(n))

【例230】查找数组中的所有重复项 难度等级★★
3.代码实现

class Solution:#参数nums为整数列表#返回整数列表def findDuplicates(self, nums):if not nums:return []duplicates = []    for each in range(len(nums)):index = nums[each]if index<0:index = -indexif nums[index-1]>0:nums[index-1]=-nums[index-1]else:duplicates.append(index)return duplicates
#主函数
if __name__ == '__main__':s = Solution()n = [4,3,2,7,8,2,3,1]print("输入为：",n)print("输出为：",s.findDuplicates(n))

【例231】最小基因变化 难度等级★★
3.代码实现

from collections import deque
class Solution:#参数start为字符串#参数end为字符串 #参数bank为字符串 #返回整数def minMutation(self, start, end, bank):if not bank:return -1bank = set(bank)h = deque()h.append((start, 0))while h:seq, step = h.popleft()if seq == end:return stepfor c in "ACGT":for i in range(len(seq)):new_seq = seq[:i] + c + seq[i + 1:]if new_seq in bank:h.append((new_seq, step + 1))bank.remove(new_seq)return -1
#主函数
if __name__ == '__main__':s = Solution()n ="AACCGGTT"m= "AACCGGTA"p=["AACCGGTA"]print("输入起点为：",n)print("输入终点为：",m)print("输入的库为：",p)print("输出步数为：",s.minMutation(n,m,p))

【例232】替换后的最长重复字符 难度等级★★
3.代码实现

from collections import defaultdict
class Solution:#参数s为字符串#参数k为整数#返回整数def characterReplacement(self, s, k):n = len(s)char2count = defaultdict(int)maxLen = 0start = 0for end in range(n):char2count[s[end]] += 1while end - start + 1 - char2count[s[start]] > k:char2count[s[start]] -= 1start += 1maxLen = max(maxLen, end - start + 1)return maxLen
#主函数
if __name__ == '__main__':s = Solution()n ="ABAB"m=2print("输入字符串为：",n)print("输入重复次数：",m)print("输出子串长度：",s.characterReplacement(n,m))

【例233】从英文中重建数字 难度等级★★
3.代码实现

class Solution:#参数s为字符串#返回字符串def originalDigits(self, s):nums = [0 for x in range(10)]nums[0] = s.count('z')nums[2] = s.count('w')nums[4] = s.count('u')nums[6] = s.count('x')nums[8] = s.count('g')nums[3] = s.count('h') - nums[8]nums[7] = s.count('s') - nums[6]nums[5] = s.count('v') - nums[7]nums[1] = s.count('o') - nums[0] - nums[2] - nums[4]nums[9] = (s.count('n') - nums[1] - nums[7]) // 2result = ""for x in range(10):result += str(x) * nums[x]return result
#主函数
if __name__ == '__main__':s = Solution()n ="owoztneoer"print("输入为：",n)print("输出为：",s.originalDigits(n))

【例234】数组中两个数字的最大异或 难度等级★★
3.代码实现

class TrieNode:def __init__(self,val):self.val = valself.children = {}
class Solution:#参数nums为整数: #返回整数def findMaximumXOR(self, nums):answer = 0for i in range(32)[::-1]:answer <<= 1prefixes = {num >> i for num in nums}answer += any(answer^1 ^ p in prefixes for p in prefixes)return answerdef findMaximumXOR_TLE(self, nums):root = TrieNode(0)for num in nums:self.addNode(root, num)res = -sys.maxsizefor num in nums:cur_node, cur_sum = root, 0for i in reversed(range(0,32)):bit = (num >> i) & 1if (bit^1) in cur_node.children:cur_sum += 1 << icur_node = cur_node.children[bit^1]else:cur_node = cur_node.children[bit]res = max(res, cur_sum)return resdef addNode(self, root, num):cur = rootfor i in reversed(range(0,32)):bit = (num >> i) & 1if bit not in cur.children:cur.children[bit] = TrieNode(bit)cur = cur.children[bit]
#主函数
if __name__ == '__main__':s = Solution()n =[3, 10, 5, 25, 2, 8]print("输入为：",n)print("输出为：",s.findMaximumXOR(n))

【例235】根据身高重排队列 难度等级★★
3.代码实现

class Solution:"""参数people为整数列表返回整数列表"""def reconstructQueue(self, people):queue = []for person in sorted(people, key = lambda _: (-_[0], _[1])): queue.insert(person[1], person)return queue
#主函数
if __name__ == '__main__':s = Solution()n =[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]print("输入为：",n)print("输出为：",s.reconstructQueue(n))

【例236】左叶子的和 难度等级★★
3.代码实现

class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
class Solution(object):def sumOfLeftLeaves(self, root):"""参数root为二叉树根返回整数"""def dfs(root):if not root:return 0sum = 0if root.left:left = root.left;#当前节点的左子节点,并判断是否为叶子节点if not left.left and not left.right:sum += left.val;else :sum += dfs(left)if root.right:right = root.rightsum += dfs(right)return sumreturn dfs(root)
#主函数
if __name__ == '__main__':s = Solution()t = TreeNode(3)t1 = TreeNode(9)t.left = t1t2 = TreeNode(20)t.right = t2t3 = TreeNode(15)t2.left = t3t4 = TreeNode(7)t2.right = t4print("输入为：[3,9 20,# # 15 7]")print("输出为：",s.sumOfLeftLeaves(t))

【例237】移除K位 难度等级★★
3.代码实现

class Solution:"""参数num为字符串参数k为整数返回字符串"""def removeKdigits(self, num, k):if k == 0:return numif k >= len(num):return "0"result_list = []for i in range(len(num)):while len(result_list) > 0 and k > 0 and result_list[-1] > num[i]:result_list.pop()k -= 1 if num[i] != '0' or len(result_list) > 0 :result_list.append(num[i])while len(result_list) > 0 and k > 0:result_list.pop()k -= 1 if len(result_list) == 0:return '0'return ''.join(result_list)
#主函数
if __name__ == '__main__':s = Solution()n = "1432219"k = 3print("输入数字为：",n)print("输入移除数：",k)print("输出为：",s.removeKdigits(n,k))

【例238】轮转函数 难度等级★★
3.代码实现

class Solution:"""参数A数组返回整数"""def maxRotateFunction(self, A):s = sum(A)curr = sum(i*a for i, a in enumerate(A))maxVal = currfor i in range(1, len(A)):curr += s - len(A)*A[-i]maxVal = max(maxVal, curr)return maxVal
#主函数
if __name__ == '__main__':s = Solution()n = [4,3,2,6]print("输入为：",n)print("输出为：",s.maxRotateFunction(n))

【例239】字符至少出现K次的最长子串 难度等级★★
3.代码实现

class Solution:"""参数s为字符串参数k为整数返回整数"""def longestSubstring(self, s, k):for c in set(s):if s.count(c) < k:return max(self.longestSubstring(t, k) for t in s.split(c))return len(s)
#主函数
if __name__ == '__main__':s = Solution()n = "aaabb"k = 3print("输入字符串为：",n)print("输入重复次数：",k)print("输出子串长度：",s.longestSubstring(n,k))

【例240】消除游戏 难度等级★★
3.代码实现

class Solution:"""参数n为整数返回整数"""def lastRemaining(self, n):return 1 if n == 1 else 2 * (1 + n // 2 - self.lastRemaining(n // 2))
#主函数
if __name__ == '__main__':s = Solution()n = 9print("输入为：",n)print("输出为：",s.lastRemaining(n))

【例241】有序矩阵中的第K小元素 难度等级★★
3.代码实现

class Solution:"""参数matrix为整数列表参数k为整数返回整数"""def kthSmallest(self, matrix, k):start = matrix[0][0] end = matrix[-1][-1]while start + 1 < end:mid = start + (end - start) // 2 if self.get_num_less_equal(matrix, mid) < k:start = mid else:end = mid if self.get_num_less_equal(matrix, start) >= k:return startreturn end         def get_num_less_equal(self, matrix, mid):m = len(matrix)n = len(matrix[0])i = 0 j = n - 1count = 0while i < m and j >= 0:if matrix[i][j] <= mid:i += 1 count += j + 1 else:j -= 1 return count
#主函数
if __name__ == '__main__':s = Solution()n=[[ 1,  5,  9],[10, 11, 13],[12, 13, 15]]k=8print("输入数组为：",n)print("输入顺序为：",k)print("输出数字为：",s.kthSmallest(n,k))

【例242】超级幂次 难度等级★★
3.代码实现

class Solution:"""参数a为整数: the given number a参数b为数组返回整数"""def superPow(self, a, b):if a == 0:return 0ans = 1def mod(x):return x % 1337for num in b:ans = mod(mod(ans ** 10) * mod(a ** num))return ans
#主函数
if __name__ == '__main__':s = Solution()n=2k=[3]print("输入a=：",n)print("输入b=：",k)print("输出为：",s.superPow(n,k))

【例243】水罐问题 难度等级★★
3.代码实现

class Solution:"""参数x为整数参数y为整数参数z为整数返回布尔类型"""def canMeasureWater(self, x, y, z):if x+y < z:return Falsereturn z % self.gcd(x,y) == 0def gcd(self, x, y):if y == 0:return xreturn self.gcd(y, x%y)
#主函数
if __name__ == '__main__':s = Solution()x = 3y = 5z = 4print("输入x=：",x)print("输入y=：",y)print("输入z=：",z)print("输出为：",s.canMeasureWater(x,y,z))

【例244】计算不同数字整数的个数 难度等级★★
3.代码实现

class Solution:"""参数n为整数返回整数"""def countNumbersWithUniqueDigits(self, n):if n == 0:return 1n = min(n, 10)dp = [0] * (n + 1)dp[0], dp[1] = 1, 9for i in range(2, n + 1):dp[i] = dp[i - 1] * (11 - i)return sum(dp)
#主函数
if __name__ == '__main__':s = Solution()x = 2print("输入为：",x)print("输出为：",s.countNumbersWithUniqueDigits(2))

4.运行结果
输入为：2
输出为：91
【例245】最大乘积路径 难度等级★★
3.代码实现

#参数x，y代表每条边的起始和终止
#参数d是每个节点的权重
#返回值是一个整数，是取模后节点最大乘积
class Solution:ans = 0def dfs(self, x, f, g, d, mul):isLeaf = Truemul = mul * d[x - 1] % 1000000007for i in g[x]:if i == f:continueisLeaf = Falseself.dfs(i, x, g, d, mul)if(isLeaf is True):self.ans = max(self.ans, mul)def getProduct(self, x, y, d):g = [ [] for i in range(len(d) + 1)]for i in range(len(x)):g[x[i]].append(y[i])g[y[i]].append(x[i])self.dfs(1, -1, g, d, 1)return self.ans
if __name__ == '__main__':x =[1,2,2]y = [2,3,4]d = [1,1,-1,2]solution = Solution()print(" 每个边的起始和终止为：", x, y)print(" 每个节点的权重为：", d)print(" 最大路径上的乘积是:", solution.getProduct(x, y, d))

【例246】矩阵找数 难度等级★★
3.代码实现

#参数mat是待查矩阵
#返回值是一个整数，是每一行都出现的最小的数字
class Solution:def findingNumber(self, mat):hashSet = {}n = len(mat)for mati in mat:vis = {}for x in mati:vis[x] = 1for key in vis:if key not in hashSet:hashSet[key] = 0hashSet[key] += 1ans = 100001for i in hashSet:if hashSet[i] == n:ans = min(i, ans)return -1 if ans == 100001 else ans
class Solution:def findingNumber(self, mat):hashSet = {}n = len(mat)for mati in mat:vis = {}for x in mati:vis[x] = 1for key in vis:if key not in hashSet:hashSet[key] = 0hashSet[key] += 1ans = 100001for i in hashSet:if hashSet[i] == n:ans = min(i, ans)return -1 if ans == 100001 else ans
if __name__ == '__main__':mat = [[1,2,3],[3,4,1],[2,1,3]]solution = Solution()print(" 矩阵为：", mat)print(" 每一行都出现的最小的数是：", solution.findingNumber(mat))

【例247】路径数计算 难度等级★★
3.代码实现

#参数points是除了始末点外的必经点
#参数l和w是长和宽
#返回值是一个整数，有多少种走法
class Point:def __init__(self, a=0, b=0):self.x = aself.y = b
class Solution:def calculationTheSumOfPath(self, l, w, points):points.sort(key = lambda point: point.x)if points[0].x != 1 or points[0].y != 1:points = [Point(1,1)] + pointsif points[0].x != l or points[0].y != w:points = points + [Point(l,w)]arr = [[] for i in range(len(points) - 1)]maxl = 0maxw = 0for i in range(1, len(points)):l = points[i].x - points[i - 1].xw = points[i].y - points[i - 1].yarr[i - 1] = [points[i].x - points[i - 1].x, points[i].y - points[i - 1].y]maxl = max(maxl, l)maxw = max(maxw, w)dp = [[0 for i in range(max(maxl, maxw) + 1)]for j in range(max(maxl, maxw) + 1)]del l, w, maxl, maxwfor i in range(len(dp)):for j in range(i, len(dp)):if i == 0:dp[j][i] = dp[i][j] = 1else:dp[j][i] = dp[i][j] = dp[i - 1][j] + dp[i][j - 1]ans = 1for i in arr:ans = ans * dp[i[0]][i[1]] % 1000000007return ans
if __name__ == '__main__':l=43w=48points = [Point(17,19), Point(43,48), Point(3,5)]solution = Solution()print(" 长与宽分别为：", l, w)print(" 有路径种数:", solution.calculationTheSumOfPath(l, w, points))

【例248】卡牌游戏 难度等级★★
3.代码实现

class Solution:def numOfPlan(self, n, totalProfit, totalCost, a, b):dp = [[0 for j in range(110)] for i in range(110)]dp[0][0] = 1mod = 1000000007for i in range(n):for j in range(totalProfit + 1, -1, -1):for k in range(totalCost + 1, -1, -1):idxA = min(totalProfit + 1, j + a[i])idxB = min(totalCost + 1, k + b[i])dp[idxA][idxB] = (dp[j][k] + dp[idxA][idxB]) % modans = 0for i in range(totalCost):ans = (ans + dp[totalProfit + 1][i]) % modreturn ans
if __name__ == '__main__':n = 2totalProfit = 3totalCost = 5a = [2,3]b = [2,2]solution = Solution()print(" 总卡片数：", n)print(" 成本和利润的列表是：", a, b)print(" 总成本是：", totalProfit, " 需要总利润是：", totalCost)print(" 可使用方法总数:", solution.numOfPlan(n, totalProfit, totalCost, a, b)) 

【例249】词频统计 难度等级★★
3.代码实现

#参数s是待查句子
#参数excludeList是被排除的单词
#返回值是一个字符串的列表，是所有出现频次最高的单词
class Solution:def getWords(self, s, excludeList):s = s.lower()words = []p = ''for letter in s:if letter < 'a' or letter > 'z':if p != '':words.append(p)p = ''else:p += letterif p != '':words.append(p)dic = {}for word in words:if word in dic:dic[word] += 1else:dic[word] = 1ans = []mx = 0for word in words:if dic[word] > mx and (not word in excludeList):mx = dic[word]ans = [word]elif dic[word] == mx and word not in ans and not word in excludeList:ans.append(word)return ans
if __name__ == '__main__':s="Do do do do not not Trouble trouble."excludeList=["do"]solution = Solution()print(" 待查句子为：",s , "除外词表为:", excludeList)print(" 词频最高的单词为:", solution.getWords(s, excludeList)) 

【例250】查找子数组 难度等级★★
3.代码实现

#参数arr是原数组
#参数k是目标子数组和
#返回值是个整数，代表这样一个子数组的起始位置，或者-1代表不存在
class Solution:def searchSubarray(self, arr, k):sum = 0maps = {}maps[sum] = 0st = len(arr) + 5lent = 0for i in range(0, len(arr)):sum += arr[i]if sum - k in maps:if st > maps[sum - k]:st = maps[sum - k]lent = i + 1 - maps[sum - k]if sum not in maps:maps[sum] = i + 1if st == len(arr) + 5:return -1else:return lent
if __name__ == '__main__':arr = [1,2,3,4,5]k = 5solution = Solution()print(" 数组为：", arr, "k为:", k)print(" 最短和为k的子数组是:", solution.searchSubarray(arr, k)) 

【例251】最小子矩阵 难度等级★★
3.代码实现

class Solution:def minimumSubmatrix(self, arr):ans = arr[0][0]for i in range(len(arr)):sum = [0 for x in range(len(arr[0]))]for j in range(i,len(arr)):for k in range(len(arr[0])):sum[k] += arr[j][k]dp = [0 for i in range(len(arr[0]))]for k in range(len(arr[0])):if k == 0:dp[k] = sum[k]else:dp[k] = min(sum[k],dp[k-1]+sum[k])ans = min(ans,dp[k])return ans
if __name__ == '__main__':arr = a = [[-3,-2,-1],[-2,3,-2],[-1,3,-1]]solution = Solution()print(" 数组为：", arr)print(" 最小子数组是:", solution.minimumSubmatrix(arr)) 

【例252】最佳购物计划 难度等级★★
3.代码实现

#参数k代表你有的钱
#参数m和n分别代表商品和礼盒数
#参数val是代表价值的列表
#参数costs是代表费用的列表
#返回值是一个整数，代表最大可获得价值
class Solution:def getAns(self, n, m, k, val, cost, belong):dp = [[-1 for i in range(0, 100001)] for i in range(0, 105)]arr = [[] for i in range(0, 105)]for i in range(n, n + m):if not belong[i] == -1:arr[belong[i]].append(i)dp[0][cost[0]] = val[0]for i in arr[0]:for j in range(k, cost[i] - 1, -1):if not dp[0][j - cost[i]] == -1:dp[0][j] = dp[0][j - cost[i]] + val[i]for i in range(1, n):for j in range(k, cost[i] - 1, -1):if not dp[i - 1][j - cost[i]] == -1:dp[i][j] = dp[i - 1][j - cost[i]] + val[i]dp[i][cost[i]] = val[i]for j in arr[i]:for l in range(k, cost[j] - 1, -1):if not dp[i][l - cost[j]] == -1:dp[i][l] = max(dp[i][l], dp[i][l - cost[j]] + val[j])for j in range(0, k + 1):dp[i][j] = max(dp[i][j], dp[i - 1][j])ans = 0for i in range(0, k + 1):ans = max(ans, dp[n - 1][i])return ans
if __name__ == '__main__':k = 10m = 2n = 3val = [17, 20, 8, 1, 4]cost = [3, 5, 2, 3, 1]belong = [-1, -1, -1, 0, 2]solution = Solution()print(" 拥有的钱：", k)print(" 有商品数：", m, " 有礼盒数：", n)print(" 价值的列表：", val, " 费用的列表：", cost)print(" 可以得到最大价值:", solution.getAns(n, m, k, val, cost, belong)) 

【例253】询问冷却时间 难度等级★★
3.代码实现

#参数arr是输入的待查数组
#参数n是公共冷却时间
#返回值是一个整数，代表需要多少时间
class Solution:def askForCoolingTime(self, arr, n):ans = 0l = [0 for i in range(110)]for x in arr:if l[x] == 0 or ans - l[x] > n:ans += 1else:ans = l[x] + n + 1l[x] = ansreturn ans
if __name__ == '__main__':arr = [1, 2, 1, 2]n = 2solution = Solution()print(" 数组为：", arr, " 冷却为：", n)print(" 至少需要时间:", solution.askForCoolingTime(arr, n)) 

【例254】树上最长路径 难度等级★★
3.代码实现

#参数n是节点总数
#参数starts是每条边的起始
#参数ends是每条边的结束
#参数lens是每条边的权重
#返回值是个整数，代表树上最长路径
import sys
sys.setrecursionlimit(200000)
class Solution:G = []dp = []def dfs(self, u, pre):for x in self.G[u]:if x[0] != pre:self.dp[x[0]] = self.dp[u] + x[1]self.dfs(x[0], u)def longestPath(self, n, starts, ends, lens):self.G = [[] for i in range(n)]self.dp = [0 for i in range(n)]for i in range(n - 1):self.G[starts[i]].append([ends[i], lens[i]])self.G[ends[i]].append([starts[i], lens[i]])self.dp[0] = 0self.dfs(0, 0)pos = Mx = 0for i in range(n):if self.dp[i] > Mx:pos = iMx = self.dp[i]self.dp[pos] = 0self.dfs(pos, pos)ans = 0for i in range(n):if self.dp[i] > ans:ans = self.dp[i]return ans
if __name__ == '__main__':n = 5starts = [0, 0, 2, 2]ends = [1, 2, 3, 4]lens = [1, 2, 5, 6]solution = Solution()print(" 总共有节点：", n)print(" 每条边的起始为：", starts)print(" 每条边的结束为：", ends)print(" 每条边的权重为：", lens)print(" 树上最长路径:", solution.longestPath(n, starts, ends, lens))

【例255】取数游戏 难度等级★★
3.代码实现

#参数s和t是一对字符串，他们需要被验证能否互相根据规则转换
#返回值是个字符串，意为能否根据规则转换
class Solution:def theGameOfTakeNumbers(self, arr):n = len(arr)if n == 0:return 1sum = [0 for i in range(n)]for i in range(1, n + 1):for j in range(0, n - i + 1):if i == 1:sum[j] = arr[j]continuek = j + i - 1sum[j] = max(arr[k] - sum[j], arr[j] - sum[j + 1])return 1 if sum[0] >= 0 else 2
if __name__ == '__main__':arr = [1,3,3,1]solution = Solution()print(" 游戏数组为：", arr)print(" 赢家会是:", solution.theGameOfTakeNumbers(arr))

【例256】数组求和 难度等级★★
3.代码实现

#参数arr是原始总列表
#返回值是个整数，代表所有子数组的和
class Solution:def findTheSumOfTheArray(self, arr):ans = 0n = len(arr)for i in range(n):ans = (ans + arr[i] * (i + 1) * (n - i)) % 1000000007;return ans
if __name__ == '__main__':arr = [2,4,6,8,10]solution = Solution()print(" 输入数组arr为：", arr)print(" 所有子数组的和为:", solution.findTheSumOfTheArray(arr))

【例257】最短短语 难度等级★★
3.代码实现

#参数k是最短单词数
#参数lim是最短短语长度
#参数str是被查找的字符串列表
#返回值是个整数，代表最短短语
class Solution:def getLength(self, k, lim, str):n = len(str)arr = [0] * nfor i in range(n):arr[i] = len(str[i])l = 0r = 0sum = 0ans = 1e9for r in range(n):sum += arr[r]while r - l >= k and sum - arr[l] >= lim:sum -= arr[l]l += 1if r - l + 1 >= k and sum >= lim:ans = min(ans, sum)return ans
if __name__ == '__main__':k = 2lim = 10str = ["she","was","bad","in","singing"]solution = Solution()print(" 最短单词数为：", k)print(" 短语长度限制为大于：", lim)print(" 文章列表为：", str)print(" 最短短语为:", solution.getLength(k, lim, str)) 

【例258】频率最高的词 难度等级★★
3.代码实现

#参数s为“小说”的字符串，excludeWords是不统计的词列表
#返回值是个单词，是出现最多的词
class Solution:def frequentWord(self, s, excludewords):map = {}while len(s) > 0:end = s.find(' ') if s.find(' ') > -1 else len(s)word = s[:end] if s[end - 1].isalpha() else s[:end - 1]s = s[end + 1:]if word not in excludewords:if word in map:map[word] += 1else:map[word] = 1max = -1res = []for key, val in map.items():if val == max:res.append(key)elif val > max:max = valres = [key]res.sort()return res[0]
if __name__ == '__main__':s = "Jimmy has an apple, it is on the table, he like it"excludeWords = ["a","an","the"]solution = Solution()print("小说的内容为：", s)print("统计不包含的词：", excludeWords)print("最常出现的词为：", solution.frequentWord(s, excludeWords))

【例259】判断三角形 难度等级★★
3.代码实现

#参数a为输入原始数组
#返回值是个字符串，意为能否形成三角形
class Solution:def judgingTriangle(self, arr):n = len(arr)if n > 44:return "YES"arr.sort();for i in range(n - 2):for j in range(i + 1, n - 1):for k in range(j + 1, n):if arr[i] + arr[j] > arr[k]:return "YES"return "NO"
if __name__ == '__main__':a = [1,2,5,9,10]solution = Solution()print(" 输入数组为：", a)print(" 能否组成三角形:", solution.judgingTriangle(a))

【例260】最大矩阵边界和 难度等级★★
3.代码实现

#参数arr为输入矩阵
#返回值是个整数，代表最大边界数值的和
class Solution:def solve(self, arr):n = len(arr)m = len(arr[0])preCol = []preRow = []for r in range(n):tem = [0]res = 0for c in range(m):res += arr[r][c]tem.append(res)preRow.append(tem)for c in range(m):tem = [0]res = 0for r in range(n):res += arr[r][c]tem.append(res)preCol.append(tem)ans = arr[0][0]for r1 in range(n):for r2 in range(r1, n):for c1 in range(m):for c2 in range(c1, m):if r1 == r2 and c1 == c2:res = arr[r1][c1]elif r1 == r2:res = preRow[r1][c2 + 1] - preRow[r1][c1]elif c1 == c2:res = preCol[c1][r2 + 1] - preCol[c1][r1]else:res = preCol[c1][r2 + 1] - preCol[c1][r1] + preCol[c2][r2 + 1] - preCol[c2][r1] + \preRow[r1][c2 + 1] - preRow[r1][c1] + preRow[r2][c2 + 1] - preRow[r2][c1] - arr[r1][c1] - arr[r1][c2] - arr[r2][c1] - arr[r2][c2]ans = max(ans, res)return ans
if __name__ == '__main__':arr=[[-1,-3,2],[2,3,4],[-3,7,2]]solution = Solution()print(" 矩阵为：", arr)print(" 最大能得到边界和为：", solution.solve(arr))

【例261】卡牌游戏 难度等级★★
3.代码实现

#参数Cost和Damage为卡牌属性
#参数totalCost和totalDamage为手上的费用和需要造成的伤害
#返回值是个布尔值，代表能否达成伤害
class Solution:def cardGame(self, cost, damage, totalMoney, totalDamage):num = len(cost)dp = [0] * (totalMoney + 1)for i in range(0, num):for j in range(totalMoney, cost[i] - 1, -1):dp[j] = max(dp[j], dp[j - cost[i]] + damage[i])if dp[j] >= totalDamage:return Truereturn False
if __name__ == '__main__':cost = [3,4,5,1,2]damage = [3,5,5,2,4]totalMoney = 7totalDamage = 11solution = Solution()print(" 卡牌的cost和damage数组分别为：", cost, damage)print(" 总共拥有金钱：", totalMoney)print(" 需要造成伤害：", totalDamage)print(" 能否达成：", solution.cardGame(cost, damage, totalMoney, totalDamage)) 

【例262】停车问题 难度等级★★
3.代码实现

#参数a是进出表
#返回值是个整数，代表最多同时有几辆车
class Solution:def getMax(self, a):ans = [0] * 23for i in a:for j in range(i[0], i[1]):ans[j] += 1max = ans[0]for i in ans:if i > max:max = ireturn max
if __name__ == '__main__':a = [[1,2],[2,3],[3,4],[4,5]]solution = Solution()print(" 车辆进出表为：", a)print(" 最多同时有车:", solution.getMax(a))

【例263】爬楼梯 难度等级★★
3.代码实现

#参数a与b分别是匹配数组和价值数组
#返回值是个整数，代表选择区间的最大价值
class Solution:def getAnswer(self, n, num):ans = [0] * (len(num) + 1)ans[0] = 1for i in range(n):for j in range(1 + i, min(len(num) + 1, i + num[i] + 1)):ans[j] = (ans[j] + ans[i]) % (10**9 + 7)return ans[len(num)]
if __name__ == '__main__':n = 4num = [1,1,1,1]solution = Solution()print(" 台阶数和每层台阶能往上登的阶数为：", n, num)print(" 走到顶一共有几种走法：", solution.getAnswer(n, num))

【例264】最小字符串 难度等级★★
3.代码实现

#参数s是原始字符串
#参数k是最大删除数目
#返回值是个字符串，代表删完的最小字典序字符串
class Solution:def findMinC(self, s, k):ans = 0if len(s) <= k:return -1for i in range(1, k + 1):if ord(s[i]) < ord(s[i - 1]):ans = ireturn ansdef MinimumString(self, s, k):ans = ""while k > 0:temp = self.findMinC(s, k)if temp == -1:s = ''breakans = ans + s[temp]s = s[temp + 1:]k -= tempans += sreturn ans
if __name__ == '__main__':s = "cba"k = 2solution = Solution()print(" 原始字符串为：", s)print(" 可以删除到最小字典序:", solution.MinimumString(s, k))

【例265】目的地的最短路径 难度等级★★
3.代码实现

#参数targetMap是地图
#返回值是个整数，是最短步数
class Solution:ans = []def cal(self, targetMap, x, y, z):if targetMap[x][y] == 1:returnif z < self.ans[x][y] or self.ans[x][y] == -1:self.ans[x][y] = zif x != 0:self.cal(targetMap, x - 1, y, z + 1)if x != len(targetMap) - 1:self.cal(targetMap, x + 1, y, z + 1)if y != 0:self.cal(targetMap, x, y - 1, z + 1)if y != len(targetMap[0]) - 1:self.cal(targetMap, x, y + 1, z + 1)returndef shortestPath(self, targetMap):self.ans = [[-1 for i in range(len(targetMap[0]))] for j in range(len(targetMap))]self.cal(targetMap, 0, 0, 0)print(self.ans)for i in range(len(targetMap)):for j in range(len(targetMap[0])):if targetMap[i][j] == 2:return self.ans[i][j]
if __name__ == '__main__':targetMap = [[0, 0, 0],[0, 0, 1],[0, 0, 2]]solution = Solution()print(" 地图为：", targetMap)print(" 最少需要走:", solution.shortestPath(targetMap)) 

【例266】毒药测试 难度等级★★
3.代码实现

#参数n是总水瓶数
#返回值是个整数，代表需要多少小白鼠
class Solution:def getAns(self, n):n -= 1ans = 0while n != 0:n //= 2ans += 1return ans
if __name__ == '__main__':n = 4solution = Solution()print("总共有：",n,"瓶水")print("至少需要:", solution.getAns(n),"只小白鼠")

【例267】社交网络 难度等级★★
3.代码实现

#参数n是网络人数
#参数a与b是关系两方
#返回值是个字符串，根据所有人能否联系返回“YES”或“NO”
class Solution:father = [0] * 5000def ask(self, x):if Solution.father[x] == x:return xSolution.father[x] = Solution.ask(self, Solution.father[x])return Solution.father[x]def socialNetwork(self, n, a, b):for i in range(0, n):Solution.father[i] = im = len(b)for i in range(m):x = Solution.ask(self, a[i])y = Solution.ask(self, b[i])Solution.father[x] = yfor i in range(0, n):if Solution.ask(self, i) != Solution.ask(self, 1):return "NO"return "YES"
if __name__ == '__main__':n = 4a = [1, 1, 1]b = [2, 3, 4]solution = Solution()print("好友关系组为：",a,b)print("他们能否直接或间接互相联系：", solution.socialNetwork(n, a, b))

【例268】前K高的基点 难度等级★★
3.代码实现

#参数list是学生ID与成绩的列表
#返回值是个列表，为前K名GPA学生的原序列表
from heapq import heappush, heappop
class Solution:def topKgpa(self, list, k):if len(list) == 0 or k < 0:return []minheap = []ID_set = set([])result = []for ID, GPA in list:ID_set.add(ID)heappush(minheap, (float(GPA), ID))if len(ID_set) > k:_, old_ID = heappop(minheap)ID_set.remove(old_ID)for ID, GPA in list:if ID in ID_set:result.append([ID, GPA])return result
if __name__ == '__main__':List = [["001","4.53"],["002","4.87"],["003","4.99"]]k = 2solution = Solution()print("学生按ID排序为：",List,"，K为：",k)print("前K高GPA的学生为：", solution.topKgpa(List, k)) 

【例269】寻找最长01子串 难度等级★★
3.代码实现

#参数str是原始01串
#返回值为整数，为最大长度
class Solution:def askingForTheLongest01Substring(self, str):str += strans = 1cnt = 1for i in range(1, len(str)):if str[i] != str[i - 1]:cnt += 1else:cnt = 1if ans < cnt and 2 * cnt <= len(str):ans = cntreturn ans
if __name__ == '__main__':str = "1001"solution = Solution()print(" 二进制串是",str)print(" 最长01子串有:", solution.askingForTheLongest01Substring(str)) 

【例270】合法字符串 难度等级★★
3.代码实现

#参数S是原始字符串
#参数k表示相同字符至少间隔多少字符
#返回值为列表，为每个位置插入的个数
class Solution:def getAns(self, k, S):n = len(S)pre = [-1] * 26 # 当前位置之前最靠右的相同字母位置,只有大写sm = [0] * (n + 1) #当前位置之前的"_"总数ans = []for i in range(1, n + 1):c = ord(S[i - 1]) - ord('A')if pre[c] == -1 or sm[i - 1] - sm[pre[c]] - pre[c] + i >= k:sm[i] = sm[i - 1]ans.append(0)else:sm[i] = sm[i - 1] + k - (sm[i - 1] - sm[pre[c]] + i - pre[c])ans.append(k - (sm[i - 1] - sm[pre[c]] + i - pre[c]))pre[c] = ireturn ans
if __name__ == '__main__':S = "AABACCDCD"k = 3solution = Solution()print(" 字符串是", S, "，每个相同字符间至少间隔",k , "个字符")print(" _字符的列表是:", solution.getAns(k,S))

【例271】叶节点的和 难度等级★★
3.代码实现

#参数root是树根
#返回值为整数，为叶节点值的和
class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
class Solution:#莫里斯中序遍历def sumLeafNode(self, root):res = 0p = rootwhile p:if p.left is None:if p.right is None:  # p 是一个叶节点res += p.valp = p.rightelse:tmp = p.leftwhile tmp.right is not None and tmp.right != p:tmp = tmp.rightif tmp.right is None:if tmp.left is None:  # tmp 是一个叶子节点res += tmp.valtmp.right = pp = p.leftelse: # 因为tmp.right为前序，所以停止tmp.right = Nonep = p.rightreturn res
if __name__ == '__main__':n1 = TreeNode(1)n1.left = TreeNode(2)n1.right = TreeNode(3)n1.left.left = TreeNode(4)n1.left.right = TreeNode(5)solution = Solution()print(" 结果为:", solution.sumLeafNode(n1))

【例272】转换字符串 难度等级★★
3.代码实现

#参数startString是起始链
#参数endString是目标链
#返回值是布尔值，如果可以转换则返回True，否则返回False
class Solution:def canTransfer(self, startString, endString):if not startString and not endString:return True# 长度不等if len(startString) != len(endString):return False# 字母种类起始链比终止链少if len(set(startString)) < len(set(endString)):return Falsemaptable = {}for i in range(len(startString)):a, b = startString[i], endString[i]if a in maptable:if maptable[a] != b:return Falseelse:maptable[a] = bdef noloopinhash(maptable):  # 映射表带环keyset = set(maptable)while keyset:a = keyset.pop()loopset = {a}while a in maptable:if a in keyset:keyset.remove(a)loopset.add(a)if a == maptable[a]:breaka = maptable[a]if a in loopset:return Falsereturn Truereturn noloopinhash(maptable)
if __name__ == '__main__':startString = "abc"endString = "bca"solution = Solution()print(" 起始链是：", startString)print(" 终止链是：", endString)print(" 能否转换：", solution.canTransfer(startString, endString))

【例273】最少按键次数 难度等级★★
3.代码实现

#参数s是一个字符串
#返回值为整数，为最小按键次数
class Solution:def getAns(self, s):left = -1ans = 0ncaps = Truefor right in range(0, len(s)):if ncaps:if ord(s[right]) < 95 and right-left <= 2:ans += 2if right-left == 2:ncaps = Falseans -= 1left = rightelse:left = rightans +=1else:if ord(s[right]) > 95 and right-left <= 2:ans += 2if right - left == 2:ncaps = Trueans -= 1left = rightelse:left = rightans +=1return ans
#主函数
if __name__ == '__main__':str = "EWlweWXZXxcscSDSDcccsdcfdsFvccDCcDCcdDcGvTvEEdddEEddEdEdAs"solution = Solution()print(" str是：", str)print(" 最小按键数是:", solution.getAns(str))

【例274】二分查找 难度等级★★
3.代码实现

class Solution:# 参数nums为整数数组# 参数target为整数# 返回整数def binarySearch(self, nums, target):left, right = 0, len(nums)-1while left + 1 < right :mid = (left + right)// 2if nums[mid] < target :left = midelse :right = midif nums[left] == target :return leftelif nums[right] == target :return rightreturn -1;
#主函数
if __name__ == '__main__':nums=[1,3,4,5,6,9]target=6solution = Solution()
answer=solution.binarySearch(nums,target)print("输入数组为：",nums)print("输入目标为：",target)print("输出下标为：",answer)

【例275】全排列 难度等级★★
3.代码实现

class Solution:"""参数nums为整数列表返回排序列表"""def permute(self, nums):if nums is None:return []if nums == []:return [[]]nums = sorted(nums)permutation = []stack = [-1]permutations = []while len(stack):index = stack.pop()index += 1while index < len(nums):if nums[index] not in permutation:breakindex += 1else:if len(permutation):permutation.pop()continuestack.append(index)stack.append(-1)permutation.append(nums[index])if len(permutation) == len(nums):permutations.append(list(permutation))return permutations
#主函数
if __name__ == '__main__':solution=Solution()nums=[0,1,2]name=solution.permute(nums)print("输入为：",nums)print("输出为：",name)

【例276】最小路径和 难度等级★★
3.代码实现

class Solution:"""参数grid为整数列表返回整数"""def minPathSum(self, grid):for i in range(len(grid)):for j in range(len(grid[0])):if i == 0 and j > 0:grid[i][j] += grid[i][j-1]elif j == 0 and i > 0:grid[i][j] += grid[i-1][j]elif i > 0 and j > 0:grid[i][j] += min(grid[i-1][j], grid[i][j-1])return grid[len(grid) - 1][len(grid[0]) - 1]
#主函数
if __name__ == '__main__':solution=Solution()nums=[[1,3,1],[1,5,1],[4,2,1]]answer=solution.minPathSum(nums)print("输入列表为：",nums)print("输出路径和：",answer)

【例277】最长路径序列 难度等级★★
3.代码实现

class Solution:"""参数num为整数列表返回整数"""def longestConsecutive(self, num):dict = {}for x in num:dict[x] = 1ans = 0for x in num:if x in dict:len = 1del dict[x]l = x - 1r = x + 1while l in dict:del dict[l]l -= 1len += 1while r in dict:del dict[r]r += 1len += 1if ans < len:ans = lenreturn ans
#主函数
if __name__ == '__main__':solution=Solution()nums=[100,4,200,1,3,2]answer=solution.longestConsecutive(nums)print("输入列表为：",nums)print("输出长度为：",answer)

【例278】背包问题2 难度等级★★
3.代码实现

class Solution:# 参数m为整数# 参数A和V为整数列表def backPackII(self, m, A, V):n = len(A)dp = [[0] * (m + 1), [0] * (m + 1)]for i in range(1, n + 1):dp[i % 2][0] = 0for j in range(1, m + 1):dp[i % 2][j] = dp[(i - 1) % 2][j]if A[i - 1] <= j:dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + V[i - 1])return dp[n % 2][m]
# 主函数
if __name__ == '__main__':solution=Solution()vol=34nums=[4,13,2,6,7,11,8]val=[1,23,4,5,2,14,9]answer = solution.backPackII(vol,nums,val)print("输入总体积：",vol)print("输入物品为：",nums)print("输入价值为：",val)print("输出结果为：",answer)

【例279】哈希函数 难度等级★★
3.代码实现

class Solution:"""参数key为字符串参数HASH_SIZE为整数返回整数"""def hashCode(self, key, HASH_SIZE):ans = 0for x in key:ans = (ans * 33 + ord(x)) % HASH_SIZEreturn ans
#主函数
if __name__ == '__main__':num=100key="abcd"answer= solution.hashCode(key,num)print("输入key为：",key)print("输入num为：",num)print("输出值为：",answer)

【例280】第一个只出现一次的字符 难度等级★★
3.代码实现

class Solution:"""参数str为字符串返回字符"""def firstUniqChar(self, str):counter = {}for c in str:counter[c] = counter.get(c, 0) + 1for c in str:if counter[c] == 1:return c
#主函数
if __name__ == '__main__':solution = Solution()s = "abaccdeff"ans = solution.firstUniqChar(s)solution = Solution()s = "abaccdeff"ans = solution.firstUniqChar(s)print("输入为：", s)print("输出为：", ans)

【例281】空格替换 难度等级★★
3.代码实现

class Solution:# 参数string为字符数组# 参数length为字符串的真实长度# 返回新字符串的真实长度def replaceBlank(self, string, length):if string is None:return lengthf = 0L = len(string)for i in range(len(string)):if string[i] == ' ':string[i] = '%20'f+=1return L-f+f*3
#主函数
if __name__ == '__main__':solution = Solution()si = "Mr John Smith"s1 = list(si)ans = solution.replaceBlank(s1, 13)so = ''.join(s1)print("输入字符串：", si)print("输出字符串：", so)print("输出其长度：", ans)

【例282】字符串压缩 难度等级★★
3.代码实现

class Solution:"""参数originalString为字符串返回压缩字符串"""def compress(self, originalString):l = len(originalString)if l <=2 : return originalStringlength = 1res = ""for i in range(1,l):if originalString[i] != originalString[i-1]:res = res + originalString[i-1] + str(length)length = 1else:length += 1if originalString[-1] != originalString[-2]:res = res + originalString[-1] + "1"else:res = res + originalString[i-1] + str(length)if len(originalString)<=len(res):return originalStringelse:return res
#主函数
if __name__ == '__main__':solution = Solution()si = "aabcccccaaa"arr = list(si)ans = solution.compress(arr)print("输入为：", si)print("输出为：", ans)

【例283】数组的最大值 难度等级★★
3.代码实现

class Solution:def max_num(self, arr):if arr == []:returnmaxnum = arr[0]for x in arr:if x > maxnum:maxnum = xreturn maxnum
#主函数
if __name__ == '__main__':solution = Solution()arr = [1.0, 2.1, -3.3]ans = solution.max_num(arr)print("输入为：", arr)print("输出为：", ans)

【例284】无序链表的重复项删除 难度等级★★
3.代码实现

class ListNode(object):def __init__(self, val):self.val = valself.next = None
class Solution:"""参数head为链表的第一个节点。返回头结点"""def removeDuplicates(self, head):seen, root, pre = set(), head, ListNode(-1)while head:if head.val not in seen:pre.next = headseen.add(head.val)pre = headhead = head.nextpre.next = Nonereturn root
#主函数
if __name__ == '__main__':solution = Solution()l0 = ListNode(1)l1 = ListNode(2)l2 = ListNode(2)l3 = ListNode(2)l0.next = l1l1.next = l2l2.next = l3root = solution.removeDuplicates(l0)a = [root.val, root.next.val]if a == [1, 2]:print("输入： 1->2->2->2->null")print("输出： 1->2->null")else:print("Error")

【例285】在O(1)时间复杂度删除链表节点 难度等级★★
3.代码实现

#参数node是要删除的节点
#无返回值，操作完毕
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
class Solution:def deleteNode(self, node):if node.next is None:node = Nonereturnnode.val = node.next.valnode.next = node.next.next
#主函数
if __name__ == '__main__':node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node1.next=ListNode(2)node2.next=ListNode(3)node3.next=ListNode(4)solution= Solution()print("输入是 :",node1.val,node2.val,node3.val,node4.val)solution.deleteNode(node3)print("删除节点3")print("输出是 :",node1.val,node2.val,node3.val)

【例286】将数组重新排序以构造最小值 难度等级★★
3.代码实现

from functools import cmp_to_key
class Solution:def cmp(self,a,b):if a+b>b+a:return 1if a+b<b+a:return -1else:return 0def PrintMinNumber(self,numbers):if not numbers:return ""number = list(map(str,numbers))number.sort(key=cmp_to_key(self.cmp))return "".join(number).lstrip('0') or '0'    
#主函数
if __name__ == '__main__':generation=[3,32,321]solution= Solution()print("输入是 :",generation)print("输出是 :",solution.PrintMinNumber(generation))

【例287】两个链表的交叉 难度等级★★
3.代码实现

#参数list_a是一个链表
#参数list_b是另一个链表
#无返回值，直接打印出结果
class ListNode:def __init__(self, val=None, next=None):self.value = valself.next = next
class Solution:def get_list_length(self, head):"""获取链表长度"""length = 0while head:length += 1head = head.nextreturn lengthdef get_intersect_node(self, list_a, list_b):length_a = self.get_list_length(list_a)length_b = self.get_list_length(list_b)cur1, cur2 = list_a, list_bif length_a > length_b:for i in range(length_a - length_b):cur1 = cur1.nextelse:for i in range(length_b - length_a):cur2 = cur2.nextflag = Falsewhile cur1 and cur2:if cur1.value == cur2.value:print(cur1.value)flag = Truebreakelse:cur1 = cur1.nextcur2 = cur2.nextif not flag:print('链表没有交叉结点')
#主函数
if __name__ == '__main__':solution= Solution()list_a = ListNode('a1', ListNode('a2', ListNode('c1', ListNode('c2', ListNode('c3')))))list_b = ListNode('b1', ListNode('b2', ListNode('b3', ListNode('c1', ListNode('c2', ListNode('c3'))))))print("输入是：")print("a = a1 a2 c1 c2 c3")print("b = b1 b2 b3 c1 c2 c3")print("输出是：")solution.get_intersect_node(list_a,list_b)

【例288】螺旋矩阵 难度等级★★
3.代码实现

#参数n是指123 … n任意一个整型数
#返回值是一个矩阵
class Solution:def generateMatrix(self, n):if n == 0: return []matrix = [[0 for i in range(n)] for j in range(n)]up = 0; down = len(matrix)-1left = 0; right = len(matrix[0])-1direct = 0; count = 0while True:if direct == 0:for i in range(left, right+1):count += 1; matrix[up][i] = countup += 1if direct == 1:for i in range(up, down+1):count += 1; matrix[i][right] = countright -= 1if direct == 2:for i in range(right, left-1, -1):count += 1; matrix[down][i] = countdown -= 1if direct == 3:for i in range(down, up-1, -1):count += 1; matrix[i][left] = countleft += 1if count == n*n: return matrixdirect = (direct+1) % 4
#主函数
if __name__ == '__main__':n=3solution = Solution()print("输入是： n = ", n)print("输出是：",solution.generateMatrix(n))

【例289】三角形计数 难度等级★★
3.代码实现

#参数S是一个正整数数组
#返回值count是计数结果
class Solution:def triangleCount(self, S):if len(S)<3:return;count=0;S.sort();#从小到大排序for i in range(0,len(S)):for j in range(i+1,len(S)):w,r=i+1,jtarget=S[j]-S[i]while w<r:mid=(w +r)//2  #取整数S_mid=S[mid]if S_mid>target:r=midelse:w=mid+1count+=(j-w)return count
#主函数
if __name__ == '__main__':generation=[3,4,6,7]solution= Solution()print("输入是：", generation)print("输出是：",solution.triangleCount(generation))

【例290】买卖股票的最佳时机 难度等级★★
3.代码实现

class Solution:"""参数k为整数参数prices为整数数组返回整数"""def maxProfit(self, k, prices):size = len(prices)if k >= size / 2:return self.quickSolve(size, prices)dp = [-10000] * (2 * k + 1)dp[0] = 0for i in range(size):for j in range(min(2 * k, i + 1) , 0 , -1):dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])return max(dp)def quickSolve(self, size, prices):sum = 0for x in range(size - 1):if prices[x + 1] > prices[x]:sum += prices[x + 1] - prices[x]return sum
#主函数
if __name__ == "__main__":solution=Solution()price=[4,4,6,1,1,4,2,5]k=2maxprofit=solution.maxProfit(k,price)print("输入价格为：",price)print("交易次数为：",k)print("最大利润为：",maxprofit)

【例291】加一 难度等级★★
3.代码实现

class Solution:#参数digits为整数数组#返回整数数组def plusOne(self, digits):digits = list(reversed(digits))digits[0] += 1i, carry = 0, 0while i < len(digits):next_carry = (digits[i] + carry) // 10digits[i] = (digits[i] + carry) % 10i, carry = i + 1, next_carryif carry > 0:digits.append(carry)return list(reversed(digits))
#主函数
if __name__ =="__main__":solution=Solution()num=[9,9,9]answer=solution.plusOne(num)print("输入为：",num)print("输出为：",answer)

【例292】炸弹袭击 难度等级★★
3.代码实现

#参数grid是一个表示二维网格的数组，由'W' 'E' '0'组成
#返回值result是放置一个炸弹后消灭敌人的最大数量
class Solution:def maxKilledEnemies(self, grid):m, n = len(grid), 0if m:n = len(grid[0])result, rows = 0, 0cols = [0 for i in range(n)]for i in range(m):for j in range(n):if j == 0 or grid[i][j-1] == 'W':rows = 0for k in range(j, n):if grid[i][k] == 'W':breakif grid[i][k] == 'E':rows += 1if i == 0 or grid[i-1][j] == 'W':cols[j] = 0for k in range(i, m):if grid[k][j] == 'W':breakif grid[k][j] == 'E':cols[j] += 1if grid[i][j] == '0' and rows + cols[j] > result:result = rows + cols[j]return result
#主函数
if __name__ == '__main__':generation =["0E00","E0WE","0E00"]solution= Solution()print("输入是：", generation)print("输出是：", solution.maxKilledEnemies(generation))

【例293】组合总和 IV 难度等级★★
3.代码实现

#参数nums是一个不重复的正整型数组
#参数target是一个整数
#返回值是一个整数，表示组合方式的个数
class Solution:def backPackVI(self, nums, target):row = len(nums)col = targetdp = [0 for i in range(col + 1)]dp[0] = 1for j in range(1, col + 1):for i in range(1, row + 1):if nums[i - 1] > j:continuedp[j] += dp[j - nums[i - 1]]return dp[-1]
#主函数
if __name__ == '__main__':generation=[1,2,4]target=4solution= Solution()print("输入是：", generation)print("输出是：", solution.backPackVI(generation,target))

【例294】向循环有序链表插入节点 难度等级★★
3.代码实现

#参数node是要插入的链表节点序列
#参数x是一个整数，表示插入的新的节点
#返回值new_node是插入新节点后的链表序列
class ListNode:def __init__(self, val=None, next=None):self.val = valself.next = next
class Solution:def insert(self, node, x):new_node = ListNode(x)if node is None:node = new_nodenode.next = nodereturn node#定义当前节点和前一节点cur, pre = node, Nonewhile cur:pre = curcur = cur.next#   pre.val <= x <= cur.valif x <= cur.val and x >= pre.val:break#链表循环处特殊判断（最大值->最小值），如果x小于最小值或x大于最大值，在此插入if pre.val > cur.val and (x < cur.val or x > pre.val):break#循环了一遍if cur is node:break#插入该节点new_node.next = curpre.next = new_nodereturn new_node
#主函数
if __name__ == '__main__':k=4generation = ListNode(3, ListNode(5, ListNode(1)))solution= Solution()solution.insert(generation,k)print("输入是： {3,5,1}")print("输出是：",generation.val,generation.next.val,generation.next.next.val, generation.next.next.next.val)

【例295】大岛的数量 难度等级★★
3.代码实现

class Solution:"""参数grid为二维布尔数组参数k为整数返回岛的数量"""def numsofIsland(self, grid, k):# Write your code hereif not grid or len(grid)==0 or len(grid[0])==0: return 0rows, cols = len(grid), len(grid[0])visited = [[False for i in range(cols)] for i in range(rows)]res = 0for i in range(rows):for j in range(cols):if visited[i][j]==False and grid[i][j] == 1:check = self.bfs(grid, visited, i,j,k)if check: res+=1return res def bfs(self, grid, visited, x, y, k):rows, cols = len(grid), len(grid[0])import collectionsqueue = collections.deque([(x, y)])visited[x][y] = Trueres = 0while queue:item = queue.popleft()res+=1 for idx, idy in ((1,0),(-1,0),(0,1),(0,-1)):x_new, y_new = item[0]+idx, item[1]+idyif x_new < 0 or x_new >= rows or y_new < 0 or y_new >= cols or visited[x_new][y_new] or grid[x_new][y_new] == 0: continuequeue.append((x_new, y_new))visited[x_new][y_new] = Truereturn res >= k
#主函数
if __name__ == '__main__':solution = Solution()g = [[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,0,0,1]]k = 3ans = solution.numsofIsland(g, k)print("输入：", g, "\nk=", k)print("输出：", ans)

【例296】最短回文串 难度等级★★
3.代码实现

class Solution:"""参数str为字符串返回字符串"""def convertPalindrome(self, str):if not str or len(str) == 0:return ""n = len(str)for i in range(n - 1, -1, -1):substr = str[:i + 1]if self.isPalindrome(substr):if i == n - 1:return str else:return (str[i + 1:] [::-1]) + str[:]def isPalindrome(self, str):left, right = 0, len(str) - 1 while left < right:if str[left] != str[right]:return Falseleft += 1 right -= 1 return True
#主函数
if __name__ == '__main__':solution = Solution()s = "sdsdlkjsaoio"ans = solution.convertPalindrome(s)print("输入：", s)print("输出：", ans)

【例297】不同的路径 难度等级★★
3.代码实现

class Solution:"""参数grid为二维数组返回所有唯一加权路径之和"""def uniqueWeightedPaths(self, grid):n=len(grid)m=len(grid[0])if n == 0 or m == 0:return 0s=[[set() for _ in range(m)] for __ in range(n)]s[0][0].add(grid[0][0])for i in range(n):for j in range(m):if i==0 and j==0:s[i][j].add(grid[i][j])else:for val in s[i-1][j]:s[i][j].add(val+grid[i][j])for val in s[i][j-1]:s[i][j].add(val+grid[i][j])ans=0for val in s[-1][-1]:ans+=valreturn ans
#主函数
if __name__ == '__main__':solution = Solution()arr = [[1,1,2],[1,2,3],[3,2,4]]ans = solution.uniqueWeightedPaths(arr)print("输入：", arr)print("输出：", ans)

【例298】分割字符串 难度等级★★
3.代码实现

class Solution:"""参数s为要拆分的字符串返回所有可能的拆分字符串数组"""def splitString(self, s):result = []self.dfs(result, [], s)return result def dfs(self, result, path, s):if s == "":result.append(path[:]) #important: use path[:] to clone itreturn for i in range(2):if i+1 <= len(s):path.append(s[:i+1])self.dfs(result, path, s[i+1:])path.pop()
#主函数
if __name__ == '__main__':solution = Solution()s = "123"ans = solution.splitString(s)print("输入：", s)print("输出：", ans)

【例299】缺失的第一个素数 难度等级★★
3.代码实现

class Solution:"""参数nums为数组返回整数"""def firstMissingPrime(self, nums):if not nums:return 2start = 0l = len(nums)integer = 2while start < l:while self.isPrime(integer) == False:integer += 1if nums[start] != integer:return integerinteger += 1start += 1while self.isPrime(integer) == False:integer += 1return integerdef isPrime(self, num):if num == 2 or num == 3:return Truefor i in range(2, int(num**(0.5)) + 1):if num % i == 0:return Falsereturn True
if __name__=='__main__':solution=Solution()n=[3,5,7]print("输入为：",n)print("输出为：",solution.firstMissingPrime(n))

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！