一. python3的各种经典案例，总共299个案例，直接可以运行（前：100个案例）
二. python3的各种经典案例，总共299个案例，直接可以运行（中：100个案例）
三. python3的各种经典案例，总共299个案例，直接可以运行（后：99个案例））
【例101】插入区间 难度等级★★
3.代码实现
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
def get(self):
str1 = "(" + str(self.start) + "," + str(self.end) + ")"
return str1
def equals(self, Intervalx):
if self.start == Intervalx.start and self.end == Intervalx.end:
return 1
else:
return 0
class Solution:
#参数intevals: 已排序的非重叠区间列表
#参数newInterval: 新的区间
#返回值: 一个新的排序非重叠区间列表与新的区间
def insert(self, intervals, newInterval):
results = []
insertPos = 0
for interval in intervals:
if interval.end < newInterval.start:
results.append(interval)
insertPos += 1
elif interval.start > newInterval.end:
results.append(interval)
else:
newInterval.start = min(interval.start, newInterval.start)
newInterval.end = max(interval.end, newInterval.end)
results.insert(insertPos, newInterval)
return results
#主函数
if __name__ == '__main__':
solution = Solution()
interval1 = Interval(1,2)
interval2 = Interval(5,9)
interval3 = Interval(2,5)
results = solution.insert([interval1,interval2], interval3)
print("输入：[",interval1.get(),",", interval2.get(),"]","", interval3.get())
print("输出：[", results[0].get(), "]")
【例102】N皇后问题 难度等级★★
3.代码实现
class Solution:
#参数n: 皇后的数量
#返回值: 不同解的总数
total = 0
n = 0
def attack(self, row, col):
for c, r in self.cols.items():
if c - r == col - row or c + r == col + row:
return True
return False
def search(self, row):
if row == self.n:
self.total += 1
return
for col in range(self.n):
if col in self.cols:
continue
if self.attack(row, col):
continue
self.cols[col] = row
self.search(row + 1)
del self.cols[col]
def totalNQueens(self, n):
self.n = n
self.cols = {
}
self.search(0)
return self.total
#主函数
if __name__ == '__main__':
solution = Solution()
solution.totalNQueens(4)
print("输入：", solution.n)
print("输出：", solution.total)
【例103】主元素 难度等级★★
3.代码实现
class Solution:
#参数nums: 整数数组
#返回值: 主元素
def majorityNumber(self, nums):
nums.sort()
i=0;j=0
while i<=len(nums):
j=nums.count(nums[i])
if j>len(nums)//3:
return nums[i]
i+=j
return
#主函数
if __name__ == '__main__':
solution = Solution()
nums = [99,2,99,2,99,3,3]
n = solution.majorityNumber(nums)
print("输入：", "[99,2,99,2,99,3,3]")
print("输出：", n)
【例104】字符大小写排序 难度等级★★
3.代码实现
class Solution:
#参数chars: 需要排序的字母数组
def sortLetters(self, chars):
chars.sort(key=lambda c: c.isupper())
#主函数
if __name__ == '__main__':
solution = Solution()
str1 = "abAcD"
arr = list(str1)
solution.sortLetters(arr)
print("输入：", str1)
print("输出：", ''.join(arr))
【例105】上一个排列 难度等级★★
3.代码实现
class Solution:
#参数num: 整数列表
#参数: 整数列表
def previousPermuation(self, num):
for i in range(len(num)-2, -1, -1):
if num[i] > num[i+1]:
break
else:
num.reverse()
return num
for j in range(len(num)-1, i, -1):
if num[j] < num[i]:
num[i], num[j] = num[j], num[i]
break
for j in range(0, (len(num) - i)//2):
num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]
return num
#主函数
if __name__ == '__main__':
solution = Solution()
num = [1,3,2,3]
num1 = solution.previousPermuation(num)
print("输入：", "[1,3,2,3]")
print("输出：", num1)
【例106】下一个排列 难度等级★★
3.代码实现
class Solution:
#参数num: 整数列表
#返回值: 整数列表
def nextPermutation(self, num):
for i in range(len(num)-2, -1, -1):
if num[i] < num[i+1]:
break
else:
num.reverse()
return num
for j in range(len(num)-1, i, -1):
if num[j] > num[i]:
num[i], num[j] = num[j], num[i]
break
for j in range(0, (len(num) - i)//2):
num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]
return num
#主函数
if __name__ == '__main__':
solution = Solution()
num = [1,3,2,3]
num1 = solution.nextPermutation(num)
print("输入：", "[1, 3, 2, 3]")
print("输出：", num1)
【例107】二叉树的层次遍历 难度等级★★
3.代码实现
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val=val
self.left=left #左子树
self.right=right #右子树
class Solution:
#参数root: 二叉树的根
#返回值:从底向上的层次序遍历
def levelOrderBottom(self, root):
self.results = []
if not root:
return self.results
q = [root]
while q:
new_q = []
self.results.append([n.val for n in q])
for node in q:
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
q = new_q
return list(reversed(self.results))
#主函数
if __name__ == '__main__':
solution = Solution()
root=TreeNode(1,TreeNode(2),TreeNode(3))
results = solution.levelOrderBottom(root)
print("输入： {1,2,3}")
print("输出：", results)
【例108】最长公共子串 难度等级★★
3.代码实现
class Solution:
#参数A, B: 两个字符串
#返回值: 最长公共子串的长度
def longestCommonSubstring(self, A, B):
ans = 0
for i in range(len(A)):
for j in range(len(B)):
l = 0
while i + l < len(A) and j + l < len(B) \
and A[i + l] == B[j + l]:
l += 1
if l > ans:
ans = l
return ans
#主函数
if __name__ == '__main__':
solution = Solution()
A = "ABCD"
B = "CBCE"
ans = solution.longestCommonSubstring(A, B)
print("输入：","A =",A,"B =",B)
print("输出：", ans)
【例109】最近公共祖先 难度等级★★
3.代码实现
#Definition of TreeNode:
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val=val
self.left=left #左子树
self.right=right #右子树
class Solution:
#参数root: 二叉搜索树的根
#参数A: 二叉树的一个节点
#参数B: 二叉树的一个节点
#返回值: 返回两个节点的最低公共祖先(LCA)
def lowestCommonAncestor(self, root, A, B):
# A且其下面有B => A
# B且其下面有A => B
# A且其下面啥都没有 => A
# B且其下面啥都有 => B
if root is None:
return None
if root == A or root == B:
return root
left_result = self.lowestCommonAncestor(root.left, A, B)
right_result = self.lowestCommonAncestor(root.right, A, B)
# A 和 B 一边一个
if left_result and right_result:
return root
# 左子树有一个点或者左子树有LCA
if left_result:
return left_result
# 右子树有一个点或者右子树有LCA
if right_result:
return right_result
# 左右子树啥都没有
return None
#主函数
if __name__ == '__main__':
tree = TreeNode(4, TreeNode(3), TreeNode(7, TreeNode(5), TreeNode(6)))
solution = Solution()
result = solution.lowestCommonAncestor(tree, tree.left, tree.right.left)
print("输入：{4,3,7,#,#,5,6}, LCA(3,5)")
print("输出：", result.val)
【例110】k数和 难度等级★★
3.代码实现
class Solution:
def kSumII(self, A, k, target):
anslist = []
self.dfs(A, k, target, 0, [], anslist)
return anslist
def dfs(self, A, k, target, index, onelist, anslist):
if target == 0 and k == 0:
anslist.append(onelist)
return
if len(A) == index or target < 0 or k < 0:
return
self.dfs(A, k, target, index + 1, onelist, anslist)
self.dfs(A, k - 1, target - A[index], index + 1 , onelist + [A[index]], anslist)
#主函数
if __name__ == '__main__':
solution = Solution()
A = [1,2,3,4]
k = 2
target = 5
anslist = solution.kSumII(A, k, target)
print("输入：A = [1,2,3,4] k = 2 target = 5")
print("输出：", anslist)
【例111】有序链表转换为二分查找树 难度等级★★
3.代码实现
#定义链表节点
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
#定义树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
#参数head: 链表的第一个节点
#返回值: 树节点
def sortedListToBST(self, head):
num_list = []
while head:
num_list.append(head.val)
head = head.next
return self.create(num_list, 0, len(num_list) - 1)
def create(self, nums, start, end):
if start > end:
return None
if start == end:
return TreeNode(nums[start])
root = TreeNode(nums[(start + end) // 2])
root.left = self.create(nums, start, (start + end) // 2 - 1) #注意是-1
root.right = self.create(nums, (start + end) // 2 + 1, end)
return root
#主函数
if __name__ == '__main__':
solution = Solution()
listnode = ListNode(1, ListNode(2, ListNode(3)))
root = solution.sortedListToBST(listnode)
print("输入： 1=>2=>3")
print("输出：", "{", root.val, root.left.val, root.right.val, "}")
【例112】最长连续序列 难度等级★★
3.代码实现
```ruby
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()
num = [100, 4, 200, 1, 3, 2]
ans = solution.longestConsecutive(num)
print("输入：", num)
print("输出：", ans)
【例113】背包问题 难度等级★★
3.代码实现
class Solution:
#参数m: 整数m表示背包的大小
#参数A & V: 给定n个大小为A[i]和值V[i]的物品
def backPackII(self, m, A, V):
f = [0 for i in range(m+1)]
n = len(A)
for i in range(n):
for j in range(m, A[i]-1, -1):
f[j] = max(f[j] , f[j-A[i]] + V[i])
return f[m]
#主函数
if __name__ == '__main__':
solution = Solution()
m = 100
A = [77,22,29,50,99]
V = [92,22,87,46,90]
result = solution.backPackII(m, A, V)
print("输入：\n","m = ",m, "\n A = ", A, "\n V = ",V)
print("输出：", result)
【例114】拓扑排序 难度等级★★
3.代码实现
#定义有向图节点
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
#参数graph: 有向图节点列表
#返回值: 整数列表
def topSort(self, graph):
indegree = {
}
for x in graph:
indegree[x] = 0
for i in graph:
for j in i.neighbors:
indegree[j] += 1
ans = []
for i in graph:
if indegree[i] == 0:
self.dfs(i, indegree, ans)
return ans
def dfs(self, i, indegree, ans):
ans.append(i.label)
indegree[i] -= 1
for j in i.neighbors:
indegree[j] -= 1
if indegree[j] == 0:
self.dfs(j, indegree, ans)
#主函数
if __name__ == '__main__':
solution = Solution()
g0 = DirectedGraphNode(0)
g1 = DirectedGraphNode(1)
g2 = DirectedGraphNode(2)
g3 = DirectedGraphNode(3)
g4 = DirectedGraphNode(4)
g5 = DirectedGraphNode(5)
g0.neighbors = [g1, g2, g3]
g1.neighbors = [g4]
g2.neighbors = [g4, g5]
g3.neighbors = [g4, g5]
graph = [g0, g1, g2, g3, g4, g5]
result = solution.topSort(graph)
print("输入：如样例图")
print("输出：",result)
【例115】克隆图 难度等级★★
3.代码实现
#定义无向图节点
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
def __init__(self):
self.dict = {
}
#参数node: 无向图节点
#返回值: 无向图节点
def cloneGraph(self, node):
if node is None:
return None
if node.label in self.dict:
return self.dict[node.label]
root = UndirectedGraphNode(node.label)
self.dict[node.label] = root
for item in node.neighbors:
root.neighbors.append(self.cloneGraph(item))
return root
#主函数
if __name__ == '__main__':
solution = Solution()
g0 = UndirectedGraphNode(0)
g1 = UndirectedGraphNode(1)
g2 = UndirectedGraphNode(2)
g0.neighbors = [g1, g2]
g1.neighbors = [g2]
g2.neighbors = [g2]
ans = solution.cloneGraph(g0)
a = [ans.label, ans.neighbors[0].label, ans.neighbors[1].label,
ans.neighbors[0].neighbors[0].label, ans.neighbors[1].neighbors[0].label]
print("输入： {0,1,2#1,2#2,2}")
print("输出：", a)
【例116】不同的二叉查找树 难度等级★★
3.代码实现
class Solution:
#参数n: 整数
#返回值: 整数
def numTrees(self, n):
dp = [1, 1, 2]
if n <= 2:
return dp[n]
else:
dp += [0 for i in range(n-2)]
for i in range(3, n + 1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
#主函数
if __name__ == '__main__':
solution = Solution()
n = 3
ans = solution.numTrees(n)
print("输入：", n)
print("输出：", ans)
【例117】汉诺塔 难度等级★★
3.代码实现
class Solution:
def move(self, n, a, b, c, ans): #n为圆盘数，a代表初始位圆柱，b代表过渡位圆柱，c代表目标位圆柱
if n==1:
ans.append("from “+a+” to "+c)
else:
self.move(n-1,a,c,b,ans)
ans.append("from “+a+” to "+c)
self.move(n-1,b,a,c,ans)
return ans
#主函数
if name == ‘main’:
solution = Solution()
ans = []
res = solution.move(3, ‘A’, ‘B’, ‘C’, ans)
print(“输入： 3, ‘A’, ‘B’, ‘C’”)
print(“输出：”, res)
【例118】图中两个点之间的路线 难度等级★★
3.代码实现
#定义有向图节点
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
def dfs(self, i, countrd, graph, t):
if countrd[i] == 1:
return False
if i == t:
return True
countrd[i] = 1
for j in i.neighbors:
if countrd[j] == 0 and self.dfs(j, countrd, graph, t):
return True
return False
#参数graph: 有向图节点列表
#参数s: 起始有向图节点
#参数t: 终端有向图节点
#返回值: 布尔值
def hasRoute(self, graph, s, t):
countrd = {
}
for x in graph:
countrd[x] = 0
return self.dfs(s, countrd, graph, t)
#主函数
if __name__ == '__main__':
solution = Solution()
gA = DirectedGraphNode('A')
gB = DirectedGraphNode('B')
gC = DirectedGraphNode('C')
gD = DirectedGraphNode('D')
gE = DirectedGraphNode('E')
gA.neighbors = [gB, gD]
gB.neighbors = [gC, gD]
gD.neighbors = [gE]
graph = [gA, gB, gC, gD, gE]
ans = solution.hasRoute(graph, gB, gE)
print("输入： {A,B,C,D,E,A#B,A#D,B#C,B#D,D#E}, B, E")
print("输出：", ans)
【例119】丢失的第一个正整数 难度等级★★
3.代码实现
class Solution:
#参数A：整数数组
#返回值：整数
def firstMissingPositive(self, A):
n = len(A)
i = 0
if n == 0:
return 1
while i < n:
while A[i]!=i+ 1 and A[i] <= n and A[i] > 0 and A[i] != A[A[i] - 1]:
t = A[i]
A[i] = A[A[i] - 1]
A[t - 1] = t
i = i + 1
for i in range(n):
if A[i] != i + 1: return i + 1
return n + 1
#主函数
if __name__ == '__main__':
solution = Solution()
A = [3,4,-1,1]
ans = solution.firstMissingPositive(A)
print("输入：", A)
print("输出：", ans)
【例120】寻找缺失的数 难度等级★★
3.代码实现
class Solution:
def findMissing(self, nums):
if not nums:
return 0
sum = 0
for _ in nums:
sum += _
return int((len(nums) * (len(nums) + 1) / 2)) - sum
#主函数
if __name__ == '__main__':
solution = Solution()
nums = [0,1,3]
ans = solution.findMissing(nums)
print("输入：", nums)
print("输出：", ans)
【例121】排列序号I 难度等级★★
3.代码实现
class Solution:
#参数A: 整数数组
#返回值: 整数
def permutationIndex(self, A):
result = 1
factor = 1
for i in range(len(A)-1, -1, -1):
rank = 0
for j in range(i+1, len(A)):
if A[i] > A[j]:
rank +=1
result += factor*rank
factor *= len(A)-i
return result
#主函数
if __name__ == '__main__':
solution = Solution()
A = [3,2,1]
ans = solution.permutationIndex(A)
print("输入：", A)
print("输出：", ans)
【例122】排列序号II 难度等级★★
3.代码实现
class Solution:
#参数A: 整数数组
#返回值: 长整数
def permutationIndexII(self, A):
if A is None or len(A) == 0:
return 0
index, factor, multi_fact = 1, 1, 1
counter = {
}
for i in range(len(A) - 1, -1, -1):
counter[A[i]] = counter.get(A[i], 0) + 1
multi_fact *= counter[A[i]]
count = 0
for j in range(i + 1, len(A)):
if A[i] > A[j]:
count += 1
index += count * factor // multi_fact
factor *= (len(A) - i)
return index
#主函数
if __name__ == '__main__':
solution = Solution()
A = [1,4,2,2]
ans = solution.permutationIndexII(A)
print("输入：", A)
print("输出：", ans)
【例123】最多有k个不同字符的最长子字符串 难度等级★★
3.代码实现
#参数s是一个字符串
#返回值res是最长字符串的长度
class Solution:
def lengthOfLongestSubstring(self, s):
res = 0
if s is None or len(s) == 0:
return res
d = {
}
tmp = 0
start = 0
for i in range(len(s)):
if s[i] in d and d[s[i]] >= start:
start = d[s[i]] + 1
tmp = i - start + 1
d[s[i]] = i
res = max(res, tmp)
return res
#主函数
if __name__ == '__main__':
generator = 'eceba'
solution = Solution()
print("输入：", generator)
print("输出：", solution. lengthOfLongestSubstring(generator))
【例124】第k个排列 难度等级★★
3.代码实现
#参数n是指1~n
#参数k是指所有全排列中的第几个
#返回值是第k个全排列
class Solution:
def getPermutation(self, n, k):
fac = [1]
for i in range(1, n + 1):
fac.append(fac[-1] * i)
elegible = list(range(1, n + 1))
per = []
for i in range(n):
digit = (k - 1) // fac[n - i - 1]
per.append(elegible[digit])
elegible.remove(elegible[digit])
k = (k - 1) % fac[n - i - 1] + 1
return "".join([str(x) for x in per])
#主函数
if __name__ == '__main__':
k=4
n=3
solution = Solution()
print("输入：", "n=",n,"k=",k)
print("输出：", solution.getPermutation(n,k))
【例125】数飞机 难度等级★★
3.代码实现
#参数start是开始时间
#参数end是结束时间
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
#参数airplanes是一个由时间间隔对象组成的数组
#返回值max_number_of_airplane是飞机的最大数
class Solution:
def countOfAirplanes(self, airplanes):
points = []
for airplane in airplanes:
points.append([airplane.start, 1])
points.append([airplane.end, -1])
number_of_airplane, max_number_of_airplane = 0, 0
for _, count_delta in sorted(points):
number_of_airplane += count_delta
max_number_of_airplane = max(max_number_of_airplane,
number_of_airplane)
return max_number_of_airplane
#主函数
if __name__ == '__main__':
generator=[Interval(1,10),Interval(5,8),Interval(2,3),Interval(4,7)]
solution = Solution()
print("输入：",[(1, 10), (2, 3), (5, 8), (4, 7)] )
print("输出：", solution.countOfAirplanes(generator))
【例126】格雷编码 难度等级★★
3.代码实现
#参数n是一个整型数
#返回值seq是所对应的格雷编码
class Solution：
def grayCode(self, n):
if n == 0:
return [0]
result = self.grayCode(n - 1)
seq = list(result)
for i in reversed(result):
seq.append((1 << (n - 1)) | i)
return seq
#主函数
if __name__ == '__main__':
generator=2
solution = Solution()
print("输入：", generator)
print("输出：", solution. grayCode(generator))
【例127】迷你Cassandra 难度等级★★
3.代码实现
#参数raw_key是一个字符串，用于哈希
#参数column_key是一个整数，支持范围查询
#参数column_value是储存字符串的值
#参数column_start是开始位置
#参数column_start是结束位置
#返回值rt是一个由Column对象组成的列表
class Column:
def __init__(self, key, value):
self.key = key
self.value = value
from collections import OrderedDict
class Solution:
def __init__(self):
self.hash = {
}
def insert(self, raw_key, column_key, column_value):
if raw_key not in self.hash:
self.hash[raw_key] = OrderedDict()
self.hash[raw_key][column_key] = column_value
def query(self, raw_key, column_start, column_end):
rt = []
if raw_key not in self.hash:
return rt
self.hash[raw_key] = OrderedDict(sorted(self.hash[raw_key].items()))
for key, value in self.hash[raw_key].items():
if key >= column_start and key <= column_end:
rt.append(Column(key, value))
return rt
#主函数
if __name__ == '__main__':
generator = Column(1, "abcd")
generator1 = Column(2, "hijk")
solution = Solution()
solution.insert("google",generator.key,generator.value)
solution.insert("google",generator1.key,generator1.value)
ls = solution.query("google", 0, 2)
print('输入: query("google", 0, 2)')
print("输出: ")
for i in ls:
print(i.key,i.value)
【例128】网络日志 难度等级★★
3.代码实现
#参数timestamp是个整数，建立一个时间点
#返回值是个整数，表示最后五分钟时间点的个数
class WebLogger:
def __init__(self):
self.Q = []
def hit(self, timestamp):
self.Q.append(timestamp)
def get_hit_count_in_last_5_minutes(self, timestamp):
if self.Q == []:
return 0
i = 0
n = len(self.Q)
while i < n and self.Q[i] + 300 <= timestamp:
i += 1
self.Q = self.Q[i:]
return len(self.Q)
#主函数
if __name__ == '__main__':
solution = WebLogger()
print("输入：hit(1),hit(2) ")
solution.hit(1)
solution.hit(2)
print("输出最后5分钟时间戳个数：")
print(solution.get_hit_count_in_last_5_minutes(3))
print("输入：hit(300) ")
solution.hit(300)
print("输出最后5分钟时间戳个数：")
print(solution.get_hit_count_in_last_5_minutes(300))
print("输出最后5分钟时间戳个数：")
print(solution.get_hit_count_in_last_5_minutes(301))
【例129】栅栏染色 难度等级★★
3.代码实现
#参数n是个非负整数，柱子数
#参数n是个非负整数，颜色数
#返回值是个整数，所有的染色方案
class Solution:
def numWays(self, n, k):
dp = [0, k, k * k]
if n <= 2:
return dp[n]
if k == 1 and n >= 3:
return 0
for i in range(2, n):
dp.append((k - 1) * (dp[-1] + dp[-2]))
return dp[-1]
#主函数
if __name__ == '__main__':
solution= Solution()
n=3
k=2
print("输入： n=",n ,"k=",k)
print("输出：",solution.numWays(n,k))
【例130】房屋染色 难度等级★★
3.代码实现
#参数costs是个nx3矩阵
#返回值是个整数，刷完所有房子最小花费
class Solution:
def minCost(self, costs):
n = len(costs)
if n == 0:
return 0
INF = 0x7fffffff
f = [costs[0], [INF, INF, INF]]
for i in range(1, n):
for j in range(3):
f[i&1][j] = INF
for k in range(3):
if j != k:
f[i&1][j] = min(f[i&1][j], f[(i+1)&1][k] + costs[i][j])
return min(f[(n-1)&1])
#主函数
if __name__ == '__main__':
generator=[[14,2,11],[11,14,5],[14,3,10]]
solution= Solution()
print("输入： ",generator)
print("输出： ",solution.minCost(generator))
【例131】去除重复元素 难度等级★★
3.代码实现
#参数nums是个一个整型数组
#返回值result是不重复元素的个数
class Solution:
def deduplication(self, nums):
n = len(nums)
if n == 0:
return 0
nums.sort()
result = 1
for i in range(1, n):
if nums[i - 1] != nums[i]:
nums[result] = nums[i]
result += 1
return result
#主函数
if __name__ == '__main__':
generator=[1,3,1,4,4,2]
solution= Solution()
print("输入：",generator)
print("输出：",solution.deduplication(generator))
【例132】左填充 难度等级★★
3.代码实现
#参数originalStr是需要添加的字符串
#参数size是目标长度
#参数padchar是在字符串左边填充的字符
#返回值是左填充后的字符串
class StringUtils:
def leftPad(self, originalStr, size, padChar=' '):
return padChar * (size - len(originalStr)) + originalStr
#主函数
if __name__ == '__main__':
size=8
generator = "foobar"
solution= StringUtils()
print("输入:",generator)
print("输出:",solution.leftPad(generator,size))
【例133】负载均衡器 难度等级★★
3.代码实现
#参数server_id是一个服务器的ID
#返回值是一个ID，集群中随机的一个服务器ID
class LoadBalancer:
def __init__(self):
self.server_ids = []
self.id2index = {
}
def add(self, server_id):
if server_id in self.id2index:
return
self.server_ids.append(server_id)
self.id2index[server_id] = len(self.server_ids) - 1
def remove(self, server_id):
if server_id not in self.id2index:
return
# remove the server_id
index = self.id2index[server_id]
del self.id2index[server_id]
# overwrite the one to be removed
last_server_id = self.server_ids[-1]
self.id2index[last_server_id] = index
self.server_ids[index] = last_server_id
self.server_ids.pop()
def pick(self):
import random
index = random.randint(0, len(self.server_ids) - 1)
return self.server_ids[index]
#主函数
if __name__ == '__main__':
solution= LoadBalancer()
solution.add(1)
solution.add(2)
solution.remove(1)
print("输入: \nadd(1)\nadd(2)\nremove(1)")
print("输出:",solution.pick())
print("输出:",solution.pick())
【例134】两数和的最接近值 难度等级★★
3.代码实现
#参数nums是个整数数组
#参数target是一个整数
#返回值diff是target和两数求和的差距
import sys
class Solution:
def twoSumClosest(self, nums, target):
nums.sort()
i, j = 0, len(nums) - 1
diff = sys.maxsize
while i < j:
if nums[i] + nums[j] < target:
diff = min(diff, target - nums[i] - nums[j])
i += 1
else:
diff = min(diff, nums[i] + nums[j] - target)
j -= 1
return diff
#主函数
if __name__ == '__main__':
generator = [-1,2,-1,4]
solution= Solution()
target = 4
print("target =",target)
print("输入：",generator)
print("输出:",solution.twoSumClosest(generator,target))
【例135】打劫房屋 难度等级★★
3.代码实现
#参数nums是个非负整数列表，表示每个房子中存放的钱
#返回值是个整数，表示可以拿到的钱
class Solution:
def houseRobber2(self, nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0], dp[1] = 0, nums[1]
for i in range(2, n):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
answer = dp[n - 1]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, n - 1):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return max(dp[n - 2], answer)
#主函数
if __name__ == '__main__':
generator = [2,3,2,3]
solution= Solution()
print("输入:",generator)
print("输出:",solution.houseRobber2(generator))
【例136】左旋右旋迭代器 难度等级★★
3.代码实现
#参数v1，v2表示两个一维向量
#返回值是一个一维数组，交替返回v1，v2元素
class ZigzagIterator:
def __init__(self, v1, v2):
self.queue = [v for v in (v1, v2) if v]
def next(self):
v = self.queue.pop(0)
value = v.pop(0)
if v:
self.queue.append(v)
return value
def hasNext(self):
return len(self.queue) > 0
#主函数
if __name__ == '__main__':
v1= [1,2]
v2= [3,4,5,6]
print("输入:")
print(",".join(str(i) for i in v1))
print(",".join(str(i) for i in v2))
solution, result = ZigzagIterator(v1, v2), []
while solution.hasNext():
result.append(solution.next())
print("输出:",result)
【例137】N数组第K大元素 难度等级★★
3.代码实现
import heapq
#参数arrays一个数组列表
#参数k表示第k大
#返回值num是列表中最大的数
class Solution:
def KthInArrays(self, arrays, k):
if not arrays:
return None
# in order to avoid directly changing the original arrays
# and remove the empty arrays, we need a new sortedArrays
sortedArrays = []
for arr in arrays:
if not arr:
continue
sortedArrays.append(sorted(arr, reverse=True))
maxheap = [
(-arr[0], index, 0)
for index, arr in enumerate(sortedArrays)
]
heapq.heapify(maxheap)
num = None
for _ in range(k):
num, x, y = heapq.heappop(maxheap)
num = -num
if y + 1 < len(sortedArrays[x]):
heapq.heappush(maxheap, (-sortedArrays[x][y + 1], x, y + 1))
return num
#主函数
if __name__ == '__main__':
generator = [[2,3,2,4],[3,4,7,9]]
k=5
solution= Solution()
print("输入:",generator)
print("k= ",k)
print("输出:",solution.KthInArrays(generator,k))
【例138】前K大数 难度等级★★
3.代码实现
import heapq
#参数nums是个整数数组
#参数k表示第k大
#返回值是个整型数组，前k大的整数组成
class Solution:
def topk(self, nums, k):
heapq.heapify(nums)
topk = heapq.nlargest(k, nums)
topk.sort()
topk.reverse()
return topk
#主函数
if __name__ == '__main__':
generator = [8, 7, 6, 5, 4, 3, 2, 1]
k=4
solution= Solution()
print("输入:",generator)
print("k=",k)
print("输出:",solution.topk(generator,k))
【例139】计数型布隆过滤器 难度等级★★
3.代码实现
import random
#参数str是个字符串，表示一个word
#返回值是个布尔值，若该word存在返回True，否则返回False
class HashFunction:
def __init__(self, cap, seed):
self.cap = cap
self.seed = seed
def hash(self, value):
ret = 0
for i in value:
ret += self.seed * ret + ord(i)
ret %= self.cap
return ret
class CountingBloomFilter:
def __init__(self, k):
self.hashFunc = []
for i in range(k):
self.hashFunc.append(HashFunction(random.randint(10000, 20000), i * 2 + 3))
self.bits = [0 for i in range(20000)]
def add(self, word):
for f in self.hashFunc:
position = f.hash(word)
self.bits[position] += 1
def remove(self, word):
for f in self.hashFunc:
position = f.hash(word)
self.bits[position] -= 1
def contains(self, word):
for f in self.hashFunc:
position = f.hash(word)
if self.bits[position] <= 0:
return False
return True
#主函数
if __name__ == '__main__':
solution= CountingBloomFilter(3)
solution.add("long")
solution.add("term")
print('输入:')
print('add("long")')
print('add("term")')
print('contains("long")')
print("输出:",solution.contains("long"))
solution.remove("long")
print('remove("long")')
print('contains("long")')
print("输出:",solution.contains("long"))
【例140】字符计数 难度等级★★
3.代码实现
#参数str一个任意的字符串
#返回值map是个哈希map
class Solution:
def countCharacters(self, str):
map = dict()
for c in str:
map[c] = map.get(c, 0) + 1
return map
#主函数
if __name__ == '__main__':
generator="abca"
solution = Solution()
print('输入:',generator)
print("输出:",solution.countCharacters(generator))
【例141】最长重复子序列 难度等级★★
3.代码实现
#参数str是个任意字符串
#返回值是个整数表示这个字符串最长重复的子序列长度
class Solution:
def longestRepeatingSubsequence(self, str):
n = len(str)
dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if str[i - 1] == str[j - 1] and i != j:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[n][n]
#主函数
if __name__ == '__main__':
solution = Solution()
generator="abcaa"
print('输入：',generator)
print("输出：",solution. longestRepeatingSubsequence(generator))
【例142】僵尸矩阵 难度等级★★
3.代码实现
import collections
#参数grid是一个二维整数矩阵
#返回值是个整数，表示需要的天数，若不能完成则返回-1
class Solution:
def zombie(self, grid):
if len(grid) == 0 or len(grid[0]) == 0:
return 0
m, n = len(grid), len(grid[0])
queue = collections.deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
queue.append((i, j))
day = 0
while queue:
size = len(queue)
day += 1
for k in range(size):
(i, j) = queue.popleft()
DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for (di, dj) in DIR:
next_i, next_j = i + di, j + dj
if next_i < 0 or next_i >= m or next_j < 0 or next_j >= n:
continue
if grid[next_i][next_j] == 1 or grid[next_i][next_j] == 2:
continue
grid[next_i][next_j] = 1
queue.append((next_i, next_j))
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
return -1
return day - 1
#主函数
if __name__ == '__main__':
solution = Solution()
generator=[[0,0,0],
[0,0,0],
[0,0,1]]
print("输入：",generator)
print("输出：",solution. zombie(generator))
【例143】摊平二维向量 难度等级★★
3.代码实现
class Vector2D(object):
def __init__(self, vec2d):
self.vec2d = vec2d
self.row, self.col = 0, -1
self.next_elem = None
def next(self):
if self.next_elem is None:
self.hasNext()
temp, self.next_elem = self.next_elem, None
return temp
def hasNext(self):
if self.next_elem:
return True
self.col += 1
while self.row < len(self.vec2d)and self.col>= len(self.vec2d[self.row]):
self.row += 1
self.col = 0
if self.row < len(self.vec2d) and self.col < len(self.vec2d[self.row]):
self.next_elem = self.vec2d[self.row][self.col]
return True
return False
#主函数
if __name__ == '__main__':
inputnum=[[1,2],[3],[4,5,6]]
vector2d=Vector2D(inputnum)
print("输入：",inputnum)
print("输出：")
print(vector2d.next())
while vector2d.hasNext():
print(vector2d.next())
【例144】第K大的元素 难度等级★★
3.代码实现
class Solution:
# nums是整型数组
# k是整数
# 返回数组第k大的元素
def kthLargestElement2(self, nums, k):
import heapq
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heapq.heappop(heap)
#主函数
if __name__ == '__main__':
inputnum=[9,3,2,4,8]
k=3
print("输入数组：",inputnum)
print("输入k=",k)
solution=Solution()
print("输出：",solution.kthLargestElement2(inputnum,k))
【例145】两数和小于或等于目标值 难度等级★★
3.代码实现
class Solution:
# 参数nums是整数数组
# 参数target是整数
# 返回整数
def twoSum5(self, nums, target):
l, r = 0, len(nums)-1
cnt = 0
nums.sort()
while l < r:
value = nums[l] + nums[r]
if value > target:
r -= 1
else:
cnt += r - l
l += 1
return cnt
#主函数
if __name__ == '__main__':
inputnum= [2, 7, 11, 15]
target=24
solution=Solution()
print("输入数组：",inputnum)
print("输入target：",target)
solution=Solution()
print("输出：",solution.twoSum5(inputnum,target))
【例146】两数差等于目标值 难度等级★★
3.代码实现
class Solution:
#参数nums是整数数组
#参数target是整数
#返回数组的索引值加1，[index1 + 1, index2 + 1] (index1 < index2)
def twoSub(self, nums, target):
nums = [(num, i) for i, num in enumerate(nums)]
target = abs(target)
n, indexs = len(nums), []
nums = sorted(nums, key=lambda x: x[0])
j = 0
for i in range(n):
if i == j:
j += 1
while j < n and nums[j][0] - nums[i][0] < target:
j += 1
if j < n and nums[j][0] - nums[i][0] == target:
indexs = [nums[i][1] + 1, nums[j][1] + 1]
if indexs[0] > indexs[1]:
indexs[0], indexs[1] = indexs[1], indexs[0]
return indexs
#主函数
if __name__ == '__main__':
inputnum= [2, 7, 15, 24]
target=5
solution=Solution()
print("输入数组：",inputnum)
print("输入target：",target)
print("输出：",solution.twoSub(inputnum,target))
【例147】骑士的最短路线 难度等级★★
3.代码实现
import collections
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
DIRECTIONS = [
(-2, -1), (-2, 1), (-1, 2), (1, 2),
(2, 1), (2, -1), (1, -2), (-1, -2),
]
class Solution:
#参数grid表示棋盘
#参数source表示起点
#参数destination表示终点
#返回最短路径长度
def shortestPath(self, grid, source, destination):
queue = collections.deque([(source.x, source.y)])
distance = {
(source.x, source.y): 0}
while queue:
x, y = queue.popleft()
if (x, y) == (destination.x, destination.y):
return distance[(x, y)]
for dx, dy in DIRECTIONS:
next_x, next_y = x + dx, y + dy
if (next_x, next_y) in distance:
continue
if not self.is_valid(next_x, next_y, grid):
continue
distance[(next_x, next_y)] = distance[(x, y)] + 1
queue.append((next_x, next_y))
return -1
def is_valid(self, x, y, grid):
n, m = len(grid), len(grid[0])
if x < 0 or x >= n or y < 0 or y >= m:
return False
return not grid[x][y]
#主函数
if __name__ == '__main__':
inputnum=[[0,0,0],
[0,0,0],
[0,0,0]]
source = Point(2,0)
destination = Point(2,2)
solution=Solution()
print("输入棋盘：",inputnum)
print("输入起点：[2,0]")
print("输入终点：[2,2]")
print("输出步数：",solution.shortestPath(inputnum,source,destination))
【例148】K个最近的点 难度等级★★
3.代码实现
import heapq
import numpy as np
np.set_printoptions(threshold=np.inf)
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
class Solution:
#参数points为坐标点列表
#参数origin为初始点
#参数k为整数
#返回k个最邻近点
def kClosest(self, points, origin, k):
self.heap = []
for point in points:
dist = self.getDistance(point, origin)
heapq.heappush(self.heap, (-dist, -point.x, -point.y))
if len(self.heap) > k:
heapq.heappop(self.heap)
ret = []
while len(self.heap) > 0:
_, x, y = heapq.heappop(self.heap)
ret.append(Point(-x, -y))
ret.reverse()
return ret
def getDistance(self, a, b):
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2
#主函数
if __name__=='__main__':
a1=Point(0,0)
a2=Point(0,9)
inputnum=[a1,a2]
origin=Point(0,0)
k=1
solution=Solution()
rp=Point(0,0)
rp=solution.kClosest(inputnum,origin,k)
array=[[rp[0].x,rp[0].y]]
print("输入坐标点：[[0,0],[0,9]]")
print("最近坐标数：k=1")
print("输出坐标点：",array)
【例149】优秀成绩 难度等级★★
3.代码实现
class Record:
def __init__(self, id, score):
self.id = id
self.score = score
class Solution:
# @param {Record[]} results a list of <student_id, score>
# @return {dict(id, average)} find the average of 5 highest scores for each person
# <key, value> (student_id, average_score)
def highFive(self, results):
# Write your code here
hash = dict()
for r in results:
if r.id not in hash:
hash[r.id] = []
hash[r.id].append(r.score)
if len(hash[r.id]) > 5:
index = 0
for i in range(1, 6):
if hash[r.id][i] < hash[r.id][index]:
index = i
hash[r.id].pop(index)
answer = dict()
for id, scores in hash.items():
answer[id] = sum(scores) / 5.0
return answer
#主函数
if __name__=='__main__':
r1=Record(1,90)
r2=Record(1,93)
r3=Record(2,93)
r4=Record(2,99)
r5=Record(2,98)
r6=Record(2,97)
r7=Record(1,62)
r8=Record(1,56)
r9=Record(2,95)
r10=Record(1,61)
list=[r1,r2,r3,r4,r5,r6,r7,r8,r9,r10]
solution=Solution()
print(solution.highFive(list))
【例150】二叉树的最长连续子序列I 难度等级★★
3.代码实现
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
#参数root是二叉树的根节点
#返回最长连续序列路径的长度
def longestConsecutive2(self, root):
max_len, _, _, = self.helper(root)
return max_len
def helper(self, root):
if root is None:
return 0, 0, 0
left_len, left_down, left_up = self.helper(root.left)
right_len, right_down, right_up = self.helper(root.right)
down, up = 0, 0
if root.left is not None and root.left.val + 1 == root.val:
down = max(down, left_down + 1)
if root.left is not None and root.left.val - 1 == root.val:
up = max(up, left_up + 1)
if root.right is not None and root.right.val + 1 == root.val:
down = max(down, right_down + 1)
if root.right is not None and root.right.val - 1 == root.val:
up = max(up, right_up + 1)
len = down + 1 + up
len = max(len, left_len, right_len)
return len, down, up
#主函数
if __name__=='__main__':
inputnum={
1,2,0,3}
root0=TreeNode(0)
root1=TreeNode(1)
root2=TreeNode(2)
root3=TreeNode(3)
root1.left=root2
root1.right=root0
root2.left=root3
solution=Solution()
print("输入：",inputnum)
print("输出：",solution.longestConsecutive2(root1))
【例151】二叉树的最长连续子序列II 难度等级★★
3.代码实现
# 定义一个多节点的树
class MultiTreeNode(object):
def __init__(self, x):
self.val = x
self.children = [] # children 是 MultiTreeNode 的list
class Solution:
# 参数root为k叉树
# 返回最长连续序列路径的长度
def longestConsecutive3(self, root):
max_len, _, _, = self.helper(root)
return max_len
def helper(self, root):
if root is None:
return 0, 0, 0
max_len, up, down = 0, 0, 0
for child in root.children:
result = self.helper(child)
max_len = max(max_len, result[0])
if child.val + 1 == root.val:
down = max(down, result[1] + 1)
if child.val - 1 == root.val:
up = max(up, result[2] + 1)
max_len = max(down + 1 + up, max_len)
return max_len, down, up
#主函数
if __name__ == '__main__':
root=MultiTreeNode(5)
root1=MultiTreeNode(6)
root2=MultiTreeNode(4)
root3=MultiTreeNode(7)
root4=MultiTreeNode(5)
root5=MultiTreeNode(8)
root6=MultiTreeNode(3)
root7=MultiTreeNode(5)
root8=MultiTreeNode(3)
root.children=[root1,root2]
root1.children=[root3,root4,root5]
root2.children=[root6,root7,root8]
solution=Solution()
print("输入为：5<6<7<>,5<>,8<>>,4<3<>,5<>,31<>>>")
print("输出为：",solution.longestConsecutive3(root))
【例152】课程表 难度等级★★
3.代码实现
from collections import deque
class Solution:
#参数numCourses为整数
#参数prerequisites为先修课列表对
#返回是否能够完成所有课程
def canFinish(self, numCourses, prerequisites):
edges = {
i: [] for i in range(numCourses)}
degrees = [0 for i in range(numCourses)]
for i, j in prerequisites:
edges[j].append(i)
degrees[i] += 1
queue, count = deque([]), 0
for i in range(numCourses):
if degrees[i] == 0:
queue.append(i)
while queue:
node = queue.popleft()
count += 1
for x in edges[node]:
degrees[x] -= 1
if degrees[x] == 0:
queue.append(x)
return count == numCourses
#主函数
if __name__=='__main__':
list1=[[1,0]]
n=2
solution=Solution()
print("输入课程数：",n)
print("课程关系为：",list1)
print("输出为：",solution.canFinish(n,list1))
【例153】安排课程 难度等级★★
3.代码实现
from queue import Queue
class Solution:
# 参数numCourses为整数
# 参数prerequisites为课程约束关系
# 返回课程顺序
def findOrder(self, numCourses, prerequisites):
edges = {
i: [] for i in range(numCourses)}
degrees = [0 for i in range(numCourses)]
for i, j in prerequisites:
edges[j].append(i)
degrees[i] += 1
queue = Queue(maxsize = numCourses)
for i in range(numCourses):
if degrees[i] == 0:
queue.put(i)
order = []
while not queue.empty():
node = queue.get()
order.append(node)
for x in edges[node]:
degrees[x] -= 1
if degrees[x] == 0:
queue.put(x)
if len(order) == numCourses:
return order
return []
#主函数
if __name__ =='__main__':
n=4
list=[[1,0],[2,0],[3,1],[3,2]]
solution=Solution()
print("输入课程数：",n)
print("输入约束为：",list1)
print("输出课程为：",solution.findOrder(n,list1))
【例 154】单词表示数字 难度等级★★
3.代码实现
class Solution:
"""
参数number为整数
返回字符串
"""
def convertWords(self, number):
n1 = ["", "one", "two", "three", "four", "five",
"six", "seven", "eight", "nine", "ten",
"eleven", "twelve", "thirteen", "fourteen", "fifteen",
"sixteen", "seventeen", "eighteen", "nineteen"]
n2 = ["", "ten", "twenty", "thirty", "forty",
"fifty", "sixty", "seventy", "eighty", "ninety"]
n3 = ['hundred', '', 'thousand', 'million', 'billion']
res = ''
index = 1
if number == 0:
return 'zero'
elif 0 < number < 20:
return n1[number]
elif 20 <= number < 100:
return n2[number // 10] + ' ' + n1[number]
else:
while number != '':
digit = int(str(number)[-3::])
number = (str(number)[:-3:])
i = len(str(digit))
r = ''
while True:
if digit < 20:
r += n1[digit]
break
elif 20 <= digit < 100:
r += n2[digit // 10] + ' '
elif 100 <= digit < 1000:
r += n1[digit // 100] + ' ' + n3[0] + ' '
digit = digit % (10 ** (i - 1))
i -= 1
if digit != 0:
r += ' ' + n3[index] + ' '
index += 1
r += res
res = r
return res.strip()
if __name__=='__main__':
solution=Solution()
n=10245
print("输入为：",n)
print("输出为：",solution.convertWords(n))
【例155】最大子序列的和 难度等级★★
3.代码实现
class Solution:
# 参数nums为整型数组
# 参数k为整数
# 返回最大和
def maxSubarray(self, nums, k):
n = len(nums)
if n < k:
return 0
result = 0
for i in range(k):
result += nums[i]
sum = [0 for _ in range(n + 1)]
min_prefix = 0
for i in range(1, n + 1):
sum[i] = sum[i - 1] + nums[i - 1]
if i >= k and sum[i] - min_prefix > result:
result = max(result, sum[i] - min_prefix)
if i >= k:
min_prefix = min(min_prefix, sum[i - k + 1])
return result
#主函数
if __name__=='__main__':
inputnum=[-2,2,-3,4,-1,2,1,-5,3]
k=5
solution=Solution()
print("输入数组为：",inputnum)
print("输入k=：",k)
print("输出sum=：",solution.maxSubarray(inputnum,k))
【例156】移除子串 难度等级★★
3.代码实现
class Solution:
# 参数s为字符串
# 参数dict为一组子字符串
# 返回最小长度
def minLength(self, s, dict):
import queue
que = queue.Queue()
que.put(s)
hash = set([s])
min = len(s)
while not que.empty():
s = que.get()
for sub in dict:
found = s.find(sub)
while found != -1:
new_s = s[:found] + s[found + len(sub):]
if new_s not in hash:
if len(new_s) < min:
min = len(new_s)
que.put(new_s)
hash.add(new_s)
found = s.find(sub, found + 1)
return min
#主函数
if __name__=='__main__':
inputwords="ccdaabcdbb"
k=["ab","cd"]
solution=Solution()
print("输入字符串为：",inputwords)
print("输入的子串为：",k)
print("字符串长度为：",solution.minLength(inputwords,k))
【例157】数组划分 难度等级★★
3.代码实现
class Solution:
# 参数nums为整型数组
# 参数low为整型
# 参数high整型
# 返回任意可能的解
def partition2(self, nums, low, high):
if len(nums) <= 1:
return
pl, pr = 0, len(nums) - 1
i = 0
while i <= pr:
if nums[i] < low:
nums[pl], nums[i] = nums[i], nums[pl]
pl += 1
i += 1
elif nums[i] > high:
nums[pr], nums[i] = nums[i], nums[pr]
pr -= 1
else:
i += 1
return nums
#主函数
if __name__ == '__main__':
inputnum=[4,3,4,1,2,3,1,2]
low=2
high=3
solution=Solution()
print("输入数组为：",inputnum)
print("输入下限为：",low)
print("输入上限为：",high)
print("输出结果为：",solution.partition2(inputnum,low,high))
【例158】矩形重叠 难度等级★★
3.代码实现
# 定义一个点
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
class Solution:
# 参数l1 第一个长方形左上角的坐标
# 参数r1 第一个长方形右下角的坐标
# 参数l2 第二个长方形左上角的坐标
# 参数r2 第二个长方形右下角的坐标
# 如果重叠返回True
def doOverlap(self, l1, r1, l2, r2):
if l1.x > r2.x or l2.x > r1.x:
return False
if l1.y < r2.y or l2.y < r1.y:
return False
return True
#主函数
if __name__ == '__main__':
l1=Point(0,8)
r1=Point(8,0)
l2=Point(6,6)
r2=Point(10,0)
solution=Solution()
print("输入矩形一：l1=(0,8)，r1=Point(8,0)")
print("输入矩形二：l2=(6,6)，r2=Point(10,0)")
print("输出的结果：",solution.doOverlap(l1,r1,l2,r2))
【例159】最长回文串 难度等级★★
3.代码实现
class Solution:
# 参数s 是一个包含大小写的字符串
# 返回能构建的最长回文串4
def longestPalindrome(self, s):
hash = {
}
for c in s:
if c in hash:
del hash[c]
else:
hash[c] = True
remove = len(hash)
if remove > 0:
remove -= 1
return len(s) - remove
#主函数
if __name__ == '__main__':
inputnum="abccccdd"
solution=Solution()
print("输入字符串为：",inputnum)
print("输出回文长度：",solution.longestPalindrome(inputnum))
【例160】最大子树 难度等级★★
3.代码实现
# 定义一个多节点的树
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right=None
class Solution:
# 参数root为二叉树根
# 返回最大节点值
import sys
maximum_weight = 0
result = None
def findSubtree(self, root):
self.helper(root)
return self.result.val
def helper(self, root):
if root is None:
return 0
left_weight = self.helper(root.left)
right_weight = self.helper(root.right)
if left_weight + right_weight + root.val >= self.maximum_weight or self.result is None:
self.maximum_weight = left_weight + right_weight + root.val
self.result = root
return left_weight + right_weight + root.val
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root1 = TreeNode(-5)
root2 = TreeNode(2)
root3 = TreeNode(0)
root4 = TreeNode(3)
root5 = TreeNode(-4)
root6 = TreeNode(-5)
root.left=root1
root.right=root2
root1.left=root3
root1.right=root4
root2.left=root5
root2.right=root6
solution = Solution()
print("输入为：[1,-5 2,0 3 -4 -5]")
print("输出为：",solution.findSubtree(root))
【例161】最小生成树 难度等级★★
3.代码实现
#定义Connection
class Connection:
def __init__(self, city1, city2, cost):
self.city1, self.city2, self.cost = city1, city2, cost
def comp(a, b):
if a.cost != b.cost:
return a.cost - b.cost
if a.city1 != b.city1:
if a.city1 < b.city1:
return -1
else:
return 1
if a.city2 == b.city2:
return 0
elif a.city2 < b.city2:
return -1
else:
return 1
class Solution:
# @param {Connection[]} connections 城市和花费的List
# @return {Connection[]} 返回这个type
def lowestCost(self, connections):
# Write your code here
cmp=0
# connections.sort()
hash = {
}
n = 0
for connection in connections:
if connection.city1 not in hash:
n += 1
hash[connection.city1] = n
if connection.city2 not in hash:
n += 1
hash[connection.city2] = n
father = [0 for _ in range(n + 1)]
results = []
for connection in connections:
num1 = hash[connection.city1]
num2 = hash[connection.city2]
root1 = self.find(num1, father)
root2 = self.find(num2, father)
if root1 != root2:
father[root1] = root2
results.append(connection)
if len(results)!= n - 1:
return []
return results
def find(self, num, father):
if father[num] == 0:
return num
father[num] = self.find(father[num], father)
return father[num]
#主函数
if __name__ == '__main__':
conn=Connection("Acity","Bcity",1)
conn1=Connection("Acity","Ccity",2)
conn2=Connection("Bcity","Ccity",3)
connections=[conn,conn1,conn2]
solution = Solution()
ci01=solution.lowestCost(connections)[0].city1
ci02=solution.lowestCost(connections)[0].city2
co0=solution.lowestCost(connections)[0].cost
ci11=solution.lowestCost(connections)[1].city1
ci12=solution.lowestCost(connections)[1].city2
ci1=solution.lowestCost(connections)[1].cost
print([[ci01,ci02,co0],[ci11,ci12,ci1]])
【例162】骑士的最短路径 难度等级★★
3.代码实现
import sys
class Solution:
# 参数grid是棋盘
# 返回最短路径长度
def shortestPath2(self, grid):
n = len(grid)
if n == 0:
return -1
m = len(grid[0])
if m == 0:
return -1
f = [ [sys.maxsize for j in range(m)] for _ in range(n)]
f[0][0] = 0
for j in range(m):
for i in range(n):
if not grid[i][j]:
if i >= 1 and j >= 2 and f[i - 1][j - 2] != sys.maxsize:
f[i][j] = min(f[i][j], f[i - 1][j - 2] + 1)
if i + 1 < n and j >= 2 and f[i + 1][j - 2] != sys.maxsize:
f[i][j] = min(f[i][j], f[i + 1][j - 2] + 1)
if i >= 2 and j >= 1 and f[i - 2][j - 1] != sys.maxsize:
f[i][j] = min(f[i][j], f[i - 2][j - 1] + 1)
if i + 2 < n and j >= 1 and f[i + 2][j - 1] != sys.maxsize:
f[i][j] = min(f[i][j], f[i + 2][j - 1] + 1)
if f[n - 1][m - 1] == sys.maxsize:
return -1
return f[n - 1][m - 1]
#主函数
if __name__ == '__main__':
inputnum=[[0,0,0,0],[0,0,0,0],[0,0,0,0]]
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.shortestPath2(inputnum))
【例163】最大矩阵 难度等级★★
3.代码实现
class Solution:
#参数matrix为矩阵
#@返回整数
def maxSquare2(self, matrix):
if not matrix or not matrix[0]:
return 0
n, m = len(matrix), len(matrix[0])
f = [[0] * m, [0] * m]
up = [[0] * m, [0] * m]
for i in range(m):
f[0][i] = matrix[0][i]
up[0][i] = 1 - matrix[0][i]
edge = max(matrix[0])
for i in range(1, n):
f[i % 2][0] = matrix[i][0]
up[i % 2][0] = 0 if matrix[i][0] else up[(i - 1) % 2][0] + 1
left = 1 - matrix[i][0]
for j in range(1, m):
if matrix[i][j]:
f[i%2][j] =min(f[(i-1)%2][j-1],left,up[(i-1)%2][j])+1
up[i % 2][j] = 0
left = 0
else:
f[i % 2][j] = 0
up[i % 2][j] = up[(i - 1) % 2][j] + 1
left += 1
edge = max(edge, max(f[i % 2]))
return edge * edge
#主函数
if __name__ == '__main__':
inputnum=[[1,0,1,0,0],[1,0,0,1,0],[1,1,0,0,1],[1,0,0,1,0]]
solution = Solution()
print("输入为：", inputnum)
print("输出为：",solution.maxSquare2(inputnum))
【例164】二叉树的最大节点 难度等级★★
3.代码实现
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 参数root为二叉树根
# 返回最大节点值
def maxNode(self, root):
if root is None:
return root
left = self.maxNode(root.left)
right = self.maxNode(root.right)
return self.max(root, self.max(left, right))
def max(self, a, b):
if a is None:
return b
if b is None:
return a
if a.val > b.val:
return a
return b
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root1 = TreeNode(-5)
root2 = TreeNode(3)
root3 = TreeNode(1)
root4 = TreeNode(2)
root5 = TreeNode(-4)
root6 = TreeNode(-5)
root.left = root1
root.right= root2
root1.left = root3
root1.right= root4
root2.left = root5
root2.right= root6
solution = Solution()
print("输入为：[1,-5 3,1 2 -4 -5]")
print("输出为：",solution.maxNode(root).val)
【例165】寻找重复的数 难度等级★★
3.代码实现
class Solution:
#参数nums为整型数组
#返回重复的数
def findDuplicate(self, nums):
start, end = 1, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if self.smaller_than_or_equal_to(nums, mid) > mid:
end = mid
else:
start = mid
if self.smaller_than_or_equal_to(nums, start) > start:
return start
return end
def smaller_than_or_equal_to(self, nums, val):
count = 0
for num in nums:
if num <= val:
count += 1
return count
#主函数
if __name__ == '__main__':
inputnum= [5,5,4,3,2,1]
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.findDuplicate(inputnum))
【例166】拼字游戏 难度等级★★
3.代码实现
import collections
class TrieNode(object):
def __init__(self, value=0):
self.value = value
self.isWord = False
self.children = collections.OrderedDict()
@classmethod
def insert(cls, root, word):
p = root
for c in word:
child = p.children.get(c)
if not child:
child = TrieNode(c)
p.children[c] = child
p = child
p.isWord = True
class Solution:
# 参数board为字符列表
# 参数words为字符串列表
# 返回整数
def boggleGame(self, board, words):
self.board = board
self.words = words
self.m = len(board)
self.n = len(board[0])
self.results = []
self.temp = []
self.visited = [[False for _ in range(self.n)] for _ in range(self.m)]
self.root = TrieNode()
for word in words:
TrieNode.insert(self.root, word)
self.dfs(0, 0, self.root)
return len(self.results)
def dfs(self, x, y, root):
for i in range(x, self.m):
for j in range(y, self.n):
paths = []
temp = []
self.getAllPaths(i, j, paths, temp, root)
for path in paths:
word = ''
for px, py in path:
word += self.board[px][py]
self.visited[px][py] = True
self.temp.append(word)
if len(self.temp) > len(self.results):
self.results = self.temp[:]
self.dfs(i, j, root)
self.temp.pop()
for px, py in path:
self.visited[px][py] = False
y = 0
def getAllPaths(self, i, j, paths, temp, root):
if i < 0 or i >= self.m or j < 0 or j >= self.n or \
self.board[i][j] not in root.children or \
self.visited[i][j] == True:
return
root = root.children[self.board[i][j]]
if root.isWord:
temp.append((i,j))
paths.append(temp[:])
temp.pop()
return
self.visited[i][j] = True
deltas = [(0,1), (0,-1), (1,0), (-1, 0)]
for dx, dy in deltas:
newx = i + dx
newy = j + dy
temp.append((i,j))
self.getAllPaths(newx, newy, paths, temp, root)
temp.pop()
self.visited[i][j] = False
#主函数
if __name__ == '__main__':
inputnum= [['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i']]
dictw = ["abc", "cfi", "beh", "defi", "gh"]
solution = Solution()
print("输入字符为：",inputnum)
print("输入字典为：",dictw)
print("输出个数为：",solution.boggleGame(inputnum,dictw))
【例167】132模式识别 难度等级★★
3.代码实现
class Solution:
# 参数nums为整数列表
# 返回True或者False
def find132pattern(self, nums):
stk = [-sys.maxsize]
for i in range(len(nums)-1, -1, -1):
if nums[i] < stk[-1]:
return True
else:
while stk and nums[i] > stk[-1]:
v = stk.pop()
stk.append(nums[i])
stk.append(v)
return False
#主函数
if __name__ == '__main__':
inputnum=[1, 2, 3, 4]
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.find132pattern(inputnum))
【例168】检查缩写字 难度等级★★
3.代码实现
class Solution:
#参数word为字符串
#参数abbr为字符串
#返回布尔类型
def validWordAbbreviation(self, word, abbr):
i = 0
j = 0
while i < len(word) and j < len(abbr):
if word[i] == abbr[j]:
i += 1
j += 1
elif abbr[j].isdigit() and abbr[j] != '0':
start = j
while j < len(abbr) and abbr[j].isdigit():
j += 1
i += int(abbr[start : j])
else:
return False
return i == len(word) and j == len(abbr)
#主函数
if __name__ == '__main__':
s = "internationalization"
abbr = "i12iz4n"
solution = Solution()
print("输入为：",s)
print("缩写为：",abbr)
print("输出为：",solution.validWordAbbreviation(s,abbr))
【例169】一次编辑距离 难度等级★★
3.代码实现
class Solution:
# 参数s为字符串
# 参数t为字符串
# 返回布尔类型
def isOneEditDistance(self, s, t):
m = len(s)
n = len(t)
if abs(m - n) > 1:
return False
if m > n:
return self.isOneEditDistance(t, s)
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i + 1:] == t[i + 1:]
return s[i:] == t[i + 1:]
return m != n
#主函数
if __name__ == '__main__':
s = "aDb"
t = "adb"
solution = Solution()
print("输入字符串s：",s)
print("输入字符串t：",t)
print("输出为：",solution.isOneEditDistance(s,t))
【例170】数据流滑动窗口平均值 难度等级★★
3.代码实现
from collections import deque
class MovingAverage(object):
def __init__(self, size):
self.queue = deque([])
self.size = size
self.sum = 0.0
def next(self, val):
if len(self.queue) == self.size:
self.sum -= self.queue.popleft()
self.sum += val
self.queue.append(val)
return self.sum / len(self.queue)
if __name__ == '__main__':
solution = MovingAverage(3)
print("输入数据流：1,10,3,5")
print("输出流动窗1：",solution.next(1))
print("输出流动窗2：",solution.next(10))
print("输出流动窗3：",solution.next(3))
print("输出流动窗4：",solution.next(5))
【例171】最长绝对文件路径 难度等级★★
3.代码实现
import re
import collections
class Solution:
#参数input为抽象的文件系统
#返回最长文件的绝度路径长度
def lengthLongestPath(self, input):
dict = collections.defaultdict(lambda: "")
lines = input.split("\n")
n = len(lines)
result = 0
for i in range(n):
count = lines[i].count("\t")
lines[i] = dict[count - 1] + re.sub("\\t+","/", lines[i])
if "." in lines[i]:
result = max(result, len(lines[i]))
dict[count] = lines[i]
return result
#主函数
if __name__ == '__main__':
inputwords="dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
solution=Solution()
print("输入为：",inputwords)
print("输出为：",solution.lengthLongestPath(inputwords))
【例172】识别名人 难度等级★★
3.代码实现
#假定0认识1,1不认识0
class Celebrity:
def knows(a,b):
if a==0 and b==1 :
return True
if a==1 and b==0 :
return False
class Solution:
# 参数n为整数
# 返回整数
def findCelebrity(self, n):
celeb = 0
for i in range(1, n):
if Celebrity.knows(celeb, i):
celeb = i
for i in range(n):
if celeb != i and Celebrity.knows(celeb, i):
return -1
if celeb != i and not Celebrity.knows(i, celeb):
return -1
return celeb
#主函数
if __name__ == '__main__':
n=2
solution=Solution()
print("输入为：",n)
print("输出为：",solution.findCelebrity(n))
【例173】第一个独特字符位置 难度等级★★
3.代码实现
class Solution:
# 参数s为字符串
# 返回整数
def firstUniqChar(self, s):
alp = {
}
for c in s:
if c not in alp:
alp[c] = 1
else:
alp[c] += 1
index = 0
for c in s:
if alp[c] == 1:
return index
index += 1
return -1
#主函数
if __name__ == '__main__':
s = "lintcode"
solution=Solution()
print("输入为：",s)
print("输出为：",solution.firstUniqChar(s))
【例174】子串字谜 难度等级★★
3.代码实现
class Solution:
# 参数s为字符串
# 参数p为字符串
# 返回索引列表
def findAnagrams(self, s, p):
ans = []
sum = [0 for x in range(0,30)]
plength = len(p)
slength = len(s)
for i in range(plength):
sum[ord(p[i]) - ord('a')] += 1
start = 0
end = 0
matched = 0
while end < slength:
if sum[ord(s[end]) - ord('a')] >= 1:
matched += 1
sum[ord(s[end]) - ord('a')] -= 1
end += 1
if matched == plength:
ans.append(start)
if end - start == plength:
if sum[ord(s[start]) - ord('a')] >= 0:
matched -= 1
sum[ord(s[start]) - ord('a')] += 1
start += 1
return ans
#主函数
if __name__ == '__main__':
s = "cbaebabacd"
p = "abc"
solution = Solution()
print("输入字符串：",s)
print("输入子串为：",p)
print("输出索引为：",solution.findAnagrams(s,p))
【例175】单词缩写集 难度等级★★
3.代码实现
class ValidWordAbbr:
def __init__(self, dictionary):
self.map = {
}
for word in dictionary:
abbr = self.word_to_abbr(word)
if abbr not in self.map:
self.map[abbr] = set()
self.map[abbr].add(word)
def word_to_abbr(self, word):
if len(word) <= 1:
return word
return word[0] + str(len(word[1:-1])) + word[-1]
def isUnique(self, word):
abbr = self.word_to_abbr(word)
if abbr not in self.map:
return True
for word_in_dict in self.map[abbr]:
if word != word_in_dict:
return False
return True
#主函数
if __name__ == '__main__':
dic=[ "deer", "door", "cake", "card" ]
solution = ValidWordAbbr(dic)
print("输入字典为：",dic)
print("输入单词为： dear")
print("输出结果为：",solution.isUnique("dear"))
print("输入单词为： cart")
print("输出结果为：",solution.isUnique("cart"))
【例176】二叉树翻转 难度等级★★
3.代码实现
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
def upsideDownBinaryTree(self, root):
if root is None:
return None
return self.dfs(root)
def dfs(self, root):
if root.left is None:
return root
newRoot = self.dfs(root.left)
root.left.right = root
root.left.left = root.right
root.left = None
root.right = None
return newRoot
#主函数
if __name__ == '__main__':
root1 = TreeNode(1)
root2 = TreeNode(2)
root3 = TreeNode(3)
root4 = TreeNode(4)
root5 = TreeNode(5)
inputnum=[1,2,3,4,5,"#","#"]
root1.left = root2
root1.right=root3
root2.left=root4
root2.right=root5
solution = Solution()
a=solution.upsideDownBinaryTree(root1)
a0=a.val
a1=a.left.val
a2=a.right.val
a3='#'
a4='#'
a5=a.right.left.val
a6=a.right.right.val
aa=[a0,a1,a2,a3,a4,a5,a6]
print("输入为",inputnum)
print("输出为",aa)
【例177】 二叉树垂直遍历 难度等级★★
3.代码实现
import collections
import queue as Queue
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
# 参数root为二叉树根
# 返回整型列表
def verticalOrder(self, root):
results = collections.defaultdict(list)
queue = Queue.Queue()
queue.put((root, 0))
while not queue.empty():
node, x = queue.get()
if node:
results[x].append(node.val)
queue.put((node.left, x - 1))
queue.put((node.right, x + 1))
return [results[i] for i in sorted(results)]
#主函数
if __name__ == '__main__':
root=TreeNode(3)
root1=TreeNode(9)
root2=TreeNode(20)
root3=TreeNode(15)
root4=TreeNode(7)
root.left=root1
root.right=root2
root2.left=root3
root2.right=root4
solution = Solution()
a=solution.verticalOrder(root)
print("输入为： [3,9,20,#,#,15,7]")
print("输出为：",a)
【例178】因式分解 难度等级★★
3.代码实现
class Solution:
#参数n为整数
#返回组合列表
def getFactors(self, n):
result = []
self.helper(result, [], n, 2);
return result
def helper(self, result, item, n, start):
if n <= 1:
if len(item) > 1:
result.append(item[:])
return
import math
for i in range(start, int(math.sqrt(n)) + 1):
if n % i == 0:
item.append(i)
self.helper(result, item, n / i, i)
item.pop()
if n >= start:
item.append(n)
self.helper(result, item, 1, n)
item.pop()
#主函数
if __name__ == '__main__':
inputnum=8
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.getFactors(inputnum))
【例179】Insert Delete GetRandom O(1) 难度等级★★
3.代码实现
import random
class RandomizedSet(object):
def __init__(self):
self.nums, self.pos = [], {
}
# 参数val为整数
# 返回布尔类型
def insert(self, val):
if val not in self.pos:
self.nums.append(val)
self.pos[val] = len(self.nums) - 1
return True
return False
# 参数val为整数
# 返回布尔类型
def remove(self, val):
if val in self.pos:
idx, last = self.pos[val], self.nums[-1]
self.nums[idx], self.pos[last] = last, idx
self.nums.pop()
del self.pos[val]
return True
return False
def getRandom(self):
return self.nums[random.randint(0, len(self.nums) - 1)]
#主函数
if __name__ == '__main__':
solution=RandomizedSet()
print("插入一个元素：1")
print("输出为：",solution.insert(1))
print("移除一个元素：2")
print("输出为：",solution.remove(2))
print("插入一个元素：2")
print("输出为：",solution.insert(2))
print("获取随机元素：1")
print("输出为：",solution.getRandom())
print("移除一个元素：1")
print("输出为：",solution.remove(1))
print("插入一个元素：2")
print("输出为：",solution.insert(2))
【例180】编码和解码字符串 难度等级★★
3.代码实现
class Solution:
#参数strs为字符串列表
#返回编码后的字符串列表
# " " -> ": " 分隔不同单词
# ":" -> "::" 区分":"
def encode(self, strs):
encoded = []
for string in strs:
for char in string:
if char == ":":
encoded.append("::")
else:
encoded.append(char)
encoded.append(": ")
return "".join(encoded)
#参数str为字符串
#返回解码字符串列表
def decode(self, str):
res = []
idx = 0
length = len(str)
tmp_str = []
while idx < length - 1:
if str[idx] == ":":
if str[idx + 1] == ":":
tmp_str.append(":")
idx += 2
elif str[idx + 1] == " ":
res.append("".join(tmp_str))
tmp_str = []
idx += 2
else:
tmp_str.append(str[idx])
idx += 1
return res
#主函数
if __name__ == '__main__':
inputwords=["lint","code","love","you"]
solution=Solution()
print("输入为：",inputwords)
print("编码为：",solution.encode(inputwords))
print("解码为：",solution.decode(solution.encode(inputwords)))
【例181】猜数游戏 难度等级★★
3.代码实现
def guess(mid):
if mid>4:
return -1
if mid <4:
return 1
if mid==4:
return 0
class Solution:
#参数n为整数
#返回所猜的数
def guessNumber(self, n):
l = 1
r = n
while l <= r:
mid = abs(l + (r - l) / 2)
res = guess(mid)
if res == 0:
return mid
if res == -1:
r = mid - 1
if res == 1:
l = mid + 1
return int(mid)
#主函数
if __name__ == '__main__':
inputnum=10
selectedNumber=4
solution=Solution()
print("输入总数为：",inputnum)
print("所选的数字：",selectedNumber)
print("所猜的数字：",solution.guessNumber(inputnum))
【例182】数1的个数 难度等级★★
3.代码实现
class Solution:
#参数num为非负整数
#返回数组
def countBits(self, num):
f = [0] * (num + 1)
for i in range(1, num+1):
f[i] = f[i & i-1] + 1
return f
#主函数
if __name__ == '__main__':
inputnum=5
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.countBits(inputnum))
【例183】平面范围求和 -不可变矩阵 难度等级★★
3.代码实现
class NumMatrix(object):
#参数matrix为矩阵
def __init__(self, matrix):
if len(matrix) == 0 or len(matrix[0]) == 0:
return
n = len(matrix)
m = len(matrix[0])
self.dp = [[0] * (m + 1) for _ in range(n + 1)]
for r in range(n):
for c in range(m):
self.dp[r+ 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + \
matrix[r][c] - self.dp[r][c]
# 参数row1为整数
# 参数col1为整数
# 参数row2为整数
# 参数col2为整数
# 返回整数
def sumRegion(self, row1, col1, row2, col2):
return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - \
self.dp[row2 + 1][col1] + self.dp[row1][col1]
#主函数
if __name__ == '__main__':
inputnum=[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
solution = NumMatrix(inputnum)
print("输入矩阵为：",inputnum)
print("区域1的和：",solution.sumRegion(2, 1, 4, 3))
print("区域2的和：",solution.sumRegion(1, 1, 2, 2))
print("区域3的和：",solution.sumRegion(1, 2, 2, 4))
【例184】猜数游戏 难度等级★★
3.代码实现
class Solution:
# 参数n为整数
# 返回整数
def getMoneyAmount(self, n):
dp = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
for len in range(2, n + 1):
for start in range(1, n - len + 2):
import sys
temp = sys.maxsize
for k in range(start + int((len - 1) / 2), start + int(len - 1)):
left, right = dp[start][k - 1], dp[k + 1][start + len - 1]
temp = min(k + max(left, right), temp)
if left > right:
break
dp[start][start + len - 1] = temp
return dp[1][n]
#主函数
if __name__ == '__main__':
inputnum=10
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.getMoneyAmount(inputnum))
【例185】最长的回文序列 难度等级★★
3.代码实现
class Solution:
# 参数s为字符串
# 返回整数
def longestPalindromeSubseq(self, s):
length = len(s)
if length == 0:
return 0
dp = [[0 for _ in range(length)] for __ in range(length)]
for i in range(length - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, length):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][length - 1]
#主函数
if __name__ == '__main__':
inputnum="bbbab"
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.longestPalindromeSubseq(inputnum))
【例186】1和0 难度等级★★
3.代码实现
class Solution:
#参数strs为字符串数组
#参数m为整数
#参数n为整数
#返回整数
def findMaxForm(self, strs, m, n):
dp = [[0] * (m + 1) for _ in range(n + 1)]
for s in strs:
zero = 0
one = 0
for ch in s:
if ch == "1":
one += 1
else:
zero += 1
for i in range(n,one - 1,-1):
for j in range(m,zero - 1,-1):
if dp[i - one][j - zero] + 1 > dp[i][j]:
dp[i][j] = dp[i - one][j - zero] + 1
return dp[-1][-1]
#主函数
if __name__ == '__main__':
inputnum=["10", "0001", "111001", "1", "0"]
m=5
n=3
solution = Solution()
print("输入为：",inputnum)
print("输入m ：",m)
print("输入n ：",n)
print("输出 ：",solution.findMaxForm(inputnum,m,n))
【例187】预测能否胜利 难度等级★★
3.代码实现
class Solution:
#参数nums为整数数组
#返回布尔类型
def PredictTheWinner(self, nums):
if len(nums) & 1 == 0: return True
dp = [[0] * len(nums) for _ in range(len(nums))]
for i, v in enumerate(nums):
dp[i][i] = v
for i in range(1, len(nums)):
for j in range(len(nums) - i):
dp[j][j + i] = max(nums[j] - dp[j + 1][j + i], nums[j + i] - dp[j][j + i - 1])
return dp[0][-1] > 0
#主函数
if __name__ == '__main__':
inputnum=[1, 5, 2]
solution = Solution()
print("输入为：",inputnum)
print("输出为：",solution.PredictTheWinner(inputnum))
【例188】循环单词 难度等级★★
3.代码实现
class Solution:
#参数words为单词列表
#返回整数
def countRotateWords(self, words):
dict1 = set()
for w in words:
s = w + w
for i in range(0, len(w)):
tmp = s[i : i +len(w)]
if tmp in dict1:
dict1.remove(tmp)
dict1.add(w)
return len(dict1)
#主函数
if __name__ == '__main__':
dict1 = ["picture", "turepic", "icturep", "word", "ordw", "long"]
solution = Solution()
print("输入为：",dict1)
print("输出为：",solution.countRotateWords(dict1))
【例189】最大子数组之和为k 难度等级★★
3.代码实现
class Solution:
#参数nums为数组
#参数k为整数
#返回整数
def maxSubArrayLen(self, nums, k):
m = {
}
ans = 0
m[k] = 0
n = len(nums)
sum = [0 for i in range(n + 1)]
for i in range(1, n + 1):
sum[i] = sum[i - 1] + nums[i - 1]
if sum[i] in m:
ans = max(ans, i - m[sum[i]])
if sum[i] + k not in m:
m[sum[i] + k] = i
return ans
if __name__ == '__main__':
num = [-2, 7, 3, -4, 1]
k = 5
solution = Solution()
print("输入数组为：",num)
print("输入目标值：",k)
print("输出为：",solution.maxSubArrayLen(num, k))
【例190】等差切片 难度等级★★
3.代码实现
class Solution(object):
def numberOfArithmeticSlices(self, A):
#参数A为列表
#返回整数
size = len(A)
if size < 3: return 0
ans = cnt = 0
delta = A[1] - A[0]
for x in range(2, size):
if A[x] - A[x - 1] == delta:
cnt += 1
ans += cnt
else:
delta = A[x] - A[x - 1]
cnt = 0
return ans
if __name__ == '__main__':
solution=Solution()
inputnum=[1, 2, 3, 4]
print("输入为：",inputnum)
print("输出为：",solution.numberOfArithmeticSlices(inputnum))
【例191】2D战舰 难度等级★★
3.代码实现
class Solution(object):
def countBattleships(self, board):
#参数board为列表
#返回整数
len1 = len(board)
if len1 == 0:
return 0;
len2 = len(board[0])
ans = 0
for i in range(0, len1):
for j in range(0,len2):
if board[i][j] == 'X' and ( i == 0 or board[i-1][j] == '.' )and (j == 0 or board[i][j-1] == '.'):
ans += 1
return ans
if __name__ == '__main__':
solution=Solution()
inputnum=["X..X","...X","...X"]
print("输入为：",inputnum)
print("输出为：",solution.countBattleships(inputnum))
【例192】连续数组 难度等级★★
3.代码实现
class Solution:
#参数nums为数组
#返回整数
def findMaxLength(self, nums):
index_sum = {
}
cur_sum = 0
ans = 0
for i in range(len(nums)):
if nums[i] == 0: cur_sum -= 1
else: cur_sum += 1
if cur_sum == 0: ans = i+1
elif cur_sum in index_sum: ans = max(ans, i-index_sum[cur_sum])
if cur_sum not in index_sum: index_sum[cur_sum] = i
return ans
if __name__ == '__main__':
solution=Solution()
inputnum=[1,0]
print("输入为：",inputnum)
print("输出为：",solution.findMaxLength(inputnum))
【例193】带有冷却时间的买卖股票最佳时间 难度等级★★
3.代码实现
class Solution:
#参数prices为整数列表
#返回整数
def maxProfit(self, prices):
if not prices:
return 0
buy, sell, cooldown = [0 for _ in range(len(prices))], [0 for _ in range(len(prices))], [0 for _ in range(len(prices))]
buy[0] = -prices[0]
for i in range(1, len(prices)):
cooldown[i] = sell[i - 1]
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i])
return max(sell[-1], cooldown[-1])
if __name__ == '__main__':
solution=Solution()
inputnum=[1,2,3,0,2]
print("输入为：",inputnum)
print("输出为：",solution.maxProfit(inputnum))
4.运行结果
输入为：[1, 2, 3, 0, 2]
输出为：3
【例194】小行星的碰撞 难度等级★★
3.代码实现
class Solution:
#参数asteroids为整数数组
#返回整数数组
def asteroidCollision(self, asteroids):
ans, i, n= [], 0, len(asteroids)
while i < n:
if asteroids[i] > 0:
ans.append(asteroids[i])
elif len(ans) == 0 or ans[-1] < 0:
ans.append(asteroids[i])
elif ans[-1] <= -asteroids[i]:
if ans[-1] < -asteroids[i]:
i -= 1
ans.pop()
i += 1
return ans
if __name__ == '__main__':
solution=Solution()
inputnum=[5,10,-5]
print("输入为：",inputnum)
print("输出入为：",solution.asteroidCollision(inputnum))
4.运行结果
输入为：[5, 10, -5]
输出入为：[5, 10]
【例195】扩展弹性词 难度等级★★
3.代码实现
class Solution:
#参数S为字符串
#参数words为字符串列表
#返回整数
def expressiveWords(self, S, words):
SList = self.countGroup(S)
n = len(SList)
ans = 0
for word in words:
wordList = self.countGroup(word)
if n != len(wordList):
continue
ok = 1
for i in range(n):
if not self.canExtend(wordList[i], SList[i]):
ok = 0
break
ans += ok
return ans
def countGroup(self, s):
n = len(s)
cnt = 1
ret = []
for i in range(1, n):
if s[i] == s[i - 1]:
cnt += 1
else:
ret.append((s[i - 1], cnt))
cnt = 1
ret.append((s[-1], cnt))
return ret
def canExtend(self, From, To):
return From[0] == To[0] and \
(From[1] == To[1] or (From[1] < To[1] and To[1] >= 3))
if __name__ == '__main__':
solution=Solution()
inputnum1="heeellooo"
inputnum2=["hello", "hi", "helo"]
print("输入字符串1为：",inputnum1)
print("输入字符串2为：",inputnum2)
print("输出为：",solution.expressiveWords(inputnum1,inputnum2))
【例196】找到最终的安全状态 难度等级★★
3.代码实现
class Solution:
#参数graph为整数数组
#返回整数
def eventualSafeNodes(self, graph):
def dfs(graph, i, visited):
for j in graph[i]:
if j in visited:
return False
if j in ans:
continue
visited.add(j)
if not dfs(graph, j, visited):
return False
visited.remove(j)
ans.add(i)
return True
ans = set()
for i in range(len(graph)):
visited = set([i])
dfs(graph, i, visited)
return sorted(list(ans))
if __name__ == '__main__':
solution=Solution()
inputnum=[[1,2],[2,3],[5],[0],[5],[],[]]
print("输入为：",inputnum)
print("输出为：",solution.eventualSafeNodes(inputnum))
【例197】使序列递增的最小交换次数 难度等级★★
3.代码实现
class Solution:
def minSwap(self, A, B):
if len(A) == 0 or len(A) != len(B):
return 0
non_swapped, swapped = [0] * len(A), [1] + [0] * (len(A) - 1)
for i in range(1, len(A)):
swps, no_swps = set(), set()
if A[i - 1] < A[i] and B[i - 1] < B[i]:
swps.add(swapped[i - 1] + 1)
no_swps.add(non_swapped[i - 1])
if B[i - 1] < A[i] and A[i - 1] < B[i]:
swps.add(non_swapped[i - 1] + 1)
no_swps.add(swapped[i - 1])
swapped[i], non_swapped[i] = min(swps), min(no_swps)
return min(swapped[-1], non_swapped[-1])
if __name__ == '__main__':
solution=Solution()
inputnum1=[1,3,5,4]
inputnum2=[1,2,3,7]
print("输入1为：",inputnum1)
print("输入2为：",inputnum2)
print("输出为：",solution.minSwap(inputnum1,inputnum2))
【例198】所有可能的路径 难度等级★★
3.代码实现
class Solution:
#参数graph为数组
#返回数组
def allPathsSourceTarget(self, graph):
N = len(graph)
res = []
def dfs(N, graph, start, res, path):
if start == N-1:
res.append(path)
else:
for node in graph[start]:
dfs(N, graph, node, res, path + [node])
dfs(N, graph, 0, res, [0])
return (res)
if __name__ == '__main__':
solution=Solution()
inputnum=[[1,2],[3],[3],[]]
print("输入为：",inputnum)
print("输出为：",solution.allPathsSourceTarget(inputnum))
【例199】合法的井字棋状态 难度等级★★
3.代码实现
class Solution:
def validTicTacToe(self, board):
#参数board为列表
#返回布尔类型
num_X, num_O = 0, 0
for i in range(0, 3):
for j in range(0, 3):
if board[i][j] == 'X':
num_X += 1
if board[i][j] == 'O':
num_O += 1
if not (num_X == num_O or num_X == num_O + 1):
return False
for i in range(3):
if board[i][0] == board[i][1] == board[i][2]:
if board[i][0] == 'X':
return num_X == num_O + 1
if board[i][0] == 'O':
return num_X == num_O
for j in range(3):
if board[0][j] == board[1][j] == board[2][j]:
if board[0][j] == 'X':
return num_X == num_O + 1
if board[0][j] == 'O':
return num_X == num_O
if board[0][0] == board[1][1] == board[2][2]:
if board[0][0] == 'X':
return num_X == num_O + 1
if board[0][0] == 'O':
return num_X == num_O
if board[0][2] == board[1][1] == board[2][0]:
if board[2][0] == 'X':
return num_X == num_O + 1
if board[2][0] == 'O':
return num_X == num_O
return True
if __name__ == '__main__':
solution=Solution()
inputnum=["O ", " ", " "]
print("输入为：",inputnum)
print("输出为：",solution.validTicTacToe(inputnum))
【例200】满足要求的子串个数 难度等级★★
3.代码实现
class Solution:
#参数S为字符串
#参数words为单词字典
#返回子串的个数
def numMatchingSubseq(self, S, words):
self.idx = {
'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4,
'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9,
'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14,
'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19,
'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
n = len(S)
nxtPos = []
tmp = [-1] * 26
for i in range(n - 1, -1, -1):
tmp[self.idx[S[i]]] = i
nxtPos.append([i for i in tmp])
nxtPos = nxtPos[::-1]
ans = 0
for word in words:
if self.isSubseq(word, nxtPos):
ans += 1
return ans
def isSubseq(self, word, nxtPos):
lenw = len(word)
lens = len(nxtPos)
i, j = 0, 0
while i < lenw and j < lens:
j = nxtPos[j][self.idx[word[i]]]
if j < 0:
return False
i += 1
j += 1
return i == lenw
if __name__ == '__main__':
solution=Solution()
input1="abcde"
input2=["a", "bb", "acd", "ace"]
print("输入字符串为：",input1)
print("输入子串为：",input2)
print("输出为：",solution.numMatchingSubseq(input1,input2))
转载：https://blog.csdn.net/cui_yonghua/article/details/117336492
查看评论