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

朱雀 2023-01-20 13:51 2阅读 0赞

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

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

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

第一章 难度等级★

### 【例1】反转一个3位整数 难度等级★ ###

3.代码实现

class Solution:
    #参数number: 一个三位整数
        #返回值: 反转后的数字
        def reverseInteger(self, number):
            h = int(number/100)
            t = int(number%100/10)
            z = int(number%10)
            return (100*z+10*t+h)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        num = 123
        ans = solution.reverseInteger(num)
        print("输入：", num)
        print("输出：", ans)

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

3.代码实现

class Solution:
        #参数A: 有序整数数组A
        #参数B: 有序整数数组B
        #返回:一个新的有序整数数组
        def mergeSortedArray(self, A, B):
            i, j = 0, 0
            C = []
            while i < len(A) and j < len(B):
                if A[i] < B[j]:
                    C.append(A[i])
                    i += 1
                else:
                    C.append(B[j])
                    j += 1
            while i < len(A):
                C.append(A[i])
                i += 1
            while j < len(B):
                C.append(B[j])
                j += 1
            return C
    #主函数
    #主函数
    if __name__ == '__main__':
        A = [1,4]
        B = [1,2,3]
        D = [1,2,3,4]
        E = [2,4,5,6]
        solution = Solution()
        print("输入：", A, " ", B)
        print("输出：", solution.mergeSortedArray(A,B))
        print("输入：", D, " ", E)
        print("输出：", solution.mergeSortedArray(D,E))

### 【例3】旋转字符串 难度等级★ ###

3.代码实现

class Solution:
        #参数s:字符列表
        #参数offset:整数
        #返回值:无
        def rotateString(self, s, offset):
            if len(s) > 0:
                offset = offset % len(s)
            temp = (s + s)[len(s) - offset : 2 * len(s) - offset]
            for i in range(len(temp)):
                s[i] = temp[i]
    #主函数
    if __name__ == '__main__':
        s = ["a","b","c","d","e","f","g"]
        offset = 3
        solution = Solution()
        solution.rotateString(s, offset)
        print("输入：s =", ["a","b","c","d","e","f","g"], " ", "offset =",offset)
        print("输出：s =", s)

### 【例4】相对排名 难度等级★ ###

3.代码实现

class Solution:
        #参数nums为整数列表
        #返回列表
        def findRelativeRanks(self, nums):
            score = { }
            for i in range(len(nums)):
                score[nums[i]] = i
            sortedScore = sorted(nums, reverse=True)
            answer = [0] * len(nums)
            for i in range(len(sortedScore)):
                res = str(i + 1)
                if i == 0:
                    res = 'Gold Medal'
                if i == 1:
                    res = 'Silver Medal'
                if i == 2:
                    res = 'Bronze Medal'
                answer[score[sortedScore[i]]] = res
            return answer
    #主函数
    if __name__ == '__main__':
        num = [5,4,3,2,1]
        s = Solution()
        print("输入为：",num)
        print("输出为：",s.findRelativeRanks(num))

### 【例5】二分查找 难度等级★ ###

3.代码实现

class Solution:
        #参数nums: 整数数组
        #参数target: 要查找的目标数字
        #返回值：目标数字的第一个位置，从0开始 
    	def binarySearch(self, nums, target):
    		return self.search(nums, 0, len(nums) - 1, target)
    	def search(self, nums, start, end, target):
    		if start > end:
    			return -1
    		mid = (start + end)//2
    		if nums[mid] > target:
    			return self.search(nums, start, mid, target)
    		if nums[mid] == target:
    			return mid
    		if nums[mid] < target:
    			return self.search(nums, mid, end, target)
    #主函数
    if __name__ == '__main__':
    my_solution = Solution()
        nums = [1,2,3,4,5,6]
        target = 3
        targetIndex = my_solution.binarySearch(nums, target)
        print("输入：nums =", nums, " ", "target =",target)
        print("输出：",targetIndex)

### 【例6】下一个更大的数 难度等级★ ###

3.代码实现

class Solution:
        #参数nums1为整数数组
        #参数nums2为整数数组
        #返回整数数组
        def nextGreaterElement(self, nums1, nums2):
            answer = { }
            stack = []
            for x in nums2:
                while stack and stack[-1] < x:
                    answer[stack[-1]] = x
                    del stack[-1]
                stack.append(x)
            for x in stack:
                answer[x] = -1
            return [answer[x] for x in nums1]
    #主函数
    if __name__ == '__main__':
        s = Solution()
        nums1 = [4,1,2]
        nums2 = [1,3,4,2]
        print("输入1为：",nums1)
        print("输入2为：",nums2)
        print("输出为 ：",s.nextGreaterElement(nums1,nums2))

### 【例7】字符串中的单词数 难度等级★ ###

3.代码实现

class Solution:
        #参数s为字符串
        #返回整数
        def countSegments(self, s):
            res = 0
            for i in range(len(s)):
                if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
                    res += 1 
            return res
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n =  "Hello, my name is John"
        print("输入为：",n)
        print("输出为：",s.countSegments(n))

### 【例8】勒索信 难度等级★ ###

3.代码实现

class Solution:
        """ 参数ransomNote为字符串 参数magazine为字符串 返回布尔类型 """
        def canConstruct(self, ransomNote, magazine):
            arr = [0] * 26
            for c in magazine:
                arr[ord(c) - ord('a')] += 1 
            for c in ransomNote:
                arr[ord(c) - ord('a')] -= 1
                if arr[ord(c) - ord('a')] < 0:
                    return False
            return True
    #主函数
    if __name__ == '__main__':
        s = Solution()
        ransomNote = "aa"
        magazine = "aab"
        print("输入勒索信为：",ransomNote)
        print("输入杂志内容：",magazine)
        print("输出为：",s.canConstruct(ransomNote,magazine))

### 【例9】不重复的两个数 难度等级★ ###

3.代码实现  
\#参数arr是输入的待查数组  
\#返回值是两个值的列表，内容没有重复的

class Solution:
        def theTwoNumbers(self, a):
            ans = [0, 0]
            for i in a:
                ans[0] = ans[0] ^ i
            c = 1
            while c & ans[0] != c:
                c = c << 1
            for i in a:
                if i & c == c:
                    ans[1] = ans[1] ^ i
            ans[0] = ans[0] ^ ans[1]
            return ans
    if __name__ == '__main__':
        arr = [1, 2, 5, 1]
        solution = Solution()
        print(" 数组为：", arr)
        print(" 两个没有重复的数字是:", solution.theTwoNumbers(arr))

### 【例10】双胞胎字符串 难度等级★ ###

3.代码实现

#参数s和t是一对字符串
    #返回值是个字符串，能否根据规则转换
    class Solution:
        def isTwin(self, s, t):
            if len(s) != len(t):
                return "No"
            oddS = []
            evenS = []
            oddT = []
            evenT = []
            for i in range(len(s)):
                if i & 1:
                    oddS.append(s[i])
                    oddT.append(t[i])
                else :
                    evenS.append(s[i])
                    evenT.append(t[i])
            oddS.sort()
            oddT.sort()
            evenS.sort()
            evenT.sort()
            for i in range (len(oddS)) :
                if oddS[i] != oddT[i]:
                    return "No"
            for i in range (len(evenS)) :
                if evenS[i] != evenT[i]:
                    return "No"
            return "Yes"
    if __name__ == '__main__':
        s="abcd"
        t="cdab"
        solution = Solution()
        print(" s与t分别为：", s, t)
        print(" 是否:", solution.isTwin(s, t))

### 【例11】最接近target的值 难度等级★ ###

3.代码实现

#参数array是输入列表
    #参数target是目标值
    #返回值是整数
    class Solution:
        def closestTargetValue(self, target, array):
            n = len(array)
            if n < 2:
                return -1
            array.sort()
            diff = 0x7fffffff
            left = 0
            right = n - 1
            while left < right:
                if array[left] + array[right] > target:
                    right -= 1
                else:
                    diff = min(diff, target - array[left] - array[right])
                    left += 1
            if diff == 0x7fffffff:
                return -1
            else:
                return target - diff
    if __name__ == '__main__':
        array = [1,3,5,11,7]
        target = 15
        solution = Solution()
        print(" 输入数组为：", array,"目标值为：", target)
        print(" 最近可以得到值为:", solution.closestTargetValue(target, array))

### 【例12】点积 难度等级★ ###

3.代码实现

#参数A和B是输入列表
    #返回值是个整数，是点积
    class Solution:
        def dotProduct(self, A, B):
            if len(A) == 0 or len(B) == 0 or len(A) != len(B):
                return -1
            ans = 0
            for i in range(len(A)):
                ans += A[i] * B[i]
            return ans
    if __name__ == '__main__':
        A = [1,1,1]
        B = [2,2,2]
        solution = Solution()
        print(" A与B分别为：", A, B)
        print(" 点积为：", solution.dotProduct(A, B))

### 【例13】函数运行时间 难度等级★ ###

3.代码实现

#参数s为输入原始字符串
    #返回值是个字符串，意为每个名字的函数运行了多久
    class Solution:
        def getRuntime(self, a):
            map={ }
            for i in a:
                count = 0
                while not i[count] == ' ':
                    count = count + 1
                fun = i[0 : count]
                if i[count+2] == 'n':
                    count = count + 7
                    v = int(i[count:len(i)])
                    if fun in map.keys():
                        map[fun] = v - map[fun]
                    else:
                        map[fun] = v
                else:
                    count = count + 6
                    v = int(i[count:len(i)])
                    map[fun] = v - map[fun]
            res=[]
            for i in map:
                res.append(i)
            res.sort()
            for i in range(0,len(res)):
                res[i] = res[i] + '|' + str(map[res[i]])
            return res
    if __name__ == '__main__':
        s = ["F1 Enter 10","F2 Enter 18","F2 Exit 19","F1 Exit 20"]
        solution = Solution()
        print(" 输入运行时间为：", s)
        print(" 每个输出时间为:", solution.getRuntime(s))

### 【例14】查询区间 难度等级★ ###

1.问题描述  
给定一个包含若干个区间的List数组，长度是1000，例如，\[500,1500\]，\[2100,3100\].给定一个number，number是否在这些区间内，返回True或False。  
2.问题示例  
输入是 List = \[\[100,1100\],\[1000,2000\],\[5500,6500\]\]和number = 6000，输出是True，6000在区间\[5500,6500\]。输是List = \[\[100,1100\],\[2000,3000\]\]和number = 3500，输出是 False，3500不在list的任何一个区间中。  
3.代码实现

#参数List是区间列表
    #参数number是待查数字
    #返回值是个字符串，True或者False
    class Solution:
        def isInterval(self, intervalList, number):
            high = len(intervalList) - 1
            low = 0
            while high >= low:
                if 0 < (number - intervalList[(high + low)//2][0]) <= 1000:
                    return 'True'
                elif 1000 < number - intervalList[(high + low)//2][0]:
                    low = (high + low) // 2 + 1
                elif 0 > number - intervalList[(high + low)//2][0]:
                    high = (high + low) // 2 - 1
            return 'False'
    if __name__ == '__main__':
        number = 6000
        intervalList = [[100,1100],[1000,2000],[5500,6500]]
        solution = Solution()
        print(" 区间List为：", intervalList)
        print(" 数字为：", number)
        print(" 是否在区间中:", solution.isInterval(intervalList, number))

4.运行结果  
输入区间List为： \[\[100, 1100\], \[1000, 2000\], \[5500, 6500\]\]  
输出数字为： 6000  
是否在区间中: True

### 【例15】飞行棋 难度等级★ ###

3.代码实现

#参数length是棋盘长度（不包含起始点）
    #参数connections是跳点的集合
    #返回值是个整数，代表最小步数
    class Solution:
        def modernLudo(self, length, connections):
            ans = [i for i in range(length+1)]
            for i in range(length+1):
                for j in range(1,7):
                    if i - j >= 0:
                        ans[i] = min(ans[i], ans[i-j]+1)
                for j in connections:
                    if i == j[1]:
                        ans[i] = min(ans[i], ans[j[0]])
            return ans[length]
    #参数length是棋盘长度（不包含起始点）
    #参数connections是跳点的集合
    #返回值是个整数，代表最小步数
    #SPFA解法
    class Solution:
        """ 参数length为棋盘长度 参数connections为连接位置表 返回最小次数 """
        def modernLudo(self, length, connections):
            dist = [1000000000 for i in range(100050)]
            vis  = [0 for i in range(100050)]
            Q  = [0 for i in range(100050)]
            st = 0
            ed = 0        
            dist[1] =0
            vis[1] = 1 
            Q[ed] = 1;
            ed += 1
            while(st<ed) :
                u = Q[st]
                st += 1
                vis[u] = 0
                for roads in connections :
                    if(roads[0] != u):
                        continue
                    v = roads[1]
                    if(dist[v] > dist[u]):
                        dist[v] = dist[u]
                        if(vis[v] == 0) :
                            vis[v] = 1
                            Q[ed] = v
                            ed += 1
                for i in range(1, 7):
                    if (i + u > length):
                        break
                    v = i + u
                    if(dist[v] > dist[u] + 1) :
                        dist[v] = dist[u] + 1
                        if(vis[v] == 0):
                            vis[v] = 1
                            Q[ed] = v
                            ed += 1
            return dist[length]
    if __name__ == '__main__':
        length = 15
        connections = [[2, 8],[6, 9]]
        solution = Solution()
        print(" 棋盘长度为：", length)
        print(" 连接为：", connections)
        print(" 最小需要为:", solution.modernLudo(length, connections))

### 【例16】移动石子 难度等级★ ###

3.代码实现

#参数arr是一个列表
    #返回值为整数，为最小移动次数
    class Solution:
        def movingStones(self, arr):
            arr = sorted(arr)
            even = 0
            odd = 0
            for i in range(0,len(arr)):
                odd += abs(arr[i]-(2*i+1))
                even += abs(arr[i] - (2*i+2))
            if odd < even:
                return odd
            return even
    if __name__ == '__main__':
    arr = [1, 6, 7, 8, 9]
    solution = Solution()
        print(" 数组是：", arr)
        print(" 最小移动数是:", solution.movingStones(arr))

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

3.代码实现

class Solution:
        #参数A: 整数数组A
        #返回值: 整数数组B
        def productExcludeItself(self, A):
            length ,B  = len(A) ,[]
            f = [ 0 for i in range(length + 1)]
            f[ length ] = 1
            for i in range(length - 1 , 0 , -1):
                f[ i ] = f[ i + 1 ] * A[ i ]
            tmp = 1
            for i in range(length):
                B.append(tmp * f[ i + 1 ])
                tmp *= A[ i ]
            return B
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [1, 2, 3, 4]
        B = solution.productExcludeItself(A)
        print("输入：", A)
        print("输出：", B)

### 【例18】键盘的一行 难度等级★ ###

3.代码实现

class Solution:
        #参数words为字符串列表
        #返回字符串列表
        def findWords(self, words):
            res = []
            s = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
            for w in words:
                for j in range(3):
                    flag = 1
                    for i in w:
                        if i.lower() not in s[j]:
                            flag = 0
                            break
                    if flag == 1:
                        res.append(w)
                        break
            return res
    #主函数
    if __name__ == '__main__':
    word = ["Hello", "Alaska", "Dad", "Peace"]
        s = Solution()
        print("输入为：",word)
        print("输出为：",s.findWords(word))

### 【例19】第n个数位 难度等级★ ###

3.代码实现

class Solution:
        """ 参数n为整数 返回整数 """
        def findNthDigit(self, n):
            # 初始化一位数的个数为9，从1开始
            length = 1
            count = 9
            start = 1
            while n > length * count:
                # 以此类推二位数的个数为90，从10开始
                n -= length * count
                length += 1
                count *= 10
                start *= 10
            # 找到第n位数所在的整数start 
            start += (n - 1) // length
            return int(str(start)[(n - 1) % length])
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = 11
        print("输入为：",n)
        print("输出为：",s.findNthDigit(n))

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

3.代码实现

class Solution:
        """ 参数s为字符串 参数t为字符串 返回字符 """
        def findTheDifference(self, s, t):
            flag = 0
            for i in range(len(s)):
                # 计算每一位字符的Ascll码之差
                flag += (ord(t[i]) - ord(s[i]))
            flag += ord(t[-1])
            return chr(flag)
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n =  "abcd"
        t = "abcde"
        print("输入字符串1为：",n)
        print("输入字符串2为：",t)
        print("输出插入字符为：",s.findTheDifference(n,t))

### 【例21】第k个组合 难度等级★ ###

3.代码实现

#参数k代表寻找的组数
    #参数n代表有多少人
    #返回值是一个列表，是目标数组数里的按序排列
    class Solution:
        def getCombination(self, n, k):
            C = [[0] * (n + 1) for _ in range(n + 1)]
            for i in range(n + 1):
                C[i][0] = 1
                C[i][i] = 1
            # Compute C(m, n) using C(m, n) = C(m-1, n-1)+C(m-1, n).
            for i in range(1, n + 1):
                for j in range(1, i):
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
            ans = []
            curr_index = 1
            for i in range(1, n // 2 + 1):
                base = C[n - curr_index][n // 2 - i]
                # Search for next digit in ans.
                while k > base:
                    curr_index = curr_index + 1
                    base = base + C[n - curr_index][n // 2 - i]
                base = base - C[n - curr_index][n // 2 - i]
                k = k - base;
                ans.append(curr_index)
                curr_index = curr_index + 1
            return ans
    if __name__ == '__main__':
        n = 8
        k = 11
        solution = Solution()
        print(" 人数为：", n, " 找第k组：", k)
        print(" 第k组为:", solution.getCombination(n, k))

### 【例22】平面列表 难度等级★ ###

3.代码实现

class Solution(object):
        #参数nestedList： 一个列表，列表中的每个元素都可以是一个列表或整数
        #返回值：一个整数列表
        def flatten(self, nestedList):
            stack = [nestedList]
            flatten_list = []
            while stack:
                top = stack.pop()
                if isinstance(top, list):
                    for elem in reversed(top):
                        stack.append(elem)
                else:
                    flatten_list.append(top)
                    
            return flatten_list
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        nums = [[1,2],2,[1,1,3]]
        flatten_list = solution.flatten(nums)
        print("输入：", nums)
        print("输出：", flatten_list)

### 【例23】子域名访问计数 难度等级★ ###

2.问题示例  
例如，输入\[“9001 school.bupt.edu”\]，输出\[“9001 school.bupt.edu”, “9001 bupt.edu”, “9001 edu”\]，只有一个域名：“school.bupt.edu”，如题所述，子域名"bupt.edu"和"edu"也会被访问，所以要访问9001次。  
3.代码实现

class Solution:
        # 利用hash表，对子域名计数。注意对字符串的划分
        def subdomainVisits(self, cpdomains):
            count = { }
            for domain in cpdomains:
                visits = int(domain.split()[0])
                domain_segments = domain.split()[1].split('.')
                top_level_domain = domain_segments[-1]
                sec_level_domain = domain_segments[-2] + '.' + domain_segments[-1]
                count[top_level_domain] = count[top_level_domain] + visits if top_level_domain in count.keys() else visits
                count[sec_level_domain] = count[sec_level_domain] + visits if sec_level_domain in count.keys() else visits
                if domain.count('.') == 2:
                    count[domain.split()[1]] = count[domain.split()[1]] + visits if domain.split()[1] in count.keys() else visits
            return [str(v) + ' ' + k for k,v in count.items()]
    if __name__ == '__main__':
        solution=Solution()
        inputnum=["1201 school.bupt.edu"]
        print("输入为：",inputnum)
        print("输入为：",solution.subdomainVisits(inputnum))

4.运行结果  
输入为： \[‘1201 school.bupt.edu’\]  
输入为： \[‘1201 edu’, ‘1201 bupt.edu’, ‘1201 school.bupt.edu’\]

### 【例24】最长AB子串 难度等级★ ###

3.代码实现

#参数S是待查字符串
    #返回值是一个整数，是最大字符串长度
    class Solution:
        def getAns(self, S):
            ans = 0
            arr = [0 for i in range(len(S))]
            sets = { }
            if S[0] == 'A':
                arr[0] = 1
                sets[1] = 0
            else:
                arr[0] = -1
                sets[-1] = 0
            for i in range(1, len(S)):
                if S[i] == 'A':
                    arr[i] = arr[i - 1] + 1
                    if arr[i] == 0:
                        ans = i + 1
                        continue
                    if arr[i] in sets:
                        ans = max(ans, i - sets[arr[i]])
                    else:
                        sets[arr[i]] = i
                else:
                    arr[i] = arr[i - 1] - 1
                    if arr[i] == 0:
                        ans = i + 1
                        continue
                    if arr[i] in sets:
                        ans = max(ans, i - sets[arr[i]])
                    else:
                        sets[arr[i]] = i
            return ans
    if __name__ == '__main__':
        S = "ABABAB"
        solution = Solution()
        print(" AB字符串为：", S)
        print(" 最长AB出现次数相同的子字符串长度是:", solution.getAns(S))

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

3.代码实现

#参数s是待删除字符的原字符串
    #参数t是目标字符串
    #返回值是一个布尔值，意为能否由s删除一些字符得到t
    class Solution:
        def canGetString(self, s, t):
            pos = 0
            for x in t:
                while pos < len(s) and s[pos] != x:
                    pos += 1
                if pos == len(s):
                    return False
                pos += 1
            return True
    if __name__ == '__main__':
        s="abc"
        t="c"
        solution = Solution()
        print(" 原string和目标string分别为：", s, t)
        print(" 能否实现:", solution.canGetString(s, t))

### 【例26】字符串写入的行数 难度等级★ ###

3.代码实现

class Solution(object):
        def numberOfLines(self, widths, S):
            #参数widths为数组
            #参数S为字符串
            #返回数组
            line = 1
            space = 0
            flag = False
            for c in S:
                if flag:
                    line += 1
                    flag = False
                space += widths[ord(c) - 97]
                if space > 100:
                    line += 1
                    space = widths[ord(c) - 97]
                elif space == 100:
                    space = 0
                    flag = True
            return [line, space]
    if __name__ == '__main__':
        solution=Solution()
    width=[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
        s="abcdefghijklmnopqrstuvwxyz"
        print("输入字符宽度为：",width)
        print("输入的字符串为：",s)
        print("输出为：",solution.numberOfLines(width,s))

### 【例27】独特的摩尔斯编码 难度等级★ ###

3.代码实现

class Solution:
        def uniqueMorseRepresentations(self, words):
            #参数words为列表
            #返回整数
            # 用set保存出现过的摩斯码即可
            morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
                     "-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
            s = set()
            for word in words:
                tmp = ''
                for w in word:
                    tmp += morse[ord(w) - 97]
                s.add(tmp)
            return len(s)
    if __name__ == '__main__':
        solution=Solution()
        inputnum=["gin", "zen", "gig", "msg"]
        print("输入为：",inputnum)
        print("输出为：",solution.uniqueMorseRepresentations(inputnum))

### 【例28】比较字符串 难度等级★ ###

3.代码实现

class Solution:
        #参数A : 包括大写字母的字符串
        #参数B : 包括大写字母的字符串
        #返回值: 如果字符串A包含B中的所有字符，返回True，否则返回False
        def compareStrings(self, A, B):
            if len(B) == 0:
                return True
            if len(A) == 0:
                return False
            #trackTable首先记录A中所有的字符以及它们的个数，然后遍历B,如果出现trackTable[i]小于0的情况，说明B中该字符出现的次数大于在A中出现的次数
            trackTable = [0 for _ in range(26)]
            for i in A:
                trackTable[ord(i) - 65] += 1
            for i in B:
                if trackTable[ord(i) - 65] == 0:
                    return False
                else:
                    trackTable[ord(i) -65] -= 1
            return True
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = "ABCD"
        B = "ACD"
        print("输入：", A, B)
        print("输出：", solution.compareStrings(A,B))

### 【例29】能否转换 难度等级★ ###

3.代码实现

#参数S和T为原始字符串和目标字符串
    #返回值是布尔值，代表能否转换
    class Solution:
        def canConvert(self, s, t):
            j = 0
            for i in range(len(s)):
                if s[i] == t[j]:
                    j += 1
                    if j == len(t):
                        return True
            return False
    if __name__ == '__main__':
        s = "longterm"
        t = "long"
        solution = Solution()
        print(" S与T分别为：", s, t)
        print(" 能否删除得到:", solution.canConvert(s, t))

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

3.代码实现

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

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

3.代码实现

class Solution:
        def twitchWords(self, str):
            n = len(str)
            c = str[0]
            left = 0
            ans = []
            for i in range(n):
                if str[i] != c:
                    if i - left >= 3:
                        ans.append([left, i - 1])
                    c = str[i]
                    left = i
            if n - left >= 3:
                ans.append([left, n - 1])
            return ans
    #主函数
    if __name__ == '__main__':
        str = "whooooisssbesssst"
        solution = Solution()
        print(" 输入为：", str)
        print(" 输出为：", solution.twitchWords(str))

### 【例32】排序数组中最接近元素 难度等级★ ###

3.代码实现

#参数nums是一个整型排序数组
    #参数target是一个整型数
    #返回值是这个数组中最接近target的整数
    class Solution:
        def findPosition(self, A, target):
            if not A:
                return -1
            start, end = 0,len(A)-1
            while start+ 1<end:
                mid = start +(end-start)//2
                if A[mid]<target:
                    start= mid
                elif A[mid]>target:
                    end = mid
                else:
                    return mid
            if target-A[start]<A[end]-target:
                return start
            else:
                return end
    #主函数
    if __name__ == '__main__':
        generator = [1,4,6]
        target = 3
        solution = Solution()
        print("输入：", generator,",target =",target)
        print("输出：", solution.findPosition(generator, target))

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

3.代码实现

class Solution:
        #参数area为整数
        #返回为整数
        def constructRectangle(self, area):
            import math
            W = math.floor(math.sqrt(area))
            while area % W != 0:
                W -= 1
            return [area // W, W]
    #主函数
    if __name__ == '__main__':
        s = Solution()
        area =4
        print("输入面积为：",area)
        print("输出长宽为：",s.constructRectangle(area))

### 【例34】两个排序数组合组和的第k小元素 难度等级★ ###

3.代码实现

#参数A，B是整型排序数组
    #参数k是一个整型数，表示第k小
    #返回值是数组中第k小的整数
    class Solution:
        def kthSmallestSum(self, A, B, k):
            if not A or not B:
                return None
            n, m = len(A), len(B)
            minheap = [(A[0] + B[0], 0, 0)]
            visited = set([0])
            num = None
            for _ in range(k):
                num, x, y = heapq.heappop(minheap)
                if x + 1 < n and (x + 1) * m + y not in visited:
                    heapq.heappush(minheap, (A[x + 1] + B[y], x + 1, y))
                    visited.add((x + 1) * m + y)
                if y + 1 < m and x * m + y + 1 not in visited:
                    heapq.heappush(minheap, (A[x] + B[y + 1], x, y + 1))
                    visited.add(x * m + y + 1)
            return num
    #主函数
    if __name__ == '__main__':
    generator_A = [1,7,11]
    generator_B = [2,4,6]
        k = 3
        solution = Solution()
    print("输入:", generator_A,generator_B)
    print("k= ",k)
        print("输出:", solution.kthSmallestSum(generator_A,generator_B, k))

### 【例35】玩具工厂 难度等级★ ###

3.代码实现

#参数type是一个字符串，表示不同玩具类型
    #返回值是不同类型对应的玩具对象
    class Toy:
        def talk(self):
            raise NotImplementedError('This method should have implemented.')
    class Dog(Toy):
        def talk(self):
            print ("Wow")
    class Cat(Toy):
        def talk(self):
            print ("Meow")
    class ToyFactory:
        def getToy(self, type):
            if type == 'Dog':
                return Dog()
            elif type == 'Cat':
                return Cat()
            return None
    #主函数
    if __name__ == '__main__':
    ty = ToyFactory()
    type='Dog'
    type1='Cat'
    toy = ty.getToy(type)
    print("输入：type= Dog，输出：")
    toy.talk()
    toy = ty.getToy(type1)
    print("输入：type= Cat，输出：")
    toy.talk()

### 【例36】形状工厂 难度等级★ ###

3.代码实现

#参数shapeType是一个字符串，表示不同形状
    #返回值是不同对象，Triangle，Square，Rectangle
    class Shape:
        def draw(self):
            raise NotImplementedError('This method should have implemented.')
    class Triangle(Shape):
           def draw(self):
               print(" /\\")
               print(" / \\")
               print("/____\\")
    class Rectangle(Shape):
        def draw(self):
            print(" ----")
            print("| |")
            print(" ----")
    class Square(Shape):
        def draw(self):
            print( " ----")
            print( "| |")
            print( "| |")
            print( " ----")
    class ShapeFactory:
        def getShape(self, shapeType):
            if shapeType == "Triangle":
                return Triangle()
            elif shapeType == "Rectangle":
                return Rectangle()
            elif shapeType == "Square":
                return Square()
            else:
                return None
    #主函数
    if __name__ == '__main__':
        sf = ShapeFactory()
        shapeType='Triangle'
        shape = sf.getShape(shapeType)
        print("输入：type= Triangle，\n输出：")
        shape.draw()
        shapeType1='Rectangle'
        shape = sf.getShape(shapeType1)
        print("输入：type= Rectangle，\n输出：")
        shape.draw()
        shapeType2='Square'
        shape = sf.getShape(shapeType2)
        print("输入：type= Square，\n输出：")
        shape.draw()

### 【例37】二叉树最长连续序列 难度等级★ ###

3.代码实现

#参数root是一个二叉树的根
    #返回值是此二叉树中最长连续序列
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    class Solution:
        def longestConsecutive(self, root):
            return self.helper(root, None, 0)
        def helper(self, root, parent, len):
            if root is None:
                return len
            if parent != None and root.val == parent.val + 1:
                len += 1
            else:
                len = 1
            return max(len, max(self.helper(root.left, root, len), \
                                self.helper(root.right, root, len)))
    #主函数
    if __name__ == '__main__':
        root = TreeNode(1)
        root.right = TreeNode(3)
        root.right.left = TreeNode(2)
        root.right.right = TreeNode(4)
        root.right.right.right = TreeNode(5)
    solution= Solution()
    print("输入是： {1,#,3,2,4,#,#,#,5}")
    print("输出是：", solution.longestConsecutive(root))

### 【例38】首字母大写 难度等级★ ###

3.代码实现

class Solution:
        #参数s为字符串
        #返回字符串
        def capitalizesFirst(self, s):
            n = len(s)
            s1 = list(s)
            if s1[0] >= 'a' and s1[0] <= 'z':
                s1[0] = chr(ord(s1[0]) - 32)
            for i in range(1, n):
                if s1[i - 1] == ' ' and s1[i] != ' ':
                    s1[i] = chr(ord(s1[i]) - 32)
            return ''.join(s1)
    if __name__ == '__main__':
        s = "i am from bupt"
        solution = Solution()
        print("输入为：",s)
        print("输出为：",solution.capitalizesFirst(s))

### 【例39】7进制 难度等级★ ###

3.代码实现

class Solution:
        #参数num为10进制整数
        #返回7进制整数
        #不断执行对7取模和取整操作，直到商小于7
        def convertToBase7(self, num):
            if num < 0: 
                return '-' + self.convertToBase7(-num)
            if num < 7: 
                return str(num)
            return self.convertToBase7(num // 7) + str(num % 7)
    if __name__ == '__main__':
        num = 777
        solution = Solution()
        print("输入为：",num)
        print("输出为：",solution.convertToBase7(num))

### 【例40】查找数组中没有出现的所有数字 难度等级★ ###

3.代码实现

class Solution:
        #参数为nums整数列表
        #返回整数列表
        def findDisappearedNumbers(self, nums):
            n = len(nums)
            s = set(nums)
            res = [i for i in range(1, n+1) if i not in s]
            return res
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [4,3,2,7,8,2,3,1]
        print("输入为：",n)
        print("输出为：",s.findDisappearedNumbers(n))

### 【例41】回旋镖的数量 难度等级★ ###

3.代码实现

class Solution(object):
        def getDistance(self, a, b):
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            return dx * dx + dy * dy
        def numberOfBoomerangs(self, points):
            #参数points为整数列表
            #返回整数
            if points == None:
                return 0
            ans = 0
            for i in range(len(points)):
                disCount = { }
                for j in range(len(points)):
                    if i == j:
                        continue
                    distance = self.getDistance(points[i], points[j])
                    count = disCount.get(distance, 0)
                    disCount[distance] = count + 1
                for distance in disCount:
                    ans += disCount[distance] * (disCount[distance] - 1)
            return ans
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [[0,0],[1,0],[2,0]]
        print("输入为：",n)
        print("输出为：",s.numberOfBoomerangs(n))

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

3.代码实现

class Solution:
        #参数A: 已排序整数数组A有m个元素，但是A的大小是m+n
        #参数m: 整数
        #参数B: 已排序整数数组B，它有n个元素
        #参数n: 整数
        #返回值: 无
        def mergeSortedArray(self, A, m, B, n):
            i, j = m-1, n-1
            t = len(A)-1
            while i >= 0 or j >= 0:
                if i < 0 or (j >= 0 and B[j] > A[i]):
                    A[t] = B[j]
                    j -= 1
                else:
                    A[t] = A[i]
                    i -= 1
                t -= 1
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [1,2,3,0,0]
        m = 3
        B = [4,5]
        n = 2
        solution.mergeSortedArray(A, m, B, n)
        print("输入：A = [1,2,3,0,0], 3, B = [4,5], 2")
        print("输出：", A)

### 【例43】最小路径和 难度等级★ ###

3.代码实现

class Solution:
        #参数grid: 二维整数数组
        #返回值: 一个整数，使其路径上的所有数字之和最小化
        def minPathSum(self, grid):
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if i == 0 and j > 0:
                        grid[i][j] += grid[i][j-1]
                    elif j == 0 and i > 0:
                        grid[i][j] += grid[i-1][j]
                    elif i > 0 and j > 0:
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])
            return grid[len(grid) - 1][len(grid[0]) - 1]
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        grid = [[1,3,1],[1,5,1],[4,2,1]]
        length = solution.minPathSum(grid)
        print("输入：", grid)
        print("输出：", length)

### 【例44】大小写转换 难度等级★ ###

3.代码实现

class Solution:
        #参数character: 字符
        #返回值: 字符
        def lowercaseToUppercase(self, character):
            #ASCII码中小写字母与对应的大写字母相差32
            return chr(ord(character) - 32)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        ans = solution.lowercaseToUppercase('a')
            print("输入： a")
            print("输出：", ans)

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

3.代码实现

import re
    import collections
    class Solution(object):
        def countOfAtoms(self, formula):
            parse = re.findall(r"([A-Z][a-z]*)(\d*)|(\()|(\))(\d*)", formula)
            stack = [collections.Counter()]
            for name, m1, left_open, right_open, m2 in parse:
                if name:
                  stack[-1][name] += int(m1 or 1)
                if left_open:
                  stack.append(collections.Counter())
                if right_open:
                    top = stack.pop()
                    for k in top:
                      stack[-1][k] += top[k] * int(m2 or 1)
            return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '') for name in sorted(stack[-1]))
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        Test_in = "H2O"
        Test_out = solution.countOfAtoms(Test_in)
        print("输入为：",Test_in)
        print("输出为：",Test_out)

### 【例46】矩阵中的最长递增路径 难度等级★ ###

3.代码实现

DIRECTIONS = [(1, 0), (-1, 0), (0, -1), (0, 1)]
    class Solution:
        """ 参数matrix为整数矩阵 返回整数 """
        def longestIncreasingPath(self, matrix):
            if not matrix or not matrix[0]:
                return 0
            sequence = []
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    sequence.append((matrix[i][j], i, j))
            sequence.sort()
            check = { }
            for h, x, y in sequence:
                cur_pos = (x, y)
                if cur_pos not in check:
                    check[cur_pos] = 1
                cur_path = 0
                for dx, dy in DIRECTIONS:
                    if self.is_valid(x+dx, y+dy, matrix, h):
                        cur_path = max(cur_path, check[(x+dx, y+dy)])
                check[cur_pos] += cur_path
            vals = check.values()
            return max(vals)
        def is_valid(self, x, y, matrix, h):
            row, col = len(matrix), len(matrix[0])
            return x >= 0 and x < row and y >= 0 and y < col and matrix[x][y]<h
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        Test_in = [
          [9,9,4],
          [6,6,8],
          [2,1,1]
        ]
        Test_out = solution.longestIncreasingPath(Test_in)
        print("输入为：",Test_in)
        print("输出为：",Test_out)

### 【例47】大小写转换 难度等级★ ###

3.代码实现

class Solution:
        #参数str: 字符串
        #返回值: 字符串
        def lowercaseToUppercase2(self, str):
            p = list(str)
            #遍历整个字符串，将所有的小写字母转成大写字母
            for i in range(len(p)):
                if p[i] >= 'a' and p[i] <= 'z':
                    p[i] = chr(ord(p[i]) - 32)
            return ''.join(p)
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        s1 = "abC12"
        ans = solution.lowercaseToUppercase2(s1)
        print("输入：", s1)
        print("输出：", ans)

### 【例48】水仙花数 难度等级★ ###

3.代码实现

class Solution:
        #参数n: 数字的位数
        @返回值: 所有n位数的水仙花数
        def getNarcissisticNumbers(self, n):
            res = []
            for x in range([0, 10**(n-1)][n > 1], 10**n):
                y, k = x, 0
                while x > 0:
                    k += (x % 10)**n
                    x //= 10
                if k == y: res.append(k)
            return res
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        n = 4
        ans = solution.getNarcissisticNumbers(n)
        print("输入：", n)
        print("输出：", ans)

### 【例49】余弦相似度 难度等级★ ###

3.代码实现

import math
    #参数A，B都是一个整型数组，表示两个矢量
    #返回值是两个输入矢量的余弦相似度
    class Solution:
        def cosineSimilarity(self, A, B):
            if len(A) != len(B):
                return 2
            n = len(A)
            up = 0
            for i in range(n):
                up += A[i] * B[i]
            down = sum(a*a for a in A) * sum(b*b for b in B)
            if down == 0:
                return 2
            return up / math.sqrt(down)
    #主函数
    if __name__ == '__main__':
    generator_A = [1,4,0]
        generator_B = [1,2,3]
        solution = Solution()
        print("输入: A=", generator_A)
        print("输入: B=", generator_B)
        print("输出: ", solution.cosineSimilarity(generator_A,generator_B))

### 【例50】链表节点计数 难度等级★ ###

3.代码实现

#参数head是链表的头部
    #返回值是链表的长度
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    class Solution:
        def countNodes(self, head):
            cnt = 0
            while head is not None:
                cnt += 1
                head = head.next
            return cnt
    #主函数
    if __name__ == '__main__':
        node1 = ListNode(1)
        node2 = ListNode(2)
        node3 = ListNode(3)
        node4 = ListNode(4)
        node1.next = node2
        node2.next = node3
        node3.next = node4
    solution = Solution()
    print("输入: ", node1.val,node2.val,node3.val,node4.val)
        print("输出: ", solution. countNodes(node1))

### 【例51】最高频的K个单词 难度等级★ ###

3.代码实现

#参数words是一个字符串数组
    #参数k代表第k高频率出现
    #返回值是一个字符串数组，表示出现频率前k高字符串
    class Solution:
        def topKFrequentWords(self, words, k):
            dict = { }
            res = []
            for word in words:
                if word not in dict:
                    dict[word] = 1
                else:
                    dict[word] += 1
            sorted_d = sorted(dict.items(), key=lambda x:x[1], reverse=True)
            for i in range(k):
                res.append(sorted_d[i][0])
            return res
    #主函数
    if __name__ == '__main__':
    generator = ["yes", "long", "code",
                     "yes", "code", "baby",
                     "you", "baby", "chrome",
                     "safari", "long", "code",
                     "body", "long", "code"]
    k = 4
    solution = Solution()
    print("输入: ", generator)
    print("输入: ","k = ", k)
    print("输出: ", solution.topKFrequentWords(generator,k))

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

3.代码实现

#参数word是要添加的的单词
    #返回值是个布尔值，查找单词成功则返回True，否则，返回False
    class TrieNode:
        def __init__(self):
            self.children = { }
            self.is_word = False
    class WordDictionary:
        def __init__(self):
            self.root = TrieNode()
        def addWord(self, word):
            node = self.root
            for c in word:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.is_word =True
        def search(self, word):
            if word is None:
                return False
            return self.search_helper(self.root, word, 0)
        def search_helper(self, node, word, index):
            if node is None:
                return False
            if index >= len(word):
                return node.is_word
            char = word[index]
            if char != '.':
                return self.search_helper(node.children.get(char), word, index + 1)
            for child in node.children:
                if self.search_helper(node.children[child], word, index + 1):
                    return True
            return False
    #主函数
    if __name__ == '__main__':
        solution = WordDictionary()
        solution.addWord("bad")
        solution.addWord("dad")
        solution.addWord("mad")
        print('输入： addWord("bad"),addWord("dad"),addWord("mad")')
        print('输入： search("pad"),search("dad"),search(".ad"),search("b..")')
        print("输出： ",
        solution.search("pad"),
        solution.search("bad"),
        solution.search(".ad"),
        solution.search("b.."))

### 【例53】石子归并 难度等级★ ###

3.代码实现

#参数A是一个整型数组
    #返回值是一个整数，表示最小的合并代价
    import sys
    class Solution:
        def stoneGame(self, A):
            n = len(A)
            if n < 2:
                return 0
            dp = [[0] * n for _ in range(n)]
            cut = [[0] * n for _ in range(n)]
            range_sum = self.get_range_sum(A)
            for i in range(n - 1):
                dp[i][i + 1] = A[i] + A[i + 1]
                cut[i][i + 1] = i
            for length in range(3, n + 1):
                for i in range(n - length + 1):
                    j = i + length - 1
                    dp[i][j] = sys.maxsize
                    for mid in range(cut[i][j - 1], cut[i + 1][j] + 1):
                        if dp[i][j] > dp[i][mid] + dp[mid + 1][j] + range_sum[i][j]:
                            dp[i][j] = dp[i][mid] + dp[mid + 1][j] + range_sum[i][j]
                            cut[i][j] = mid
            return dp[0][n - 1]
        def get_range_sum(self, A):
            n = len(A)
            range_sum = [[0] * n for _ in range(len(A))]
            for i in range(n):
                range_sum[i][i] = A[i]
                for j in range(i + 1, n):
                    range_sum[i][j] = range_sum[i][j - 1] + A[j]
            return range_sum
    #主函数
    if __name__ == '__main__':
    generator = [3,4,3]
    solution = Solution()
    print("输入：", generator)
    print("输出：", solution.stoneGame(generator))

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

3.代码实现

#参数a，b是两个任意整数
    #operator是运算符+, -, *, /
    #返回值是浮点型运算结果
    class Solution:
        def calculate(self, a, operator, b):
            if operator == '+':
                return a + b
            elif operator == '-':
                return a - b
            elif operator == '*':
                return a * b
            elif operator == '/':
                return a / b
    #主函数
    if __name__ == '__main__':
    a=8
    b=3
    operator1='+'
    operator2='-'
    operator3='*'
    operator4='/'solution = Solution()
    print("输入：", a ,operator1 ,b)
    print("输出：", solution.calculate(a,operator1,b))
    print("输入：", a ,operator2 ,b)
    print("输出：", solution.calculate(a,operator2,b))
    print("输入：", a ,operator3 ,b)
    print("输出：", solution.calculate(a,operator3,b))
    print("输入：", a ,operator4 ,b)
    print("输出：", solution.calculate(a,operator4,b))

### 【例55】数组第二大数 难度等级★ ###

3.代码实现

#参数nums是一个整型数组
    #返回值secValue是数组中第二大数
    class Solution:
        def secondMax(self, nums):
            maxValue = max(nums[0], nums[1])
            secValue = min(nums[0], nums[1])
            for i in range(2, len(nums)):
                if nums[i] > maxValue:
                    secValue = maxValue
                    maxValue = nums[i]
                elif nums[i] > secValue:
                    secValue = nums[i]
            return secValue
    #主函数
    if __name__ == '__main__':
        generator = [3,4,7,9]
        solution = Solution()
        print("输入： ", generator)
        print("输出： ", solution.secondMax(generator))

### 【例56】二叉树叶子节点之和 难度等级★ ###

3.代码实现

#参数root是二叉树的根
    #返回值是个整数，叶子节点之和
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    class Solution:
        def leafSum(self, root):
            p = []
            self.dfs(root, p)
            return sum(p)
        def dfs(self, root, p):
            if root is None:
                return
            if root.left is None and root.right is None:
                p.append(root.val)
            self.dfs(root.left, p)
            self.dfs(root.right, p)
    #主函数
    if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    solution = Solution()
    print("输入：", root.val,root.left.val,root.right.val,root.left.left.val)
    print("输出：", solution.leafSum(root))

### 【例57】二叉树的某层节点之和 难度等级★ ###

3.代码实现

#参数root是二叉树的根
    #参数level是树的目标层的深度
    #返回值是一个整数，表示该level叶子节点之和
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    class Solution:
        def levelSum(self, root, level):
            p = []
            self.dfs(root, p, 1, level)
            return sum(p)
        def dfs(self, root, p, dep, level):
            if root is None:
                return
            if dep == level:
                p.append(root.val)
                return
            self.dfs(root.left, p, dep+1, level)
            self.dfs(root.right, p, dep+1, level)
    #主函数
    if __name__ == '__main__':
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)
        root.right.left = TreeNode(6)
        root.right.right = TreeNode(7)
        root.left.right.right = TreeNode(8)
        root.right.right.right = TreeNode(9)
        depth = 3
        solution = Solution()
        print("输入：",root.val,root.left.val,root.right.val,root.left.left.val,
              root.left.right.val,root.right.left.val,root.right.right.val,
              root.left.right.right.val,root.right.right.right.val)
    print("输入： depth= ", depth)
         print("输出：",solution.levelSum(root,depth))

### 【例58】判断尾数 难度等级★ ###

3.代码实现

#参数str是输入01串
    #返回值是一个整数，代表最后一个词的长度
    class Solution:
        def judgeTheLastNumber(self, str):
            if str[-1] == 1:
                return 2
            for i in range(-2, -len(str) - 1, -1):
                if str[i] == 0:
                    return -1 * ((i * -1 + 1) % 2) + 2
            return -1 * (len(str) % 2) + 2
    if __name__ == '__main__':
        str = "111110"
        solution = Solution()
        print(" 原01串为：", str)
        print(" 最后一个词长度是:", solution.judgeTheLastNumber(str))

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

3.代码实现

class Solution:
        #参数s: 第一个字符串
        #参数t: 第二个字符串
        #返回值: True或False
        def anagram(self, s, t):
            set_s = [0] * 256
            set_t = [0] * 256
            for i in range(0, len(s)):
                set_s[ord(s[i])] += 1
            for i in range(0, len(t)):
                set_t[ord(t[i])] += 1
            for i in range(0, 256):
                if set_s[i] != set_t[i]:
                    return False
            return True
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        s = "abcd"
        t = "dcba"
        ans = solution.anagram(s, t)
        print("输入：", s, t)
        print("输出：", ans)

### 【例60】最长单词 难度等级★ ###

3.代码实现

class Solution:
        #参数dictionary: 字符串数组
        #返回值: 字符串数组
        def longestWords(self, dictionary):
            answer = []
            maxLength = 0
            for item in dictionary:
                if len(item) > maxLength:
                    maxLength = len(item)
                    answer = [item]
                elif len(item) == maxLength:
                    answer.append(item)
            return answer
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        dic = ["dog","google","facebook","internationalization","blabla"]
        answer = solution.longestWords(dic)
        print("输入：", dic)
        print("输出：", answer)

### 【例61】机器人能否返回原点 难度等级★ ###

3.代码实现

class Solution:
        #参数moves为字符串
        #返回布尔类型
        def judgeCircle(self, moves):
            count_RL = count_UD = 0
            for c in moves:
                if c == 'R':
                    count_RL += 1
                if c == 'L':
                    count_RL -= 1
                if c == 'U':
                    count_UD += 1
                if c == 'D':
                    count_UD -= 1
            return count_RL == 0 and count_UD == 0
    if __name__ == '__main__':
        solution=Solution()
        moves="UD"
        print("输入为：",moves)
    print("输出为：",solution.judgeCircle(moves))

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

3.代码实现

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

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

3.代码实现

#定义链表节点
    class ListNode(object):
        def __init__(self, val):
            self.val = val
            self.next = None
    class Solution:
        def addLists(self, l1, l2) -> list:
            dummy = ListNode(None)
            tail = dummy
            carry = 0 
            while l1 or l2 or carry:
                num = 0 
                if l1:
                    num += l1.val 
                    l1 = l1.next
                if l2:
                    num += l2.val 
                    l2 = l2.next
                num += carry
                digit, carry = num % 10, num // 10
                node = ListNode(digit)
                tail.next, tail = node, node 
            return dummy.next
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        l0 = ListNode(7)
        l1 = ListNode(1)
        l2 = ListNode(6)
        l0.next = l1
        l1.next = l2
        l3 = ListNode(5)
        l4 = ListNode(9)
        l5 = ListNode(2)
        l3.next = l4
        l4.next = l5
        ans = solution.addLists(l0, l3)
        a = [ans.val, ans.next.val, ans.next.next.val]
        print("输入： 7->1->6->null, 5->9->2->null")
        print("输出： 2->1->9->null")

### 【例64】删除元素 难度等级★ ###

3.代码实现

class Solution:
        #参数A: 整数列表
        #参数elem: 整数
        #返回值：移除后的长度
        def removeElement(self, A, elem):
            j = len(A)-1
            for i in range(len(A) - 1, -1, -1):
                if A[i] == elem:
                    A[i], A[j] = A[j], A[i]
                    j -= 1
            return j+1
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [0,4,4,0,0,2,4,4]
        e = 4
        ans = solution.removeElement(A, e)
        print("输入： [0,4,4,0,0,2,4,4], value = 4")
        print("输出：", ans)

### 【例65】克隆二叉树 难度等级★ ###

3.代码实现

#树的节点结构
    #参数val是节点值
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    #参数{TreeNode} root是二进制树的根
    #返回值clone_root是复制后新树的根
    class Solution:
        def cloneTree(self, root):
            if root is None:
                return None
            clone_root = TreeNode(root.val)
            clone_root.left = self.cloneTree(root.left)
            clone_root.right = self.cloneTree(root.right)
            return clone_root
    #主函数
    if __name__ == '__main__':
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)
        solution = Solution()
        print("输入：", root.val,root.left.val,root.right.val,root.left.left.val,root.left.right.val)
        print("输出： ", solution.cloneTree(root).val,solution.cloneTree(root).left.val,solution.cloneTree(root).right.val,solution.cloneTree(root).left.left.val,solution.cloneTree(root).left.right.val)

### 【例66】合并两个排序链表 难度等级★ ###

3.代码实现

#定义链表节点
    class ListNode(object):
        def __init__(self, val):
            self.val = val
            self.next = None
    class Solution(object):
        #参数l1: 链表头结节点
        #参数l2: 链表头节点
        #返回值: 链表头节点
        def mergeTwoLists(self, l1, l2):
            dummy = ListNode(0)
            tmp = dummy
            while l1 != None and l2 != None:
                if l1.val < l2.val:
                    tmp.next = l1
                    l1 = l1.next
                else:
                    tmp.next = l2
                    l2 = l2.next
                tmp = tmp.next
            if l1 != None:
                tmp.next = l1
            else:
                tmp.next = l2
            return dummy.next
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        l0 = ListNode(1)
        l1 = ListNode(3)
        l2 = ListNode(8)
        l0.next = l1
        l1.next = l2
        l5 = ListNode(2)
        l6 = ListNode(4)
        l5.next = l6
        ans = solution.mergeTwoLists(l0, l5)
        a = [ans.val, ans.next.val, ans.next.next.val, 
             ans.next.next.next.val, ans.next.next.next.next.val]
        print("输入： list1 = 1->3->8->null, list2 = 2->4->null")
        print("输出： 1->2->3->4->8->null")

### 【例67】反转整数 难度等级★ ###

3.代码实现

#参数n是一个整型数
    #返回值reverse是反转的整数
    class Solution:
        def reverseInteger(self, n):
            if n == 0:
                return 0
            neg = 1
            if n < 0:
                neg, n = -1, -n
            reverse = 0
            while n > 0:
                reverse = reverse * 10 + n % 10
                n = n // 10
            reverse = reverse * neg
            if reverse < -(1 << 31) or reverse > (1 << 31) - 1:
                return 0
            return reverse
    #主函数
    if __name__ == '__main__':
        generator=1234
    solution = Solution()
    print("输入：", generator)
    print("输出：", solution. reverseInteger(generator))

### 【例68】报数 难度等级★ ###

3.代码实现

#参数n是一个正整数
    #返回值string是n所表示的报数序列
    class Solution:
        def countAndSay(self, n):
            string = '1'
            for i in range(n - 1):
                a = string[0]
                count = 0
                s = ''
                for ch in string:
                    if a == ch:
                        count += 1
                    else:
                        s += str(count) + a
                        a = ch
                        count = 1
                s += str(count) + a
                string = s
                a = string[0]
            return string
    #主函数
    if __name__ == '__main__':
        generator=5
    solution = Solution()
    print("输入:", generator)
    print("输出:", solution.countAndSay(generator))

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

3.代码实现

#参数root是二叉树的根
    #返回值是个布尔值，当完全二叉树时返回True，否则返回False
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    class Solution:
        def isComplete(self, root):
            if root is None:
                return True
            queue = [root]
            index = 0
            while index < len(queue):
                if queue[index] is not None:
                    queue.append(queue[index].left)
                    queue.append(queue[index].right)
                index += 1
            while queue[-1] is None:
                queue.pop()
            for q in queue:
                if q is None:
                    return False
            return True
    #主函数
    if __name__ == '__main__':
    root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        solution = Solution()
    print("输入: ", root.val,root.left.val,root.right.val,root.left.left.val)
    print("输出: ", solution.isComplete(root))

### 【例70】对称二叉树 难度等级★ ###

3.代码实现

#参数root是二叉树的的根
    #返回值是个布尔值，是对称二叉树时返回True，否则返回False
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    class Solution:
        def help(self, p, q):
            if p == None and q == None: return True
            if p and q and p.val == q.val:
                return self.help(p.right, q.left) and self.help(p.left, q.right)
            return False
        def isSymmetric(self, root):
            if root:
                return self.help(root.left, root.right)
            return True
    #主函数
    if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.left.right = TreeNode(4)
    root.left.left = TreeNode(3)
    solution = Solution()
    print("输入: ", 
    root.val,root.left.val,root.right.val,root.left.left.val,root.left.right. val,root.right.left.val, root.right.right.val)
    print("输出: ", solution.isSymmetric(root))

### 【例71】扭转后等价的二叉树 难度等级★ ###

3.代码实现

#参数a、b是二叉树的根
    #返回值是个布尔值，当它们等价时返回True，否则返回False
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    class Solution:
        def isTweakedIdentical(self, a, b):
            if a == None and b == None: return True
            if a and b and a.val == b.val:
                return self.isTweakedIdentical(a.left, b.left) and \
                    self.isTweakedIdentical(a.right, b.right) or \
                    self.isTweakedIdentical(a.left, b.right) and \
                    self.isTweakedIdentical(a.right, b.left)
            return False
    #主函数
    if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root1 = TreeNode(1)
    root1.right = TreeNode(2)
    root1.left = TreeNode(3)
    root1.right.right = TreeNode(4)
    solution = Solution()
    print("输入: ", root.val,root.left.val,root.right.val,root.left.left.val," , ",root1.val,root1.left.val,root1.right.val,root1.right.right.val)
    print("输出: ", solution.isTweakedIdentical(root,root1))

### 【例72】岛屿的个数 难度等级★ ###

3.代码实现

from collections import deque
    #参数grid是一个01矩阵
    #返回值islands是岛屿的个数
    class Solution:
        def numIslands(self, grid):
            if not grid or not grid[0]:
                return 0
            islands = 0
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]:
                        self.bfs(grid, i, j)
                        islands += 1
            return islands
        def bfs(self, grid, x, y):
            queue = deque([(x, y)])
            grid[x][y] = False
            while queue:
                x, y = queue.popleft()
                for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
                    next_x = x + delta_x
                    next_y = y + delta_y
                    if not self.is_valid(grid, next_x, next_y):
                        continue
                    queue.append((next_x, next_y))
                    grid[next_x][next_y] = False
        def is_valid(self, grid, x, y):
            n, m = len(grid), len(grid[0])
            return 0 <= x < n and 0 <= y < m and grid[x][y]
    #主函数
    if __name__ == '__main__':
        generator= [
      				[1,1,0,0,0],
      				[0,1,0,0,1],
      				[0,0,0,1,1],
      				[0,0,0,0,0],
      				[0,0,0,0,1]
    ]
    solution = Solution()
    print("输入：", generator)
    print("输出：", solution.numIslands(generator))

### 【例73】判断是否为平方数之和 难度等级★ ###

3.代码实现

import math
    class Solution:
        """ 参数num为整数 返回布尔类型 """
        def checkSumOfSquareNumbers(self, num):
            # write your code here
            if num < 0:
                return False
            for i in reversed(range(0, int(math.sqrt(num)) + 1)):
                if i * i == num:
                    return True
                j = num - i * i
                k = int(math.sqrt(j))
                if k * k == j:
                    return True
            return False
    if __name__=='__main__':
    	solution=Solution()
    	num=5
    	print("输入为：",num)
    	print("输出为：",solution.checkSumOfSquareNumbers(num))

### 【例74】滑动窗口内数的和 难度等级★ ###

3.代码实现

class Solution:
        #nums是整数数组
        #k是滑动窗口
        #返回每个窗口的数字和
        def winSum(self, nums, k):
            n = len(nums)
            if n < k or k <= 0:
                return []
            sums = [0] * (n - k + 1)
            for i in range(k):
                sums[0] += nums[i];
            for i in range(1, n - k + 1):
                sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1]
            return sums
    #主函数
    if __name__ == '__main__':
        inputnum=[1,2,7,8,5]
        k=3
        print("输入数组：",inputnum)
        print("输入窗口：",k)
        solution=Solution()
        print("输出数组：",solution.winSum(inputnum,k))

4.运行结果  
输入数组：\[1, 2, 7, 8, 5\]  
输入窗口：3  
输出数组：\[10, 17, 20\]

### 【例75】单词拆分 难度等级★★ ###

.代码实现

class Solution:
        """ 参数s为字符串 参数dict为单词列表 返回整数数量 """
        def wordBreak3(self, s, dict):
            if not s or not dict:
                return 0
            n, hash = len(s), set()
            lowerS = s.lower()
            for d in dict:
                hash.add(d.lower())
            f = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(i, n):
                    sub = lowerS[i:j + 1]
                    if sub in hash:
                        f[i][j] = 1
            for i in range(n):
                for j in range(i, n):
                    for k in range(i, j):
                        f[i][j] += f[i][k] * f[k + 1][j]
            return f[0][-1]
    if __name__=='__main__':
    	solution=Solution()
    	s="CatMat"
    	dict1=["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
    	print("输入句子为：",s)
    	print("输入列表为：",dict1)
    	print("输出数量为：",solution.wordBreak3(s,dict1))

### 【例76】硬币摆放 难度等级★ ###

3.代码实现

import math
    class Solution:
        #参数n为整数
        #返回整数
        # n = (1 + x) * x / 2, 求得 x = (-1 + sqrt(8 * n + 1)) / 2, 对x取整
        def arrangeCoins(self, n):
            return math.floor((-1 + math.sqrt(1 + 8*n)) / 2)
    if __name__ == '__main__':
        n = 10
        solution = Solution()
        print("输入为：",n)
        print("输出为：",solution.arrangeCoins(n))

### 【例77】字母大小写转换 难度等级★ ###

3.代码实现

class Solution(object):
        def letterCasePermutation(self, S):
            #参数S为字符串
            #返回字符串列表
            # 利用二进制对应字符串。其中0表示大小写不变，1表示改变大小写
            res = []
            indices = []
            indices = [i for i,_ in enumerate(S) if S[i].isalpha()]
            for i in range(0, pow(2,len(indices))):
                if i==0:
                    res.append(S)
                else:
                    j=i;bpos=0;nsl=list(S)
                    while j>0:
                        ci2c = indices[bpos]
                        if j&1 and S[ci2c].islower():
                            nsl[ci2c]=S[ci2c].upper()
                        elif j&1 and S[ci2c].isupper():
                            nsl[ci2c]=S[ci2c].lower()
                        bpos+=1
                        j = j >> 1
                    res.append("".join(nsl))
            return res
    if __name__ == '__main__':
        solution=Solution()
        S = "a1b2"
        print("输入为：",S)
        print("输出为：",solution.letterCasePermutation(S))

4.运行结果  
输入为： a1b2  
输出为： \[‘a1b2’, ‘A1b2’, ‘a1B2’, ‘A1B2’\]

### 【例78】二进制表示中质数个计算置位 难度等级★ ###

3.代码实现

class Solution(object):
        def countPrimeSetBits(self, L, R):
            # "L, R在[1, 10^6]范围
            # 可能的质数为2, 3, 5, 7, 11, 13, 17, 19.
            # 统计1的个数在进行质数判定,因为二进制1的个数不会超过20个，枚举质数即可
            k = 0
            for n in range(L, R + 1):
                if bin(n).count('1') in [2, 3, 5, 7, 11, 13, 17, 19]:
                    k = k + 1
            return k
    if __name__ == '__main__':
        solution=Solution()
        L=6
        R=10
        print("输入为：[",L,R,"]")
        print("输出为：",solution.countPrimeSetBits(L,R))

4.运行结果  
输入为：\[ 6 10 \]  
输出为：4

### 【例79】最少费用的爬台阶方法 难度等级★ ###

3.代码实现

class Solution:
        #参数cost为数组
        #返回最小费用
        #状态转移方程 dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])
        def minCostClimbingStairs(self, cost):
            a, b = 0, 0
            for i in range(2, len(cost) + 1):
                c = min(a + cost[i - 2], b + cost[i - 1])
                a, b = b, c
            return b
    if __name__ == '__main__':
        solution=Solution()
        print("输入为：",cost)
        print("输出为：",solution.minCostClimbingStairs(cost))

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

### 【例80】中心索引 难度等级★ ###

3.代码实现

class Solution(object):
        def pivotIndex(self, nums):
            left, right = 0, sum(nums)
            for index, num in enumerate(nums):
                right -= num
                if left == right:
                    return index
                left += num
            return -1
    if __name__ == '__main__':
        solution=Solution()
        words=[1,7,3,6,5,6]
        print(solution.pivotIndex(words))

### 【例81】词典中最长的单词 难度等级★ ###

3.代码实现

class Solution(object):
        def longestWord(self, words):
            words.sort()
            words.sort(key=len, reverse=True)
            res = []
            for word in words:
                temp = word
                i = 1
                for i in range(len(temp)):
                    if temp[:len(temp) - i] in words:
                        if i == len(temp) - 1:
                            return temp
                        continue
                    else:
                        break
            return ''
    if __name__ == '__main__':
        solution=Solution()
        words=["w","wo","wor","worl", "world"]
        print("输入字典为：",words)
        print("输出单词为：",solution.longestWord(words))

### 【例82】重复字符串匹配 难度等级★ ###

3.代码实现

class Solution:
        #参数A为字符串
        #参数B为字符串
        #返回整数
        def repeatedStringMatch(self, A, B):
            C = ""
            for i in range(int(len(B)/len(A) + 3)):
                if B in C:
                    return i
                C += A
            return -1
    if __name__ == '__main__':
        solution=Solution()
        A = "abcd"
        B = "cdabcdab"
        print("输入字符串A为：",A)
        print("输入字符串B为：",B)
        print("需要重复次数：",solution.repeatedStringMatch(A,B))

### 【例83】不下降数组 难度等级★ ###

3.代码实现

class Solution:
        #参数nums为数组
        #返回布尔类型
        def checkPossibility(self, nums):
            count = 0
            for i in range(1, len(nums)):
                if nums[i] < nums[i - 1]:
                    count += 1
                    if i >= 2 and nums[i] < nums[i - 2]:
                        nums[i] = nums[i - 1]
                    else:
                        nums[i - 1] = nums[i]
            return count <= 1
    if __name__ == '__main__':
        solution=Solution()
        nums=[4,2,3]
        print("输入为：",nums)
        print("输出为：",solution.checkPossibility(nums))

### 【例84】最大的回文乘积 难度等级★ ###

3.代码实现

class Solution:
        #参数n为整数
        #返回整数
        def largestPalindrome(self, n):
            if n==1:
                return 9
            elif n ==7:
                return 877
            elif n== 8:
                return 475
            maxNum,minNum = 10**n - 1, 10**(n-1)
            for i in range(maxNum, minNum, -1):
                candidate  = str(i)
                candidate  = candidate  + candidate [::-1]
                candidate  = int(candidate)
                j = maxNum
                while j*j > candidate :
                    if candidate  % j == 0:
                        return candidate  % 1337
                    j -= 1
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = 2
        print("输入为：",n)
        print("输出为：",s.largestPalindrome(n))

### 【例85】补数 难度等级★ ###

3.代码实现

class Solution:
        #参数num为整数
        #返回整数
        def findComplement(self, num):
            return num ^ ((1<<num.bit_length())-1)
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = 5
        print("输入为：",n)
        print("输出为：",s.findComplement(n))

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

3.代码实现

class Solution:
        #参数houses为数组
        #参数heaters为整数
        #返回整数
        def findRadius(self, houses, heaters):
            heaters.sort()
            ans = 0
            for house in houses:
                ans=max(ans,self.closestHeater(house,heaters))
            return ans
        def closestHeater(self,house,heaters):
            start = 0
            end = len(heaters) - 1
            while start + 1 < end:
                m = start + (end - start) // 2
                if heaters[m] == house:
                    return 0
                elif heaters[m] < house:
                    start = m
                else:
                    end = m
            return min(abs(house - heaters[start]), abs(heaters[end] - house))
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [1,2,3]
        m = [2]
        print("输入房间位置为：",n)
        print("输入加热器位置：",m)
        print("输出加热半径为：",s.findRadius(n,m))

### 【例87】将火柴摆放成正方形 难度等级★ ###

3.代码实现

class Solution:
        #参数nums为数组
        #返回布尔类型
        def makesquare(self, nums):
            def dfs(nums, pos, target):
                if pos == len(nums): 
                    return True
                for i in range(4):
                    if target[i] >= nums[pos]:
                        target[i] -= nums[pos]
                        if dfs(nums, pos+1, target):
                            return True
                        target[i] += nums[pos]
                return False
            if len(nums) < 4 :
                return False
            numSum = sum(nums)
            nums.sort(reverse = True)
            if numSum % 4 != 0: 
                return False
            target = [numSum / 4] * 4;
            return dfs(nums, 0, target)
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [1,1,2,2,2]
        print("输入为：",n)
        print("输出为：",s.makesquare(n))

### 【例88】可怜的猪 难度等级★ ###

3.代码实现

class Solution:
        #参数buckets为整数
        #参数minutesToDie为整数
        #参数minutesToTest为整数
        返回整数
        def poorPigs(self, buckets, minutesToDie, minutesToTest):
            pigs = 0
            while (minutesToTest / minutesToDie + 1) ** pigs < buckets:
                pigs += 1
            return pigs
    #主函数
    if __name__ == '__main__':
       s = Solution()
       n = 1000
       m = 15
       p = 60
       print("输入总桶数为：",n)
       print("输入中毒时间：",m)
       print("输入测试时间：",p)
       print("输出为：",s.poorPigs(n,m,p))

### 【例89】循环数组中的环 难度等级★ ###

3.代码实现

class Solution:
        #参数nums为数组
        #返回布尔类型
        def get_index(self, i, nums):
            n = (i + nums[i]) % len(nums)
            return n if n >= 0 else n + len(nums)
        def circularArrayLoop(self, nums):
            for i in range(len(nums)):
                if nums[i] == 0:
                    continue
                j, k = i, self.get_index(i, nums)
                while nums[k] * nums[i] > 0 and nums[self.get_index(k, nums)] * nums[i] > 0:
                    if j == k:
                        if j == self.get_index(j, nums):
                            break
                        return True
                    j = self.get_index(j, nums)
                    k = self.get_index(self.get_index(k, nums), nums)
                j = i
                while nums[j] * nums[i] > 0:
                    next = self.get_index(j, nums)
                    nums[j] = 0
                    j = next
                    
            return False
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [2,-1,1,2,2]
        print("输入为：",n)
        print("输出为：",s.circularArrayLoop(n))

### 【例90】分饼干 难度等级★ ###

3.代码实现

class Solution(object):
        def findContentChildren(self, g, s):
            #参数g为整数列表
            #参数s为整数列表
            #返回整型
            g.sort()
            s.sort()
            i, j = 0, 0
            while i < len(g) and j < len(s):
                if g[i] <= s[j]:
                    i += 1
                j += 1
            return i
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [1,2,3]
        m = [1,1]
        print("输入贪吃指数为：",n)
        print("输入饼干尺寸为：",m)
        print("输出为：",s.findContentChildren(n,m))

### 【例91】翻转字符串中的元音字母 难度等级★ ###

3.代码实现

class Solution:
        """ 参数s为字符串 返回字符串 """
        def reverseVowels(self, s):
            vowels = set(["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"])
            res = list(s)
            start, end = 0, len(res)-1
            while start <= end:
                while start <= end  and res[start] not in vowels:
                    start += 1
                while start <= end and res[end] not in vowels:
                    end -= 1
                if start <= end:
                    res[start], res[end] = res[end], res[start]
                    start += 1
                    end -= 1
            return "".join(res)
    #主函数
    if __name__ == '__main__':
        s = Solution()
        x = "hello"
        print("输入为：",x)
        print("输出为：",s.reverseVowels(x))

### 【例92】翻转字符串 难度等级★ ###

3.代码实现

class Solution:
        """ 参数s为字符串 返回字符串 """
        def reverseString(self, s):
            return s[::-1]
    #主函数
    if __name__ == '__main__':
        s = Solution()
        x = "hello"
        print("输入为：",x)
        print("输出为：",s.reverseString(x))

### 【例93】使数组元素相同的最少步数 难度等级★ ###

3.代码实现

class Solution(object):
        def minMoves(self, nums):
            #参数nums为整数列表
            #返回整数
            sumNum = sum(nums)
            minNum = min(nums)
            return sumNum - minNum * len(nums)
    #主函数
    if __name__ == '__main__':
        s = Solution()
        n = [1,2,3]
        print("输入为：",n)
        print("输出为：",s.minMoves(n))

### 【例94】加油站 难度等级★ ###

3.代码实现

#参数distance代表每个加油站的距离
    #参数apply代表每个加油站的加油量
    #参数original代表一开始有汽油
    #参数target代表需要开的距离
    #返回值是一个整数，代表至少需要加油站次数
    class Solution:
        def getTimes(self, target, original, distance, apply):
            import queue
            que = queue.PriorityQueue()
            ans, pre = 0, 0
            if(target > distance[len(distance) - 1]):
                distance.append(target)
                apply.append(0)
            cap = original
            for i in range(len(distance)):
                if(distance[i] >= target):
                    distance[i] = target
                d = distance[i] - pre
                while(cap < d and que.qsize() != 0):
                    cap += (que.get()[1])
                    ans += 1
                if (d <= cap):
                    cap -= d
                else:
                    ans = -1
                    break
                que.put((-apply[i], apply[i]))
                pre = distance[i]
                if(pre == target):
                    break
            return ans
    if __name__ == '__main__':
        target = 25
        original = 10
        distance = [10,14,20,21]
        apply = [10,5,2,4]
        solution = Solution()
        print(" 每个加油站的距离为：", distance)
        print(" 每个加油站的加油量为：", apply)
        print(" 一开始有汽油：", original)
        print(" 需要开的距离为：", target)
        print(" 至少需要经过加油站:", solution.getTimes(target, original, distance, apply))

### 【例95】春游 难度等级★ ###

3.代码实现

#参数a是小朋友组链
    #返回值是个整数，表示至少需要多少辆车
    class Solution:
        def getAnswer(self, a):
            count = [0 for i in range(0, 5)]
            for i in range(0, len(a)):
                count[a[i]] = count[a[i]] + 1
            count[1] = count[1] - count[3]
            if count[2] % 2 == 1:
                count[2] = count[2] + 1
                count[1] = count[1] - 2
            res = count[4] + count[3] + count[2] / 2
            if count[1] > 0:
                res = res + count[1] / 4
                if not count[1] % 4 == 0:
                    res = res + 1
            return int(res)
    if __name__ == '__main__':
        a = [1,2,3,4]
        solution = Solution()
        print(" 小朋友分组为：", a)
        print(" 至少需要：", solution.getAnswer(a), "辆车")

### 【例96】合法数组 难度等级★ ###

3.代码实现

#参数a是待查数组
    #返回值是一个数值，代表出现奇数次的值或者数组不合法
    class Solution:
        def isValid(self, a):
            countSet = { }
            for i in a:
                if i in countSet:
                    countSet[i] = countSet[i] + 1
                else:
                    countSet[i] = 1
            isHas = False
            for key in countSet:
                if countSet[key] % 2 == 1:
                    if isHas:
                        return -1
                    else:
                        isHas = True
                        ans = key
            if isHas:
                return ans
            return -1
    if __name__ == '__main__':
        a=[1,1,2,2,3,3,4,4,5,5]
        solution = Solution()
        print(" 数组为：", a)
        ans = solution.isValid(a)
        print(" 数组奇数个的值是:" if ans != -1 else " 数组不合法", ans)

### 【例97】删除排序数组中的重复数字 难度等级★ ###

3.代码实现

class Solution:
        #参数A: 整数列表
        #返回值：整数
        def removeDuplicates(self, A):
            B = []
            before = None
            countb = 0
            for number in A:
                if(before != number):
                    B.append(number)
                    before = number
                    countb = 1
                elif countb < 2:
                    B.append(number)
                    countb += 1
            p = 0
            for number in B:
                A[p] = number
                p += 1
            return p
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        A = [1,1,1,2,2,3]
        p = solution.removeDuplicates(A)
        print("输入：", A)
        print("输出：", p)

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

3.代码实现

class Solution:
        #参数str: 一个字符串
        #返回值: 所有排列
        def stringPermutation2(self, str):
            result = []
            if str == '':
                return ['']
            s = list(str)
            s.sort()
            while True:
                result.append(''.join(s))
                s = self.nextPermutation(s)
                if s is None:
                    break
            return result
        def nextPermutation(self, num):
            n = len(num)
            i = n - 1
            while i >= 1 and num[i - 1] >= num[i]:
                i -= 1
            if i == 0: return None
            j = n - 1
            while j >= 0 and num[j] <= num[i - 1]:
                j -= 1
            num[i - 1], num[j] = num[j], num[i - 1]
            num[i:] = num[i:][::-1]
            return num
    #主函数
    if __name__ == '__main__':
        solution = Solution()
    s1 = "aabb"
        ans = solution.stringPermutation2(s1)
        print("输入：", s1)
        print("输出：", ans)

### 【例99】全排列 难度等级★ ###

3.代码实现

class Solution:
        #参数nums: 一个整数列表
        #返回值: 排列后的列表
        def permute(self, nums):
            def _permute(result, temp, nums):
                if nums == []:
                    result += [temp]
                else:
                    for i in range(len(nums)):
                        _permute(result, temp + [nums[i]], nums[:i] + nums[i+1:])
            if nums is None:
                return []
            if nums is []:
                return [[]]
            result = []
            _permute(result, [], sorted(nums))
            return result
    #主函数
    if __name__ == '__main__':
        nums = [1,2,3]
        solution = Solution()
        result = solution.permute(nums)
        print("输入：", nums)
        print("输出：", result)

### 【例100】带重复元素的排列 难度等级★ ###

3.代码实现

class Solution:
        #参数nums: 整数数组
        #返回值: 唯一排列的列表。
        def permuteUnique(self, nums):
            def _permute(result, temp, nums):
                if nums == []:
                    result += [temp]
                else:
                    for i in range(len(nums)):
                        if i > 0 and nums[i] == nums[i-1]:
                            continue
                        _permute(result, temp + [nums[i]], nums[:i] + nums[i+1:])
            if nums is None:
                return []
            if len(nums) == 0:
                return [[]]
            result = []
            _permute(result, [], sorted(nums))
            return result
    #主函数
    if __name__ == '__main__':
        solution = Solution()
        nums = [1,2,2]
        result = solution.permuteUnique(nums)
        print("输入：", nums)
        print("输出：", result)

[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