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

2021-05-29 20:15:34LanceLee数据爬虫193

- N +

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

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

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

第一章难度等级★

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

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

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

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

3.代码实现

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

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

3.代码实现

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

【例12】点积难度等级★

3.代码实现

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

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

3.代码实现

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

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

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

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

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

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

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

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

【例68】报数难度等级★

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

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

.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

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

3.代码实现

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

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

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

3.代码实现

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

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

【例85】补数难度等级★

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

【例95】春游难度等级★

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

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

3.代码实现

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

本文版权归趣KUAI排www.SEOguruBlog.com 所有,如有转发请注明来出,竞价开户托管,seo优化请联系QQ→61910465

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

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

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

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

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

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

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

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

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

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

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

【例12】点积 难度等级★

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【例68】报数 难度等级★

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【例12】点积难度等级★

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【例68】报数难度等级★

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

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

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

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

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

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

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

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

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

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

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

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