<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    python3的各種經典案例,總共299個案例,直接可以運行(前:100個案例)

    一. python3的各種經典案例,總共299個案例,直接可以運行(前:100個案例)

    二. python3的各種經典案例,總共299個案例,直接可以運行(中:100個案例)

    三. python3的各種經典案例,總共299個案例,直接可以運行(后:99個案例)

    第一章 難度等級★

    【例1】反轉一個3位整數 難度等級★

    3.代碼實現

    class Solution:
    #參數number: 一個三位整數
        #返回值: 反轉后的數字
        def reverseInteger(self, number):
            h = int(number/100)
            t = int(number%100/10)
            z = int(number%10)
            return (100*z+10*t+h)
    #主函數
    if __name__ == '__main__':
        solution = Solution()
        num = 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)
    
    相關推薦
    ??2020 CSDN 皮膚主題: 創作都市 設計師:CSDN官方博客 返回首頁
    多乐彩