一. python3的各种经典案例，总共299个案例，直接可以运行（前：100个案例）
二. python3的各种经典案例，总共299个案例，直接可以运行（中：100个案例）
三. python3的各种经典案例，总共299个案例，直接可以运行（后：99个案例）
第一章 难度等级★
【例1】反转一个3位整数 难度等级★
3.代码实现
class Solution:
#参数number: 一个三位整数
#返回值: 反转后的数字
def reverseInteger(self, number):
h = int(number/100)
t = int(number%100/10)
z = int(number%10)
return (100*z+10*t+h)
#主函数
if __name__ == '__main__':
solution = Solution()
num = 123
ans = solution.reverseInteger(num)
print("输入：", num)
print("输出：", ans)
【例2】合并排序数组 难度等级★
3.代码实现
class Solution:
#参数A: 有序整数数组A
#参数B: 有序整数数组B
#返回:一个新的有序整数数组
def mergeSortedArray(self, A, B):
i, j = 0, 0
C = []
while i < len(A) and j < len(B):
if A[i] < B[j]:
C.append(A[i])
i += 1
else:
C.append(B[j])
j += 1
while i < len(A):
C.append(A[i])
i += 1
while j < len(B):
C.append(B[j])
j += 1
return C
#主函数
#主函数
if __name__ == '__main__':
A = [1,4]
B = [1,2,3]
D = [1,2,3,4]
E = [2,4,5,6]
solution = Solution()
print("输入：", A, " ", B)
print("输出：", solution.mergeSortedArray(A,B))
print("输入：", D, " ", E)
print("输出：", solution.mergeSortedArray(D,E))
【例3】旋转字符串 难度等级★
3.代码实现
class Solution:
#参数s:字符列表
#参数offset:整数
#返回值:无
def rotateString(self, s, offset):
if len(s) > 0:
offset = offset % len(s)
temp = (s + s)[len(s) - offset : 2 * len(s) - offset]
for i in range(len(temp)):
s[i] = temp[i]
#主函数
if __name__ == '__main__':
s = ["a","b","c","d","e","f","g"]
offset = 3
solution = Solution()
solution.rotateString(s, offset)
print("输入：s =", ["a","b","c","d","e","f","g"], " ", "offset =",offset)
print("输出：s =", s)
【例4】相对排名 难度等级★
3.代码实现
class Solution:
#参数nums为整数列表
#返回列表
def findRelativeRanks(self, nums):
score = {
}
for i in range(len(nums)):
score[nums[i]] = i
sortedScore = sorted(nums, reverse=True)
answer = [0] * len(nums)
for i in range(len(sortedScore)):
res = str(i + 1)
if i == 0:
res = 'Gold Medal'
if i == 1:
res = 'Silver Medal'
if i == 2:
res = 'Bronze Medal'
answer[score[sortedScore[i]]] = res
return answer
#主函数
if __name__ == '__main__':
num = [5,4,3,2,1]
s = Solution()
print("输入为：",num)
print("输出为：",s.findRelativeRanks(num))
【例5】二分查找 难度等级★
3.代码实现
class Solution:
#参数nums: 整数数组
#参数target: 要查找的目标数字
#返回值：目标数字的第一个位置，从0开始
def binarySearch(self, nums, target):
return self.search(nums, 0, len(nums) - 1, target)
def search(self, nums, start, end, target):
if start > end:
return -1
mid = (start + end)//2
if nums[mid] > target:
return self.search(nums, start, mid, target)
if nums[mid] == target:
return mid
if nums[mid] < target:
return self.search(nums, mid, end, target)
#主函数
if __name__ == '__main__':
my_solution = Solution()
nums = [1,2,3,4,5,6]
target = 3
targetIndex = my_solution.binarySearch(nums, target)
print("输入：nums =", nums, " ", "target =",target)
print("输出：",targetIndex)
【例6】下一个更大的数 难度等级★
3.代码实现
class Solution:
#参数nums1为整数数组
#参数nums2为整数数组
#返回整数数组
def nextGreaterElement(self, nums1, nums2):
answer = {
}
stack = []
for x in nums2:
while stack and stack[-1] < x:
answer[stack[-1]] = x
del stack[-1]
stack.append(x)
for x in stack:
answer[x] = -1
return [answer[x] for x in nums1]
#主函数
if __name__ == '__main__':
s = Solution()
nums1 = [4,1,2]
nums2 = [1,3,4,2]
print("输入1为：",nums1)
print("输入2为：",nums2)
print("输出为 ：",s.nextGreaterElement(nums1,nums2))
【例7】字符串中的单词数 难度等级★
3.代码实现
class Solution:
#参数s为字符串
#返回整数
def countSegments(self, s):
res = 0
for i in range(len(s)):
if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
res += 1
return res
#主函数
if __name__ == '__main__':
s = Solution()
n = "Hello, my name is John"
print("输入为：",n)
print("输出为：",s.countSegments(n))
【例8】勒索信 难度等级★
3.代码实现
class Solution:
"""
参数ransomNote为字符串
参数magazine为字符串
返回布尔类型
"""
def canConstruct(self, ransomNote, magazine):
arr = [0] * 26
for c in magazine:
arr[ord(c) - ord('a')] += 1
for c in ransomNote:
arr[ord(c) - ord('a')] -= 1
if arr[ord(c) - ord('a')] < 0:
return False
return True
#主函数
if __name__ == '__main__':
s = Solution()
ransomNote = "aa"
magazine = "aab"
print("输入勒索信为：",ransomNote)
print("输入杂志内容：",magazine)
print("输出为：",s.canConstruct(ransomNote,magazine))
【例9】不重复的两个数 难度等级★
3.代码实现
#参数arr是输入的待查数组
#返回值是两个值的列表，内容没有重复的
class Solution:
def theTwoNumbers(self, a):
ans = [0, 0]
for i in a:
ans[0] = ans[0] ^ i
c = 1
while c & ans[0] != c:
c = c << 1
for i in a:
if i & c == c:
ans[1] = ans[1] ^ i
ans[0] = ans[0] ^ ans[1]
return ans
if __name__ == '__main__':
arr = [1, 2, 5, 1]
solution = Solution()
print(" 数组为：", arr)
print(" 两个没有重复的数字是:", solution.theTwoNumbers(arr))
【例10】双胞胎字符串 难度等级★
3.代码实现
#参数s和t是一对字符串
#返回值是个字符串，能否根据规则转换
class Solution:
def isTwin(self, s, t):
if len(s) != len(t):
return "No"
oddS = []
evenS = []
oddT = []
evenT = []
for i in range(len(s)):
if i & 1:
oddS.append(s[i])
oddT.append(t[i])
else :
evenS.append(s[i])
evenT.append(t[i])
oddS.sort()
oddT.sort()
evenS.sort()
evenT.sort()
for i in range (len(oddS)) :
if oddS[i] != oddT[i]:
return "No"
for i in range (len(evenS)) :
if evenS[i] != evenT[i]:
return "No"
return "Yes"
if __name__ == '__main__':
s="abcd"
t="cdab"
solution = Solution()
print(" s与t分别为：", s, t)
print(" 是否:", solution.isTwin(s, t))
【例11】最接近target的值 难度等级★
3.代码实现
#参数array是输入列表
#参数target是目标值
#返回值是整数
class Solution:
def closestTargetValue(self, target, array):
n = len(array)
if n < 2:
return -1
array.sort()
diff = 0x7fffffff
left = 0
right = n - 1
while left < right:
if array[left] + array[right] > target:
right -= 1
else:
diff = min(diff, target - array[left] - array[right])
left += 1
if diff == 0x7fffffff:
return -1
else:
return target - diff
if __name__ == '__main__':
array = [1,3,5,11,7]
target = 15
solution = Solution()
print(" 输入数组为：", array,"目标值为：", target)
print(" 最近可以得到值为:", solution.closestTargetValue(target, array))
【例12】点积 难度等级★
3.代码实现
#参数A和B是输入列表
#返回值是个整数，是点积
class Solution:
def dotProduct(self, A, B):
if len(A) == 0 or len(B) == 0 or len(A) != len(B):
return -1
ans = 0
for i in range(len(A)):
ans += A[i] * B[i]
return ans
if __name__ == '__main__':
A = [1,1,1]
B = [2,2,2]
solution = Solution()
print(" A与B分别为：", A, B)
print(" 点积为：", solution.dotProduct(A, B))
【例13】函数运行时间 难度等级★
3.代码实现
#参数s为输入原始字符串
#返回值是个字符串，意为每个名字的函数运行了多久
class Solution:
def getRuntime(self, a):
map={
}
for i in a:
count = 0
while not i[count] == ' ':
count = count + 1
fun = i[0 : count]
if i[count+2] == 'n':
count = count + 7
v = int(i[count:len(i)])
if fun in map.keys():
map[fun] = v - map[fun]
else:
map[fun] = v
else:
count = count + 6
v = int(i[count:len(i)])
map[fun] = v - map[fun]
res=[]
for i in map:
res.append(i)
res.sort()
for i in range(0,len(res)):
res[i] = res[i] + '|' + str(map[res[i]])
return res
if __name__ == '__main__':
s = ["F1 Enter 10","F2 Enter 18","F2 Exit 19","F1 Exit 20"]
solution = Solution()
print(" 输入运行时间为：", s)
print(" 每个输出时间为:", solution.getRuntime(s))
【例14】查询区间 难度等级★
1.问题描述
给定一个包含若干个区间的List数组，长度是1000，例如，[500,1500]，[2100,3100].给定一个number，number是否在这些区间内，返回True或False。
2.问题示例
输入是 List = [[100,1100],[1000,2000],[5500,6500]]和number = 6000，输出是True，6000在区间[5500,6500]。输是List = [[100,1100],[2000,3000]]和number = 3500，输出是 False，3500不在list的任何一个区间中。
3.代码实现
#参数List是区间列表
#参数number是待查数字
#返回值是个字符串，True或者False
class Solution:
def isInterval(self, intervalList, number):
high = len(intervalList) - 1
low = 0
while high >= low:
if 0 < (number - intervalList[(high + low)//2][0]) <= 1000:
return 'True'
elif 1000 < number - intervalList[(high + low)//2][0]:
low = (high + low) // 2 + 1
elif 0 > number - intervalList[(high + low)//2][0]:
high = (high + low) // 2 - 1
return 'False'
if __name__ == '__main__':
number = 6000
intervalList = [[100,1100],[1000,2000],[5500,6500]]
solution = Solution()
print(" 区间List为：", intervalList)
print(" 数字为：", number)
print(" 是否在区间中:", solution.isInterval(intervalList, number))
4.运行结果
输入区间List为： [[100, 1100], [1000, 2000], [5500, 6500]]
输出数字为： 6000
是否在区间中: True
【例15】飞行棋 难度等级★
3.代码实现
#参数length是棋盘长度（不包含起始点）
#参数connections是跳点的集合
#返回值是个整数，代表最小步数
class Solution:
def modernLudo(self, length, connections):
ans = [i for i in range(length+1)]
for i in range(length+1):
for j in range(1,7):
if i - j >= 0:
ans[i] = min(ans[i], ans[i-j]+1)
for j in connections:
if i == j[1]:
ans[i] = min(ans[i], ans[j[0]])
return ans[length]
#参数length是棋盘长度（不包含起始点）
#参数connections是跳点的集合
#返回值是个整数，代表最小步数
#SPFA解法
class Solution:
"""
参数length为棋盘长度
参数connections为连接位置表
返回最小次数
"""
def modernLudo(self, length, connections):
dist = [1000000000 for i in range(100050)]
vis = [0 for i in range(100050)]
Q = [0 for i in range(100050)]
st = 0
ed = 0
dist[1] =0
vis[1] = 1
Q[ed] = 1;
ed += 1
while(st<ed) :
u = Q[st]
st += 1
vis[u] = 0
for roads in connections :
if(roads[0] != u):
continue
v = roads[1]
if(dist[v] > dist[u]):
dist[v] = dist[u]
if(vis[v] == 0) :
vis[v] = 1
Q[ed] = v
ed += 1
for i in range(1, 7):
if (i + u > length):
break
v = i + u
if(dist[v] > dist[u] + 1) :
dist[v] = dist[u] + 1
if(vis[v] == 0):
vis[v] = 1
Q[ed] = v
ed += 1
return dist[length]
if __name__ == '__main__':
length = 15
connections = [[2, 8],[6, 9]]
solution = Solution()
print(" 棋盘长度为：", length)
print(" 连接为：", connections)
print(" 最小需要为:", solution.modernLudo(length, connections))
【例16】移动石子 难度等级★
3.代码实现
#参数arr是一个列表
#返回值为整数，为最小移动次数
class Solution:
def movingStones(self, arr):
arr = sorted(arr)
even = 0
odd = 0
for i in range(0,len(arr)):
odd += abs(arr[i]-(2*i+1))
even += abs(arr[i] - (2*i+2))
if odd < even:
return odd
return even
if __name__ == '__main__':
arr = [1, 6, 7, 8, 9]
solution = Solution()
print(" 数组是：", arr)
print(" 最小移动数是:", solution.movingStones(arr))
【例17】数组剔除元素后的乘积 难度等级★
3.代码实现
class Solution:
#参数A: 整数数组A
#返回值: 整数数组B
def productExcludeItself(self, A):
length ,B = len(A) ,[]
f = [ 0 for i in range(length + 1)]
f[ length ] = 1
for i in range(length - 1 , 0 , -1):
f[ i ] = f[ i + 1 ] * A[ i ]
tmp = 1
for i in range(length):
B.append(tmp * f[ i + 1 ])
tmp *= A[ i ]
return B
#主函数
if __name__ == '__main__':
solution = Solution()
A = [1, 2, 3, 4]
B = solution.productExcludeItself(A)
print("输入：", A)
print("输出：", B)
【例18】键盘的一行 难度等级★
3.代码实现
class Solution:
#参数words为字符串列表
#返回字符串列表
def findWords(self, words):
res = []
s = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
for w in words:
for j in range(3):
flag = 1
for i in w:
if i.lower() not in s[j]:
flag = 0
break
if flag == 1:
res.append(w)
break
return res
#主函数
if __name__ == '__main__':
word = ["Hello", "Alaska", "Dad", "Peace"]
s = Solution()
print("输入为：",word)
print("输出为：",s.findWords(word))
【例19】第n个数位 难度等级★
3.代码实现
class Solution:
"""
参数n为整数
返回整数
"""
def findNthDigit(self, n):
# 初始化一位数的个数为9，从1开始
length = 1
count = 9
start = 1
while n > length * count:
# 以此类推二位数的个数为90，从10开始
n -= length * count
length += 1
count *= 10
start *= 10
# 找到第n位数所在的整数start
start += (n - 1) // length
return int(str(start)[(n - 1) % length])
#主函数
if __name__ == '__main__':
s = Solution()
n = 11
print("输入为：",n)
print("输出为：",s.findNthDigit(n))
【例20】找不同 难度等级★
3.代码实现
class Solution:
"""
参数s为字符串
参数t为字符串
返回字符
"""
def findTheDifference(self, s, t):
flag = 0
for i in range(len(s)):
# 计算每一位字符的Ascll码之差
flag += (ord(t[i]) - ord(s[i]))
flag += ord(t[-1])
return chr(flag)
#主函数
if __name__ == '__main__':
s = Solution()
n = "abcd"
t = "abcde"
print("输入字符串1为：",n)
print("输入字符串2为：",t)
print("输出插入字符为：",s.findTheDifference(n,t))
【例21】第k个组合 难度等级★
3.代码实现
#参数k代表寻找的组数
#参数n代表有多少人
#返回值是一个列表，是目标数组数里的按序排列
class Solution:
def getCombination(self, n, k):
C = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
C[i][0] = 1
C[i][i] = 1
# Compute C(m, n) using C(m, n) = C(m-1, n-1)+C(m-1, n).
for i in range(1, n + 1):
for j in range(1, i):
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
ans = []
curr_index = 1
for i in range(1, n // 2 + 1):
base = C[n - curr_index][n // 2 - i]
# Search for next digit in ans.
while k > base:
curr_index = curr_index + 1
base = base + C[n - curr_index][n // 2 - i]
base = base - C[n - curr_index][n // 2 - i]
k = k - base;
ans.append(curr_index)
curr_index = curr_index + 1
return ans
if __name__ == '__main__':
n = 8
k = 11
solution = Solution()
print(" 人数为：", n, " 找第k组：", k)
print(" 第k组为:", solution.getCombination(n, k))
【例22】平面列表 难度等级★
3.代码实现
class Solution(object):
#参数nestedList： 一个列表，列表中的每个元素都可以是一个列表或整数
#返回值：一个整数列表
def flatten(self, nestedList):
stack = [nestedList]
flatten_list = []
while stack:
top = stack.pop()
if isinstance(top, list):
for elem in reversed(top):
stack.append(elem)
else:
flatten_list.append(top)
return flatten_list
#主函数
if __name__ == '__main__':
solution = Solution()
nums = [[1,2],2,[1,1,3]]
flatten_list = solution.flatten(nums)
print("输入：", nums)
print("输出：", flatten_list)
【例23】子域名访问计数 难度等级★
2.问题示例
例如，输入[“9001 school.bupt.edu”]，输出[“9001 school.bupt.edu”, “9001 bupt.edu”, “9001 edu”]，只有一个域名：“school.bupt.edu”，如题所述，子域名"bupt.edu"和"edu"也会被访问，所以要访问9001次。
3.代码实现
class Solution:
# 利用hash表，对子域名计数。注意对字符串的划分
def subdomainVisits(self, cpdomains):
count = {
}
for domain in cpdomains:
visits = int(domain.split()[0])
domain_segments = domain.split()[1].split('.')
top_level_domain = domain_segments[-1]
sec_level_domain = domain_segments[-2] + '.' + domain_segments[-1]
count[top_level_domain] = count[top_level_domain] + visits if top_level_domain in count.keys() else visits
count[sec_level_domain] = count[sec_level_domain] + visits if sec_level_domain in count.keys() else visits
if domain.count('.') == 2:
count[domain.split()[1]] = count[domain.split()[1]] + visits if domain.split()[1] in count.keys() else visits
return [str(v) + ' ' + k for k,v in count.items()]
if __name__ == '__main__':
solution=Solution()
inputnum=["1201 school.bupt.edu"]
print("输入为：",inputnum)
print("输入为：",solution.subdomainVisits(inputnum))
4.运行结果
输入为： [‘1201 school.bupt.edu’]
输入为： [‘1201 edu’, ‘1201 bupt.edu’, ‘1201 school.bupt.edu’]
【例24】最长AB子串 难度等级★
3.代码实现
#参数S是待查字符串
#返回值是一个整数，是最大字符串长度
class Solution:
def getAns(self, S):
ans = 0
arr = [0 for i in range(len(S))]
sets = {
}
if S[0] == 'A':
arr[0] = 1
sets[1] = 0
else:
arr[0] = -1
sets[-1] = 0
for i in range(1, len(S)):
if S[i] == 'A':
arr[i] = arr[i - 1] + 1
if arr[i] == 0:
ans = i + 1
continue
if arr[i] in sets:
ans = max(ans, i - sets[arr[i]])
else:
sets[arr[i]] = i
else:
arr[i] = arr[i - 1] - 1
if arr[i] == 0:
ans = i + 1
continue
if arr[i] in sets:
ans = max(ans, i - sets[arr[i]])
else:
sets[arr[i]] = i
return ans
if __name__ == '__main__':
S = "ABABAB"
solution = Solution()
print(" AB字符串为：", S)
print(" 最长AB出现次数相同的子字符串长度是:", solution.getAns(S))
【例25】删除字符 难度等级★
3.代码实现
#参数s是待删除字符的原字符串
#参数t是目标字符串
#返回值是一个布尔值，意为能否由s删除一些字符得到t
class Solution:
def canGetString(self, s, t):
pos = 0
for x in t:
while pos < len(s) and s[pos] != x:
pos += 1
if pos == len(s):
return False
pos += 1
return True
if __name__ == '__main__':
s="abc"
t="c"
solution = Solution()
print(" 原string和目标string分别为：", s, t)
print(" 能否实现:", solution.canGetString(s, t))
【例26】字符串写入的行数 难度等级★
3.代码实现
class Solution(object):
def numberOfLines(self, widths, S):
#参数widths为数组
#参数S为字符串
#返回数组
line = 1
space = 0
flag = False
for c in S:
if flag:
line += 1
flag = False
space += widths[ord(c) - 97]
if space > 100:
line += 1
space = widths[ord(c) - 97]
elif space == 100:
space = 0
flag = True
return [line, space]
if __name__ == '__main__':
solution=Solution()
width=[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
s="abcdefghijklmnopqrstuvwxyz"
print("输入字符宽度为：",width)
print("输入的字符串为：",s)
print("输出为：",solution.numberOfLines(width,s))
【例27】独特的摩尔斯编码 难度等级★
3.代码实现
class Solution:
def uniqueMorseRepresentations(self, words):
#参数words为列表
#返回整数
# 用set保存出现过的摩斯码即可
morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
"-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
s = set()
for word in words:
tmp = ''
for w in word:
tmp += morse[ord(w) - 97]
s.add(tmp)
return len(s)
if __name__ == '__main__':
solution=Solution()
inputnum=["gin", "zen", "gig", "msg"]
print("输入为：",inputnum)
print("输出为：",solution.uniqueMorseRepresentations(inputnum))
【例28】比较字符串 难度等级★
3.代码实现
class Solution:
#参数A : 包括大写字母的字符串
#参数B : 包括大写字母的字符串
#返回值: 如果字符串A包含B中的所有字符，返回True，否则返回False
def compareStrings(self, A, B):
if len(B) == 0:
return True
if len(A) == 0:
return False
#trackTable首先记录A中所有的字符以及它们的个数，然后遍历B,如果出现trackTable[i]小于0的情况，说明B中该字符出现的次数大于在A中出现的次数
trackTable = [0 for _ in range(26)]
for i in A:
trackTable[ord(i) - 65] += 1
for i in B:
if trackTable[ord(i) - 65] == 0:
return False
else:
trackTable[ord(i) -65] -= 1
return True
#主函数
if __name__ == '__main__':
solution = Solution()
A = "ABCD"
B = "ACD"
print("输入：", A, B)
print("输出：", solution.compareStrings(A,B))
【例29】能否转换 难度等级★
3.代码实现
#参数S和T为原始字符串和目标字符串
#返回值是布尔值，代表能否转换
class Solution:
def canConvert(self, s, t):
j = 0
for i in range(len(s)):
if s[i] == t[j]:
j += 1
if j == len(t):
return True
return False
if __name__ == '__main__':
s = "longterm"
t = "long"
solution = Solution()
print(" S与T分别为：", s, t)
print(" 能否删除得到:", solution.canConvert(s, t))
【例30】经典二分查找问题 难度等级★
3.代码实现
#参数nums是一个整型排序数组
#参数target是一个任意整型数
#返回值是一个整型数，若nums存在，返回该数位置；若不存在，返回-1
class Solution:
def findPosition(self, nums, target):
if len(nums) is 0:
return -1
start = 0
end = len(nums)-1
while start + 1 < end :
mid = start + (end-start)//2
if nums[mid] == target:
end = mid
elif nums[mid] < target:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
#主函数
if __name__ == '__main__':
generator=[1,2,2,4,5,5]
target = 2
solution = Solution()
print("输入:", generator)
print("输出:", solution. myAtoi(generator, target))
【例31】抽搐词 难度等级★
3.代码实现
class Solution:
def twitchWords(self, str):
n = len(str)
c = str[0]
left = 0
ans = []
for i in range(n):
if str[i] != c:
if i - left >= 3:
ans.append([left, i - 1])
c = str[i]
left = i
if n - left >= 3:
ans.append([left, n - 1])
return ans
#主函数
if __name__ == '__main__':
str = "whooooisssbesssst"
solution = Solution()
print(" 输入为：", str)
print(" 输出为：", solution.twitchWords(str))
【例32】排序数组中最接近元素 难度等级★
3.代码实现
#参数nums是一个整型排序数组
#参数target是一个整型数
#返回值是这个数组中最接近target的整数
class Solution:
def findPosition(self, A, target):
if not A:
return -1
start, end = 0,len(A)-1
while start+ 1<end:
mid = start +(end-start)//2
if A[mid]<target:
start= mid
elif A[mid]>target:
end = mid
else:
return mid
if target-A[start]<A[end]-target:
return start
else:
return end
#主函数
if __name__ == '__main__':
generator = [1,4,6]
target = 3
solution = Solution()
print("输入：", generator,",target =",target)
print("输出：", solution.findPosition(generator, target))
【例33】构造矩形 难度等级★
3.代码实现
class Solution:
#参数area为整数
#返回为整数
def constructRectangle(self, area):
import math
W = math.floor(math.sqrt(area))
while area % W != 0:
W -= 1
return [area // W, W]
#主函数
if __name__ == '__main__':
s = Solution()
area =4
print("输入面积为：",area)
print("输出长宽为：",s.constructRectangle(area))
【例34】两个排序数组合组和的第k小元素 难度等级★
3.代码实现
#参数A，B是整型排序数组
#参数k是一个整型数，表示第k小
#返回值是数组中第k小的整数
class Solution:
def kthSmallestSum(self, A, B, k):
if not A or not B:
return None
n, m = len(A), len(B)
minheap = [(A[0] + B[0], 0, 0)]
visited = set([0])
num = None
for _ in range(k):
num, x, y = heapq.heappop(minheap)
if x + 1 < n and (x + 1) * m + y not in visited:
heapq.heappush(minheap, (A[x + 1] + B[y], x + 1, y))
visited.add((x + 1) * m + y)
if y + 1 < m and x * m + y + 1 not in visited:
heapq.heappush(minheap, (A[x] + B[y + 1], x, y + 1))
visited.add(x * m + y + 1)
return num
#主函数
if __name__ == '__main__':
generator_A = [1,7,11]
generator_B = [2,4,6]
k = 3
solution = Solution()
print("输入:", generator_A,generator_B)
print("k= ",k)
print("输出:", solution.kthSmallestSum(generator_A,generator_B, k))
【例35】玩具工厂 难度等级★
3.代码实现
#参数type是一个字符串，表示不同玩具类型
#返回值是不同类型对应的玩具对象
class Toy:
def talk(self):
raise NotImplementedError('This method should have implemented.')
class Dog(Toy):
def talk(self):
print ("Wow")
class Cat(Toy):
def talk(self):
print ("Meow")
class ToyFactory:
def getToy(self, type):
if type == 'Dog':
return Dog()
elif type == 'Cat':
return Cat()
return None
#主函数
if __name__ == '__main__':
ty = ToyFactory()
type='Dog'
type1='Cat'
toy = ty.getToy(type)
print("输入：type= Dog，输出：")
toy.talk()
toy = ty.getToy(type1)
print("输入：type= Cat，输出：")
toy.talk()
【例36】形状工厂 难度等级★
3.代码实现
#参数shapeType是一个字符串，表示不同形状
#返回值是不同对象，Triangle，Square，Rectangle
class Shape:
def draw(self):
raise NotImplementedError('This method should have implemented.')
class Triangle(Shape):
def draw(self):
print(" /\\")
print(" / \\")
print("/____\\")
class Rectangle(Shape):
def draw(self):
print(" ----")
print("| |")
print(" ----")
class Square(Shape):
def draw(self):
print( " ----")
print( "| |")
print( "| |")
print( " ----")
class ShapeFactory:
def getShape(self, shapeType):
if shapeType == "Triangle":
return Triangle()
elif shapeType == "Rectangle":
return Rectangle()
elif shapeType == "Square":
return Square()
else:
return None
#主函数
if __name__ == '__main__':
sf = ShapeFactory()
shapeType='Triangle'
shape = sf.getShape(shapeType)
print("输入：type= Triangle，\n输出：")
shape.draw()
shapeType1='Rectangle'
shape = sf.getShape(shapeType1)
print("输入：type= Rectangle，\n输出：")
shape.draw()
shapeType2='Square'
shape = sf.getShape(shapeType2)
print("输入：type= Square，\n输出：")
shape.draw()
【例37】二叉树最长连续序列 难度等级★
3.代码实现
#参数root是一个二叉树的根
#返回值是此二叉树中最长连续序列
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def longestConsecutive(self, root):
return self.helper(root, None, 0)
def helper(self, root, parent, len):
if root is None:
return len
if parent != None and root.val == parent.val + 1:
len += 1
else:
len = 1
return max(len, max(self.helper(root.left, root, len), \
self.helper(root.right, root, len)))
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(5)
solution= Solution()
print("输入是： {1,#,3,2,4,#,#,#,5}")
print("输出是：", solution.longestConsecutive(root))
【例38】首字母大写 难度等级★
3.代码实现
class Solution:
#参数s为字符串
#返回字符串
def capitalizesFirst(self, s):
n = len(s)
s1 = list(s)
if s1[0] >= 'a' and s1[0] <= 'z':
s1[0] = chr(ord(s1[0]) - 32)
for i in range(1, n):
if s1[i - 1] == ' ' and s1[i] != ' ':
s1[i] = chr(ord(s1[i]) - 32)
return ''.join(s1)
if __name__ == '__main__':
s = "i am from bupt"
solution = Solution()
print("输入为：",s)
print("输出为：",solution.capitalizesFirst(s))
【例39】7进制 难度等级★
3.代码实现
class Solution:
#参数num为10进制整数
#返回7进制整数
#不断执行对7取模和取整操作，直到商小于7
def convertToBase7(self, num):
if num < 0:
return '-' + self.convertToBase7(-num)
if num < 7:
return str(num)
return self.convertToBase7(num // 7) + str(num % 7)
if __name__ == '__main__':
num = 777
solution = Solution()
print("输入为：",num)
print("输出为：",solution.convertToBase7(num))
【例40】查找数组中没有出现的所有数字 难度等级★
3.代码实现
class Solution:
#参数为nums整数列表
#返回整数列表
def findDisappearedNumbers(self, nums):
n = len(nums)
s = set(nums)
res = [i for i in range(1, n+1) if i not in s]
return res
#主函数
if __name__ == '__main__':
s = Solution()
n = [4,3,2,7,8,2,3,1]
print("输入为：",n)
print("输出为：",s.findDisappearedNumbers(n))
【例41】回旋镖的数量 难度等级★
3.代码实现
class Solution(object):
def getDistance(self, a, b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return dx * dx + dy * dy
def numberOfBoomerangs(self, points):
#参数points为整数列表
#返回整数
if points == None:
return 0
ans = 0
for i in range(len(points)):
disCount = {
}
for j in range(len(points)):
if i == j:
continue
distance = self.getDistance(points[i], points[j])
count = disCount.get(distance, 0)
disCount[distance] = count + 1
for distance in disCount:
ans += disCount[distance] * (disCount[distance] - 1)
return ans
#主函数
if __name__ == '__main__':
s = Solution()
n = [[0,0],[1,0],[2,0]]
print("输入为：",n)
print("输出为：",s.numberOfBoomerangs(n))
【例42】合并排序数组 难度等级★
3.代码实现
class Solution:
#参数A: 已排序整数数组A有m个元素，但是A的大小是m+n
#参数m: 整数
#参数B: 已排序整数数组B，它有n个元素
#参数n: 整数
#返回值: 无
def mergeSortedArray(self, A, m, B, n):
i, j = m-1, n-1
t = len(A)-1
while i >= 0 or j >= 0:
if i < 0 or (j >= 0 and B[j] > A[i]):
A[t] = B[j]
j -= 1
else:
A[t] = A[i]
i -= 1
t -= 1
#主函数
if __name__ == '__main__':
solution = Solution()
A = [1,2,3,0,0]
m = 3
B = [4,5]
n = 2
solution.mergeSortedArray(A, m, B, n)
print("输入：A = [1,2,3,0,0], 3, B = [4,5], 2")
print("输出：", A)
【例43】最小路径和 难度等级★
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()
grid = [[1,3,1],[1,5,1],[4,2,1]]
length = solution.minPathSum(grid)
print("输入：", grid)
print("输出：", length)
【例44】大小写转换 难度等级★
3.代码实现
class Solution:
#参数character: 字符
#返回值: 字符
def lowercaseToUppercase(self, character):
#ASCII码中小写字母与对应的大写字母相差32
return chr(ord(character) - 32)
#主函数
if __name__ == '__main__':
solution = Solution()
ans = solution.lowercaseToUppercase('a')
print("输入： a")
print("输出：", ans)
【例45】原子的数量 难度等级★
3.代码实现
import re
import collections
class Solution(object):
def countOfAtoms(self, formula):
parse = re.findall(r"([A-Z][a-z]*)(\d*)|(\()|(\))(\d*)", formula)
stack = [collections.Counter()]
for name, m1, left_open, right_open, m2 in parse:
if name:
stack[-1][name] += int(m1 or 1)
if left_open:
stack.append(collections.Counter())
if right_open:
top = stack.pop()
for k in top:
stack[-1][k] += top[k] * int(m2 or 1)
return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '') for name in sorted(stack[-1]))
#主函数
if __name__ == '__main__':
solution = Solution()
Test_in = "H2O"
Test_out = solution.countOfAtoms(Test_in)
print("输入为：",Test_in)
print("输出为：",Test_out)
【例46】矩阵中的最长递增路径 难度等级★
3.代码实现
DIRECTIONS = [(1, 0), (-1, 0), (0, -1), (0, 1)]
class Solution:
"""
参数matrix为整数矩阵
返回整数
"""
def longestIncreasingPath(self, matrix):
if not matrix or not matrix[0]:
return 0
sequence = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
sequence.append((matrix[i][j], i, j))
sequence.sort()
check = {
}
for h, x, y in sequence:
cur_pos = (x, y)
if cur_pos not in check:
check[cur_pos] = 1
cur_path = 0
for dx, dy in DIRECTIONS:
if self.is_valid(x+dx, y+dy, matrix, h):
cur_path = max(cur_path, check[(x+dx, y+dy)])
check[cur_pos] += cur_path
vals = check.values()
return max(vals)
def is_valid(self, x, y, matrix, h):
row, col = len(matrix), len(matrix[0])
return x >= 0 and x < row and y >= 0 and y < col and matrix[x][y]<h
#主函数
if __name__ == '__main__':
solution = Solution()
Test_in = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Test_out = solution.longestIncreasingPath(Test_in)
print("输入为：",Test_in)
print("输出为：",Test_out)
【例47】大小写转换 难度等级★
3.代码实现
class Solution:
#参数str: 字符串
#返回值: 字符串
def lowercaseToUppercase2(self, str):
p = list(str)
#遍历整个字符串，将所有的小写字母转成大写字母
for i in range(len(p)):
if p[i] >= 'a' and p[i] <= 'z':
p[i] = chr(ord(p[i]) - 32)
return ''.join(p)
#主函数
if __name__ == '__main__':
solution = Solution()
s1 = "abC12"
ans = solution.lowercaseToUppercase2(s1)
print("输入：", s1)
print("输出：", ans)
【例48】水仙花数 难度等级★
3.代码实现
class Solution:
#参数n: 数字的位数
@返回值: 所有n位数的水仙花数
def getNarcissisticNumbers(self, n):
res = []
for x in range([0, 10**(n-1)][n > 1], 10**n):
y, k = x, 0
while x > 0:
k += (x % 10)**n
x //= 10
if k == y: res.append(k)
return res
#主函数
if __name__ == '__main__':
solution = Solution()
n = 4
ans = solution.getNarcissisticNumbers(n)
print("输入：", n)
print("输出：", ans)
【例49】余弦相似度 难度等级★
3.代码实现
import math
#参数A，B都是一个整型数组，表示两个矢量
#返回值是两个输入矢量的余弦相似度
class Solution:
def cosineSimilarity(self, A, B):
if len(A) != len(B):
return 2
n = len(A)
up = 0
for i in range(n):
up += A[i] * B[i]
down = sum(a*a for a in A) * sum(b*b for b in B)
if down == 0:
return 2
return up / math.sqrt(down)
#主函数
if __name__ == '__main__':
generator_A = [1,4,0]
generator_B = [1,2,3]
solution = Solution()
print("输入: A=", generator_A)
print("输入: B=", generator_B)
print("输出: ", solution.cosineSimilarity(generator_A,generator_B))
【例50】链表节点计数 难度等级★
3.代码实现
#参数head是链表的头部
#返回值是链表的长度
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
def countNodes(self, head):
cnt = 0
while head is not None:
cnt += 1
head = head.next
return cnt
#主函数
if __name__ == '__main__':
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
solution = Solution()
print("输入: ", node1.val,node2.val,node3.val,node4.val)
print("输出: ", solution. countNodes(node1))
【例51】最高频的K个单词 难度等级★
3.代码实现
#参数words是一个字符串数组
#参数k代表第k高频率出现
#返回值是一个字符串数组，表示出现频率前k高字符串
class Solution:
def topKFrequentWords(self, words, k):
dict = {
}
res = []
for word in words:
if word not in dict:
dict[word] = 1
else:
dict[word] += 1
sorted_d = sorted(dict.items(), key=lambda x:x[1], reverse=True)
for i in range(k):
res.append(sorted_d[i][0])
return res
#主函数
if __name__ == '__main__':
generator = ["yes", "long", "code",
"yes", "code", "baby",
"you", "baby", "chrome",
"safari", "long", "code",
"body", "long", "code"]
k = 4
solution = Solution()
print("输入: ", generator)
print("输入: ","k = ", k)
print("输出: ", solution.topKFrequentWords(generator,k))
【例52】单词的添加与查找 难度等级★
3.代码实现
#参数word是要添加的的单词
#返回值是个布尔值，查找单词成功则返回True，否则，返回False
class TrieNode:
def __init__(self):
self.children = {
}
self.is_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_word =True
def search(self, word):
if word is None:
return False
return self.search_helper(self.root, word, 0)
def search_helper(self, node, word, index):
if node is None:
return False
if index >= len(word):
return node.is_word
char = word[index]
if char != '.':
return self.search_helper(node.children.get(char), word, index + 1)
for child in node.children:
if self.search_helper(node.children[child], word, index + 1):
return True
return False
#主函数
if __name__ == '__main__':
solution = WordDictionary()
solution.addWord("bad")
solution.addWord("dad")
solution.addWord("mad")
print('输入： addWord("bad"),addWord("dad"),addWord("mad")')
print('输入： search("pad"),search("dad"),search(".ad"),search("b..")')
print("输出： ",
solution.search("pad"),
solution.search("bad"),
solution.search(".ad"),
solution.search("b.."))
【例53】石子归并 难度等级★
3.代码实现
#参数A是一个整型数组
#返回值是一个整数，表示最小的合并代价
import sys
class Solution:
def stoneGame(self, A):
n = len(A)
if n < 2:
return 0
dp = [[0] * n for _ in range(n)]
cut = [[0] * n for _ in range(n)]
range_sum = self.get_range_sum(A)
for i in range(n - 1):
dp[i][i + 1] = A[i] + A[i + 1]
cut[i][i + 1] = i
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = sys.maxsize
for mid in range(cut[i][j - 1], cut[i + 1][j] + 1):
if dp[i][j] > dp[i][mid] + dp[mid + 1][j] + range_sum[i][j]:
dp[i][j] = dp[i][mid] + dp[mid + 1][j] + range_sum[i][j]
cut[i][j] = mid
return dp[0][n - 1]
def get_range_sum(self, A):
n = len(A)
range_sum = [[0] * n for _ in range(len(A))]
for i in range(n):
range_sum[i][i] = A[i]
for j in range(i + 1, n):
range_sum[i][j] = range_sum[i][j - 1] + A[j]
return range_sum
#主函数
if __name__ == '__main__':
generator = [3,4,3]
solution = Solution()
print("输入：", generator)
print("输出：", solution.stoneGame(generator))
【例54】简单计算器 难度等级★
3.代码实现
#参数a，b是两个任意整数
#operator是运算符+, -, *, /
#返回值是浮点型运算结果
class Solution:
def calculate(self, a, operator, b):
if operator == '+':
return a + b
elif operator == '-':
return a - b
elif operator == '*':
return a * b
elif operator == '/':
return a / b
#主函数
if __name__ == '__main__':
a=8
b=3
operator1='+'
operator2='-'
operator3='*'
operator4='/'solution = Solution()
print("输入：", a ,operator1 ,b)
print("输出：", solution.calculate(a,operator1,b))
print("输入：", a ,operator2 ,b)
print("输出：", solution.calculate(a,operator2,b))
print("输入：", a ,operator3 ,b)
print("输出：", solution.calculate(a,operator3,b))
print("输入：", a ,operator4 ,b)
print("输出：", solution.calculate(a,operator4,b))
【例55】数组第二大数 难度等级★
3.代码实现
#参数nums是一个整型数组
#返回值secValue是数组中第二大数
class Solution:
def secondMax(self, nums):
maxValue = max(nums[0], nums[1])
secValue = min(nums[0], nums[1])
for i in range(2, len(nums)):
if nums[i] > maxValue:
secValue = maxValue
maxValue = nums[i]
elif nums[i] > secValue:
secValue = nums[i]
return secValue
#主函数
if __name__ == '__main__':
generator = [3,4,7,9]
solution = Solution()
print("输入： ", generator)
print("输出： ", solution.secondMax(generator))
【例56】二叉树叶子节点之和 难度等级★
3.代码实现
#参数root是二叉树的根
#返回值是个整数，叶子节点之和
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
def leafSum(self, root):
p = []
self.dfs(root, p)
return sum(p)
def dfs(self, root, p):
if root is None:
return
if root.left is None and root.right is None:
p.append(root.val)
self.dfs(root.left, p)
self.dfs(root.right, p)
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
solution = Solution()
print("输入：", root.val,root.left.val,root.right.val,root.left.left.val)
print("输出：", solution.leafSum(root))
【例57】二叉树的某层节点之和 难度等级★
3.代码实现
#参数root是二叉树的根
#参数level是树的目标层的深度
#返回值是一个整数，表示该level叶子节点之和
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
class Solution:
def levelSum(self, root, level):
p = []
self.dfs(root, p, 1, level)
return sum(p)
def dfs(self, root, p, dep, level):
if root is None:
return
if dep == level:
p.append(root.val)
return
self.dfs(root.left, p, dep+1, level)
self.dfs(root.right, p, dep+1, level)
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
root.left.right.right = TreeNode(8)
root.right.right.right = TreeNode(9)
depth = 3
solution = Solution()
print("输入：",root.val,root.left.val,root.right.val,root.left.left.val,
root.left.right.val,root.right.left.val,root.right.right.val,
root.left.right.right.val,root.right.right.right.val)
print("输入： depth= ", depth)
print("输出：",solution.levelSum(root,depth))
【例58】判断尾数 难度等级★
3.代码实现
#参数str是输入01串
#返回值是一个整数，代表最后一个词的长度
class Solution:
def judgeTheLastNumber(self, str):
if str[-1] == 1:
return 2
for i in range(-2, -len(str) - 1, -1):
if str[i] == 0:
return -1 * ((i * -1 + 1) % 2) + 2
return -1 * (len(str) % 2) + 2
if __name__ == '__main__':
str = "111110"
solution = Solution()
print(" 原01串为：", str)
print(" 最后一个词长度是:", solution.judgeTheLastNumber(str))
【例59】两个字符串是变位词 难度等级★
3.代码实现
class Solution:
#参数s: 第一个字符串
#参数t: 第二个字符串
#返回值: True或False
def anagram(self, s, t):
set_s = [0] * 256
set_t = [0] * 256
for i in range(0, len(s)):
set_s[ord(s[i])] += 1
for i in range(0, len(t)):
set_t[ord(t[i])] += 1
for i in range(0, 256):
if set_s[i] != set_t[i]:
return False
return True
#主函数
if __name__ == '__main__':
solution = Solution()
s = "abcd"
t = "dcba"
ans = solution.anagram(s, t)
print("输入：", s, t)
print("输出：", ans)
【例60】最长单词 难度等级★
3.代码实现
class Solution:
#参数dictionary: 字符串数组
#返回值: 字符串数组
def longestWords(self, dictionary):
answer = []
maxLength = 0
for item in dictionary:
if len(item) > maxLength:
maxLength = len(item)
answer = [item]
elif len(item) == maxLength:
answer.append(item)
return answer
#主函数
if __name__ == '__main__':
solution = Solution()
dic = ["dog","google","facebook","internationalization","blabla"]
answer = solution.longestWords(dic)
print("输入：", dic)
print("输出：", answer)
【例61】机器人能否返回原点 难度等级★
3.代码实现
class Solution:
#参数moves为字符串
#返回布尔类型
def judgeCircle(self, moves):
count_RL = count_UD = 0
for c in moves:
if c == 'R':
count_RL += 1
if c == 'L':
count_RL -= 1
if c == 'U':
count_UD += 1
if c == 'D':
count_UD -= 1
return count_RL == 0 and count_UD == 0
if __name__ == '__main__':
solution=Solution()
moves="UD"
print("输入为：",moves)
print("输出为：",solution.judgeCircle(moves))
【例62】链表倒数第n个节点 难度等级★
3.代码实现
#定义链表节点
class ListNode(object):
def __init__(self, val):
self.val = val
self.next = None
class Solution:
#参数head: 链表的第一个节点。
#参数n: 整数
#返回值: 单链表的第n到最后一个节点。
def nthToLast(self, head, n):
if head is None or n < 1:
return None
cur = head.next
while cur is not None:
cur.pre = head
cur = cur.next
head = head.next
n -= 1
while n > 0:
head = head.pre
n -= 1
return head
#主函数
if __name__ == '__main__':
solution = Solution()
l0 = ListNode(3)
l1 = ListNode(2)
l2 = ListNode(1)
l3 = ListNode(5)
l0.next = l1
l1.next = l2
l2.next = l3
ans = solution.nthToLast(l0, 2).val
print("输入： 3->2->1->5->null, n = 2")
print("输出：", ans)
【例63】链表求和 难度等级★
3.代码实现
#定义链表节点
class ListNode(object):
def __init__(self, val):
self.val = val
self.next = None
class Solution:
def addLists(self, l1, l2) -> list:
dummy = ListNode(None)
tail = dummy
carry = 0
while l1 or l2 or carry:
num = 0
if l1:
num += l1.val
l1 = l1.next
if l2:
num += l2.val
l2 = l2.next
num += carry
digit, carry = num % 10, num // 10
node = ListNode(digit)
tail.next, tail = node, node
return dummy.next
#主函数
if __name__ == '__main__':
solution = Solution()
l0 = ListNode(7)
l1 = ListNode(1)
l2 = ListNode(6)
l0.next = l1
l1.next = l2
l3 = ListNode(5)
l4 = ListNode(9)
l5 = ListNode(2)
l3.next = l4
l4.next = l5
ans = solution.addLists(l0, l3)
a = [ans.val, ans.next.val, ans.next.next.val]
print("输入： 7->1->6->null, 5->9->2->null")
print("输出： 2->1->9->null")
【例64】删除元素 难度等级★
3.代码实现
class Solution:
#参数A: 整数列表
#参数elem: 整数
#返回值：移除后的长度
def removeElement(self, A, elem):
j = len(A)-1
for i in range(len(A) - 1, -1, -1):
if A[i] == elem:
A[i], A[j] = A[j], A[i]
j -= 1
return j+1
#主函数
if __name__ == '__main__':
solution = Solution()
A = [0,4,4,0,0,2,4,4]
e = 4
ans = solution.removeElement(A, e)
print("输入： [0,4,4,0,0,2,4,4], value = 4")
print("输出：", ans)
【例65】克隆二叉树 难度等级★
3.代码实现
#树的节点结构
#参数val是节点值
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
#参数{TreeNode} root是二进制树的根
#返回值clone_root是复制后新树的根
class Solution:
def cloneTree(self, root):
if root is None:
return None
clone_root = TreeNode(root.val)
clone_root.left = self.cloneTree(root.left)
clone_root.right = self.cloneTree(root.right)
return clone_root
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
solution = Solution()
print("输入：", root.val,root.left.val,root.right.val,root.left.left.val,root.left.right.val)
print("输出： ", solution.cloneTree(root).val,solution.cloneTree(root).left.val,solution.cloneTree(root).right.val,solution.cloneTree(root).left.left.val,solution.cloneTree(root).left.right.val)
【例66】合并两个排序链表 难度等级★
3.代码实现
#定义链表节点
class ListNode(object):
def __init__(self, val):
self.val = val
self.next = None
class Solution(object):
#参数l1: 链表头结节点
#参数l2: 链表头节点
#返回值: 链表头节点
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)
tmp = dummy
while l1 != None and l2 != None:
if l1.val < l2.val:
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l1 != None:
tmp.next = l1
else:
tmp.next = l2
return dummy.next
#主函数
if __name__ == '__main__':
solution = Solution()
l0 = ListNode(1)
l1 = ListNode(3)
l2 = ListNode(8)
l0.next = l1
l1.next = l2
l5 = ListNode(2)
l6 = ListNode(4)
l5.next = l6
ans = solution.mergeTwoLists(l0, l5)
a = [ans.val, ans.next.val, ans.next.next.val,
ans.next.next.next.val, ans.next.next.next.next.val]
print("输入： list1 = 1->3->8->null, list2 = 2->4->null")
print("输出： 1->2->3->4->8->null")
【例67】反转整数 难度等级★
3.代码实现
#参数n是一个整型数
#返回值reverse是反转的整数
class Solution:
def reverseInteger(self, n):
if n == 0:
return 0
neg = 1
if n < 0:
neg, n = -1, -n
reverse = 0
while n > 0:
reverse = reverse * 10 + n % 10
n = n // 10
reverse = reverse * neg
if reverse < -(1 << 31) or reverse > (1 << 31) - 1:
return 0
return reverse
#主函数
if __name__ == '__main__':
generator=1234
solution = Solution()
print("输入：", generator)
print("输出：", solution. reverseInteger(generator))
【例68】报数 难度等级★
3.代码实现
#参数n是一个正整数
#返回值string是n所表示的报数序列
class Solution:
def countAndSay(self, n):
string = '1'
for i in range(n - 1):
a = string[0]
count = 0
s = ''
for ch in string:
if a == ch:
count += 1
else:
s += str(count) + a
a = ch
count = 1
s += str(count) + a
string = s
a = string[0]
return string
#主函数
if __name__ == '__main__':
generator=5
solution = Solution()
print("输入:", generator)
print("输出:", solution.countAndSay(generator))
【例69】完全二叉树 难度等级★
3.代码实现
#参数root是二叉树的根
#返回值是个布尔值，当完全二叉树时返回True，否则返回False
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def isComplete(self, root):
if root is None:
return True
queue = [root]
index = 0
while index < len(queue):
if queue[index] is not None:
queue.append(queue[index].left)
queue.append(queue[index].right)
index += 1
while queue[-1] is None:
queue.pop()
for q in queue:
if q is None:
return False
return True
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
solution = Solution()
print("输入: ", root.val,root.left.val,root.right.val,root.left.left.val)
print("输出: ", solution.isComplete(root))
【例70】对称二叉树 难度等级★
3.代码实现
#参数root是二叉树的的根
#返回值是个布尔值，是对称二叉树时返回True，否则返回False
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def help(self, p, q):
if p == None and q == None: return True
if p and q and p.val == q.val:
return self.help(p.right, q.left) and self.help(p.left, q.right)
return False
def isSymmetric(self, root):
if root:
return self.help(root.left, root.right)
return True
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.left = TreeNode(4)
root.left.right = TreeNode(4)
root.left.left = TreeNode(3)
solution = Solution()
print("输入: ",
root.val,root.left.val,root.right.val,root.left.left.val,root.left.right. val,root.right.left.val, root.right.right.val)
print("输出: ", solution.isSymmetric(root))
【例71】扭转后等价的二叉树 难度等级★
3.代码实现
#参数a、b是二叉树的根
#返回值是个布尔值，当它们等价时返回True，否则返回False
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def isTweakedIdentical(self, a, b):
if a == None and b == None: return True
if a and b and a.val == b.val:
return self.isTweakedIdentical(a.left, b.left) and \
self.isTweakedIdentical(a.right, b.right) or \
self.isTweakedIdentical(a.left, b.right) and \
self.isTweakedIdentical(a.right, b.left)
return False
#主函数
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.left = TreeNode(3)
root1.right.right = TreeNode(4)
solution = Solution()
print("输入: ", root.val,root.left.val,root.right.val,root.left.left.val," , ",root1.val,root1.left.val,root1.right.val,root1.right.right.val)
print("输出: ", solution.isTweakedIdentical(root,root1))
【例72】岛屿的个数 难度等级★
3.代码实现
from collections import deque
#参数grid是一个01矩阵
#返回值islands是岛屿的个数
class Solution:
def numIslands(self, grid):
if not grid or not grid[0]:
return 0
islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
self.bfs(grid, i, j)
islands += 1
return islands
def bfs(self, grid, x, y):
queue = deque([(x, y)])
grid[x][y] = False
while queue:
x, y = queue.popleft()
for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
next_x = x + delta_x
next_y = y + delta_y
if not self.is_valid(grid, next_x, next_y):
continue
queue.append((next_x, next_y))
grid[next_x][next_y] = False
def is_valid(self, grid, x, y):
n, m = len(grid), len(grid[0])
return 0 <= x < n and 0 <= y < m and grid[x][y]
#主函数
if __name__ == '__main__':
generator= [
[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]
]
solution = Solution()
print("输入：", generator)
print("输出：", solution.numIslands(generator))
【例73】判断是否为平方数之和 难度等级★
3.代码实现
import math
class Solution:
"""
参数num为整数
返回布尔类型
"""
def checkSumOfSquareNumbers(self, num):
# write your code here
if num < 0:
return False
for i in reversed(range(0, int(math.sqrt(num)) + 1)):
if i * i == num:
return True
j = num - i * i
k = int(math.sqrt(j))
if k * k == j:
return True
return False
if __name__=='__main__':
solution=Solution()
num=5
print("输入为：",num)
print("输出为：",solution.checkSumOfSquareNumbers(num))
【例74】滑动窗口内数的和 难度等级★
3.代码实现
class Solution:
#nums是整数数组
#k是滑动窗口
#返回每个窗口的数字和
def winSum(self, nums, k):
n = len(nums)
if n < k or k <= 0:
return []
sums = [0] * (n - k + 1)
for i in range(k):
sums[0] += nums[i];
for i in range(1, n - k + 1):
sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1]
return sums
#主函数
if __name__ == '__main__':
inputnum=[1,2,7,8,5]
k=3
print("输入数组：",inputnum)
print("输入窗口：",k)
solution=Solution()
print("输出数组：",solution.winSum(inputnum,k))
4.运行结果
输入数组：[1, 2, 7, 8, 5]
输入窗口：3
输出数组：[10, 17, 20]
【例75】单词拆分 难度等级★★
.代码实现
class Solution:
"""
参数s为字符串
参数dict为单词列表
返回整数数量
"""
def wordBreak3(self, s, dict):
if not s or not dict:
return 0
n, hash = len(s), set()
lowerS = s.lower()
for d in dict:
hash.add(d.lower())
f = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(i, n):
sub = lowerS[i:j + 1]
if sub in hash:
f[i][j] = 1
for i in range(n):
for j in range(i, n):
for k in range(i, j):
f[i][j] += f[i][k] * f[k + 1][j]
return f[0][-1]
if __name__=='__main__':
solution=Solution()
s="CatMat"
dict1=["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
print("输入句子为：",s)
print("输入列表为：",dict1)
print("输出数量为：",solution.wordBreak3(s,dict1))
【例76】硬币摆放 难度等级★
3.代码实现
import math
class Solution:
#参数n为整数
#返回整数
# n = (1 + x) * x / 2, 求得 x = (-1 + sqrt(8 * n + 1)) / 2, 对x取整
def arrangeCoins(self, n):
return math.floor((-1 + math.sqrt(1 + 8*n)) / 2)
if __name__ == '__main__':
n = 10
solution = Solution()
print("输入为：",n)
print("输出为：",solution.arrangeCoins(n))
【例77】字母大小写转换 难度等级★
3.代码实现
class Solution(object):
def letterCasePermutation(self, S):
#参数S为字符串
#返回字符串列表
# 利用二进制对应字符串。其中0表示大小写不变，1表示改变大小写
res = []
indices = []
indices = [i for i,_ in enumerate(S) if S[i].isalpha()]
for i in range(0, pow(2,len(indices))):
if i==0:
res.append(S)
else:
j=i;bpos=0;nsl=list(S)
while j>0:
ci2c = indices[bpos]
if j&1 and S[ci2c].islower():
nsl[ci2c]=S[ci2c].upper()
elif j&1 and S[ci2c].isupper():
nsl[ci2c]=S[ci2c].lower()
bpos+=1
j = j >> 1
res.append("".join(nsl))
return res
if __name__ == '__main__':
solution=Solution()
S = "a1b2"
print("输入为：",S)
print("输出为：",solution.letterCasePermutation(S))
4.运行结果
输入为： a1b2
输出为： [‘a1b2’, ‘A1b2’, ‘a1B2’, ‘A1B2’]
【例78】二进制表示中质数个计算置位 难度等级★
3.代码实现
class Solution(object):
def countPrimeSetBits(self, L, R):
# "L, R在[1, 10^6]范围
# 可能的质数为2, 3, 5, 7, 11, 13, 17, 19.
# 统计1的个数在进行质数判定,因为二进制1的个数不会超过20个，枚举质数即可
k = 0
for n in range(L, R + 1):
if bin(n).count('1') in [2, 3, 5, 7, 11, 13, 17, 19]:
k = k + 1
return k
if __name__ == '__main__':
solution=Solution()
L=6
R=10
print("输入为：[",L,R,"]")
print("输出为：",solution.countPrimeSetBits(L,R))
4.运行结果
输入为：[ 6 10 ]
输出为：4
【例79】最少费用的爬台阶方法 难度等级★
3.代码实现
class Solution:
#参数cost为数组
#返回最小费用
#状态转移方程 dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])
def minCostClimbingStairs(self, cost):
a, b = 0, 0
for i in range(2, len(cost) + 1):
c = min(a + cost[i - 2], b + cost[i - 1])
a, b = b, c
return b
if __name__ == '__main__':
solution=Solution()
print("输入为：",cost)
print("输出为：",solution.minCostClimbingStairs(cost))
4.运行结果
输入为：[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出为：6
【例80】中心索引 难度等级★
3.代码实现
class Solution(object):
def pivotIndex(self, nums):
left, right = 0, sum(nums)
for index, num in enumerate(nums):
right -= num
if left == right:
return index
left += num
return -1
if __name__ == '__main__':
solution=Solution()
words=[1,7,3,6,5,6]
print(solution.pivotIndex(words))
【例81】词典中最长的单词 难度等级★
3.代码实现
class Solution(object):
def longestWord(self, words):
words.sort()
words.sort(key=len, reverse=True)
res = []
for word in words:
temp = word
i = 1
for i in range(len(temp)):
if temp[:len(temp) - i] in words:
if i == len(temp) - 1:
return temp
continue
else:
break
return ''
if __name__ == '__main__':
solution=Solution()
words=["w","wo","wor","worl", "world"]
print("输入字典为：",words)
print("输出单词为：",solution.longestWord(words))
【例82】重复字符串匹配 难度等级★
3.代码实现
class Solution:
#参数A为字符串
#参数B为字符串
#返回整数
def repeatedStringMatch(self, A, B):
C = ""
for i in range(int(len(B)/len(A) + 3)):
if B in C:
return i
C += A
return -1
if __name__ == '__main__':
solution=Solution()
A = "abcd"
B = "cdabcdab"
print("输入字符串A为：",A)
print("输入字符串B为：",B)
print("需要重复次数：",solution.repeatedStringMatch(A,B))
【例83】不下降数组 难度等级★
3.代码实现
class Solution:
#参数nums为数组
#返回布尔类型
def checkPossibility(self, nums):
count = 0
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
count += 1
if i >= 2 and nums[i] < nums[i - 2]:
nums[i] = nums[i - 1]
else:
nums[i - 1] = nums[i]
return count <= 1
if __name__ == '__main__':
solution=Solution()
nums=[4,2,3]
print("输入为：",nums)
print("输出为：",solution.checkPossibility(nums))
【例84】最大的回文乘积 难度等级★
3.代码实现
class Solution:
#参数n为整数
#返回整数
def largestPalindrome(self, n):
if n==1:
return 9
elif n ==7:
return 877
elif n== 8:
return 475
maxNum,minNum = 10**n - 1, 10**(n-1)
for i in range(maxNum, minNum, -1):
candidate = str(i)
candidate = candidate + candidate [::-1]
candidate = int(candidate)
j = maxNum
while j*j > candidate :
if candidate % j == 0:
return candidate % 1337
j -= 1
#主函数
if __name__ == '__main__':
s = Solution()
n = 2
print("输入为：",n)
print("输出为：",s.largestPalindrome(n))
【例85】补数 难度等级★
3.代码实现
class Solution:
#参数num为整数
#返回整数
def findComplement(self, num):
return num ^ ((1<<num.bit_length())-1)
#主函数
if __name__ == '__main__':
s = Solution()
n = 5
print("输入为：",n)
print("输出为：",s.findComplement(n))
【例86】加热器 难度等级★
3.代码实现
class Solution:
#参数houses为数组
#参数heaters为整数
#返回整数
def findRadius(self, houses, heaters):
heaters.sort()
ans = 0
for house in houses:
ans=max(ans,self.closestHeater(house,heaters))
return ans
def closestHeater(self,house,heaters):
start = 0
end = len(heaters) - 1
while start + 1 < end:
m = start + (end - start) // 2
if heaters[m] == house:
return 0
elif heaters[m] < house:
start = m
else:
end = m
return min(abs(house - heaters[start]), abs(heaters[end] - house))
#主函数
if __name__ == '__main__':
s = Solution()
n = [1,2,3]
m = [2]
print("输入房间位置为：",n)
print("输入加热器位置：",m)
print("输出加热半径为：",s.findRadius(n,m))
【例87】将火柴摆放成正方形 难度等级★
3.代码实现
class Solution:
#参数nums为数组
#返回布尔类型
def makesquare(self, nums):
def dfs(nums, pos, target):
if pos == len(nums):
return True
for i in range(4):
if target[i] >= nums[pos]:
target[i] -= nums[pos]
if dfs(nums, pos+1, target):
return True
target[i] += nums[pos]
return False
if len(nums) < 4 :
return False
numSum = sum(nums)
nums.sort(reverse = True)
if numSum % 4 != 0:
return False
target = [numSum / 4] * 4;
return dfs(nums, 0, target)
#主函数
if __name__ == '__main__':
s = Solution()
n = [1,1,2,2,2]
print("输入为：",n)
print("输出为：",s.makesquare(n))
【例88】可怜的猪 难度等级★
3.代码实现
class Solution:
#参数buckets为整数
#参数minutesToDie为整数
#参数minutesToTest为整数
返回整数
def poorPigs(self, buckets, minutesToDie, minutesToTest):
pigs = 0
while (minutesToTest / minutesToDie + 1) ** pigs < buckets:
pigs += 1
return pigs
#主函数
if __name__ == '__main__':
s = Solution()
n = 1000
m = 15
p = 60
print("输入总桶数为：",n)
print("输入中毒时间：",m)
print("输入测试时间：",p)
print("输出为：",s.poorPigs(n,m,p))
【例89】循环数组中的环 难度等级★
3.代码实现
class Solution:
#参数nums为数组
#返回布尔类型
def get_index(self, i, nums):
n = (i + nums[i]) % len(nums)
return n if n >= 0 else n + len(nums)
def circularArrayLoop(self, nums):
for i in range(len(nums)):
if nums[i] == 0:
continue
j, k = i, self.get_index(i, nums)
while nums[k] * nums[i] > 0 and nums[self.get_index(k, nums)] * nums[i] > 0:
if j == k:
if j == self.get_index(j, nums):
break
return True
j = self.get_index(j, nums)
k = self.get_index(self.get_index(k, nums), nums)
j = i
while nums[j] * nums[i] > 0:
next = self.get_index(j, nums)
nums[j] = 0
j = next
return False
#主函数
if __name__ == '__main__':
s = Solution()
n = [2,-1,1,2,2]
print("输入为：",n)
print("输出为：",s.circularArrayLoop(n))
【例90】分饼干 难度等级★
3.代码实现
class Solution(object):
def findContentChildren(self, g, s):
#参数g为整数列表
#参数s为整数列表
#返回整型
g.sort()
s.sort()
i, j = 0, 0
while i < len(g) and j < len(s):
if g[i] <= s[j]:
i += 1
j += 1
return i
#主函数
if __name__ == '__main__':
s = Solution()
n = [1,2,3]
m = [1,1]
print("输入贪吃指数为：",n)
print("输入饼干尺寸为：",m)
print("输出为：",s.findContentChildren(n,m))
【例91】翻转字符串中的元音字母 难度等级★
3.代码实现
class Solution:
"""
参数s为字符串
返回字符串
"""
def reverseVowels(self, s):
vowels = set(["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"])
res = list(s)
start, end = 0, len(res)-1
while start <= end:
while start <= end and res[start] not in vowels:
start += 1
while start <= end and res[end] not in vowels:
end -= 1
if start <= end:
res[start], res[end] = res[end], res[start]
start += 1
end -= 1
return "".join(res)
#主函数
if __name__ == '__main__':
s = Solution()
x = "hello"
print("输入为：",x)
print("输出为：",s.reverseVowels(x))
【例92】翻转字符串 难度等级★
3.代码实现
class Solution:
"""
参数s为字符串
返回字符串
"""
def reverseString(self, s):
return s[::-1]
#主函数
if __name__ == '__main__':
s = Solution()
x = "hello"
print("输入为：",x)
print("输出为：",s.reverseString(x))
【例93】使数组元素相同的最少步数 难度等级★
3.代码实现
class Solution(object):
def minMoves(self, nums):
#参数nums为整数列表
#返回整数
sumNum = sum(nums)
minNum = min(nums)
return sumNum - minNum * len(nums)
#主函数
if __name__ == '__main__':
s = Solution()
n = [1,2,3]
print("输入为：",n)
print("输出为：",s.minMoves(n))
【例94】加油站 难度等级★
3.代码实现
#参数distance代表每个加油站的距离
#参数apply代表每个加油站的加油量
#参数original代表一开始有汽油
#参数target代表需要开的距离
#返回值是一个整数，代表至少需要加油站次数
class Solution:
def getTimes(self, target, original, distance, apply):
import queue
que = queue.PriorityQueue()
ans, pre = 0, 0
if(target > distance[len(distance) - 1]):
distance.append(target)
apply.append(0)
cap = original
for i in range(len(distance)):
if(distance[i] >= target):
distance[i] = target
d = distance[i] - pre
while(cap < d and que.qsize() != 0):
cap += (que.get()[1])
ans += 1
if (d <= cap):
cap -= d
else:
ans = -1
break
que.put((-apply[i], apply[i]))
pre = distance[i]
if(pre == target):
break
return ans
if __name__ == '__main__':
target = 25
original = 10
distance = [10,14,20,21]
apply = [10,5,2,4]
solution = Solution()
print(" 每个加油站的距离为：", distance)
print(" 每个加油站的加油量为：", apply)
print(" 一开始有汽油：", original)
print(" 需要开的距离为：", target)
print(" 至少需要经过加油站:", solution.getTimes(target, original, distance, apply))
【例95】春游 难度等级★
3.代码实现
#参数a是小朋友组链
#返回值是个整数，表示至少需要多少辆车
class Solution:
def getAnswer(self, a):
count = [0 for i in range(0, 5)]
for i in range(0, len(a)):
count[a[i]] = count[a[i]] + 1
count[1] = count[1] - count[3]
if count[2] % 2 == 1:
count[2] = count[2] + 1
count[1] = count[1] - 2
res = count[4] + count[3] + count[2] / 2
if count[1] > 0:
res = res + count[1] / 4
if not count[1] % 4 == 0:
res = res + 1
return int(res)
if __name__ == '__main__':
a = [1,2,3,4]
solution = Solution()
print(" 小朋友分组为：", a)
print(" 至少需要：", solution.getAnswer(a), "辆车")
【例96】合法数组 难度等级★
3.代码实现
#参数a是待查数组
#返回值是一个数值，代表出现奇数次的值或者数组不合法
class Solution:
def isValid(self, a):
countSet = {
}
for i in a:
if i in countSet:
countSet[i] = countSet[i] + 1
else:
countSet[i] = 1
isHas = False
for key in countSet:
if countSet[key] % 2 == 1:
if isHas:
return -1
else:
isHas = True
ans = key
if isHas:
return ans
return -1
if __name__ == '__main__':
a=[1,1,2,2,3,3,4,4,5,5]
solution = Solution()
print(" 数组为：", a)
ans = solution.isValid(a)
print(" 数组奇数个的值是:" if ans != -1 else " 数组不合法", ans)
【例97】删除排序数组中的重复数字 难度等级★
3.代码实现
class Solution:
#参数A: 整数列表
#返回值：整数
def removeDuplicates(self, A):
B = []
before = None
countb = 0
for number in A:
if(before != number):
B.append(number)
before = number
countb = 1
elif countb < 2:
B.append(number)
countb += 1
p = 0
for number in B:
A[p] = number
p += 1
return p
#主函数
if __name__ == '__main__':
solution = Solution()
A = [1,1,1,2,2,3]
p = solution.removeDuplicates(A)
print("输入：", A)
print("输出：", p)
【例98】字符串的不同排列 难度等级★
3.代码实现
class Solution:
#参数str: 一个字符串
#返回值: 所有排列
def stringPermutation2(self, str):
result = []
if str == '':
return ['']
s = list(str)
s.sort()
while True:
result.append(''.join(s))
s = self.nextPermutation(s)
if s is None:
break
return result
def nextPermutation(self, num):
n = len(num)
i = n - 1
while i >= 1 and num[i - 1] >= num[i]:
i -= 1
if i == 0: return None
j = n - 1
while j >= 0 and num[j] <= num[i - 1]:
j -= 1
num[i - 1], num[j] = num[j], num[i - 1]
num[i:] = num[i:][::-1]
return num
#主函数
if __name__ == '__main__':
solution = Solution()
s1 = "aabb"
ans = solution.stringPermutation2(s1)
print("输入：", s1)
print("输出：", ans)
【例99】全排列 难度等级★
3.代码实现
class Solution:
#参数nums: 一个整数列表
#返回值: 排列后的列表
def permute(self, nums):
def _permute(result, temp, nums):
if nums == []:
result += [temp]
else:
for i in range(len(nums)):
_permute(result, temp + [nums[i]], nums[:i] + nums[i+1:])
if nums is None:
return []
if nums is []:
return [[]]
result = []
_permute(result, [], sorted(nums))
return result
#主函数
if __name__ == '__main__':
nums = [1,2,3]
solution = Solution()
result = solution.permute(nums)
print("输入：", nums)
print("输出：", result)
【例100】带重复元素的排列 难度等级★
3.代码实现
class Solution:
#参数nums: 整数数组
#返回值: 唯一排列的列表。
def permuteUnique(self, nums):
def _permute(result, temp, nums):
if nums == []:
result += [temp]
else:
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
_permute(result, temp + [nums[i]], nums[:i] + nums[i+1:])
if nums is None:
return []
if len(nums) == 0:
return [[]]
result = []
_permute(result, [], sorted(nums))
return result
#主函数
if __name__ == '__main__':
solution = Solution()
nums = [1,2,2]
result = solution.permuteUnique(nums)
print("输入：", nums)
print("输出：", result)
转载：https://blog.csdn.net/cui_yonghua/article/details/116742720
查看评论