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

一. 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 = 123ans = solution.reverseInteger(num)print("输入：", num)print("输出：", ans)

【例2】合并排序数组 难度等级★

3.代码实现

class Solution:#参数A: 有序整数数组A#参数B: 有序整数数组B#返回:一个新的有序整数数组def mergeSortedArray(self, A, B):i, j = 0, 0C = []while i < len(A) and j < len(B):if A[i] < B[j]:C.append(A[i])i += 1else:C.append(B[j])j += 1while i < len(A):C.append(A[i])i += 1while j < len(B):C.append(B[j])j += 1return 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 = 3solution = 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]] = isortedScore = 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]]] = resreturn 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 -1mid = (start + end)//2if nums[mid] > target:return self.search(nums, start, mid, target)if nums[mid] == target:return midif nums[mid] < target:return self.search(nums, mid, end, target)#主函数if __name__ == '__main__':my_solution = Solution()nums = [1,2,3,4,5,6]target = 3targetIndex = 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]] = xdel stack[-1]stack.append(x)for x in stack:answer[x] = -1return [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 = 0for i in range(len(s)):if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):res += 1return 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] * 26for c in magazine:arr[ord(c) - ord('a')] += 1for c in ransomNote:arr[ord(c) - ord('a')] -= 1if arr[ord(c) - ord('a')] < 0:return Falsereturn 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] ^ ic = 1while c & ans[0] != c:c = c << 1for i in a:if i & c == c:ans[1] = ans[1] ^ ians[0] = ans[0] ^ ans[1]return ansif __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 -1array.sort()diff = 0x7fffffffleft = 0right = n - 1while left < right:if array[left] + array[right] > target:right -= 1else:diff = min(diff, target - array[left] - array[right])left += 1if diff == 0x7fffffff:return -1else:return target - diffif __name__ == '__main__':array = [1,3,5,11,7]target = 15solution = 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 -1ans = 0for i in range(len(A)):ans += A[i] * B[i]return ansif __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 = 0while not i[count] == ' ':count = count + 1fun = i[0 : count]if i[count+2] == 'n':count = count + 7v = int(i[count:len(i)])if fun in map.keys():map[fun] = v - map[fun]else:map[fun] = velse:count = count + 6v = 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 resif __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或者Falseclass Solution:def isInterval(self, intervalList, number):high = len(intervalList) - 1low = 0while 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 + 1elif 0 > number - intervalList[(high + low)//2][0]:high = (high + low) // 2 - 1return 'False'if __name__ == '__main__':number = 6000intervalList = [[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 = 0ed = 0dist[1] =0vis[1] = 1Q[ed] = 1;ed += 1while(st<ed) :u = Q[st]st += 1vis[u] = 0for roads in connections :if(roads[0] != u):continuev = roads[1]if(dist[v] > dist[u]):dist[v] = dist[u]if(vis[v] == 0) :vis[v] = 1Q[ed] = ved += 1for i in range(1, 7):if (i + u > length):breakv = i + uif(dist[v] > dist[u] + 1) :dist[v] = dist[u] + 1if(vis[v] == 0):vis[v] = 1Q[ed] = ved += 1return dist[length]if __name__ == '__main__':length = 15connections = [[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 = 0odd = 0for i in range(0,len(arr)):odd += abs(arr[i]-(2*i+1))even += abs(arr[i] - (2*i+2))if odd < even:return oddreturn evenif __name__ == '__main__':arr = [1, 6, 7, 8, 9]solution = Solution()print(" 数组是：", arr)print(" 最小移动数是:", solution.movingStones(arr))

【例17】数组剔除元素后的乘积 难度等级★

3.代码实现

class Solution:#参数A: 整数数组A#返回值: 整数数组Bdef productExcludeItself(self, A):length ,B  = len(A) ,[]f = [ 0 for i in range(length + 1)]f[ length ] = 1for i in range(length - 1 , 0 , -1):f[ i ] = f[ i + 1 ] * A[ i ]tmp = 1for 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 = 1for i in w:if i.lower() not in s[j]:flag = 0breakif flag == 1:res.append(w)breakreturn 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 = 1count = 9start = 1while n > length * count:# 以此类推二位数的个数为90，从10开始n -= length * countlength += 1count *= 10start *= 10# 找到第n位数所在的整数startstart += (n - 1) // lengthreturn int(str(start)[(n - 1) % length])#主函数if __name__ == '__main__':s = Solution()n = 11print("输入为：",n)print("输出为：",s.findNthDigit(n))

【例20】找不同 难度等级★

3.代码实现

class Solution:"""参数s为字符串参数t为字符串返回字符"""def findTheDifference(self, s, t):flag = 0for 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] = 1C[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 = 1for 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 + 1base = 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 + 1return ansif __name__ == '__main__':n = 8k = 11solution = 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 visitscount[sec_level_domain] = count[sec_level_domain] + visits if sec_level_domain in count.keys() else visitsif domain.count('.') == 2:count[domain.split()[1]] = count[domain.split()[1]] + visits if domain.split()[1] in count.keys() else visitsreturn [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 = 0arr = [0 for i in range(len(S))]sets = {}if S[0] == 'A':arr[0] = 1sets[1] = 0else:arr[0] = -1sets[-1] = 0for i in range(1, len(S)):if S[i] == 'A':arr[i] = arr[i - 1] + 1if arr[i] == 0:ans = i + 1continueif arr[i] in sets:ans = max(ans, i - sets[arr[i]])else:sets[arr[i]] = ielse:arr[i] = arr[i - 1] - 1if arr[i] == 0:ans = i + 1continueif arr[i] in sets:ans = max(ans, i - sets[arr[i]])else:sets[arr[i]] = ireturn ansif __name__ == '__main__':S = "ABABAB"solution = Solution()print(" AB字符串为：", S)print(" 最长AB出现次数相同的子字符串长度是:", solution.getAns(S))

【例25】删除字符 难度等级★

3.代码实现

#参数s是待删除字符的原字符串#参数t是目标字符串#返回值是一个布尔值，意为能否由s删除一些字符得到tclass Solution:def canGetString(self, s, t):pos = 0for x in t:while pos < len(s) and s[pos] != x:pos += 1if pos == len(s):return Falsepos += 1return Trueif __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 = 1space = 0flag = Falsefor c in S:if flag:line += 1flag = Falsespace += widths[ord(c) - 97]if space > 100:line += 1space = widths[ord(c) - 97]elif space == 100:space = 0flag = Truereturn [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，否则返回Falsedef compareStrings(self, A, B):if len(B) == 0:return Trueif 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] += 1for i in B:if trackTable[ord(i) - 65] == 0:return Falseelse:trackTable[ord(i) -65] -= 1return 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 = 0for i in range(len(s)):if s[i] == t[j]:j += 1if j == len(t):return Truereturn Falseif __name__ == '__main__':s = "longterm"t = "long"solution = Solution()print(" S与T分别为：", s, t)print(" 能否删除得到:", solution.canConvert(s, t))

【例30】经典二分查找问题 难度等级★

3.代码实现

#参数nums是一个整型排序数组#参数target是一个任意整型数#返回值是一个整型数，若nums存在，返回该数位置；若不存在，返回-1class Solution:def findPosition(self, nums, target):if len(nums) is 0:return -1start = 0end = len(nums)-1while start + 1 < end :mid = start + (end-start)//2if nums[mid] == target:end = midelif nums[mid] < target:start = midelse:end = midif nums[start] == target:return startif nums[end] == target:return endreturn -1#主函数if __name__ == '__main__':generator=[1,2,2,4,5,5]target = 2solution = Solution()print("输入:", generator)print("输出:", solution. myAtoi(generator, target))

【例31】抽搐词 难度等级★

3.代码实现

class Solution:def twitchWords(self, str):n = len(str)c = str[0]left = 0ans = []for i in range(n):if str[i] != c:if i - left >= 3:ans.append([left, i - 1])c = str[i]left = iif 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 -1start, end = 0,len(A)-1while start+ 1<end:mid = start +(end-start)//2if A[mid]<target:start= midelif A[mid]>target:end = midelse:return midif target-A[start]<A[end]-target:return startelse:return end#主函数if __name__ == '__main__':generator = [1,4,6]target = 3solution = Solution()print("输入：", generator,",target =",target)print("输出：", solution.findPosition(generator, target))

【例33】构造矩形 难度等级★

3.代码实现

class Solution:#参数area为整数#返回为整数def constructRectangle(self, area):import mathW = math.floor(math.sqrt(area))while area % W != 0:W -= 1return [area // W, W]#主函数if __name__ == '__main__':s = Solution()area =4print("输入面积为：",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 Nonen, m = len(A), len(B)minheap = [(A[0] + B[0], 0, 0)]visited = set([0])num = Nonefor _ 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 = 3solution = 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，Rectangleclass 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 = valself.left = Noneself.right = Noneclass Solution:def longestConsecutive(self, root):return self.helper(root, None, 0)def helper(self, root, parent, len):if root is None:return lenif parent != None and root.val == parent.val + 1:len += 1else:len = 1return 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取模和取整操作，直到商小于7def 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 = 777solution = 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 * dydef numberOfBoomerangs(self, points):#参数points为整数列表#返回整数if points == None:return 0ans = 0for i in range(len(points)):disCount = {}for j in range(len(points)):if i == j:continuedistance = self.getDistance(points[i], points[j])count = disCount.get(distance, 0)disCount[distance] = count + 1for 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-1t = len(A)-1while i >= 0 or j >= 0:if i < 0 or (j >= 0 and B[j] > A[i]):A[t] = B[j]j -= 1else:A[t] = A[i]i -= 1t -= 1#主函数if __name__ == '__main__':solution = Solution()A = [1,2,3,0,0]m = 3B = [4,5]n = 2solution.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码中小写字母与对应的大写字母相差32return chr(ord(character) - 32)#主函数if __name__ == '__main__':solution = Solution()ans = solution.lowercaseToUppercase('a')print("输入： a")print("输出：", ans)

【例45】原子的数量 难度等级★

3.代码实现

import reimport collectionsclass 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 0sequence = []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] = 1cur_path = 0for 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_pathvals = 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, 0while x > 0:k += (x % 10)**nx //= 10if k == y: res.append(k)return res#主函数if __name__ == '__main__':solution = Solution()n = 4ans = 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 2n = len(A)up = 0for 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 2return 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 = valself.next = nextclass Solution:def countNodes(self, head):cnt = 0while head is not None:cnt += 1head = head.nextreturn cnt#主函数if __name__ == '__main__':node1 = ListNode(1)node2 = ListNode(2)node3 = ListNode(3)node4 = ListNode(4)node1.next = node2node2.next = node3node3.next = node4solution = 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] = 1else:dict[word] += 1sorted_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 = 4solution = Solution()print("输入: ", generator)print("输入: ","k = ", k)print("输出: ", solution.topKFrequentWords(generator,k))

【例52】单词的添加与查找 难度等级★

3.代码实现

#参数word是要添加的的单词#返回值是个布尔值，查找单词成功则返回True，否则，返回Falseclass TrieNode:def __init__(self):self.children = {}self.is_word = Falseclass WordDictionary:def __init__(self):self.root = TrieNode()def addWord(self, word):node = self.rootfor c in word:if c not in node.children:node.children[c] = TrieNode()node = node.children[c]node.is_word =Truedef search(self, word):if word is None:return Falsereturn self.search_helper(self.root, word, 0)def search_helper(self, node, word, index):if node is None:return Falseif index >= len(word):return node.is_wordchar = 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 Truereturn 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 sysclass Solution:def stoneGame(self, A):n = len(A)if n < 2:return 0dp = [[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] = ifor length in range(3, n + 1):for i in range(n - length + 1):j = i + length - 1dp[i][j] = sys.maxsizefor 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] = midreturn 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]soluti5fa84on = Solution()print("输入：", generator)print("输出：", solution.stoneGame(generator))

【例54】简单计算器 难度等级★

3.代码实现

#参数a，b是两个任意整数#operator是运算符+, -, *, /#返回值是浮点型运算结果class Solution:def calculate(self, a, operator, b):if operator == '+':return a + belif operator == '-':return a - belif operator == '*':return a * belif operator == '/':return a / b#主函数if __name__ == '__main__':a=8b=3operator1='+'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 = maxValuemaxValue = 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 = valself.left, self.right = None, Noneclass Solution:def leafSum(self, root):p = []self.dfs(root, p)return sum(p)def dfs(self, root, p):if root is None:returnif 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 = valself.left, self.right = None, Noneclass 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:returnif dep == level:p.append(root.val)returnself.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 = 3solution = 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 2for i in range(-2, -len(str) - 1, -1):if str[i] == 0:return -1 * ((i * -1 + 1) % 2) + 2return -1 * (len(str) % 2) + 2if __name__ == '__main__':str = "111110"solution = Solution()print(" 原01串为：", str)print(" 最后一个词长度是:", solution.judgeTheLastNumber(str))

【例59】两个字符串是变位词 难度等级★

3.代码实现

class Solution:#参数s: 第一个字符串#参数t: 第二个字符串#返回值: True或Falsedef anagram(self, s, t):set_s = [0] * 256set_t = [0] * 256for i in range(0, len(s)):set_s[ord(s[i])] += 1for i in range(0, len(t)):set_t[ord(t[i])] += 1for i in range(0, 256):if set_s[i] != set_t[i]:return Falsereturn 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 = 0for 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 = 0for c in moves:if c == 'R':count_RL += 1if c == 'L':count_RL -= 1if c == 'U':count_UD += 1if c == 'D':count_UD -= 1return count_RL == 0 and count_UD == 0if __name__ == '__main__':solution=Solution()moves="UD"print("输入为：",moves)print("输出为：",solution.judgeCircle(moves))

【例62】链表倒数第n个节点 难度等级★

3.代码实现

#定义链表节点class ListNode(object):def __init__(self, val):self.val = valself.next = Noneclass Solution:#参数head: 链表的第一个节点。#参数n: 整数#返回值: 单链表的第n到最后一个节点。def nthToLast(self, head, n):if head is None or n < 1:return Nonecur = head.nextwhile cur is not None:cur.pre = headcur = cur.nexthead = head.nextn -= 1while n > 0:head = head.pren -= 1return head#主函数if __name__ == '__main__':solution = Solution()l0 = ListNode(3)l1 = ListNode(2)l2 = ListNode(1)l3 = ListNode(5)l0.next = l1l1.next = l2l2.next = l3ans = solution.nthToLast(l0, 2).valprint("输入： 3->2->1->5->null,  n = 2")print("输出：", ans)

【例63】链表求和 难度等级★

3.代码实现

#定义链表节点class ListNode(object):def __init__(self, val):self.val = valself.next = Noneclass Solution:def addLists(self, l1, l2) -> list:dummy = ListNode(None)tail = dummycarry = 0while l1 or l2 or carry:num = 0if l1:num += l1.vall1 = l1.nextif l2:num += l2.vall2 = l2.nextnum += carrydigit, carry = num % 10, num // 10node = ListNode(digit)tail.next, tail = node, nodereturn dummy.next#主函数if __name__ == '__main__':solution = Solution()l0 = ListNode(7)l1 = ListNode(1)l2 = ListNode(6)l0.next = l1l1.next = l2l3 = ListNode(5)l4 = ListNode(9)l5 = ListNode(2)l3.next = l4l4.next = l5ans = 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)-1for i in range(len(A) - 1, -1, -1):if A[i] == elem:A[i], A[j] = A[j], A[i]j -= 1return j+1#主函数if __name__ == '__main__':solution = Solution()A = [0,4,4,0,0,2,4,4]e = 4ans = 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 = valself.left, self.right = None, None#参数{TreeNode} root是二进制树的根#返回值clone_root是复制后新树的根class Solution:def cloneTree(self, root):if root is None:return Noneclone_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 = valself.next = Noneclass Solution(object):#参数l1: 链表头结节点#参数l2: 链表头节点#返回值: 链表头节点def mergeTwoLists(self, l1, l2):dummy = ListNode(0)tmp = dummywhile l1 != None and l2 != None:if l1.val < l2.val:tmp.next = l1l1 = l1.nextelse:tmp.next = l2l2 = l2.nexttmp = tmp.nextif l1 != None:tmp.next = l1else:tmp.next = l2return dummy.next#主函数if __name__ == '__main__':solution = Solution()l0 = ListNode(1)l1 = ListNode(3)l2 = ListNode(8)l0.next = l1l1.next = l2l5 = ListNode(2)l6 = ListNode(4)l5.next = l6ans = 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 0neg = 1if n < 0:neg, n = -1, -nreverse = 0while n > 0:reverse = reverse * 10 + n % 10n = n // 10reverse = reverse * negif reverse < -(1 << 31) or reverse > (1 << 31) - 1:return 0return reverse#主函数if __name__ == '__main__':generator=1234solution = 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 = 0s = ''for ch in string:if a == ch:count += 1else:s += str(count) + aa = chcount = 1s += str(count) + astring = sa = string[0]return string#主函数if __name__ == '__main__':generator=5solution = Solution()print("输入:", generator)print("输出:", solution.countAndSay(generator))

【例69】完全二叉树 难度等级★

3.代码实现

#参数root是二叉树的根#返回值是个布尔值，当完全二叉树时返回True，否则返回Falseclass TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneclass Solution:def isComplete(self, root):if root is None:return Truequeue = [root]index = 0while index < len(queue):if queue[index] is not None:queue.append(queue[index].left)queue.append(queue[index].right)index += 1while queue[-1] is None:queue.pop()for q in queue:if q is None:return Falsereturn 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，否则返回Falseclass TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneclass Solution:def help(self, p, q):if p == None and q == None: return Trueif p and q and p.val == q.val:return self.help(p.right, q.left) and self.help(p.left, q.right)return Falsedef 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，否则返回Falseclass TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneclass Solution:def isTweakedIdentical(self, a, b):if a == None and b == None: return Trueif 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 0islands = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j]:self.bfs(grid, i, j)islands += 1return islandsdef bfs(self, grid, x, y):queue = deque([(x, y)])grid[x][y] = Falsewhile queue:x, y = queue.popleft()for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:next_x = x + delta_xnext_y = y + delta_yif not self.is_valid(grid, next_x, next_y):continuequeue.append((next_x, next_y))grid[next_x][next_y] = Falsedef 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 mathclass Solution:"""参数num为整数返回布尔类型"""def checkSumOfSquareNumbers(self, num):# write your code hereif num < 0:return Falsefor i in reversed(range(0, int(math.sqrt(num)) + 1)):if i * i == num:return Truej = num - i * ik = int(math.sqrt(j))if k * k == j:return Truereturn Falseif __name__=='__main__':solution=Solution()num=5print("输入为：",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=3print("输入数组：",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 0n, 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] = 1for 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 mathclass 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 = 10solution = 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+=1j = j >> 1res.append("".join(nsl))return resif __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 = 0for n in range(L, R + 1):if bin(n).count('1') in [2, 3, 5, 7, 11, 13, 17, 19]:k = k + 1return kif __name__ == '__main__':solution=Solution()L=6R=10print("输入为：[",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, 0for i in range(2, len(cost) + 1):c = min(a + cost[i - 2], b + cost[i - 1])a, b = b, creturn bif __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 -= numif left == right:return indexleft += numreturn -1if __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 = wordi = 1for i in range(len(temp)):if temp[:len(temp) - i] in words:if i == len(temp) - 1:return tempcontinueelse:breakreturn ''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 iC += Areturn -1if __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 = 0for i in range(1, len(nums)):if nums[i] < nums[i - 1]:count += 1if i >= 2 and nums[i] < nums[i - 2]:nums[i] = nums[i - 1]else:nums[i - 1] = nums[i]return count <= 1if __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 9elif n ==7:return 877elif n== 8:return 475maxNum,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 = maxNumwhile j*j > candidate :if candidate  % j == 0:return candidate  % 1337j -= 1#主函数if __name__ == '__main__':s = Solution()n = 2print("输入为：",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 = 5print("输入为：",n)print("输出为：",s.findComplement(n))

【例86】加热器 难度等级★

3.代码实现

class Solution:#参数houses为数组#参数heaters为整数#返回整数def findRadius(self, houses, heaters):heaters.sort()ans = 0for house in houses:ans=max(ans,self.closestHeater(house,heaters))return ansdef closestHeater(self,house,heaters):start = 0end = len(heaters) - 1while start + 1 < end:m = start + (end - start) // 2if heaters[m] == house:return 0elif heaters[m] < house:start = melse:end = mreturn 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 Truefor i in range(4):if target[i] >= nums[pos]:target[i] -= nums[pos]if dfs(nums, pos+1, target):return Truetarget[i] += nums[pos]return Falseif len(nums) < 4 :return FalsenumSum = sum(nums)nums.sort(reverse = True)if numSum % 4 != 0:return Falsetarget = [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 = 0while (minutesToTest / minutesToDie + 1) ** pigs < buckets:pigs += 1return pigs#主函数if __name__ == '__main__':s = Solution()n = 1000m = 15p = 60print("输入总桶数为：",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:continuej, 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):breakreturn Truej = self.get_index(j, nums)k = self.get_index(self.get_index(k, nums), nums)j = iwhile nums[j] * nums[i] > 0:next = self.get_index(j, nums)nums[j] = 0j = nextreturn 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, 0while i < len(g) and j < len(s):if g[i] <= s[j]:i += 1j += 1return 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)-1while start <= end:while start <= end  and res[start] not in vowels:start += 1while start <= end and res[end] not in vowels:end -= 1if start <= end:res[start], res[end] = res[end], res[start]start += 1end -= 1return "".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 queueque = queue.PriorityQueue()ans, pre = 0, 0if(target > distance[len(distance) - 1]):distance.append(target)apply.append(0)cap = originalfor i in range(len(distance)):if(distance[i] >= target):distance[i] = targetd = distance[i] - prewhile(cap < d and que.qsize() != 0):cap += (que.get()[1])ans += 1if (d <= cap):cap -= delse:ans = -1breakque.put((-apply[i], apply[i]))pre = distance[i]if(pre == target):breakreturn ansif __name__ == '__main__':target = 25original = 10distance = [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]] + 1count[1] = count[1] - count[3]if count[2] % 2 == 1:count[2] = count[2] + 1count[1] = count[1] - 2res = count[4] + count[3] + count[2] / 2if count[1] > 0:res = res + count[1] / 4if not count[1] % 4 == 0:res = res + 1return 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] + 1else:countSet[i] = 1isHas = Falsefor key in countSet:if countSet[key] % 2 == 1:if isHas:return -1else:isHas = Trueans = keyif isHas:return ansreturn -1if __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 = Nonecountb = 0for number in A:if(before != number):B.append(number)before = numbercountb = 1elif countb < 2:B.append(number)countb += 1p = 0for number in B:A
 = numberp += 1return p#主函数if __name__ == '__main__':solution = Solution()A = [1,1,1,2,2,3]p = solution.removeDuplicates(A)print("输入：", A)print("输出：", p)

【例98】字符串的不同排列 难度等级★

[p]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:breakreturn resultdef nextPermutation(self, num):n = len(num)i = n - 1while i >= 1 and num[i - 1] >= num[i]:i -= 1if i == 0: return Nonej = n - 1while j >= 0 and num[j] <= num[i - 1]:j -= 1num[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)