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

骑猪看日落 2022-10-16 07:15 12阅读 0赞

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

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

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

【例101】插入区间 难度等级★★  
3.代码实现

class Interval(object):
        def __init__(self, start, end):
            self.start = start
            self.end = end
        def get(self):
            str1 = "(" + str(self.start) + "," + str(self.end) + ")"
            return str1
        def equals(self, Intervalx):
            if self.start == Intervalx.start and self.end == Intervalx.end:
                return 1
            else:
                return 0
    class Solution:
        #参数intevals: 已排序的非重叠区间列表
        #参数newInterval: 新的区间
        #返回值: 一个新的排序非重叠区间列表与新的区间
        def insert(self, intervals, newInterval):
            results = []
            insertPos = 0
            for interval in intervals:
                if interval.end < newInterval.start:
                    results.append(interval)
                    insertPos += 1
                elif interval.start > newInterval.end:
                    results.append(interval)
                else:
                    newInterval.start = min(interval.start, newInterval.start)
                    newInterval.end = max(interval.end, newInterval.end)
            results.insert(insertPos, newInterval)
            return results
    #主函数
    if __name__ == '__main__':
    solution = Solution()
        interval1 = Interval(1,2)
        interval2 = Interval(5,9)
        interval3 = Interval(2,5)
        results = solution.insert([interval1,interval2], interval3)
        print("输入：[",interval1.get(),",", interval2.get(),"]","", interval3.get())
        print("输出：[", results[0].get(), "]")

【例102】N皇后问题 难度等级★★  
3.代码实现

class Solution:
        #参数n: 皇后的数量
        #返回值: 不同解的总数
        total = 0
        n = 0
        def attack(self, row, col):
            for c, r in self.cols.items():
                if c - r == col - row or c + r == col + row:
                    return True
            return False
        def search(self, row):
            if row == self.n:
                self.total += 1
                return
            for col in range(self.n):
                if col in self.cols:
                    continue
                if self.attack(row, col):
                    continue
                self.cols[col] = row
                self.search(row + 1)
                del self.cols[col]
        def totalNQueens(self, n):
            self.n = n
            self.cols = { }
            self.search(0)
            return self.total
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        solution.totalNQueens(4)
        print("输入：", solution.n)
        print("输出：", solution.total)

【例103】主元素 难度等级★★  
3.代码实现

class Solution:
        #参数nums: 整数数组
        #返回值: 主元素
        def majorityNumber(self, nums):
            nums.sort()
            i=0;j=0
            while i<=len(nums):
                j=nums.count(nums[i])
                if j>len(nums)//3:
                    return nums[i]
                i+=j
            return
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        nums = [99,2,99,2,99,3,3]
        n = solution.majorityNumber(nums)
        print("输入：", "[99,2,99,2,99,3,3]")
        print("输出：", n)

【例104】字符大小写排序 难度等级★★  
3.代码实现

class Solution:
        #参数chars: 需要排序的字母数组
        def sortLetters(self, chars):
            chars.sort(key=lambda c: c.isupper())
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        str1 = "abAcD"
        arr = list(str1)
        solution.sortLetters(arr)
        print("输入：", str1)
        print("输出：", ''.join(arr))

【例105】上一个排列 难度等级★★  
3.代码实现

class Solution:
        #参数num: 整数列表
        #参数: 整数列表
        def previousPermuation(self, num):
            for i in range(len(num)-2, -1, -1):
                if num[i] > num[i+1]:
                    break
            else:
                num.reverse()
                return num
            for j in range(len(num)-1, i, -1):
                if num[j] < num[i]:
                    num[i], num[j] = num[j], num[i]
                    break
            for j in range(0, (len(num) - i)//2):
                num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]
            return num
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        num = [1,3,2,3]
        num1 = solution.previousPermuation(num)
        print("输入：", "[1,3,2,3]")
        print("输出：", num1)

【例106】下一个排列 难度等级★★  
3.代码实现

class Solution:
        #参数num: 整数列表
        #返回值: 整数列表
        def nextPermutation(self, num):
            for i in range(len(num)-2, -1, -1):
                if num[i] < num[i+1]:
                    break
            else:
                num.reverse()
                return num
            for j in range(len(num)-1, i, -1):
                if num[j] > num[i]:
                    num[i], num[j] = num[j], num[i]
                    break
            for j in range(0, (len(num) - i)//2):
                num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]
            return num
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        num = [1,3,2,3]
        num1 = solution.nextPermutation(num)
        print("输入：", "[1, 3, 2, 3]")
        print("输出：", num1)

【例107】二叉树的层次遍历 难度等级★★  
3.代码实现

class TreeNode:  
         def __init__(self, val=None, left=None, right=None):
             self.val=val  
             self.left=left    #左子树
             self.right=right  #右子树
    class Solution:
        #参数root: 二叉树的根
        #返回值:从底向上的层次序遍历
        def levelOrderBottom(self, root):
            self.results = []
            if not root:
                return self.results
            q = [root]
            while q:
                new_q = []
                self.results.append([n.val for n in q])
                for node in q:
                    if node.left:
                        new_q.append(node.left)
                    if node.right:
                        new_q.append(node.right)
                q = new_q
            return list(reversed(self.results))
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        root=TreeNode(1,TreeNode(2),TreeNode(3))
        results = solution.levelOrderBottom(root)
        print("输入： {1,2,3}")
        print("输出：", results)

【例108】最长公共子串 难度等级★★  
3.代码实现

class Solution:
        #参数A, B: 两个字符串
        #返回值: 最长公共子串的长度
        def longestCommonSubstring(self, A, B):
            ans = 0
            for i in range(len(A)):
                for j in range(len(B)):
                    l = 0
                    while i + l < len(A) and j + l < len(B) \
                        and A[i + l] == B[j + l]:
                        l += 1
                    if l > ans:
                        ans = l
            return ans
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = "ABCD"
        B = "CBCE"
        ans = solution.longestCommonSubstring(A, B)
        print("输入：","A =",A,"B =",B)
        print("输出：", ans)

【例109】最近公共祖先 难度等级★★  
3.代码实现

#Definition of TreeNode:
    class TreeNode:  
         def __init__(self, val=None, left=None, right=None):
             self.val=val  
             self.left=left    #左子树
             self.right=right  #右子树
            
    class Solution:
        #参数root: 二叉搜索树的根
        #参数A: 二叉树的一个节点
        #参数B: 二叉树的一个节点
        #返回值: 返回两个节点的最低公共祖先(LCA)
        def lowestCommonAncestor(self, root, A, B):
            # A且其下面有B => A
            # B且其下面有A => B
            # A且其下面啥都没有 => A
            # B且其下面啥都有 => B
            if root is None:
                return None
            if root == A or root == B:
                return root
            left_result = self.lowestCommonAncestor(root.left, A, B)
            right_result = self.lowestCommonAncestor(root.right, A, B)
            # A 和 B 一边一个
            if left_result and right_result: 
                return root
            # 左子树有一个点或者左子树有LCA
            if left_result:
                return left_result
            # 右子树有一个点或者右子树有LCA
            if right_result:
                return right_result
            # 左右子树啥都没有
            return None
    #主函数
    if __name__ == '__main__':
        tree = TreeNode(4, TreeNode(3), TreeNode(7, TreeNode(5), TreeNode(6)))
        solution = Solution()
        result = solution.lowestCommonAncestor(tree, tree.left, tree.right.left)
        print("输入：{4,3,7,#,#,5,6}, LCA(3,5)")
        print("输出：", result.val)

【例110】k数和 难度等级★★  
3.代码实现

class Solution:
        def kSumII(self, A, k, target):
            anslist = []
            self.dfs(A, k, target, 0, [], anslist)
            return anslist
        def dfs(self, A, k, target, index, onelist, anslist):
            if target == 0 and k == 0:
                anslist.append(onelist)
                return
            if len(A) == index or target < 0 or k < 0:
                return
            self.dfs(A, k, target, index + 1, onelist, anslist)
            self.dfs(A, k - 1, target - A[index],  index + 1 , onelist + [A[index]], anslist)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [1,2,3,4]
        k = 2
        target = 5
        anslist = solution.kSumII(A, k, target)
        print("输入：A = [1,2,3,4] k = 2 target = 5")
        print("输出：", anslist)

【例111】有序链表转换为二分查找树 难度等级★★  
3.代码实现

#定义链表节点
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    #定义树节点
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    class Solution:
        #参数head: 链表的第一个节点
        #返回值: 树节点
        def sortedListToBST(self, head):
            num_list = []
            while head:
                num_list.append(head.val)
                head = head.next
            return self.create(num_list, 0, len(num_list) - 1)
        def create(self, nums, start, end):
            if start > end:
                return None
            if start == end:
                return TreeNode(nums[start])
            root = TreeNode(nums[(start + end) // 2])
            root.left = self.create(nums, start, (start + end) // 2 - 1) #注意是-1
            root.right = self.create(nums, (start + end) // 2 + 1, end)
            return root
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        listnode = ListNode(1, ListNode(2, ListNode(3)))
        root = solution.sortedListToBST(listnode)
        print("输入： 1=>2=>3")
        print("输出：", "{", root.val, root.left.val, root.right.val, "}")

【例112】最长连续序列 难度等级★★  
3.代码实现

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

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

class Solution:
        #参数m: 整数m表示背包的大小
        #参数A & V: 给定n个大小为A[i]和值V[i]的物品
        def backPackII(self, m, A, V):
            f = [0 for i in range(m+1)]
            n = len(A)
            for i in range(n):
                for j in range(m, A[i]-1, -1):
                    f[j] = max(f[j] , f[j-A[i]] + V[i])
            return f[m]
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        m = 100
        A = [77,22,29,50,99]
        V = [92,22,87,46,90]
        result = solution.backPackII(m, A, V)
    print("输入：\n","m = ",m, "\n A = ", A, "\n V = ",V)
    print("输出：", result)

【例114】拓扑排序 难度等级★★  
3.代码实现

#定义有向图节点
    class DirectedGraphNode:
        def __init__(self, x):
            self.label = x
            self.neighbors = []
    class Solution:
        #参数graph: 有向图节点列表
        #返回值: 整数列表
        def topSort(self, graph):
            indegree = { }
            for x in graph:
                indegree[x] = 0
            for i in graph:
                for j in i.neighbors:
                    indegree[j] += 1
            ans = []
            for i in graph:
                if indegree[i] == 0:
                    self.dfs(i, indegree, ans)
            return ans
        def dfs(self, i, indegree, ans):
            ans.append(i.label)
            indegree[i] -= 1
            for j in i.neighbors:
                indegree[j] -= 1
                if indegree[j] == 0:
                    self.dfs(j, indegree, ans)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        g0 = DirectedGraphNode(0)
        g1 = DirectedGraphNode(1)
        g2 = DirectedGraphNode(2)
        g3 = DirectedGraphNode(3)
        g4 = DirectedGraphNode(4)
        g5 = DirectedGraphNode(5)
        g0.neighbors = [g1, g2, g3]
        g1.neighbors = [g4]
        g2.neighbors = [g4, g5]
        g3.neighbors = [g4, g5]
        graph = [g0, g1, g2, g3, g4, g5]
        result = solution.topSort(graph)
        print("输入：如样例图")
        print("输出：",result)

【例115】克隆图 难度等级★★  
3.代码实现

#定义无向图节点
    class UndirectedGraphNode:
        def __init__(self, x):
            self.label = x
            self.neighbors = []
    class Solution:
        def __init__(self):
            self.dict = { }
        #参数node: 无向图节点
        #返回值: 无向图节点
        def cloneGraph(self, node):
            if node is None:
                return None
            if node.label in self.dict:
                return self.dict[node.label]
            root = UndirectedGraphNode(node.label)
            self.dict[node.label] = root
            for item in node.neighbors:
                root.neighbors.append(self.cloneGraph(item))
            return root
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        g0 = UndirectedGraphNode(0)
        g1 = UndirectedGraphNode(1)
        g2 = UndirectedGraphNode(2)
        g0.neighbors = [g1, g2]
        g1.neighbors = [g2]
        g2.neighbors = [g2]
        ans = solution.cloneGraph(g0)
        a = [ans.label, ans.neighbors[0].label, ans.neighbors[1].label, 
             ans.neighbors[0].neighbors[0].label, ans.neighbors[1].neighbors[0].label]
        print("输入： {0,1,2#1,2#2,2}")
        print("输出：", a)

【例116】不同的二叉查找树 难度等级★★  
3.代码实现

class Solution:
        #参数n: 整数
        #返回值: 整数
        def numTrees(self, n):
            dp = [1, 1, 2]
            if n <= 2:
                return dp[n]
            else:
                dp += [0 for i in range(n-2)]
                for i in range(3, n + 1):
                    for j in range(1, i+1):
                        dp[i] += dp[j-1] * dp[i-j]
                return dp[n]
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        n = 3
        ans = solution.numTrees(n)
        print("输入：", n)
        print("输出：", ans)

【例117】汉诺塔 难度等级★★  
3.代码实现  
class Solution:  
def move(self, n, a, b, c, ans): \#n为圆盘数，a代表初始位圆柱，b代表过渡位圆柱，c代表目标位圆柱  
if n==1:  
ans.append("from “+a+” to "+c)  
else:  
self.move(n-1,a,c,b,ans)  
ans.append("from “+a+” to "+c)  
self.move(n-1,b,a,c,ans)  
return ans  
\#主函数  
if **name** == ‘**main**’:  
solution = Solution()  
ans = \[\]  
res = solution.move(3, ‘A’, ‘B’, ‘C’, ans)  
print(“输入： 3, ‘A’, ‘B’, ‘C’”)  
print(“输出：”, res)  
【例118】图中两个点之间的路线 难度等级★★  
3.代码实现

#定义有向图节点
    class DirectedGraphNode:
        def __init__(self, x):
            self.label = x
            self.neighbors = []
    class Solution:
        def dfs(self, i, countrd, graph, t):
            if countrd[i] == 1:
                return False
            if i == t:
                return True
            countrd[i] = 1
            for j in i.neighbors:
                if countrd[j] == 0 and self.dfs(j, countrd, graph, t):
                    return True
            return False
        #参数graph: 有向图节点列表
        #参数s: 起始有向图节点
        #参数t: 终端有向图节点
        #返回值: 布尔值
        def hasRoute(self, graph, s, t):
            countrd = { }
            for x in graph:
                countrd[x] = 0
            return self.dfs(s, countrd, graph, t)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        gA = DirectedGraphNode('A')
        gB = DirectedGraphNode('B')
        gC = DirectedGraphNode('C')
        gD = DirectedGraphNode('D')
        gE = DirectedGraphNode('E')
        gA.neighbors = [gB, gD]
        gB.neighbors = [gC, gD]
        gD.neighbors = [gE]
        graph = [gA, gB, gC, gD, gE]
        ans = solution.hasRoute(graph, gB, gE)
        print("输入： {A,B,C,D,E,A#B,A#D,B#C,B#D,D#E}, B, E")
        print("输出：", ans)

【例119】丢失的第一个正整数 难度等级★★  
3.代码实现

class Solution:
        #参数A：整数数组
        #返回值：整数
        def firstMissingPositive(self, A):
            n = len(A)
            i = 0
            if n == 0: 
                return 1
            while i < n:
               while A[i]!=i+ 1 and A[i] <= n and A[i] > 0 and A[i] != A[A[i] - 1]: 
                    t = A[i]
                    A[i] = A[A[i] - 1] 
                    A[t - 1] = t
                i = i + 1
            for i in range(n):
                if A[i] != i + 1: return i + 1
            return n + 1
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [3,4,-1,1]
        ans = solution.firstMissingPositive(A)
        print("输入：", A)
        print("输出：", ans)

【例120】寻找缺失的数 难度等级★★  
3.代码实现

class Solution:
        def findMissing(self, nums):
            if not nums:
                return 0
            sum = 0 
            for _ in nums:
                sum += _
            return int((len(nums) * (len(nums) + 1) / 2)) - sum
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        nums = [0,1,3]
        ans = solution.findMissing(nums)
        print("输入：", nums)
        print("输出：", ans)

【例121】排列序号I 难度等级★★  
3.代码实现

class Solution:
        #参数A: 整数数组
        #返回值: 整数
        def permutationIndex(self, A):
            result = 1
            factor = 1
            for i in range(len(A)-1, -1, -1):
                rank = 0
                for j in range(i+1, len(A)):
                    if A[i] > A[j]:
                        rank +=1
                result += factor*rank
                factor *= len(A)-i
            return result
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [3,2,1]
        ans = solution.permutationIndex(A)
        print("输入：", A)
        print("输出：", ans)

【例122】排列序号II 难度等级★★  
3.代码实现

class Solution:
    #参数A: 整数数组 
    #返回值: 长整数
        def permutationIndexII(self, A):
            if A is None or len(A) == 0:
                return 0
            index, factor, multi_fact = 1, 1, 1
            counter = { }
            for i in range(len(A) - 1, -1, -1):
                counter[A[i]] = counter.get(A[i], 0) + 1
                multi_fact *= counter[A[i]]
                count = 0
                for j in range(i + 1, len(A)):
                    if A[i] > A[j]:
                        count += 1
                index += count * factor // multi_fact
                factor *= (len(A) - i)
            return index
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [1,4,2,2]
        ans = solution.permutationIndexII(A)
        print("输入：", A)
        print("输出：", ans)

【例123】最多有k个不同字符的最长子字符串 难度等级★★  
3.代码实现

#参数s是一个字符串
    #返回值res是最长字符串的长度
    class Solution:
        def lengthOfLongestSubstring(self, s):
            res = 0
            if s is None or len(s) == 0:
                return res
            d = { }
            tmp = 0
            start = 0
            for i in range(len(s)):
                if s[i] in d and d[s[i]] >= start:
                    start = d[s[i]] + 1
                tmp = i - start + 1
                d[s[i]] = i
                res = max(res, tmp)
            return res
    #主函数
    if __name__ == '__main__':
        generator = 'eceba'
        solution = Solution()
        print("输入：", generator)
        print("输出：", solution. lengthOfLongestSubstring(generator))

【例124】第k个排列 难度等级★★  
3.代码实现

#参数n是指1~n
    #参数k是指所有全排列中的第几个
    #返回值是第k个全排列
    class Solution:
        def getPermutation(self, n, k):
            fac = [1]
            for i in range(1, n + 1):
                fac.append(fac[-1] * i)
            elegible = list(range(1, n + 1))
            per = []
            for i in range(n):
                digit = (k - 1) // fac[n - i - 1]
                per.append(elegible[digit])
                elegible.remove(elegible[digit])
                k = (k - 1) % fac[n - i - 1] + 1
            return "".join([str(x) for x in per])
    #主函数
    if __name__ == '__main__':
        k=4
        n=3
        solution = Solution()
        print("输入：", "n=",n,"k=",k)
        print("输出：", solution.getPermutation(n,k))

【例125】数飞机 难度等级★★  
3.代码实现

#参数start是开始时间
    #参数end是结束时间
    class Interval(object):
        def __init__(self, start, end):
            self.start = start
            self.end = end
    #参数airplanes是一个由时间间隔对象组成的数组
    #返回值max_number_of_airplane是飞机的最大数
    class Solution:
        def countOfAirplanes(self, airplanes):
            points = []
            for airplane in airplanes:
                points.append([airplane.start, 1])
                points.append([airplane.end, -1])
            number_of_airplane, max_number_of_airplane = 0, 0
            for _, count_delta in sorted(points):
                number_of_airplane += count_delta
                max_number_of_airplane = max(max_number_of_airplane,
     number_of_airplane)
            return max_number_of_airplane
    #主函数
    if __name__ == '__main__':
        generator=[Interval(1,10),Interval(5,8),Interval(2,3),Interval(4,7)]
    solution = Solution()
        print("输入：",[(1, 10), (2, 3), (5, 8), (4, 7)] )
        print("输出：", solution.countOfAirplanes(generator))

【例126】格雷编码 难度等级★★  
3.代码实现

#参数n是一个整型数
    #返回值seq是所对应的格雷编码
    class Solution：
        def grayCode(self, n):
            if n == 0:
                return [0]
            
            result = self.grayCode(n - 1)
            seq = list(result)
            for i in reversed(result):
                seq.append((1 << (n - 1)) | i)
            return seq
    #主函数
    if __name__ == '__main__':
        generator=2
    solution = Solution()
    print("输入：", generator)
        print("输出：", solution. grayCode(generator))

【例127】迷你Cassandra 难度等级★★  
3.代码实现

#参数raw_key是一个字符串，用于哈希
    #参数column_key是一个整数，支持范围查询
    #参数column_value是储存字符串的值
    #参数column_start是开始位置
    #参数column_start是结束位置
    #返回值rt是一个由Column对象组成的列表
    class Column:
        def __init__(self, key, value):
            self.key = key
            self.value = value
    from collections import OrderedDict
    class Solution:
        def __init__(self):
            self.hash = { }
        def insert(self, raw_key, column_key, column_value):
            if raw_key not in self.hash:
                self.hash[raw_key] = OrderedDict()
            self.hash[raw_key][column_key] = column_value
        def query(self, raw_key, column_start, column_end):
            rt = []
            if raw_key not in self.hash:
                return rt
            self.hash[raw_key] = OrderedDict(sorted(self.hash[raw_key].items()))
            for key, value in self.hash[raw_key].items():
                if key >= column_start and key <= column_end:
                    rt.append(Column(key, value))
            return rt
    #主函数
    if __name__ == '__main__':
    generator = Column(1, "abcd")
    generator1 = Column(2, "hijk")
    solution = Solution()
    solution.insert("google",generator.key,generator.value)
    solution.insert("google",generator1.key,generator1.value)
    ls = solution.query("google", 0, 2)
    print('输入: query("google", 0, 2)')
    print("输出: ")
    for i in ls:
     	print(i.key,i.value)

【例128】网络日志 难度等级★★  
3.代码实现

#参数timestamp是个整数，建立一个时间点
    #返回值是个整数，表示最后五分钟时间点的个数
    class WebLogger:
        def __init__(self):
            self.Q = []
        def hit(self, timestamp):
            self.Q.append(timestamp)
        def get_hit_count_in_last_5_minutes(self, timestamp):
            if self.Q == []:
                return 0
            i = 0
            n = len(self.Q)
            while i < n and self.Q[i] + 300 <= timestamp:
                i += 1
            self.Q = self.Q[i:]
            return len(self.Q)
    #主函数
    if __name__ == '__main__':
    solution = WebLogger()
     print("输入：hit(1),hit(2) ")
     solution.hit(1)
     solution.hit(2)
     print("输出最后5分钟时间戳个数：")
     print(solution.get_hit_count_in_last_5_minutes(3))
     print("输入：hit(300) ")
     solution.hit(300)
     print("输出最后5分钟时间戳个数：")
     print(solution.get_hit_count_in_last_5_minutes(300))
     print("输出最后5分钟时间戳个数：")
     print(solution.get_hit_count_in_last_5_minutes(301))

【例129】栅栏染色 难度等级★★  
3.代码实现

#参数n是个非负整数，柱子数
    #参数n是个非负整数，颜色数
    #返回值是个整数，所有的染色方案
    class Solution:
        def numWays(self, n, k):
            dp = [0, k, k * k]
            if n <= 2:
                return dp[n]
            if k == 1 and n >= 3:
                return 0
            for i in range(2, n):
                dp.append((k - 1) * (dp[-1] + dp[-2]))
            return dp[-1]
    #主函数
    if __name__ == '__main__':
    solution= Solution()
    n=3
    k=2
    print("输入： n=",n ,"k=",k)
    print("输出：",solution.numWays(n,k))

【例130】房屋染色 难度等级★★  
3.代码实现

#参数costs是个nx3矩阵
    #返回值是个整数，刷完所有房子最小花费
    class Solution:
        def minCost(self, costs):
            n = len(costs)
            if n == 0:
                return 0
            INF = 0x7fffffff
            f = [costs[0], [INF, INF, INF]]
            for i in range(1, n):
                for j in range(3):
                    f[i&1][j] = INF
                    for k in range(3):
                        if j != k:
                            f[i&1][j] = min(f[i&1][j], f[(i+1)&1][k] + costs[i][j])
            return min(f[(n-1)&1])
    #主函数
    if __name__ == '__main__':
    generator=[[14,2,11],[11,14,5],[14,3,10]]
    solution= Solution()
    print("输入： ",generator)
    print("输出： ",solution.minCost(generator))

【例131】去除重复元素 难度等级★★  
3.代码实现

#参数nums是个一个整型数组
    #返回值result是不重复元素的个数
    class Solution:
        def deduplication(self, nums):
            n = len(nums)
            if n == 0:
                return 0
            nums.sort()
            result = 1
            for i in range(1, n):
                if nums[i - 1] != nums[i]:
                    nums[result] = nums[i]
                    result += 1
            return result
    #主函数
    if __name__ == '__main__':
    generator=[1,3,1,4,4,2]
    solution= Solution()
    print("输入：",generator)
    print("输出：",solution.deduplication(generator))

【例132】左填充 难度等级★★  
3.代码实现

#参数originalStr是需要添加的字符串
    #参数size是目标长度
    #参数padchar是在字符串左边填充的字符
    #返回值是左填充后的字符串
    class StringUtils:
        def leftPad(self, originalStr, size, padChar=' '):
            return padChar * (size - len(originalStr)) + originalStr
    #主函数
    if __name__ == '__main__':
    size=8
    generator = "foobar"
    solution= StringUtils()
    print("输入:",generator)
    print("输出:",solution.leftPad(generator,size))

【例133】负载均衡器 难度等级★★  
3.代码实现

#参数server_id是一个服务器的ID
    #返回值是一个ID，集群中随机的一个服务器ID
    class LoadBalancer:
        def __init__(self):
            self.server_ids = []
            self.id2index = { }
        def add(self, server_id):
            if server_id in self.id2index:
                return
            self.server_ids.append(server_id)
            self.id2index[server_id] = len(self.server_ids) - 1
        def remove(self, server_id):
            if server_id not in self.id2index:
                return
            # remove the server_id
            index = self.id2index[server_id]
            del self.id2index[server_id]
            # overwrite the one to be removed
            last_server_id = self.server_ids[-1]
            self.id2index[last_server_id] = index
            self.server_ids[index] = last_server_id
            self.server_ids.pop()
        def pick(self):
            import random
            index = random.randint(0, len(self.server_ids) - 1)
            return self.server_ids[index]
    #主函数
    if __name__ == '__main__':
    solution= LoadBalancer()
    solution.add(1)
    solution.add(2)
    solution.remove(1)
    print("输入: \nadd(1)\nadd(2)\nremove(1)")
    print("输出:",solution.pick())
    print("输出:",solution.pick())

【例134】两数和的最接近值 难度等级★★  
3.代码实现

#参数nums是个整数数组
    #参数target是一个整数
    #返回值diff是target和两数求和的差距
    import sys
    class Solution:
        def twoSumClosest(self, nums, target):
            nums.sort()
            i, j = 0, len(nums)  - 1
            diff = sys.maxsize
            while i < j:
                if nums[i] + nums[j] < target:
                    diff = min(diff, target - nums[i] - nums[j])
                    i += 1
                else:
                    diff = min(diff, nums[i] + nums[j] - target)
                    j -= 1
            return diff
    #主函数
    if __name__ == '__main__':
    generator = [-1,2,-1,4]
    solution= Solution()
    target = 4
    print("target =",target)
    print("输入：",generator)
    print("输出:",solution.twoSumClosest(generator,target))

【例135】打劫房屋 难度等级★★  
3.代码实现

#参数nums是个非负整数列表，表示每个房子中存放的钱
    #返回值是个整数，表示可以拿到的钱
    class Solution:
        def houseRobber2(self, nums):
            n = len(nums)
            if n == 0:
                return 0
            if n == 1:
                return nums[0]
            dp = [0] * n
            dp[0], dp[1] = 0, nums[1]
            for i in range(2, n):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
            answer = dp[n - 1]
            dp[0], dp[1] = nums[0], max(nums[0], nums[1])
            for i in range(2, n - 1):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
            return max(dp[n - 2], answer)
    #主函数
    if __name__ == '__main__':
    generator = [2,3,2,3]
    solution= Solution()
    print("输入:",generator)
    print("输出:",solution.houseRobber2(generator))

【例136】左旋右旋迭代器 难度等级★★  
3.代码实现

#参数v1，v2表示两个一维向量
    #返回值是一个一维数组，交替返回v1，v2元素
    class ZigzagIterator:
        def __init__(self, v1, v2):
            self.queue = [v for v in (v1, v2) if v]
        def next(self):
            v = self.queue.pop(0)
            value = v.pop(0)
            if v:
                self.queue.append(v)
            return value
        def hasNext(self):
            return len(self.queue) > 0
    #主函数
    if __name__ == '__main__':
    v1= [1,2]
    v2= [3,4,5,6]
    print("输入:")
    print(",".join(str(i) for i in v1))
    print(",".join(str(i) for i in v2))
    solution, result = ZigzagIterator(v1, v2), []
    while solution.hasNext():
        result.append(solution.next())
    print("输出:",result)

【例137】N数组第K大元素 难度等级★★  
3.代码实现

import heapq
    #参数arrays一个数组列表
    #参数k表示第k大
    #返回值num是列表中最大的数
    class Solution:
        def KthInArrays(self, arrays, k):
            if not arrays:
                return None
            # in order to avoid directly changing the original arrays
            # and remove the empty arrays, we need a new sortedArrays
            sortedArrays = []
            for arr in arrays:
                if not arr:
                    continue
                sortedArrays.append(sorted(arr, reverse=True))
            maxheap = [
                       (-arr[0], index, 0)
                       for index, arr in enumerate(sortedArrays)
            ]
            heapq.heapify(maxheap)
            num = None
            for _ in range(k):
                num, x, y = heapq.heappop(maxheap)
                num = -num
                if y + 1 < len(sortedArrays[x]):
                    heapq.heappush(maxheap, (-sortedArrays[x][y + 1], x, y + 1))
            return num
    #主函数
    if __name__ == '__main__':
    generator = [[2,3,2,4],[3,4,7,9]]
    k=5
    solution= Solution()
    print("输入:",generator)
    print("k= ",k)
    print("输出:",solution.KthInArrays(generator,k))

【例138】前K大数 难度等级★★  
3.代码实现

import heapq
    #参数nums是个整数数组
    #参数k表示第k大
    #返回值是个整型数组，前k大的整数组成
    class Solution:
        def topk(self, nums, k):
            heapq.heapify(nums)
            topk = heapq.nlargest(k, nums)
            topk.sort()
            topk.reverse()
            return topk
    #主函数
    if __name__ == '__main__':
    generator = [8, 7, 6, 5, 4, 3, 2, 1]
    k=4
    solution= Solution()
    print("输入:",generator)
    print("k=",k)
    print("输出:",solution.topk(generator,k))

【例139】计数型布隆过滤器 难度等级★★  
3.代码实现

import random
    #参数str是个字符串，表示一个word
    #返回值是个布尔值，若该word存在返回True，否则返回False
    class HashFunction:
        def __init__(self, cap, seed):
            self.cap = cap
            self.seed = seed
        def hash(self, value):
            ret = 0
            for i in value:
                ret += self.seed * ret + ord(i)
                ret %= self.cap
            return ret
    class CountingBloomFilter:
        def __init__(self, k):
            self.hashFunc = []
            for i in range(k):
                self.hashFunc.append(HashFunction(random.randint(10000, 20000), i * 2 + 3))
            self.bits = [0 for i in range(20000)]
        def add(self, word):
            for f in self.hashFunc:
                position = f.hash(word)
                self.bits[position] += 1
        def remove(self, word):
            for f in self.hashFunc:
                position = f.hash(word)
                self.bits[position] -= 1
        def contains(self, word):
            for f in self.hashFunc:
                position = f.hash(word)
                if self.bits[position] <= 0:
                    return False
            return True
    #主函数
    if __name__ == '__main__':
    solution= CountingBloomFilter(3)
    solution.add("long")
    solution.add("term")
    print('输入:')
    print('add("long")')
    print('add("term")')
    print('contains("long")')
    print("输出:",solution.contains("long"))
    solution.remove("long")
    print('remove("long")')
    print('contains("long")')
    print("输出:",solution.contains("long"))

【例140】字符计数 难度等级★★  
3.代码实现

#参数str一个任意的字符串
    #返回值map是个哈希map
    class Solution:
        def countCharacters(self, str):
            map = dict()
            for c in str:
                map[c] = map.get(c, 0) + 1
            return map
    #主函数
    if __name__ == '__main__':
    generator="abca"
    solution = Solution()
    print('输入:',generator)
    print("输出:",solution.countCharacters(generator))

【例141】最长重复子序列 难度等级★★  
3.代码实现

#参数str是个任意字符串
    #返回值是个整数表示这个字符串最长重复的子序列长度
    class Solution:
        def longestRepeatingSubsequence(self, str):
            n = len(str)
            dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if str[i - 1] == str[j - 1] and i != j:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    else:
                        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            return dp[n][n]
    #主函数
    if __name__ == '__main__':
    solution = Solution()
    generator="abcaa"
    print('输入：',generator)
    print("输出：",solution. longestRepeatingSubsequence(generator))

【例142】僵尸矩阵 难度等级★★  
3.代码实现

import collections
    #参数grid是一个二维整数矩阵
    #返回值是个整数，表示需要的天数，若不能完成则返回-1
    class Solution:
        def zombie(self, grid):
            if len(grid) == 0 or len(grid[0]) == 0:
                return 0
            m, n = len(grid), len(grid[0])
            queue = collections.deque()
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1:
                        queue.append((i, j))
            day = 0
            while queue:
                size = len(queue)
                day += 1
                for k in range(size):
                    (i, j) = queue.popleft()
                    DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
                    for (di, dj) in DIR:
                        next_i, next_j = i + di, j + dj
                        if next_i < 0 or next_i >= m or next_j < 0 or next_j >= n:
                            continue
                        if grid[next_i][next_j] == 1 or grid[next_i][next_j] == 2:
                            continue
                        grid[next_i][next_j] = 1
                        queue.append((next_i, next_j))
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 0:
                        return -1
            return day - 1
    #主函数
    if __name__ == '__main__':
    solution = Solution()
    generator=[[0,0,0],
                 [0,0,0],
                 [0,0,1]]
    print("输入：",generator)
    print("输出：",solution. zombie(generator))

【例143】摊平二维向量 难度等级★★  
3.代码实现

class Vector2D(object):
        def __init__(self, vec2d):
            self.vec2d = vec2d
            self.row, self.col = 0, -1
            self.next_elem = None
        def next(self):
            if self.next_elem is None:
                self.hasNext()
            temp, self.next_elem = self.next_elem, None
            return temp
        def hasNext(self):
            if self.next_elem:
                return True
            self.col += 1
            while self.row < len(self.vec2d)and self.col>= len(self.vec2d[self.row]):
                self.row += 1
                self.col = 0
            if self.row < len(self.vec2d) and self.col < len(self.vec2d[self.row]):
                self.next_elem = self.vec2d[self.row][self.col]
                return True
            return False
    #主函数
    if __name__ == '__main__':
        inputnum=[[1,2],[3],[4,5,6]]
        vector2d=Vector2D(inputnum)
        print("输入：",inputnum)
        print("输出：")
        print(vector2d.next())
        while vector2d.hasNext():
            print(vector2d.next())

【例144】第K大的元素 难度等级★★  
3.代码实现

class Solution:
        # nums是整型数组
        # k是整数
        # 返回数组第k大的元素
        def kthLargestElement2(self, nums, k):
            import heapq
            heap = []
            for num in nums:
                heapq.heappush(heap, num)
                if len(heap) > k:
                    heapq.heappop(heap)
            return heapq.heappop(heap)
    #主函数
    if __name__ == '__main__':
        inputnum=[9,3,2,4,8]
        k=3
        print("输入数组：",inputnum)
        print("输入k=",k)
        solution=Solution()
        print("输出：",solution.kthLargestElement2(inputnum,k))

【例145】两数和小于或等于目标值 难度等级★★  
3.代码实现

class Solution:
        # 参数nums是整数数组
        # 参数target是整数
        # 返回整数
        def twoSum5(self, nums, target):
            l, r = 0, len(nums)-1
            cnt = 0
            nums.sort()
            while l < r:
                value = nums[l] + nums[r]
                if value > target:
                    r -= 1
                else:
                    cnt += r - l
                    l += 1
            return cnt
    #主函数
    if __name__ == '__main__':
        inputnum= [2, 7, 11, 15]
        target=24
    solution=Solution()
    print("输入数组：",inputnum)
    print("输入target：",target)
    solution=Solution()
    print("输出：",solution.twoSum5(inputnum,target))

【例146】两数差等于目标值 难度等级★★  
3.代码实现

class Solution:
        #参数nums是整数数组
        #参数target是整数
        #返回数组的索引值加1，[index1 + 1, index2 + 1] (index1 < index2)
        def twoSub(self, nums, target):
            nums = [(num, i) for i, num in enumerate(nums)]
            target = abs(target)    
            n, indexs = len(nums), []
            nums = sorted(nums, key=lambda x: x[0])
            j = 0
            for i in range(n):
                if i == j:
                    j += 1
                while j < n and nums[j][0] - nums[i][0] < target:
                    j += 1
                if j < n and nums[j][0] - nums[i][0] == target:
                    indexs = [nums[i][1] + 1, nums[j][1] + 1]
            if indexs[0] > indexs[1]:
                indexs[0], indexs[1] = indexs[1], indexs[0]
            return indexs
    #主函数
    if __name__ == '__main__':
        inputnum= [2, 7, 15, 24]
        target=5
    solution=Solution()
    print("输入数组：",inputnum)
    print("输入target：",target)
    print("输出：",solution.twoSub(inputnum,target))

【例147】骑士的最短路线 难度等级★★  
3.代码实现

import collections
    class Point:
        def __init__(self, a=0, b=0):
            self.x = a
            self.y = b
    DIRECTIONS = [
        (-2, -1), (-2, 1), (-1, 2), (1, 2),
        (2, 1), (2, -1), (1, -2), (-1, -2),
    ]
    class Solution:
        #参数grid表示棋盘
        #参数source表示起点
        #参数destination表示终点
        #返回最短路径长度
        def shortestPath(self, grid, source, destination):
            queue = collections.deque([(source.x, source.y)])
            distance = { (source.x, source.y): 0}
            while queue:
                x, y = queue.popleft()
                if (x, y) == (destination.x, destination.y):
                    return distance[(x, y)]
                for dx, dy in DIRECTIONS:
                    next_x, next_y = x + dx, y + dy
                    if (next_x, next_y) in distance:
                        continue
                    if not self.is_valid(next_x, next_y, grid):
                        continue
                    distance[(next_x, next_y)] = distance[(x, y)] + 1
                    queue.append((next_x, next_y))
            return -1
        def is_valid(self, x, y, grid):
            n, m = len(grid), len(grid[0])
            if x < 0 or x >= n or y < 0 or y >= m:
                return False
            return not grid[x][y]
    #主函数
    if __name__ == '__main__':
        inputnum=[[0,0,0],
                   [0,0,0],
                   [0,0,0]]
        source = Point(2,0)
        destination = Point(2,2)
    solution=Solution()
    print("输入棋盘：",inputnum)
    print("输入起点：[2,0]")
    print("输入终点：[2,2]")
    print("输出步数：",solution.shortestPath(inputnum,source,destination))

【例148】K个最近的点 难度等级★★  
3.代码实现

import heapq
    import numpy as np
    np.set_printoptions(threshold=np.inf)
    class Point:
        def __init__(self, a=0, b=0):
            self.x = a
            self.y = b
    class Solution:
        #参数points为坐标点列表
        #参数origin为初始点
        #参数k为整数
        #返回k个最邻近点
        def kClosest(self, points, origin, k):
            self.heap = []
            for point in points:
                dist = self.getDistance(point, origin)
                heapq.heappush(self.heap, (-dist, -point.x, -point.y))
                if len(self.heap) > k:
                    heapq.heappop(self.heap)
            ret = []
            while len(self.heap) > 0:
                _, x, y = heapq.heappop(self.heap)
                ret.append(Point(-x, -y))
            ret.reverse()
            return ret
        def getDistance(self, a, b):
            return (a.x - b.x) ** 2 + (a.y - b.y) ** 2
    #主函数
    if __name__=='__main__':
        a1=Point(0,0)
        a2=Point(0,9)
        inputnum=[a1,a2]
        origin=Point(0,0)
        k=1
        solution=Solution()
        rp=Point(0,0)
        rp=solution.kClosest(inputnum,origin,k)
    array=[[rp[0].x,rp[0].y]]
    print("输入坐标点：[[0,0],[0,9]]")
    print("最近坐标数：k=1")
    print("输出坐标点：",array)

【例149】优秀成绩 难度等级★★  
3.代码实现

class Record:
        def __init__(self, id, score):
            self.id = id
            self.score = score
    class Solution:
        # @param {Record[]} results a list of <student_id, score>
        # @return {dict(id, average)} find the average of 5 highest scores for each person
        # <key, value> (student_id, average_score)
        def highFive(self, results):
            # Write your code here
            hash = dict()
            for r in results:
                if r.id not in hash:
                    hash[r.id] = []
                hash[r.id].append(r.score)
                if len(hash[r.id]) > 5:
                    index = 0
                    for i in range(1, 6):
                        if hash[r.id][i] < hash[r.id][index]:
                            index = i
                    hash[r.id].pop(index)
            answer = dict()
            for id, scores in hash.items():
                answer[id] = sum(scores) / 5.0
            return answer
    #主函数
    if __name__=='__main__':
        r1=Record(1,90)
        r2=Record(1,93)
        r3=Record(2,93)
        r4=Record(2,99)
        r5=Record(2,98)
        r6=Record(2,97)
        r7=Record(1,62)
        r8=Record(1,56)
        r9=Record(2,95)
        r10=Record(1,61)
        list=[r1,r2,r3,r4,r5,r6,r7,r8,r9,r10]
        solution=Solution()
        print(solution.highFive(list))

【例150】二叉树的最长连续子序列I 难度等级★★  
3.代码实现

class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        #参数root是二叉树的根节点
        #返回最长连续序列路径的长度
        def longestConsecutive2(self, root):
            max_len, _, _, = self.helper(root)
            return max_len
        def helper(self, root):
            if root is None:
                return 0, 0, 0
            left_len, left_down, left_up = self.helper(root.left)
            right_len, right_down, right_up = self.helper(root.right)
            down, up = 0, 0
            if root.left is not None and root.left.val + 1 == root.val:
                down = max(down, left_down + 1)
            if root.left is not None and root.left.val - 1 == root.val:
                up = max(up, left_up + 1)
            if root.right is not None and root.right.val + 1 == root.val:
                down = max(down, right_down + 1)
            if root.right is not None and root.right.val - 1 == root.val:
                up = max(up, right_up + 1)
            len = down + 1 + up
            len = max(len, left_len, right_len)
            return len, down, up
    #主函数
    if __name__=='__main__':
        inputnum={ 1,2,0,3}
        root0=TreeNode(0)
        root1=TreeNode(1)
        root2=TreeNode(2)
        root3=TreeNode(3)
        root1.left=root2
        root1.right=root0
        root2.left=root3
    solution=Solution()
        print("输入：",inputnum)
        print("输出：",solution.longestConsecutive2(root1))

【例151】二叉树的最长连续子序列II 难度等级★★  
3.代码实现

# 定义一个多节点的树
    class MultiTreeNode(object):
        def __init__(self, x):
                self.val = x
                self.children = [] # children 是 MultiTreeNode 的list
    class Solution:
        # 参数root为k叉树
        # 返回最长连续序列路径的长度
        def longestConsecutive3(self, root):
            max_len, _, _, = self.helper(root)
            return max_len
        def helper(self, root):
            if root is None:
                return 0, 0, 0
            max_len, up, down = 0, 0, 0
            for child in root.children:
                result = self.helper(child)
                max_len = max(max_len, result[0])
                if child.val + 1 == root.val:
                    down = max(down, result[1] + 1)
                if child.val - 1 == root.val:
                    up = max(up, result[2] + 1)
            max_len = max(down + 1 + up, max_len)
            return max_len, down, up
    #主函数
    if __name__ == '__main__':
        root=MultiTreeNode(5)
        root1=MultiTreeNode(6)
        root2=MultiTreeNode(4)
        root3=MultiTreeNode(7)
        root4=MultiTreeNode(5)
        root5=MultiTreeNode(8)
        root6=MultiTreeNode(3)
        root7=MultiTreeNode(5)
        root8=MultiTreeNode(3)
        root.children=[root1,root2]
        root1.children=[root3,root4,root5]
        root2.children=[root6,root7,root8]
        solution=Solution()
        print("输入为：5<6<7<>,5<>,8<>>,4<3<>,5<>,31<>>>")
        print("输出为：",solution.longestConsecutive3(root))

【例152】课程表 难度等级★★  
3.代码实现

from collections import deque
    class Solution:
        #参数numCourses为整数
        #参数prerequisites为先修课列表对
        #返回是否能够完成所有课程
        def canFinish(self, numCourses, prerequisites):
            edges = { i: [] for i in range(numCourses)}
            degrees = [0 for i in range(numCourses)] 
            for i, j in prerequisites:
                edges[j].append(i)
                degrees[i] += 1
            queue, count = deque([]), 0
            for i in range(numCourses):
                if degrees[i] == 0:
                    queue.append(i)
            while queue:
                node = queue.popleft()
                count += 1
                for x in edges[node]:
                    degrees[x] -= 1
                    if degrees[x] == 0:
                        queue.append(x)
            return count == numCourses
    #主函数
    if __name__=='__main__':
        list1=[[1,0]]
        n=2
        solution=Solution()
        print("输入课程数：",n)
        print("课程关系为：",list1)
        print("输出为：",solution.canFinish(n,list1))

【例153】安排课程 难度等级★★  
3.代码实现

from queue import Queue
    class Solution:
        # 参数numCourses为整数
        # 参数prerequisites为课程约束关系
        # 返回课程顺序
        def findOrder(self, numCourses, prerequisites):
            edges = { i: [] for i in range(numCourses)}
            degrees = [0 for i in range(numCourses)] 
            for i, j in prerequisites:
                edges[j].append(i)
                degrees[i] += 1
            queue = Queue(maxsize = numCourses)
            for i in range(numCourses):
                if degrees[i] == 0:
                    queue.put(i)
            order = []
            while not queue.empty():
                node = queue.get()
                order.append(node)
                for x in edges[node]:
                    degrees[x] -= 1
                    if degrees[x] == 0:
                        queue.put(x)
            if len(order) == numCourses:
                return order
            return []
    #主函数
    if __name__ =='__main__':
        n=4
        list=[[1,0],[2,0],[3,1],[3,2]]
        solution=Solution()
        print("输入课程数：",n)
        print("输入约束为：",list1)
        print("输出课程为：",solution.findOrder(n,list1))

【例 154】单词表示数字 难度等级★★  
3.代码实现

class Solution:
        """ 参数number为整数 返回字符串 """
        def convertWords(self, number):
            n1 = ["", "one", "two", "three", "four", "five",
                  "six", "seven", "eight", "nine", "ten",
                  "eleven", "twelve", "thirteen", "fourteen", "fifteen",
                  "sixteen", "seventeen", "eighteen", "nineteen"]
            n2 = ["", "ten", "twenty", "thirty", "forty",
                  "fifty", "sixty", "seventy", "eighty", "ninety"]
            n3 = ['hundred', '', 'thousand', 'million', 'billion']
            res = ''
            index = 1
            if number == 0:
                return 'zero'
            elif 0 < number < 20:
                return n1[number]
            elif 20 <= number < 100:
                return n2[number // 10] + ' ' + n1[number]
            else:
                while number != '':
                    digit = int(str(number)[-3::])
                    number = (str(number)[:-3:])
                    i = len(str(digit))
                    r = ''
                    while True:
                        if digit < 20:
                            r += n1[digit]
                            break
                        elif 20 <= digit < 100:
                            r += n2[digit // 10] + ' '
                        elif 100 <= digit < 1000:
                            r += n1[digit // 100] + ' ' + n3[0] + ' '
                        digit = digit % (10 ** (i - 1))
                        i -= 1
                    if digit != 0:
                        r += ' ' + n3[index] + ' '
                    index += 1
                    r += res
                    res = r
            return res.strip()
    if __name__=='__main__':
    	solution=Solution()
    	n=10245
    	print("输入为：",n)
    	print("输出为：",solution.convertWords(n))

【例155】最大子序列的和 难度等级★★  
3.代码实现

class Solution:
        # 参数nums为整型数组
        # 参数k为整数
        # 返回最大和
        def maxSubarray(self, nums, k):
            n = len(nums)
            if n < k:
                return 0
            result = 0
            for i in range(k):
                result += nums[i]
            sum = [0 for _ in range(n + 1)]
            min_prefix = 0
            for i in range(1, n + 1):
                sum[i] = sum[i - 1] + nums[i - 1]
                if i >= k and sum[i] - min_prefix > result:
                    result = max(result, sum[i] - min_prefix)
                if i >= k:
                    min_prefix = min(min_prefix, sum[i - k + 1])
            return result
    #主函数
    if __name__=='__main__':
        inputnum=[-2,2,-3,4,-1,2,1,-5,3]
        k=5
    solution=Solution()
        print("输入数组为：",inputnum)
        print("输入k=：",k)
        print("输出sum=：",solution.maxSubarray(inputnum,k))

【例156】移除子串 难度等级★★  
3.代码实现

class Solution:
        # 参数s为字符串
    # 参数dict为一组子字符串
    # 返回最小长度
        def minLength(self, s, dict):
            import queue
            que = queue.Queue()
            que.put(s)
            hash = set([s])
            min = len(s)
            while not que.empty():
                s = que.get()
                for sub in dict:
                    found = s.find(sub)
                    while found != -1:
                        new_s = s[:found] + s[found + len(sub):]
                        if new_s not in hash:
                            if len(new_s) < min:
                                min = len(new_s)
                            que.put(new_s)
                            hash.add(new_s)
                        found = s.find(sub, found + 1)
            return min
    #主函数
    if __name__=='__main__':
        inputwords="ccdaabcdbb"
        k=["ab","cd"]
        solution=Solution()
        print("输入字符串为：",inputwords)
        print("输入的子串为：",k)
        print("字符串长度为：",solution.minLength(inputwords,k))

【例157】数组划分 难度等级★★  
3.代码实现

class Solution:
        # 参数nums为整型数组
        # 参数low为整型
        # 参数high整型
        # 返回任意可能的解
        def partition2(self, nums, low, high):
            if len(nums) <= 1:
                return
            pl, pr = 0, len(nums) - 1
            i = 0
            while i <= pr:
                if nums[i] < low:
                    nums[pl], nums[i] = nums[i], nums[pl]
                    pl += 1
                    i += 1
                elif nums[i] > high:
                    nums[pr], nums[i] = nums[i], nums[pr]
                    pr -= 1
                else:
                    i += 1
            return nums
    #主函数
    if __name__ == '__main__':
        inputnum=[4,3,4,1,2,3,1,2]
        low=2
        high=3
        solution=Solution()
        print("输入数组为：",inputnum)
        print("输入下限为：",low)
        print("输入上限为：",high)
        print("输出结果为：",solution.partition2(inputnum,low,high))

【例158】矩形重叠 难度等级★★  
3.代码实现

# 定义一个点
    class Point:
        def __init__(self, a=0, b=0):
            self.x = a
            self.y = b
    class Solution:
        # 参数l1 第一个长方形左上角的坐标
        # 参数r1 第一个长方形右下角的坐标
        # 参数l2 第二个长方形左上角的坐标
        # 参数r2 第二个长方形右下角的坐标
        # 如果重叠返回True
        def doOverlap(self, l1, r1, l2, r2):
            if l1.x > r2.x or l2.x > r1.x:
                return False
            if l1.y < r2.y or l2.y < r1.y:
                return False
            return True
    #主函数
    if __name__ == '__main__':
        l1=Point(0,8)
        r1=Point(8,0)
        l2=Point(6,6)
        r2=Point(10,0)
        solution=Solution()
        print("输入矩形一：l1=(0,8)，r1=Point(8,0)")
        print("输入矩形二：l2=(6,6)，r2=Point(10,0)")
        print("输出的结果：",solution.doOverlap(l1,r1,l2,r2))

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

class Solution:
        # 参数s 是一个包含大小写的字符串
        # 返回能构建的最长回文串4
        def longestPalindrome(self, s):
            hash = { }
            for c in s:
                if c in hash:
                    del hash[c]
                else:
                    hash[c] = True
            remove = len(hash)
            if remove > 0:
                remove -= 1
            return len(s) - remove
    #主函数
    if __name__ == '__main__':
        inputnum="abccccdd"
        solution=Solution()
        print("输入字符串为：",inputnum)    
        print("输出回文长度：",solution.longestPalindrome(inputnum))

【例160】最大子树 难度等级★★  
3.代码实现

# 定义一个多节点的树
    class TreeNode(object):
        def __init__(self, x):
                self.val = x
                self.left = None
                self.right=None
    class Solution:
        # 参数root为二叉树根
        # 返回最大节点值
        import sys
        maximum_weight = 0
        result = None
        def findSubtree(self, root):
            self.helper(root)
            return self.result.val
        def helper(self, root):
            if root is None:
                return 0
            left_weight = self.helper(root.left)
            right_weight = self.helper(root.right)
            
            if left_weight + right_weight + root.val >= self.maximum_weight or self.result is None:
                self.maximum_weight = left_weight + right_weight + root.val
                self.result = root
            return left_weight + right_weight + root.val
    #主函数
    if __name__ == '__main__':
        root = TreeNode(1)
        root1 = TreeNode(-5)
        root2 = TreeNode(2)
        root3 = TreeNode(0)
        root4 = TreeNode(3)
        root5 = TreeNode(-4)
        root6 = TreeNode(-5)
        root.left=root1
        root.right=root2
        root1.left=root3
        root1.right=root4
        root2.left=root5
        root2.right=root6
        solution = Solution()
        print("输入为：[1,-5 2,0 3 -4 -5]")
        print("输出为：",solution.findSubtree(root))

【例161】最小生成树 难度等级★★  
3.代码实现

#定义Connection
    class Connection:
        def __init__(self, city1, city2, cost):
            self.city1, self.city2, self.cost = city1, city2, cost
    def comp(a, b):
        if a.cost != b.cost:
            return a.cost - b.cost
        if a.city1 != b.city1:
            if a.city1 < b.city1:
                return -1
            else:
                return 1
        if a.city2 == b.city2:
            return 0
        elif a.city2 < b.city2:
            return -1
        else:
            return 1
    class Solution:
        # @param {Connection[]} connections 城市和花费的List
        # @return {Connection[]} 返回这个type
        def lowestCost(self, connections):
            # Write your code here
            cmp=0
          # connections.sort()
            hash = { }
            n = 0
            for connection in connections:
                if connection.city1 not in hash:
                    n += 1
                    hash[connection.city1] = n
                if connection.city2 not in hash:
                    n += 1
                    hash[connection.city2] = n
            father = [0 for _ in range(n + 1)] 
            results = []
            for connection in connections:
                num1 = hash[connection.city1]
                num2 = hash[connection.city2]
                root1 = self.find(num1, father)
                root2 = self.find(num2, father)
                if root1 != root2:
                    father[root1] = root2
                    results.append(connection)
            if len(results)!= n - 1:
                return []
            return results
        def find(self, num, father):
            if father[num] == 0:
                return num
            father[num] = self.find(father[num], father)
            return father[num]
    #主函数
    if __name__ == '__main__':
        conn=Connection("Acity","Bcity",1)
        conn1=Connection("Acity","Ccity",2)
        conn2=Connection("Bcity","Ccity",3)
        connections=[conn,conn1,conn2]
        solution = Solution()
        ci01=solution.lowestCost(connections)[0].city1
        ci02=solution.lowestCost(connections)[0].city2
        co0=solution.lowestCost(connections)[0].cost
        ci11=solution.lowestCost(connections)[1].city1
        ci12=solution.lowestCost(connections)[1].city2
        ci1=solution.lowestCost(connections)[1].cost
        print([[ci01,ci02,co0],[ci11,ci12,ci1]])

【例162】骑士的最短路径 难度等级★★  
3.代码实现

import sys
    class Solution:
        # 参数grid是棋盘
        # 返回最短路径长度
        def shortestPath2(self, grid):
            n = len(grid)
            if n == 0:
                return -1
            m = len(grid[0])
            if m == 0:
                return -1
            f = [ [sys.maxsize for j in range(m)] for _ in range(n)]
            f[0][0] = 0
            for j in range(m):
                for i in range(n):
                    if not grid[i][j]:
                        if i >= 1 and j >= 2 and f[i - 1][j - 2] != sys.maxsize:
                            f[i][j] = min(f[i][j], f[i - 1][j - 2] + 1)
                        if i + 1 < n and j >= 2 and f[i + 1][j - 2] != sys.maxsize:
                            f[i][j] = min(f[i][j], f[i + 1][j - 2] + 1)
                        if i >= 2 and j >= 1 and f[i - 2][j - 1] != sys.maxsize:
                            f[i][j] = min(f[i][j], f[i - 2][j - 1] + 1)
                        if i + 2 < n and j >= 1 and f[i + 2][j - 1] != sys.maxsize:
                            f[i][j] = min(f[i][j], f[i + 2][j - 1] + 1)
            if f[n - 1][m - 1] == sys.maxsize:
                return -1
            return f[n - 1][m - 1]
    #主函数
    if __name__ == '__main__':
        inputnum=[[0,0,0,0],[0,0,0,0],[0,0,0,0]]
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.shortestPath2(inputnum))

【例163】最大矩阵 难度等级★★  
3.代码实现

class Solution:
        #参数matrix为矩阵
        #@返回整数
        def maxSquare2(self, matrix):
            if not matrix or not matrix[0]:
                return 0
            n, m = len(matrix), len(matrix[0])
            f = [[0] * m, [0] * m]
            up = [[0] * m, [0] * m]
            for i in range(m):
                f[0][i] = matrix[0][i]
                up[0][i] = 1 - matrix[0][i]
            edge = max(matrix[0])
            for i in range(1, n):
                f[i % 2][0] = matrix[i][0]
                up[i % 2][0] = 0 if matrix[i][0] else up[(i - 1) % 2][0] + 1
                left = 1 - matrix[i][0]
                for j in range(1, m):
                    if matrix[i][j]:
                        f[i%2][j] =min(f[(i-1)%2][j-1],left,up[(i-1)%2][j])+1
                        up[i % 2][j] = 0
                        left = 0
                    else:
                        f[i % 2][j] = 0
                        up[i % 2][j] = up[(i - 1) % 2][j] + 1
                        left += 1
                edge = max(edge, max(f[i % 2]))
            return edge * edge
    #主函数
    if __name__ == '__main__':
        inputnum=[[1,0,1,0,0],[1,0,0,1,0],[1,1,0,0,1],[1,0,0,1,0]]
        solution = Solution()
        print("输入为：", inputnum)
        print("输出为：",solution.maxSquare2(inputnum))

【例164】二叉树的最大节点 难度等级★★  
3.代码实现

class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        # 参数root为二叉树根
        # 返回最大节点值
        def maxNode(self, root):
            if root is None:
                return root
            left = self.maxNode(root.left)
            right = self.maxNode(root.right)
            return self.max(root, self.max(left, right))
        def max(self, a, b):
            if a is None:
                return b
            if b is None:
                return a
            if a.val > b.val:
                return a
            return b
    #主函数
    if __name__ == '__main__':
        root = TreeNode(1)
        root1 = TreeNode(-5)
        root2 = TreeNode(3)
        root3 = TreeNode(1)
        root4 = TreeNode(2)
        root5 = TreeNode(-4)
        root6 = TreeNode(-5)
        root.left = root1
        root.right= root2
        root1.left = root3
        root1.right= root4
        root2.left = root5
        root2.right= root6
        solution = Solution()
        print("输入为：[1,-5 3,1 2 -4 -5]")
        print("输出为：",solution.maxNode(root).val)

【例165】寻找重复的数 难度等级★★  
3.代码实现

class Solution:
        #参数nums为整型数组
        #返回重复的数
        def findDuplicate(self, nums):
            start, end = 1, len(nums) - 1
            while start + 1 < end:
                mid = (start + end) // 2
                if self.smaller_than_or_equal_to(nums, mid) > mid:
                    end = mid
                else:
                    start = mid
            if self.smaller_than_or_equal_to(nums, start) > start:
                return start
            return end
        def smaller_than_or_equal_to(self, nums, val):
            count = 0
            for num in nums:
                if num <= val:
                    count += 1
            return count
    #主函数
    if __name__ == '__main__':
        inputnum= [5,5,4,3,2,1]
        solution = Solution()
        print("输入为：",inputnum)
    print("输出为：",solution.findDuplicate(inputnum))

【例166】拼字游戏 难度等级★★  
3.代码实现

import collections
    class TrieNode(object):
        def __init__(self, value=0):
            self.value = value
            self.isWord = False
            self.children = collections.OrderedDict()
        @classmethod
        def insert(cls, root, word):
            p = root
            for c in word:
                child = p.children.get(c)
                if not child:
                    child = TrieNode(c)
                    p.children[c] = child
                p = child
            p.isWord = True
    class Solution:
        # 参数board为字符列表
        # 参数words为字符串列表
        # 返回整数
        def boggleGame(self, board, words):
            self.board = board
            self.words = words
            self.m = len(board)
            self.n = len(board[0])
            self.results = []
            self.temp = []
            self.visited = [[False for _ in range(self.n)] for _ in range(self.m)]
            self.root = TrieNode()
            for word in words:
                TrieNode.insert(self.root, word)
            self.dfs(0, 0, self.root)
            return len(self.results)
        def dfs(self, x, y, root):
            for i in range(x, self.m):
                for j in range(y, self.n):
                    paths = []
                    temp = []
                    self.getAllPaths(i, j, paths, temp, root)
                    for path in paths:
                        word = ''
                        for px, py in path:
                            word += self.board[px][py]
                            self.visited[px][py] = True
                        self.temp.append(word)
                        if len(self.temp) > len(self.results):
                            self.results = self.temp[:]
                        self.dfs(i, j, root)
                        self.temp.pop()
                        for px, py in path:
                            self.visited[px][py] = False
                y = 0
        def getAllPaths(self, i, j, paths, temp, root):
            if i < 0 or i >= self.m or j < 0 or j >= self.n or \
                self.board[i][j] not in root.children or \
                self.visited[i][j] == True:
                return
            root = root.children[self.board[i][j]]
            if root.isWord:
                temp.append((i,j))
                paths.append(temp[:])
                temp.pop()
                return
            self.visited[i][j] = True
            deltas = [(0,1), (0,-1), (1,0), (-1, 0)]
            for dx, dy in deltas:
                newx = i + dx
                newy = j + dy
                temp.append((i,j))
                self.getAllPaths(newx, newy, paths, temp, root)
                temp.pop()
            self.visited[i][j] = False
    #主函数
    if __name__ == '__main__':
        inputnum= [['a', 'b', 'c'],
    ['d', 'e', 'f'],
    ['g', 'h', 'i']]
        dictw = ["abc", "cfi", "beh", "defi", "gh"]
        solution = Solution()
        print("输入字符为：",inputnum)
        print("输入字典为：",dictw)
        print("输出个数为：",solution.boggleGame(inputnum,dictw))

【例167】132模式识别 难度等级★★  
3.代码实现

class Solution:
        # 参数nums为整数列表
        # 返回True或者False
        def find132pattern(self, nums):
            stk = [-sys.maxsize]
            for i in range(len(nums)-1, -1, -1):
                if nums[i] < stk[-1]:
                    return True
                else:
                    while stk and nums[i] > stk[-1]:
                        v = stk.pop()
                    stk.append(nums[i])
                    stk.append(v)
            return False
    #主函数
    if __name__ == '__main__':
        inputnum=[1, 2, 3, 4]
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.find132pattern(inputnum))

【例168】检查缩写字 难度等级★★  
3.代码实现

class Solution:
        #参数word为字符串
        #参数abbr为字符串
        #返回布尔类型
        def validWordAbbreviation(self, word, abbr):
            i = 0
            j = 0
            while i < len(word) and j < len(abbr):
                if word[i] == abbr[j]:
                    i += 1
                    j += 1
                elif abbr[j].isdigit() and abbr[j] != '0':
                    start = j
                    while j < len(abbr) and abbr[j].isdigit():
                        j += 1
                    i += int(abbr[start : j])
                else:
                    return False
            return i == len(word) and j == len(abbr)
    #主函数
    if __name__ == '__main__':
        s = "internationalization"
        abbr = "i12iz4n"
        solution = Solution()
        print("输入为：",s)
        print("缩写为：",abbr)
        print("输出为：",solution.validWordAbbreviation(s,abbr))

【例169】一次编辑距离 难度等级★★  
3.代码实现

class Solution:
        # 参数s为字符串
        # 参数t为字符串
        # 返回布尔类型
        def isOneEditDistance(self, s, t):
            m = len(s)
            n = len(t)
            if abs(m - n) > 1:
                return False
            if m > n:
                return self.isOneEditDistance(t, s)
            for i in range(m):
                if s[i] != t[i]:
                    if m == n:
                        return s[i + 1:] == t[i + 1:]
                    return s[i:] == t[i + 1:]
            return m != n
    #主函数
    if __name__ == '__main__':
         s = "aDb"
         t = "adb"
         solution = Solution()
         print("输入字符串s：",s)
         print("输入字符串t：",t)
         print("输出为：",solution.isOneEditDistance(s,t))

【例170】数据流滑动窗口平均值 难度等级★★  
3.代码实现

from collections import deque
    class MovingAverage(object):
        def __init__(self, size):
            self.queue = deque([])
            self.size = size
            self.sum = 0.0
        def next(self, val):
            if len(self.queue) == self.size:
                self.sum -= self.queue.popleft()
            self.sum += val
            self.queue.append(val)
            return self.sum / len(self.queue)
    if __name__ == '__main__':
        solution = MovingAverage(3)
        print("输入数据流：1,10,3,5")
        print("输出流动窗1：",solution.next(1))
        print("输出流动窗2：",solution.next(10))
        print("输出流动窗3：",solution.next(3))
        print("输出流动窗4：",solution.next(5))

【例171】最长绝对文件路径 难度等级★★  
3.代码实现

import re
    import collections
    class Solution:
        #参数input为抽象的文件系统
        #返回最长文件的绝度路径长度
        def lengthLongestPath(self, input):
            dict = collections.defaultdict(lambda: "")
            lines = input.split("\n")
            n = len(lines)
            result = 0
            for i in range(n):
                count = lines[i].count("\t")
                lines[i] = dict[count - 1] + re.sub("\\t+","/", lines[i])
                if "." in lines[i]:
                    result = max(result, len(lines[i]))
                dict[count] = lines[i]
            return result
    #主函数
    if __name__ == '__main__':
    inputwords="dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
        solution=Solution()
        print("输入为：",inputwords)
        print("输出为：",solution.lengthLongestPath(inputwords))

【例172】识别名人 难度等级★★  
3.代码实现

#假定0认识1,1不认识0
    class Celebrity: 
        def knows(a,b):
            if a==0 and b==1 :
                return True
            if a==1 and b==0 :
                return False
    class Solution:
        # 参数n为整数
        # 返回整数
        def findCelebrity(self, n):
            celeb = 0 
            for i in range(1, n):
                if Celebrity.knows(celeb, i):
                    celeb = i
            for i in range(n):
                if celeb != i and Celebrity.knows(celeb, i):
                    return -1
                if celeb != i and not Celebrity.knows(i, celeb):
                    return -1
            return celeb
    #主函数
    if __name__ == '__main__':
        n=2
        solution=Solution()
        print("输入为：",n)
        print("输出为：",solution.findCelebrity(n))

【例173】第一个独特字符位置 难度等级★★  
3.代码实现

class Solution:
        # 参数s为字符串
        # 返回整数
        def firstUniqChar(self, s):
            alp = { }
            for c in s:
                if c not in alp:
                    alp[c] = 1
                else:
                    alp[c] += 1
            index = 0
            for c in s:
                if alp[c] == 1:
                    return index
                index += 1
            return -1
    #主函数
    if __name__ == '__main__':
        s = "lintcode"
        solution=Solution()
        print("输入为：",s)
        print("输出为：",solution.firstUniqChar(s))

【例174】子串字谜 难度等级★★  
3.代码实现

class Solution:
        # 参数s为字符串
        # 参数p为字符串
        # 返回索引列表
        def findAnagrams(self, s, p):
            ans = []
            sum = [0 for x in range(0,30)]
            plength = len(p)
            slength = len(s)
            for i in range(plength):
                sum[ord(p[i]) - ord('a')] += 1
            start = 0
            end = 0
            matched = 0
            while end < slength:
                if sum[ord(s[end]) - ord('a')] >= 1:
                    matched += 1
                sum[ord(s[end]) - ord('a')] -= 1
                end += 1
                if matched == plength:
                    ans.append(start)
                if end - start == plength:
                    if sum[ord(s[start]) - ord('a')] >= 0:
                        matched -= 1
                    sum[ord(s[start]) - ord('a')] += 1
                    start += 1
            return ans
    #主函数
    if __name__ == '__main__':
        s = "cbaebabacd"
        p = "abc"
        solution = Solution()
        print("输入字符串：",s)
        print("输入子串为：",p)
        print("输出索引为：",solution.findAnagrams(s,p))

【例175】单词缩写集 难度等级★★  
3.代码实现

class ValidWordAbbr:
        def __init__(self, dictionary):
            self.map = { }
            for word in dictionary:
                abbr = self.word_to_abbr(word)
                if abbr not in self.map:
                    self.map[abbr] = set() 
                self.map[abbr].add(word)
        def word_to_abbr(self, word):
            if len(word) <= 1:
                return word
            return word[0] + str(len(word[1:-1])) + word[-1]
        def isUnique(self, word):
            abbr = self.word_to_abbr(word)
            if abbr not in self.map:
                return True
            for word_in_dict in self.map[abbr]:
                if word != word_in_dict:
                    return False
            return True
    #主函数
    if __name__ == '__main__':
        dic=[ "deer", "door", "cake", "card" ]
        solution = ValidWordAbbr(dic)
        print("输入字典为：",dic)
        print("输入单词为： dear")
        print("输出结果为：",solution.isUnique("dear"))
        print("输入单词为： cart")
        print("输出结果为：",solution.isUnique("cart"))

【例176】二叉树翻转 难度等级★★  
3.代码实现

class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    class Solution:
        def upsideDownBinaryTree(self, root):
            if root is None:
                return None
            return self.dfs(root)
        def dfs(self, root):
            if root.left is None:
                return root
            newRoot = self.dfs(root.left)
            root.left.right = root
            root.left.left = root.right
            root.left = None
            root.right = None
            return newRoot
    #主函数
    if __name__ == '__main__':
        root1 = TreeNode(1)
        root2 = TreeNode(2)
        root3 = TreeNode(3)
        root4 = TreeNode(4)
        root5 = TreeNode(5)
        inputnum=[1,2,3,4,5,"#","#"]
        root1.left = root2
        root1.right=root3
        root2.left=root4
        root2.right=root5
        solution = Solution()
        a=solution.upsideDownBinaryTree(root1)
        a0=a.val
        a1=a.left.val
        a2=a.right.val
        a3='#'
        a4='#'
        a5=a.right.left.val
        a6=a.right.right.val
        aa=[a0,a1,a2,a3,a4,a5,a6]
        print("输入为",inputnum)
        print("输出为",aa)

【例177】 二叉树垂直遍历 难度等级★★  
3.代码实现

import collections
    import queue as Queue
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    class Solution:
        # 参数root为二叉树根
        # 返回整型列表
        def verticalOrder(self, root):
            results = collections.defaultdict(list)
            queue = Queue.Queue()
            queue.put((root, 0))
            while not queue.empty():
                node, x = queue.get()
                if node:
                    results[x].append(node.val)
                    queue.put((node.left, x - 1))
                    queue.put((node.right, x + 1))
            return [results[i] for i in sorted(results)]
    #主函数
    if __name__ == '__main__':
        root=TreeNode(3)
        root1=TreeNode(9)
        root2=TreeNode(20)
        root3=TreeNode(15)
        root4=TreeNode(7)
        root.left=root1
        root.right=root2
        root2.left=root3
        root2.right=root4
        solution = Solution()
        a=solution.verticalOrder(root)
        print("输入为： [3,9,20,#,#,15,7]")
        print("输出为：",a)

【例178】因式分解 难度等级★★  
3.代码实现

class Solution:
        #参数n为整数
        #返回组合列表
        def getFactors(self, n):
            result = []
            self.helper(result, [], n, 2);
            return result
        def helper(self, result, item, n, start):
            if n <= 1:
                if len(item) > 1:
                    result.append(item[:])
                return
            import math
            for i in range(start, int(math.sqrt(n)) + 1):
                if n % i == 0:
                    item.append(i)
                    self.helper(result, item, n / i, i)
                    item.pop()
            if n >= start:
                item.append(n)
                self.helper(result, item, 1, n)
                item.pop()
    #主函数
    if __name__ == '__main__':
        inputnum=8
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.getFactors(inputnum))

【例179】Insert Delete GetRandom O(1) 难度等级★★  
3.代码实现

import random
    class RandomizedSet(object):
        def __init__(self):
            self.nums, self.pos = [], { }
        # 参数val为整数
        # 返回布尔类型
        def insert(self, val):
            if val not in self.pos:
                self.nums.append(val)
                self.pos[val] = len(self.nums) - 1
                return True
            return False
        # 参数val为整数
        # 返回布尔类型
        def remove(self, val):
            if val in self.pos:
                idx, last = self.pos[val], self.nums[-1]
                self.nums[idx], self.pos[last] = last, idx
                self.nums.pop()
                del self.pos[val]
                return True
            return False
        def getRandom(self):
            return self.nums[random.randint(0, len(self.nums) - 1)]
    #主函数
    if __name__ == '__main__':
        solution=RandomizedSet()
        print("插入一个元素：1")
        print("输出为：",solution.insert(1))
        print("移除一个元素：2")
        print("输出为：",solution.remove(2))
        print("插入一个元素：2")
        print("输出为：",solution.insert(2))
        print("获取随机元素：1")
        print("输出为：",solution.getRandom())
        print("移除一个元素：1")
        print("输出为：",solution.remove(1))
        print("插入一个元素：2")
        print("输出为：",solution.insert(2))

【例180】编码和解码字符串 难度等级★★  
3.代码实现

class Solution:
        #参数strs为字符串列表
        #返回编码后的字符串列表
        # " " -> ": " 分隔不同单词
        # ":" -> "::" 区分":"
        def encode(self, strs):
            encoded = []
            for string in strs:
                for char in string:
                    if char == ":":
                        encoded.append("::")
                    else:
                        encoded.append(char)
                encoded.append(": ")
            return "".join(encoded)
        #参数str为字符串
        #返回解码字符串列表
        def decode(self, str):
            res = []
            idx = 0
            length = len(str)
            tmp_str = []
            while idx < length - 1:
                if str[idx] == ":":
                    if str[idx + 1] == ":":
                        tmp_str.append(":")
                        idx += 2
                    elif str[idx + 1] == " ":
                        res.append("".join(tmp_str))
                        tmp_str = []
                        idx += 2
                else:
                    tmp_str.append(str[idx])
                    idx += 1
            return res
    #主函数
    if __name__ == '__main__':
        inputwords=["lint","code","love","you"]
        solution=Solution()
        print("输入为：",inputwords)
        print("编码为：",solution.encode(inputwords))
        print("解码为：",solution.decode(solution.encode(inputwords)))

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

def guess(mid):
        if mid>4:
            return -1
        if mid <4:
            return 1
        if mid==4:
            return 0
    class Solution:
        #参数n为整数
        #返回所猜的数
        def guessNumber(self, n):
            l = 1
            r = n
            while l <= r:
                mid = abs(l + (r - l) / 2)
                res = guess(mid)
                if res == 0:
                    return mid
                if res == -1:
                    r = mid - 1
                if res == 1: 
                    l = mid + 1
            return int(mid)
    #主函数
    if __name__ == '__main__':
        inputnum=10
        selectedNumber=4
        solution=Solution()
        print("输入总数为：",inputnum)
        print("所选的数字：",selectedNumber)
        print("所猜的数字：",solution.guessNumber(inputnum))

【例182】数1的个数 难度等级★★  
3.代码实现

class Solution:
        #参数num为非负整数
        #返回数组
        def countBits(self, num):
            f = [0] * (num + 1)
            for i in range(1, num+1):
                f[i] = f[i & i-1] + 1
            return f
    #主函数
    if __name__ == '__main__':
        inputnum=5
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.countBits(inputnum))

【例183】平面范围求和 -不可变矩阵 难度等级★★  
3.代码实现

class NumMatrix(object):
        #参数matrix为矩阵
        def __init__(self, matrix):
            if len(matrix) == 0 or len(matrix[0]) == 0:
                return 
            n = len(matrix)
            m = len(matrix[0])
            self.dp  = [[0] * (m + 1) for _ in range(n + 1)]
            for r in range(n):
                for c in range(m):
                    self.dp[r+ 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + \
                        matrix[r][c] - self.dp[r][c]
        # 参数row1为整数
        # 参数col1为整数
        # 参数row2为整数
        # 参数col2为整数
        # 返回整数
        def sumRegion(self, row1, col1, row2, col2):
            return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - \
                self.dp[row2 + 1][col1] + self.dp[row1][col1]
    #主函数
    if __name__ == '__main__':
        inputnum=[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
        solution = NumMatrix(inputnum)
        print("输入矩阵为：",inputnum)
        print("区域1的和：",solution.sumRegion(2, 1, 4, 3))
        print("区域2的和：",solution.sumRegion(1, 1, 2, 2))
        print("区域3的和：",solution.sumRegion(1, 2, 2, 4))

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

class Solution:
        # 参数n为整数
        # 返回整数
        def getMoneyAmount(self, n):
            dp = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
            for len in range(2, n + 1):
                for start in range(1, n - len + 2):
                    import sys
                    temp = sys.maxsize
                    for k in range(start + int((len - 1) / 2), start + int(len - 1)):
                        left, right = dp[start][k - 1], dp[k + 1][start + len - 1]
                        temp = min(k + max(left, right), temp)
                        if left > right:
                            break
                    dp[start][start + len - 1] = temp
            return dp[1][n]
    #主函数
    if __name__ == '__main__':
        inputnum=10
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.getMoneyAmount(inputnum))

【例185】最长的回文序列 难度等级★★  
3.代码实现

class Solution:
        # 参数s为字符串
        # 返回整数
        def longestPalindromeSubseq(self, s):
            length = len(s)
            if length == 0:
                return 0
            dp = [[0 for _ in range(length)] for __ in range(length)]
            for i in range(length - 1, -1, -1):
                dp[i][i] = 1
                for j in range(i + 1, length):
                    if s[i] == s[j]:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            return dp[0][length - 1]
    #主函数
    if __name__ == '__main__':
        inputnum="bbbab"
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.longestPalindromeSubseq(inputnum))

【例186】1和0 难度等级★★  
3.代码实现

class Solution:
        #参数strs为字符串数组
        #参数m为整数
        #参数n为整数
        #返回整数
        def findMaxForm(self, strs, m, n):
            dp = [[0] * (m + 1) for _ in range(n + 1)]
            for s in strs:
                zero = 0
                one = 0
                for ch in s:
                    if ch == "1":
                        one += 1
                    else:
                        zero += 1
                for i in range(n,one - 1,-1):
                    for j in range(m,zero - 1,-1):
                        if dp[i - one][j - zero] + 1 > dp[i][j]:
                            dp[i][j] = dp[i - one][j - zero] + 1
            return dp[-1][-1]
    #主函数
    if __name__ == '__main__':
        inputnum=["10", "0001", "111001", "1", "0"]
        m=5
        n=3
        solution = Solution()
        print("输入为：",inputnum)
        print("输入m ：",m)
        print("输入n ：",n)
        print("输出 ：",solution.findMaxForm(inputnum,m,n))

【例187】预测能否胜利 难度等级★★  
3.代码实现

class Solution:
        #参数nums为整数数组
        #返回布尔类型
        def PredictTheWinner(self, nums):
            if len(nums) & 1 == 0: return True
            dp = [[0] * len(nums) for _ in range(len(nums))]
            for i, v in enumerate(nums):
                dp[i][i] = v
            for i in range(1, len(nums)):
                for j in range(len(nums) - i):
                    dp[j][j + i] = max(nums[j] - dp[j + 1][j + i], nums[j + i] - dp[j][j + i - 1])
            return dp[0][-1] > 0
    #主函数
    if __name__ == '__main__':
        inputnum=[1, 5, 2]
        solution = Solution()
        print("输入为：",inputnum)
        print("输出为：",solution.PredictTheWinner(inputnum))

【例188】循环单词 难度等级★★  
3.代码实现

class Solution:
        #参数words为单词列表
        #返回整数
        def countRotateWords(self, words):
            dict1 = set()
            for w in words:
                s = w + w
                for i in range(0, len(w)):
                    tmp = s[i : i +len(w)]
                    if tmp in dict1:
                        dict1.remove(tmp)
                dict1.add(w)
            return len(dict1)
    #主函数
    if __name__ == '__main__':
        dict1 = ["picture", "turepic", "icturep", "word", "ordw", "long"]
        solution = Solution()
        print("输入为：",dict1)
        print("输出为：",solution.countRotateWords(dict1))

【例189】最大子数组之和为k 难度等级★★  
3.代码实现

class Solution:
        #参数nums为数组
        #参数k为整数
        #返回整数
        def maxSubArrayLen(self, nums, k):
            m = { }
            ans = 0
            m[k] = 0
            n = len(nums)
            sum = [0 for i in range(n + 1)]
            for i in range(1, n + 1):
                sum[i] = sum[i - 1] + nums[i - 1]
                if sum[i] in m:
                    ans = max(ans, i - m[sum[i]])
                if sum[i] + k not in m:
                    m[sum[i] + k] = i
            return ans
    if __name__ == '__main__':
        num = [-2, 7, 3, -4, 1]
        k = 5
        solution = Solution()
        print("输入数组为：",num)
        print("输入目标值：",k)
        print("输出为：",solution.maxSubArrayLen(num, k))

【例190】等差切片 难度等级★★  
3.代码实现

class Solution(object):
        def numberOfArithmeticSlices(self, A):
            #参数A为列表
            #返回整数
            size = len(A)
            if size < 3: return 0
            ans = cnt = 0
            delta = A[1] - A[0]
            for x in range(2, size):
                if A[x] - A[x - 1] == delta:
                    cnt += 1
                    ans += cnt
                else:
                    delta = A[x] - A[x - 1]
                    cnt = 0
            return ans
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[1, 2, 3, 4]
        print("输入为：",inputnum)
        print("输出为：",solution.numberOfArithmeticSlices(inputnum))

【例191】2D战舰 难度等级★★  
3.代码实现

class Solution(object):
        def countBattleships(self, board):
            #参数board为列表
            #返回整数
            len1 = len(board)
            if len1 == 0:
                return 0;
            len2 = len(board[0])
            ans = 0
            for i in range(0, len1):
                for j in range(0,len2):
                    if board[i][j] == 'X' and ( i == 0 or board[i-1][j] == '.' )and (j == 0 or board[i][j-1] == '.'):
                        ans += 1
            return ans
    if __name__ == '__main__':
        solution=Solution()
        inputnum=["X..X","...X","...X"]
        print("输入为：",inputnum)
        print("输出为：",solution.countBattleships(inputnum))

【例192】连续数组 难度等级★★  
3.代码实现

class Solution:
        #参数nums为数组
        #返回整数
        def findMaxLength(self, nums):
            index_sum = { }
            cur_sum = 0
            ans = 0
            for i in range(len(nums)):
                if nums[i] == 0: cur_sum -= 1
                else: cur_sum += 1
                if cur_sum == 0: ans = i+1
                elif cur_sum in index_sum: ans = max(ans, i-index_sum[cur_sum])
                if cur_sum not in index_sum: index_sum[cur_sum] = i
            return ans
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[1,0]
        print("输入为：",inputnum)
        print("输出为：",solution.findMaxLength(inputnum))

【例193】带有冷却时间的买卖股票最佳时间 难度等级★★  
3.代码实现

class Solution:
        #参数prices为整数列表
        #返回整数
        def maxProfit(self, prices):
            if not prices:
                return 0
            buy, sell, cooldown = [0 for _ in range(len(prices))], [0 for _ in range(len(prices))], [0 for _ in range(len(prices))]
            buy[0] = -prices[0]
            for i in range(1, len(prices)):
                cooldown[i] = sell[i - 1]
                sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
                buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i])
            return max(sell[-1], cooldown[-1])
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[1,2,3,0,2]
        print("输入为：",inputnum)
        print("输出为：",solution.maxProfit(inputnum))

4.运行结果  
输入为：\[1, 2, 3, 0, 2\]  
输出为：3  
【例194】小行星的碰撞 难度等级★★  
3.代码实现

class Solution:
        #参数asteroids为整数数组
        #返回整数数组
        def asteroidCollision(self, asteroids):
            ans, i, n= [], 0, len(asteroids)
            while i < n:
                if asteroids[i] > 0:
                    ans.append(asteroids[i])
                elif len(ans) == 0 or ans[-1] < 0:
                    ans.append(asteroids[i])
                elif ans[-1] <= -asteroids[i]:
                    if ans[-1] < -asteroids[i]:
                        i -= 1
                    ans.pop()
                i += 1
            return ans
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[5,10,-5]
        print("输入为：",inputnum)
        print("输出入为：",solution.asteroidCollision(inputnum))

4.运行结果  
输入为：\[5, 10, -5\]  
输出入为：\[5, 10\]  
【例195】扩展弹性词 难度等级★★  
3.代码实现

class Solution:
        #参数S为字符串
        #参数words为字符串列表
        #返回整数
        def expressiveWords(self, S, words):
            SList = self.countGroup(S)
            n = len(SList)
            ans = 0
            for word in words:
                wordList = self.countGroup(word)
                if n != len(wordList):
                    continue
                ok = 1
                for i in range(n):
                    if not self.canExtend(wordList[i], SList[i]):
                        ok = 0
                        break
                ans += ok
            return ans
        def countGroup(self, s):
            n = len(s)
            cnt = 1
            ret = []
            for i in range(1, n):
                if s[i] == s[i - 1]:
                    cnt += 1
                else:
                    ret.append((s[i - 1], cnt))
                    cnt = 1
            ret.append((s[-1], cnt))
            return ret
        def canExtend(self, From, To):
            return From[0] == To[0] and \
                   (From[1] == To[1] or (From[1] < To[1] and To[1] >= 3))
    if __name__ == '__main__':
        solution=Solution()
        inputnum1="heeellooo"
        inputnum2=["hello", "hi", "helo"]
        print("输入字符串1为：",inputnum1)
        print("输入字符串2为：",inputnum2)
        print("输出为：",solution.expressiveWords(inputnum1,inputnum2))

【例196】找到最终的安全状态 难度等级★★  
3.代码实现

class Solution:
        #参数graph为整数数组
        #返回整数
        def eventualSafeNodes(self, graph):
            def dfs(graph, i, visited):
                for j in graph[i]:
                    if j in visited:
                        return False
                    if j in ans:
                        continue
                    visited.add(j)
                    if not dfs(graph, j, visited):
                        return False
                    visited.remove(j)
                ans.add(i)
                return True
            ans = set()
            for i in range(len(graph)):
                visited = set([i])
                dfs(graph, i, visited)
            return sorted(list(ans))
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[[1,2],[2,3],[5],[0],[5],[],[]]
        print("输入为：",inputnum)
        print("输出为：",solution.eventualSafeNodes(inputnum))

【例197】使序列递增的最小交换次数 难度等级★★  
3.代码实现

class Solution:
        def minSwap(self, A, B):
            if len(A) == 0 or len(A) != len(B):
                return 0
            non_swapped, swapped = [0] * len(A), [1] + [0] * (len(A) - 1)
            for i in range(1, len(A)):
                swps, no_swps = set(), set()
                if A[i - 1] < A[i] and B[i - 1] < B[i]:
                    swps.add(swapped[i - 1] + 1)
                    no_swps.add(non_swapped[i - 1])
                if B[i - 1] < A[i] and A[i - 1] < B[i]:
                    swps.add(non_swapped[i - 1] + 1)
                    no_swps.add(swapped[i - 1])
                swapped[i], non_swapped[i] = min(swps), min(no_swps)
            return min(swapped[-1], non_swapped[-1])
    if __name__ == '__main__':
        solution=Solution()
        inputnum1=[1,3,5,4]
        inputnum2=[1,2,3,7]
        print("输入1为：",inputnum1)
        print("输入2为：",inputnum2)
        print("输出为：",solution.minSwap(inputnum1,inputnum2))

【例198】所有可能的路径 难度等级★★  
3.代码实现

class Solution:
        #参数graph为数组
        #返回数组
        def allPathsSourceTarget(self, graph):
            N = len(graph)
            res = []
            def dfs(N, graph, start, res, path):
                if start == N-1:
                    res.append(path)
                else:
                    for node in graph[start]:
                        dfs(N, graph, node, res, path + [node])
            dfs(N, graph, 0, res, [0])
            return (res)
    if __name__ == '__main__':
        solution=Solution()
        inputnum=[[1,2],[3],[3],[]]
        print("输入为：",inputnum)
        print("输出为：",solution.allPathsSourceTarget(inputnum))

【例199】合法的井字棋状态 难度等级★★  
3.代码实现

class Solution:
        def validTicTacToe(self, board):
            #参数board为列表
            #返回布尔类型
            num_X, num_O = 0, 0
            for i in range(0, 3):
                for j in range(0, 3):
                    if board[i][j] == 'X':
                        num_X += 1
                    if board[i][j] == 'O':
                        num_O += 1
            if not (num_X == num_O or num_X == num_O + 1):
                return False
            for i in range(3):
                if board[i][0] == board[i][1] == board[i][2]:
                    if board[i][0] == 'X':
                        return num_X == num_O + 1
                    if board[i][0] == 'O':
                        return num_X == num_O
            for j in range(3):
                if board[0][j] == board[1][j] == board[2][j]:
                    if board[0][j] == 'X':
                        return num_X == num_O + 1
                    if board[0][j] == 'O':
                        return num_X == num_O
            if board[0][0] == board[1][1] == board[2][2]:
                if board[0][0] == 'X':
                    return num_X == num_O + 1
                if board[0][0] == 'O':
                    return num_X == num_O
            if board[0][2] == board[1][1] == board[2][0]:
                if board[2][0] == 'X':
                    return num_X == num_O + 1
                if board[2][0] == 'O':
                    return num_X == num_O
            return True
    if __name__ == '__main__':
        solution=Solution()
        inputnum=["O ", " ", " "]
        print("输入为：",inputnum)
        print("输出为：",solution.validTicTacToe(inputnum))

【例200】满足要求的子串个数 难度等级★★  
3.代码实现

class Solution:
        #参数S为字符串
        #参数words为单词字典
        #返回子串的个数
        def numMatchingSubseq(self, S, words):
            self.idx = { 'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4,
                        'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9,
                        'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14,
                        'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19,
                        'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
            n = len(S)
            nxtPos = []
            tmp = [-1] * 26
            for i in range(n - 1, -1, -1):
                tmp[self.idx[S[i]]] = i
                nxtPos.append([i for i in tmp])
            nxtPos = nxtPos[::-1]
            ans = 0
            for word in words:
                if self.isSubseq(word, nxtPos):
                    ans += 1
            return ans
        def isSubseq(self, word, nxtPos):
            lenw = len(word)
            lens = len(nxtPos)
            i, j = 0, 0
            while i < lenw and j < lens:
                j = nxtPos[j][self.idx[word[i]]]
                if j < 0:
                    return False
                i += 1
                j += 1
            return i == lenw
    if __name__ == '__main__':
        solution=Solution()
        input1="abcde"
        input2=["a", "bb", "acd", "ace"]
        print("输入字符串为：",input1)
        print("输入子串为：",input2)
        print("输出为：",solution.numMatchingSubseq(input1,input2))

[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