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

今天药忘吃喽~ 2022-10-16 07:16 23阅读 0赞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[python3_299_100]: https://blog.csdn.net/cui_yonghua/article/details/116742720
[python3_299_100 1]: https://blog.csdn.net/cui_yonghua/article/details/117336492
[python3_299_99]: https://blog.csdn.net/cui_yonghua/article/details/117336564