一. python3的各种经典案例，总共299个案例，直接可以运行（前：100个案例）
二. python3的各种经典案例，总共299个案例，直接可以运行（中：100个案例）
三. python3的各种经典案例，总共299个案例，直接可以运行（后：99个案例））
【例201】多米诺和三格骨牌铺瓦问题 难度等级★★
3.代码实现
class Solution:
#参数N为整数
#返回整数
def numTilings(self, N):
if N < 3:
return N
MOD = 1000000007
f = [[0, 0, 0] for i in range(N + 1)]
f[0][0] = f[1][0] = f[1][1] = f[1][2] = 1
for 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=3
print("输入为：",inputnum)
print("输出为：",solution.numTilings(inputnum))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例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 False
return True
if __name__ == '__main__':
solution=Solution()
inputnum1=[[1, 0], [0, 3]]
inputnum2=[0, 1]
print("输入幽灵为：",inputnum1)
print("输入目标为：",inputnum2)
print("输出为：",solution.escapeGhosts(inputnum1,inputnum2))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
【例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] = 0
for i in range(0, K + 1):
dN = list(distance)
for u, v, c in flights:
dN[v] = min(dN[v], distance[u] + c)
distance = dN
if distance[dst] != sys.maxsize:
return distance[dst]
else:
return -1
if __name__ == '__main__':
solution=Solution()
n=3
flights=[[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src=0
dst=2
K=0
print("输入城市为：",n)
print("输入航班为：",flights)
print("输入出发地：",src)
print("输入目的地：",dst)
print("输入中转数：",K)
print("输出价格为：",solution.findCheapestPrice(n, flights, src, dst, K))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
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] * n
for i in range(n):
if self.color[i] == 0 and not self.colored(i, graph, 1):
return False
return True
def colored(self, now, graph, c):
self.color[now] = c
for nxt in graph[now]:
if self.color[nxt] == 0 and not self.colored(nxt, graph, -c):
return False
elif self.color[nxt] == self.color[now]:
return False
return True
if __name__ == '__main__':
solution=Solution()
inputnum=[[1,3],[0,2],[1,3],[0,2]]
print("输入为：",inputnum)
print("输出为：",solution.isBipartite(inputnum))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
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] += 1
else:
hsh[i + 1] = 1
ans = 0
for i in hsh:
ans += math.ceil(hsh[i] / i) * i
return ans
if __name__ == '__main__':
solution=Solution()
inputnum=[1,1,2]
print("输入为：",inputnum)
print("输出为：",solution.numRabbits(inputnum))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
4.运行结果
输入为：[1, 1, 2]
输出为：5
【例206】最大分块排序 难度等级★★
3.代码实现
class Solution(object):
def maxChunksToSorted(self, arr):
def dfs(cur, localmax):
visited[cur] = True
localmax = max(localmax, cur)
if not visited[arr[cur]]:
return dfs(arr[cur], localmax)
return localmax
visited = [False] * len(arr)
count = 0
i = 0
while i < len(arr):
localmax = dfs(i, -1)
i += 1
while i < localmax + 1:
if not visited[i]:
localmax = dfs(i, localmax)
i += 1
count += 1
return count
if __name__ == '__main__':
solution=Solution()
arr = [1,0,2,3,4]
print("输入为：",arr)
print("输出为：",solution.maxChunksToSorted(arr))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
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 = 0
ans = []
for i, c in enumerate(S):
right = max(right, last[c])
if i == right:
ans.append(i - left + 1)
left = i + 1
return ans
if __name__ == '__main__':
solution=Solution()
s = "ababcbacadefegdehijhklij"
print("输入为：",s)
print("输出为：",solution.partitionLabels(s))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
4.运行结果
输入为：ababcbacadefegdehijhklij
输出为：[9, 7, 8]
【例208】网络延迟时间 难度等级★★
3.代码实现
class Solution:
#参数times为数组
#参数N为整数
#参数K为整数
#返回整数
def networkDelayTime(self, times, N, K):
INF = 0x3f3f3f3f
G = [[INF for i in range(N + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
G[i][i] = 0
for 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 = INF
p = K
for j in range(1, N + 1):
if vis[j] == 0 and dis[j] < Mini:
Mini = dis[j]
p = j
vis[p] = 1
for 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 = 0
for i in range(1, N + 1):
ans = max(ans, dis[i])
if ans == INF:
return -1
return ans
if __name__ == '__main__':
solution=Solution()
times=[[2,1,1],[2,3,1],[3,4,1]]
N=4
K=2
print("时间矩阵为：",times)
print("网络大小为：",N)
print("起始节点为：",K)
print("最小花费为：",solution.networkDelayTime(times,N,K))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
【例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:
return
image[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 = 1
sc = 1
newColor = 2
print("输入图像为：",image)
print("输入坐标为： [",sr,",",sc,"]")
print("输入颜色为：",newColor)
print("输出图像为：",(solution.floodFill(image,sr,sc,newColor)))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【例210】映射配对之和 难度等级★★
3.代码实现
class TrieNode:
def __init__(self):
self.son = {}
self.val = 0
class Trie:
root = TrieNode()
def insert(self, s, val):
cur = self.root
for 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 += val
def find(self, s):
cur = self.root
for i in range(0, len(s)):
if s[i] not in cur.son:
return 0
cur = 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] = val
def 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"))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例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=2736
print("输入为：",num)
print("输出为：",solution.maximumSwap(num))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
【例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 1
for num in nums:
if not num in cnt or cnt[num] < 1:
continue
if num - 1 in tail and tail[num - 1] > 0:
tail[num - 1] -= 1
tail[num] = tail[num] + 1 if num in tail else 1
elif num + 1 in cnt and cnt[num + 1] > 0 and num + 2 in cnt and cnt[num + 2] > 0:
cnt[num + 1] -= 1
cnt[num + 2] -= 1
tail[num + 2] = tail[num + 2] + 1 if num + 2 in tail else 1
else:
return False
cnt[num] -= 1
return True
if __name__ == '__main__':
solution=Solution()
nums=[1,2,3,3,4,5]
print("输入为：",nums)
print("输出为：",solution.isPossible(nums))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例215】合法的三角数 难度等级★★
3.代码实现
class Solution:
#参数nums为数组
#返回整数
def triangleNumber(self, nums):
nums = sorted(nums)
total = 0
for i in range(len(nums)-2):
if nums[i] == 0:
continue
end = i + 2
for j in range(i+1, len(nums)-1):
while end < len(nums) and nums[end] < (nums[i] + nums[j]):
end += 1
total += end - j - 1
return total
if __name__ == '__main__':
solution = Solution()
nums=[2,2,3,4]
print("输入为：",nums)
print("输出为：",solution.triangleNumber(nums))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
【例218】下一个更大的元素 难度等级★★
3.代码实现
class Solution:
#n为整数
#返回整数
def nextGreaterElement(self, n):
n_array = list(map(int, list(str(n))))
if len(n_array) <= 1:
return -1
if len(n_array) == 2:
if n_array[0] < n_array[1]:
return int("".join(map(str, n_array[::-1])))
else:
return -1
if 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) - 1
while i > 0 and n_array[i - 1] >= n_array[i]:
i -= 1
if i == 0:
return -1
else:
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]:
break
new_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=123
print("输入为：",n)
print("输出为：",solution.nextGreaterElement(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
【例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 x
return ''
if __name__ == '__main__':
s = "abpcplea"
d = ["ale", "apple", "monkey", "plea"]
solution=Solution()
print("输入为：",s)
print("输入为：",d)
print("输出为：",solution.findLongestWord(s,d))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
【例221】寻找树中最左下结点的值 难度等级★★
3.代码实现
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
#参数root为二叉树根
#返回整数
def findBottomLeftValue(self, root):
self.max_level = 0
self.val = None
self.helper(root, 1)
return self.val
def helper(self, root, level):
if not root: return
if level > self.max_level:
self.max_level = level
self.val = root.val
self.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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
【例222】出现频率最高的子树和 难度等级★★
3.代码实现
import collections
class TreeNode:
def __init__(self, val):
self.val = val
self.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 0
ret = node.val
if node.left:
ret += sumnode(node.left)
if node.right:
ret += sumnode(node.right)
counter[ret] += 1
return ret
sumnode(root)
arr = []
for k in counter:
arr.append((k, counter[k]))
arr.sort(key=lambda x: x[1], reverse=True)
i = 0
while i + 1 < len(arr) and arr[i + 1][1] == arr[0][1]:
i += 1
return [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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
【例223】寻找BST的modes 难度等级★★
3.代码实现
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
#参数root为根节点
#返回整数
def helper(self, root, cache):
if root == None:
return
cache[root.val] += 1
self.helper(root.left, cache)
self.helper(root.right, cache)
return
def findMode(self, root):
from collections import defaultdict
if 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 = None
T2 = TreeNode(2)
T.right = T2
T3 = TreeNode(2)
T2.left = T3
s = Solution()
print("输入为：[1,#,2,2]")
print("输出为：",s.findMode(T))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
【例224】对角线遍历 难度等级★★
3.代码实现
class Solution:
#参数matrix为矩阵
#返回整数列表
def findDiagonalOrder(self, matrix):
import collections
result = [ ]
dd = collections.defaultdict(list)
if not matrix:
return result
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例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 =2
timws = [1,4]
print("输入攻击序列：",timws)
print("输入持续时间：",time)
print("输出中毒时间：",s.findPoisonedDuration(timws,time))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
【例226】目标和 难度等级★★
3.代码实现
class Solution(object):
def findTargetSumWays(self, nums, S):
if not nums:
return 0
dic = {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 = tdic
return dic.get(S, 0)
#主函数
if __name__ == '__main__':
s = Solution()
time =3
timws = [1,1,1,1,1]
print("输入目标值：",time)
print("输入序列值：",timws)
print("输出方法为：",s.findTargetSumWays(timws,time))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
【例227】升序子序列 难度等级★★
3.代码实现
class Solution(object):
def findSubsequences(self, nums):
#参数nums为列表
#返回列表
res = []
self.subsets(nums, 0, [], res)
return res
def 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]: continue
if nums[i] in used: continue
used[nums[i]] = True
temp.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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
【例228】神奇字符串 难度等级★★
3.代码实现
class Solution(object):
def magicalString(self, n):
#参数n为整数
#返回整数
if n == 0:
return 0
elif n <= 3:
return 1
else:
so_far, grp, ones =[1,2,2], 2, 1
while len(so_far) < n:
freq, item = so_far[grp], 1 if grp % 2 == 0 else 2
for _ in range(freq):
so_far.append(item)
ones, grp = ones + freq if item == 1 else ones, grp + 1
if len(so_far) == n:
return ones
else:
return ones-1 if so_far[-1] == 1 else ones
#主函数
if __name__ == '__main__':
s = Solution()
n = 6
print("输入为：",n)
print("输出为：",s.magicalString(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例229】爆破气球的最小箭头数 难度等级★★
3.代码实现
class Solution(object):
def findMinArrowShots(self, points):
#参数points为整数列表
#返回整数
if points == None or not points:
return 0
points.sort(key = lambda x : x[1]);
ans = 1
lastEnd = points[0][1]
for i in range(1, len(points)):
if points[i][0] > lastEnd:
ans += 1
lastEnd = 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
【例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 = -index
if 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
【例231】最小基因变化 难度等级★★
3.代码实现
from collections import deque
class Solution:
#参数start为字符串
#参数end为字符串
#参数bank为字符串
#返回整数
def minMutation(self, start, end, bank):
if not bank:
return -1
bank = set(bank)
h = deque()
h.append((start, 0))
while h:
seq, step = h.popleft()
if seq == end:
return step
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
【例232】替换后的最长重复字符 难度等级★★
3.代码实现
from collections import defaultdict
class Solution:
#参数s为字符串
#参数k为整数
#返回整数
def characterReplacement(self, s, k):
n = len(s)
char2count = defaultdict(int)
maxLen = 0
start = 0
for end in range(n):
char2count[s[end]] += 1
while end - start + 1 - char2count[s[start]] > k:
char2count[s[start]] -= 1
start += 1
maxLen = max(maxLen, end - start + 1)
return maxLen
#主函数
if __name__ == '__main__':
s = Solution()
n ="ABAB"
m=2
print("输入字符串为：",n)
print("输入重复次数：",m)
print("输出子串长度：",s.characterReplacement(n,m))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例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]) // 2
result = ""
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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例234】数组中两个数字的最大异或 难度等级★★
3.代码实现
class TrieNode:
def __init__(self,val):
self.val = val
self.children = {}
class Solution:
#参数nums为整数:
#返回整数
def findMaximumXOR(self, nums):
answer = 0
for i in range(32)[::-1]:
answer <<= 1
prefixes = {num >> i for num in nums}
answer += any(answer^1 ^ p in prefixes for p in prefixes)
return answer
def findMaximumXOR_TLE(self, nums):
root = TrieNode(0)
for num in nums:
self.addNode(root, num)
res = -sys.maxsize
for num in nums:
cur_node, cur_sum = root, 0
for i in reversed(range(0,32)):
bit = (num >> i) & 1
if (bit^1) in cur_node.children:
cur_sum += 1 << i
cur_node = cur_node.children[bit^1]
else:
cur_node = cur_node.children[bit]
res = max(res, cur_sum)
return res
def addNode(self, root, num):
cur = root
for i in reversed(range(0,32)):
bit = (num >> i) & 1
if 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
【例236】左叶子的和 难度等级★★
3.代码实现
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
参数root为二叉树根
返回整数
"""
def dfs(root):
if not root:
return 0
sum = 0
if 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.right
sum += dfs(right)
return sum
return dfs(root)
#主函数
if __name__ == '__main__':
s = Solution()
t = TreeNode(3)
t1 = TreeNode(9)
t.left = t1
t2 = TreeNode(20)
t.right = t2
t3 = TreeNode(15)
t2.left = t3
t4 = TreeNode(7)
t2.right = t4
print("输入为：[3,9 20,# # 15 7]")
print("输出为：",s.sumOfLeftLeaves(t))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
【例237】移除K位 难度等级★★
3.代码实现
class Solution:
"""
参数num为字符串
参数k为整数
返回字符串
"""
def removeKdigits(self, num, k):
if k == 0:
return num
if 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 = 3
print("输入数字为：",n)
print("输入移除数：",k)
print("输出为：",s.removeKdigits(n,k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
【例238】轮转函数 难度等级★★
3.代码实现
class Solution:
"""
参数A数组
返回整数
"""
def maxRotateFunction(self, A):
s = sum(A)
curr = sum(i*a for i, a in enumerate(A))
maxVal = curr
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例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 = 3
print("输入字符串为：",n)
print("输入重复次数：",k)
print("输出子串长度：",s.longestSubstring(n,k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例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 = 9
print("输入为：",n)
print("输出为：",s.lastRemaining(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
【例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 start
return end
def get_num_less_equal(self, matrix, mid):
m = len(matrix)
n = len(matrix[0])
i = 0
j = n - 1
count = 0
while 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=8
print("输入数组为：",n)
print("输入顺序为：",k)
print("输出数字为：",s.kthSmallest(n,k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
【例242】超级幂次 难度等级★★
3.代码实现
class Solution:
"""
参数a为整数: the given number a
参数b为数组
返回整数
"""
def superPow(self, a, b):
if a == 0:
return 0
ans = 1
def mod(x):
return x % 1337
for num in b:
ans = mod(mod(ans ** 10) * mod(a ** num))
return ans
#主函数
if __name__ == '__main__':
s = Solution()
n=2
k=[3]
print("输入a=：",n)
print("输入b=：",k)
print("输出为：",s.superPow(n,k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
【例243】水罐问题 难度等级★★
3.代码实现
class Solution:
"""
参数x为整数
参数y为整数
参数z为整数
返回布尔类型
"""
def canMeasureWater(self, x, y, z):
if x+y < z:
return False
return z % self.gcd(x,y) == 0
def gcd(self, x, y):
if y == 0:
return x
return self.gcd(y, x%y)
#主函数
if __name__ == '__main__':
s = Solution()
x = 3
y = 5
z = 4
print("输入x=：",x)
print("输入y=：",y)
print("输入z=：",z)
print("输出为：",s.canMeasureWater(x,y,z))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例244】计算不同数字整数的个数 难度等级★★
3.代码实现
class Solution:
"""
参数n为整数
返回整数
"""
def countNumbersWithUniqueDigits(self, n):
if n == 0:
return 1
n = min(n, 10)
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 9
for i in range(2, n + 1):
dp[i] = dp[i - 1] * (11 - i)
return sum(dp)
#主函数
if __name__ == '__main__':
s = Solution()
x = 2
print("输入为：",x)
print("输出为：",s.countNumbersWithUniqueDigits(2))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
4.运行结果
输入为：2
输出为：91
【例245】最大乘积路径 难度等级★★
3.代码实现
#参数x，y代表每条边的起始和终止
#参数d是每个节点的权重
#返回值是一个整数，是取模后节点最大乘积
class Solution:
ans = 0
def dfs(self, x, f, g, d, mul):
isLeaf = True
mul = mul * d[x - 1] % 1000000007
for i in g[x]:
if i == f:
continue
isLeaf = False
self.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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
【例246】矩阵找数 难度等级★★
3.代码实现
#参数mat是待查矩阵
#返回值是一个整数，是每一行都出现的最小的数字
class Solution:
def findingNumber(self, mat):
hashSet = {}
n = len(mat)
for mati in mat:
vis = {}
for x in mati:
vis[x] = 1
for key in vis:
if key not in hashSet:
hashSet[key] = 0
hashSet[key] += 1
ans = 100001
for 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] = 1
for key in vis:
if key not in hashSet:
hashSet[key] = 0
hashSet[key] += 1
ans = 100001
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
【例247】路径数计算 难度等级★★
3.代码实现
#参数points是除了始末点外的必经点
#参数l和w是长和宽
#返回值是一个整数，有多少种走法
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.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)] + points
if points[0].x != l or points[0].y != w:
points = points + [Point(l,w)]
arr = [[] for i in range(len(points) - 1)]
maxl = 0
maxw = 0
for i in range(1, len(points)):
l = points[i].x - points[i - 1].x
w = points[i].y - points[i - 1].y
arr[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, maxw
for i in range(len(dp)):
for j in range(i, len(dp)):
if i == 0:
dp[j][i] = dp[i][j] = 1
else:
dp[j][i] = dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
ans = 1
for i in arr:
ans = ans * dp[i[0]][i[1]] % 1000000007
return ans
if __name__ == '__main__':
l=43
w=48
points = [Point(17,19), Point(43,48), Point(3,5)]
solution = Solution()
print(" 长与宽分别为：", l, w)
print(" 有路径种数:", solution.calculationTheSumOfPath(l, w, points))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
【例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] = 1
mod = 1000000007
for 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]) % mod
ans = 0
for i in range(totalCost):
ans = (ans + dp[totalProfit + 1][i]) % mod
return ans
if __name__ == '__main__':
n = 2
totalProfit = 3
totalCost = 5
a = [2,3]
b = [2,2]
solution = Solution()
print(" 总卡片数：", n)
print(" 成本和利润的列表是：", a, b)
print(" 总成本是：", totalProfit, " 需要总利润是：", totalCost)
print(" 可使用方法总数:", solution.numOfPlan(n, totalProfit, totalCost, a, b))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例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 += letter
if p != '':
words.append(p)
dic = {}
for word in words:
if word in dic:
dic[word] += 1
else:
dic[word] = 1
ans = []
mx = 0
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
【例250】查找子数组 难度等级★★
3.代码实现
#参数arr是原数组
#参数k是目标子数组和
#返回值是个整数，代表这样一个子数组的起始位置，或者-1代表不存在
class Solution:
def searchSubarray(self, arr, k):
sum = 0
maps = {}
maps[sum] = 0
st = len(arr) + 5
lent = 0
for 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 + 1
if st == len(arr) + 5:
return -1
else:
return lent
if __name__ == '__main__':
arr = [1,2,3,4,5]
k = 5
solution = Solution()
print(" 数组为：", arr, "k为:", k)
print(" 最短和为k的子数组是:", solution.searchSubarray(arr, k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【例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 = 0
for i in range(0, k + 1):
ans = max(ans, dp[n - 1][i])
return ans
if __name__ == '__main__':
k = 10
m = 2
n = 3
val = [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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
【例253】询问冷却时间 难度等级★★
3.代码实现
#参数arr是输入的待查数组
#参数n是公共冷却时间
#返回值是一个整数，代表需要多少时间
class Solution:
def askForCoolingTime(self, arr, n):
ans = 0
l = [0 for i in range(110)]
for x in arr:
if l[x] == 0 or ans - l[x] > n:
ans += 1
else:
ans = l[x] + n + 1
l[x] = ans
return ans
if __name__ == '__main__':
arr = [1, 2, 1, 2]
n = 2
solution = Solution()
print(" 数组为：", arr, " 冷却为：", n)
print(" 至少需要时间:", solution.askForCoolingTime(arr, n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
【例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] = 0
self.dfs(0, 0)
pos = Mx = 0
for i in range(n):
if self.dp[i] > Mx:
pos = i
Mx = self.dp[i]
self.dp[pos] = 0
self.dfs(pos, pos)
ans = 0
for i in range(n):
if self.dp[i] > ans:
ans = self.dp[i]
return ans
if __name__ == '__main__':
n = 5
starts = [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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
【例255】取数游戏 难度等级★★
3.代码实现
#参数s和t是一对字符串，他们需要被验证能否互相根据规则转换
#返回值是个字符串，意为能否根据规则转换
class Solution:
def theGameOfTakeNumbers(self, arr):
n = len(arr)
if n == 0:
return 1
sum = [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]
continue
k = j + i - 1
sum[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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【例256】数组求和 难度等级★★
3.代码实现
#参数arr是原始总列表
#返回值是个整数，代表所有子数组的和
class Solution:
def findTheSumOfTheArray(self, arr):
ans = 0
n = 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
【例257】最短短语 难度等级★★
3.代码实现
#参数k是最短单词数
#参数lim是最短短语长度
#参数str是被查找的字符串列表
#返回值是个整数，代表最短短语
class Solution:
def getLength(self, k, lim, str):
n = len(str)
arr = [0] * n
for i in range(n):
arr[i] = len(str[i])
l = 0
r = 0
sum = 0
ans = 1e9
for r in range(n):
sum += arr[r]
while r - l >= k and sum - arr[l] >= lim:
sum -= arr[l]
l += 1
if r - l + 1 >= k and sum >= lim:
ans = min(ans, sum)
return ans
if __name__ == '__main__':
k = 2
lim = 10
str = ["she","was","bad","in","singing"]
solution = Solution()
print(" 最短单词数为：", k)
print(" 短语长度限制为大于：", lim)
print(" 文章列表为：", str)
print(" 最短短语为:", solution.getLength(k, lim, str))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
【例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] += 1
else:
map[word] = 1
max = -1
res = []
for key, val in map.items():
if val == max:
res.append(key)
elif val > max:
max = val
res = [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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
【例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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例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 = 0
for c in range(m):
res += arr[r][c]
tem.append(res)
preRow.append(tem)
for c in range(m):
tem = [0]
res = 0
for 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
【例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 True
return False
if __name__ == '__main__':
cost = [3,4,5,1,2]
damage = [3,5,5,2,4]
totalMoney = 7
totalDamage = 11
solution = Solution()
print(" 卡牌的cost和damage数组分别为：", cost, damage)
print(" 总共拥有金钱：", totalMoney)
print(" 需要造成伤害：", totalDamage)
print(" 能否达成：", solution.cardGame(cost, damage, totalMoney, totalDamage))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
【例262】停车问题 难度等级★★
3.代码实现
#参数a是进出表
#返回值是个整数，代表最多同时有几辆车
class Solution:
def getMax(self, a):
ans = [0] * 23
for i in a:
for j in range(i[0], i[1]):
ans[j] += 1
max = ans[0]
for i in ans:
if i > max:
max = i
return max
if __name__ == '__main__':
a = [[1,2],[2,3],[3,4],[4,5]]
solution = Solution()
print(" 车辆进出表为：", a)
print(" 最多同时有车:", solution.getMax(a))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
【例263】爬楼梯 难度等级★★
3.代码实现
#参数a与b分别是匹配数组和价值数组
#返回值是个整数，代表选择区间的最大价值
class Solution:
def getAnswer(self, n, num):
ans = [0] * (len(num) + 1)
ans[0] = 1
for 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 = 4
num = [1,1,1,1]
solution = Solution()
print(" 台阶数和每层台阶能往上登的阶数为：", n, num)
print(" 走到顶一共有几种走法：", solution.getAnswer(n, num))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
【例264】最小字符串 难度等级★★
3.代码实现
#参数s是原始字符串
#参数k是最大删除数目
#返回值是个字符串，代表删完的最小字典序字符串
class Solution:
def findMinC(self, s, k):
ans = 0
if len(s) <= k:
return -1
for i in range(1, k + 1):
if ord(s[i]) < ord(s[i - 1]):
ans = i
return ans
def MinimumString(self, s, k):
ans = ""
while k > 0:
temp = self.findMinC(s, k)
if temp == -1:
s = ''
break
ans = ans + s[temp]
s = s[temp + 1:]
k -= temp
ans += s
return ans
if __name__ == '__main__':
s = "cba"
k = 2
solution = Solution()
print(" 原始字符串为：", s)
print(" 可以删除到最小字典序:", solution.MinimumString(s, k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
【例265】目的地的最短路径 难度等级★★
3.代码实现
#参数targetMap是地图
#返回值是个整数，是最短步数
class Solution:
ans = []
def cal(self, targetMap, x, y, z):
if targetMap[x][y] == 1:
return
if z < self.ans[x][y] or self.ans[x][y] == -1:
self.ans[x][y] = z
if 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)
return
def 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
【例266】毒药测试 难度等级★★
3.代码实现
#参数n是总水瓶数
#返回值是个整数，代表需要多少小白鼠
class Solution:
def getAns(self, n):
n -= 1
ans = 0
while n != 0:
n //= 2
ans += 1
return ans
if __name__ == '__main__':
n = 4
solution = Solution()
print("总共有：",n,"瓶水")
print("至少需要:", solution.getAns(n),"只小白鼠")
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
【例267】社交网络 难度等级★★
3.代码实现
#参数n是网络人数
#参数a与b是关系两方
#返回值是个字符串，根据所有人能否联系返回“YES”或“NO”
class Solution:
father = [0] * 5000
def ask(self, x):
if Solution.father[x] == x:
return x
Solution.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] = i
m = len(b)
for i in range(m):
x = Solution.ask(self, a[i])
y = Solution.ask(self, b[i])
Solution.father[x] = y
for i in range(0, n):
if Solution.ask(self, i) != Solution.ask(self, 1):
return "NO"
return "YES"
if __name__ == '__main__':
n = 4
a = [1, 1, 1]
b = [2, 3, 4]
solution = Solution()
print("好友关系组为：",a,b)
print("他们能否直接或间接互相联系：", solution.socialNetwork(n, a, b))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
【例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 = 2
solution = Solution()
print("学生按ID排序为：",List,"，K为：",k)
print("前K高GPA的学生为：", solution.topKgpa(List, k))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例269】寻找最长01子串 难度等级★★
3.代码实现
#参数str是原始01串
#返回值为整数，为最大长度
class Solution:
def askingForTheLongest01Substring(self, str):
str += str
ans = 1
cnt = 1
for i in range(1, len(str)):
if str[i] != str[i - 1]:
cnt += 1
else:
cnt = 1
if ans < cnt and 2 * cnt <= len(str):
ans = cnt
return ans
if __name__ == '__main__':
str = "1001"
solution = Solution()
print(" 二进制串是",str)
print(" 最长01子串有:", solution.askingForTheLongest01Substring(str))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
【例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] = i
return ans
if __name__ == '__main__':
S = "AABACCDCD"
k = 3
solution = Solution()
print(" 字符串是", S, "，每个相同字符间至少间隔",k , "个字符")
print(" _字符的列表是:", solution.getAns(k,S))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例271】叶节点的和 难度等级★★
3.代码实现
#参数root是树根
#返回值为整数，为叶节点值的和
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:#莫里斯中序遍历
def sumLeafNode(self, root):
res = 0
p = root
while p:
if p.left is None:
if p.right is None: # p 是一个叶节点
res += p.val
p = p.right
else:
tmp = p.left
while tmp.right is not None and tmp.right != p:
tmp = tmp.right
if tmp.right is None:
if tmp.left is None: # tmp 是一个叶子节点
res += tmp.val
tmp.right = p
p = p.left
else: # 因为tmp.right为前序，所以停止
tmp.right = None
p = p.right
return 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
【例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 False
maptable = {}
for i in range(len(startString)):
a, b = startString[i], endString[i]
if a in maptable:
if maptable[a] != b:
return False
else:
maptable[a] = b
def 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]:
break
a = maptable[a]
if a in loopset:
return False
return True
return noloopinhash(maptable)
if __name__ == '__main__':
startString = "abc"
endString = "bca"
solution = Solution()
print(" 起始链是：", startString)
print(" 终止链是：", endString)
print(" 能否转换：", solution.canTransfer(startString, endString))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
【例273】最少按键次数 难度等级★★
3.代码实现
#参数s是一个字符串
#返回值为整数，为最小按键次数
class Solution:
def getAns(self, s):
left = -1
ans = 0
ncaps = True
for right in range(0, len(s)):
if ncaps:
if ord(s[right]) < 95 and right-left <= 2:
ans += 2
if right-left == 2:
ncaps = False
ans -= 1
left = right
else:
left = right
ans +=1
else:
if ord(s[right]) > 95 and right-left <= 2:
ans += 2
if right - left == 2:
ncaps = True
ans -= 1
left = right
else:
left = right
ans +=1
return ans
#主函数
if __name__ == '__main__':
str = "EWlweWXZXxcscSDSDcccsdcfdsFvccDCcDCcdDcGvTvEEdddEEddEdEdAs"
solution = Solution()
print(" str是：", str)
print(" 最小按键数是:", solution.getAns(str))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
【例274】二分查找 难度等级★★
3.代码实现
class Solution:
# 参数nums为整数数组
# 参数target为整数
# 返回整数
def binarySearch(self, nums, target):
left, right = 0, len(nums)-1
while left + 1 < right :
mid = (left + right)// 2
if nums[mid] < target :
left = mid
else :
right = mid
if nums[left] == target :
return left
elif nums[right] == target :
return right
return -1;
#主函数
if __name__ == '__main__':
nums=[1,3,4,5,6,9]
target=6
solution = Solution()
answer=solution.binarySearch(nums,target)
print("输入数组为：",nums)
print("输入目标为：",target)
print("输出下标为：",answer)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【例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 += 1
while index < len(nums):
if nums[index] not in permutation:
break
index += 1
else:
if len(permutation):
permutation.pop()
continue
stack.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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
【例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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
【例277】最长路径序列 难度等级★★
3.代码实现
class Solution:
"""
参数num为整数列表
返回整数
"""
def longestConsecutive(self, num):
dict = {}
for x in num:
dict[x] = 1
ans = 0
for x in num:
if x in dict:
len = 1
del dict[x]
l = x - 1
r = x + 1
while l in dict:
del dict[l]
l -= 1
len += 1
while r in dict:
del dict[r]
r += 1
len += 1
if ans < len:
ans = len
return ans
#主函数
if __name__ == '__main__':
solution=Solution()
nums=[100,4,200,1,3,2]
answer=solution.longestConsecutive(nums)
print("输入列表为：",nums)
print("输出长度为：",answer)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
【例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] = 0
for 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=34
nums=[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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
【例279】哈希函数 难度等级★★
3.代码实现
class Solution:
"""
参数key为字符串
参数HASH_SIZE为整数
返回整数
"""
def hashCode(self, key, HASH_SIZE):
ans = 0
for x in key:
ans = (ans * 33 + ord(x)) % HASH_SIZE
return ans
#主函数
if __name__ == '__main__':
num=100
key="abcd"
answer= solution.hashCode(key,num)
print("输入key为：",key)
print("输入num为：",num)
print("输出值为：",answer)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
【例280】第一个只出现一次的字符 难度等级★★
3.代码实现
class Solution:
"""
参数str为字符串
返回字符
"""
def firstUniqChar(self, str):
counter = {}
for c in str:
counter[c] = counter.get(c, 0) + 1
for 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
【例281】空格替换 难度等级★★
3.代码实现
class Solution:
# 参数string为字符数组
# 参数length为字符串的真实长度
# 返回新字符串的真实长度
def replaceBlank(self, string, length):
if string is None:
return length
f = 0
L = len(string)
for i in range(len(string)):
if string[i] == ' ':
string[i] = '%20'
f+=1
return 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
【例282】字符串压缩 难度等级★★
3.代码实现
class Solution:
"""
参数originalString为字符串
返回压缩字符串
"""
def compress(self, originalString):
l = len(originalString)
if l <=2 :
return originalString
length = 1
res = ""
for i in range(1,l):
if originalString[i] != originalString[i-1]:
res = res + originalString[i-1] + str(length)
length = 1
else:
length += 1
if originalString[-1] != originalString[-2]:
res = res + originalString[-1] + "1"
else:
res = res + originalString[i-1] + str(length)
if len(originalString)<=len(res):
return originalString
else:
return res
#主函数
if __name__ == '__main__':
solution = Solution()
si = "aabcccccaaa"
arr = list(si)
ans = solution.compress(arr)
print("输入为：", si)
print("输出为：", ans)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
【例283】数组的最大值 难度等级★★
3.代码实现
class Solution:
def max_num(self, arr):
if arr == []:
return
maxnum = arr[0]
for x in arr:
if x > maxnum:
maxnum = x
return maxnum
#主函数
if __name__ == '__main__':
solution = Solution()
arr = [1.0, 2.1, -3.3]
ans = solution.max_num(arr)
print("输入为：", arr)
print("输出为：", ans)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
【例284】无序链表的重复项删除 难度等级★★
3.代码实现
class ListNode(object):
def __init__(self, val):
self.val = val
self.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 = head
seen.add(head.val)
pre = head
head = head.next
pre.next = None
return root
#主函数
if __name__ == '__main__':
solution = Solution()
l0 = ListNode(1)
l1 = ListNode(2)
l2 = ListNode(2)
l3 = ListNode(2)
l0.next = l1
l1.next = l2
l2.next = l3
root = 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")
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
【例285】在O(1)时间复杂度删除链表节点 难度等级★★
3.代码实现
#参数node是要删除的节点
#无返回值，操作完毕
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
def deleteNode(self, node):
if node.next is None:
node = None
return
node.val = node.next.val
node.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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
【例286】将数组重新排序以构造最小值 难度等级★★
3.代码实现
from functools import cmp_to_key
class Solution:
def cmp(self,a,b):
if a+b>b+a:
return 1
if a+b<b+a:
return -1
else:
return 0
def 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【例287】两个链表的交叉 难度等级★★
3.代码实现
#参数list_a是一个链表
#参数list_b是另一个链表
#无返回值，直接打印出结果
class ListNode:
def __init__(self, val=None, next=None):
self.value = val
self.next = next
class Solution:
def get_list_length(self, head):
"""获取链表长度"""
length = 0
while head:
length += 1
head = head.next
return length
def 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_b
if length_a > length_b:
for i in range(length_a - length_b):
cur1 = cur1.next
else:
for i in range(length_b - length_a):
cur2 = cur2.next
flag = False
while cur1 and cur2:
if cur1.value == cur2.value:
print(cur1.value)
flag = True
break
else:
cur1 = cur1.next
cur2 = cur2.next
if 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
【例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)-1
left = 0; right = len(matrix[0])-1
direct = 0; count = 0
while True:
if direct == 0:
for i in range(left, right+1):
count += 1; matrix[up][i] = count
up += 1
if direct == 1:
for i in range(up, down+1):
count += 1; matrix[i][right] = count
right -= 1
if direct == 2:
for i in range(right, left-1, -1):
count += 1; matrix[down][i] = count
down -= 1
if direct == 3:
for i in range(down, up-1, -1):
count += 1; matrix[i][left] = count
left += 1
if count == n*n: return matrix
direct = (direct+1) % 4
#主函数
if __name__ == '__main__':
n=3
solution = Solution()
print("输入是： n = ", n)
print("输出是：",solution.generateMatrix(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
【例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,j
target=S[j]-S[i]
while w<r:
mid=(w +r)//2 #取整数
S_mid=S[mid]
if S_mid>target:
r=mid
else:
w=mid+1
count+=(j-w)
return count
#主函数
if __name__ == '__main__':
generation=[3,4,6,7]
solution= Solution()
print("输入是：", generation)
print("输出是：",solution.triangleCount(generation))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
【例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] = 0
for 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 = 0
for 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=2
maxprofit=solution.maxProfit(k,price)
print("输入价格为：",price)
print("交易次数为：",k)
print("最大利润为：",maxprofit)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
【例291】加一 难度等级★★
3.代码实现
class Solution:
#参数digits为整数数组
#返回整数数组
def plusOne(self, digits):
digits = list(reversed(digits))
digits[0] += 1
i, carry = 0, 0
while i < len(digits):
next_carry = (digits[i] + carry) // 10
digits[i] = (digits[i] + carry) % 10
i, carry = i + 1, next_carry
if 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
【例292】炸弹袭击 难度等级★★
3.代码实现
#参数grid是一个表示二维网格的数组，由'W' 'E' '0'组成
#返回值result是放置一个炸弹后消灭敌人的最大数量
class Solution:
def maxKilledEnemies(self, grid):
m, n = len(grid), 0
if m:
n = len(grid[0])
result, rows = 0, 0
cols = [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 = 0
for k in range(j, n):
if grid[i][k] == 'W':
break
if grid[i][k] == 'E':
rows += 1
if i == 0 or grid[i-1][j] == 'W':
cols[j] = 0
for k in range(i, m):
if grid[k][j] == 'W':
break
if grid[k][j] == 'E':
cols[j] += 1
if 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
【例293】组合总和 IV 难度等级★★
3.代码实现
#参数nums是一个不重复的正整型数组
#参数target是一个整数
#返回值是一个整数，表示组合方式的个数
class Solution:
def backPackVI(self, nums, target):
row = len(nums)
col = target
dp = [0 for i in range(col + 1)]
dp[0] = 1
for j in range(1, col + 1):
for i in range(1, row + 1):
if nums[i - 1] > j:
continue
dp[j] += dp[j - nums[i - 1]]
return dp[-1]
#主函数
if __name__ == '__main__':
generation=[1,2,4]
target=4
solution= Solution()
print("输入是：", generation)
print("输出是：", solution.backPackVI(generation,target))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
【例294】向循环有序链表插入节点 难度等级★★
3.代码实现
#参数node是要插入的链表节点序列
#参数x是一个整数，表示插入的新的节点
#返回值new_node是插入新节点后的链表序列
class ListNode:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
class Solution:
def insert(self, node, x):
new_node = ListNode(x)
if node is None:
node = new_node
node.next = node
return node
#定义当前节点和前一节点
cur, pre = node, None
while cur:
pre = cur
cur = cur.next
# pre.val <= x <= cur.val
if 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 = cur
pre.next = new_node
return new_node
#主函数
if __name__ == '__main__':
k=4
generation = 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
【例295】大岛的数量 难度等级★★
3.代码实现
class Solution:
"""
参数grid为二维布尔数组
参数k为整数
返回岛的数量
"""
def numsofIsland(self, grid, k):
# Write your code here
if not grid or len(grid)==0 or len(grid[0])==0: return 0
rows, cols = len(grid), len(grid[0])
visited = [[False for i in range(cols)] for i in range(rows)]
res = 0
for 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+=1
return res
def bfs(self, grid, visited, x, y, k):
rows, cols = len(grid), len(grid[0])
import collections
queue = collections.deque([(x, y)])
visited[x][y] = True
res = 0
while 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]+idy
if 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: continue
queue.append((x_new, y_new))
visited[x_new][y_new] = True
return 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 = 3
ans = solution.numsofIsland(g, k)
print("输入：", g, "\nk=", k)
print("输出：", ans)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
【例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 False
left += 1
right -= 1
return True
#主函数
if __name__ == '__main__':
solution = Solution()
s = "sdsdlkjsaoio"
ans = solution.convertPalindrome(s)
print("输入：", s)
print("输出：", ans)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
【例297】不同的路径 难度等级★★
3.代码实现
class Solution:
"""
参数grid为二维数组
返回所有唯一加权路径之和
"""
def uniqueWeightedPaths(self, grid):
n=len(grid)
m=len(grid[0])
if n == 0 or m == 0:
return 0
s=[[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=0
for val in s[-1][-1]:
ans+=val
return ans
#主函数
if __name__ == '__main__':
solution = Solution()
arr = [[1,1,2],[1,2,3],[3,2,4]]
ans = solution.uniqueWeightedPaths(arr)
print("输入：", arr)
print("输出：", ans)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
【例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 it
return
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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
【例299】缺失的第一个素数 难度等级★★
3.代码实现
class Solution:
"""
参数nums为数组
返回整数
"""
def firstMissingPrime(self, nums):
if not nums:
return 2
start = 0
l = len(nums)
integer = 2
while start < l:
while self.isPrime(integer) == False:
integer += 1
if nums[start] != integer:
return integer
integer += 1
start += 1
while self.isPrime(integer) == False:
integer += 1
return integer
def isPrime(self, num):
if num == 2 or num == 3:
return True
for i in range(2, int(num**(0.5)) + 1):
if num % i == 0:
return False
return True
if __name__=='__main__':
solution=Solution()
n=[3,5,7]
print("输入为：",n)
print("输出为：",solution.firstMissingPrime(n))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33