力扣中级算法（Python）-阿里云开发者社区

1 概述

概述

这是由 LeetCode 官方推出的的经典面试题目清单，我们将题目重新整理规划，从而为大家提供更好的练习体验和帮助大家找到理想的工作。我们将题目分为以下三个部分：

初级算法 - 帮助入门

中级算法 - 巩固训练

高级算法 - 提升进阶

这一系列 LeetBook 将帮助您掌握算法及数据结构，并提高您的编程能力。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。

大多数经典面试题目都有多种解决方案。为了达到最佳的练习效果，我们强烈建议您至少将此清单里的题目练习两遍，如果可以的话，三遍会更好。

在第二遍练习时，你可能会发现一些新的技巧或新的方法。到第三遍的时候，你会发现你的代码要比第一次提交时更加简洁。如果你达到了这样的效果，那么恭喜你，你已经掌握了正确的练习方法！

记住：刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。

作者：力扣 (LeetCode)

链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/x6vk7r/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2 数组和字符串

2.1 三数之和

找出数组中和为0的三元组。

做法：转换成两数之和twoSum。固定第一个数a，问题就变成求和为-a的两数之和问题。然后可以用双指针解决。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for first in range(0,len(nums)):
            #跳过重复的数
            if first > 0 and nums[first] == nums[first-1]:
                continue
            target = -nums[first] #变成求 和为-a的twoSum问题
            third = len(nums)-1
 
            for second in range(first+1,len(nums)):
                if second> first +1 and nums[second] == nums[second-1] :
                    continue
                while second<third and nums[second] + nums[third] > target:
                    third -= 1
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first],nums[second],nums[third]])
 
        return ans

2.2 矩阵置零

容易想到用两个数组存储带0的行和列，然后将这些行和列置零。额外空间O(m+n)

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row_0 = []
        col_0 = []
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    row_0.append(i)
                    col_0.append(j)
        for i in row_0:
            for j in range(len(matrix[i])):
                matrix[i][j] = 0
        for j in col_0:
            for i in range(len(matrix)):
                matrix[i][j] = 0

如果要常数级空间O(1)，用matrix的第一行和第一列来存储为0行和列。需要额外判断第一行，第一列是否存在0

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = False #第一行存在0
        col = False #第一列存在0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    if i == 0 :
                        row = True
                    if j == 0 :
                        col = True
 
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                    
        
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if row:
            for j in range(0,len(matrix[0])):
                matrix[0][j] = 0
        if col:
            for i in range(0,len(matrix)):
                matrix[i][0] = 0

2.3 字母异位词分组

字典dict()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 思路，遍历每个元素然后排序，若是异母同位词则排序后会相同，然后把相同的进行归为一类
        res = []
        dic = dict()
        for s in strs:
            l = [s]
            temp = list(s)
            temp.sort()
            dickey = ''.join(temp)
            if dickey in dic.keys():
                dic[dickey].append(s)
            else:
                dic[dickey] = l
        for i in dic.values():
            res.append(i)
        return res

2.4 无重复字符的最长子串

滑动窗口，每次窗口的左端 i 右移一位；

关键点是：右端 r 保持，不需要回退。

例如s = "abcabcbb"，第一个循环结束时 i = 0,r = 2,最长无重复子串是abc

第二个循环时，i=1,r=2，r不需要回退，因为abc包含了bc。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ  = set()    
        maxLength,r = 0,0
        for i in range(len(s)):
            if i != 0:
                occ.remove(s[i-1])
            while r < len(s) and  s[r] not in occ:
                occ.add(s[r])
                r += 1
            if r-i > maxLength :
                maxLength = r - i
        return maxLength

2.5 最长回文子串

容易想到动态规划实现。最长回文子串

用dp[i][j] 表示从i到j的子串是否是回文子串

递推式:

dp[i][j] = s[i]== s[j] and dp[i+1][j-1]

终止条件：

i == j (length = 0), dp[i][j] = True

i+1 == j (length = 1), dp[i][j] = s[i] == s[j]

注意初始化顺序，需要按长度length顺序初始化。而不是按起始位置i。因为dp[i][j]会依赖dp[i+1][j-1]的结果。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]
        ans = ""
        for length in range(n):
            for i in range(n-length):
                j = i + length
                if length == 0:
                    dp[i][j] = True
                elif length == 1:
                    dp[i][j] = s[i]==s[j]
                else:
                    dp[i][j] = s[i]== s[j] and dp[i+1][j-1]
                if dp[i][j] and length+1 > len(ans):
                    ans = s[i:i+length+1]
        return ans

2.6 递增的三元子序列

@Cany

我们只需要在从头到尾的遍历过程中，记录第一最小值small和第二最小值mid，然后当出现一个比第二最小值大的数，就能说明存在递增三元组的！

因为 mid的存在，永远说明前面有一个比自己小的数。所以不用担心small的下标到mid的后面。

例如2315，最后small = 1 ,mid = 3 large = 5 ，这三个下标不满足i<j<k,但mid前面一定有过比它小的数（2），所以是存在递增三元子序列的。

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        
        small,mid = 2**31-1,2**31-1
        for num in nums:
            if num <= small:
                small = num
            elif num <= mid:
                mid = num
            else:
                return True
        return False

3 链表

3.1 两数相加

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head,tail = None,None
        carry = 0
        while l1 != None or l2 != None :
            n1 = l1.val if l1 != None else 0
            n2 = l2.val if l2 != None else 0
            sum_t = n1 + n2 + carry
            if head == None:
                head = ListNode(sum_t % 10) 
                tail = head
            else:
                tail.next = ListNode(sum_t % 10)
                tail = tail.next
            carry = sum_t // 10
            if l1 != None:
                l1 = l1.next
            if l2 != None:
                l2 = l2.next
        
        if carry > 0 :
            tail.next = ListNode(carry)
        return head

3.2 奇偶链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        isOdd = True
        OddHead,EvenHead = ListNode(),ListNode()
        OddCur,EvenCur = OddHead,EvenHead
        while head != None :
            if isOdd:
                OddCur.next = head
                OddCur = OddCur.next
            else:
                EvenCur.next = head
                EvenCur = EvenCur.next
            head = head.next
            isOdd = not isOdd
      
        OddCur.next = EvenHead.next
        EvenCur.next = None  #注意这里将EvenCur.next设置为None，不然就循环了
        return OddHead.next

3.3 相交链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA = 0
        lenB = 0
        curA,curB = headA,headB
        while curA != None:
            lenA += 1
            curA = curA.next
        while curB != None:
            lenB += 1
            curB = curB.next
        diff = lenA - lenB
        if diff > 0:
            while diff > 0:
                headA = headA.next
                diff -= 1
        if diff <  0:
            while diff < 0:
                headB = headB.next
                diff += 1
        
        while headA != None and headB != None:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        
        return None

4 树和图

4.1 二叉树的中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.inOrder(root, res)
        return res
    def inOrder(self, root,res):
        if root == None:
            return 
        self.inOrder(root.left,res)
        res.append(root.val)
        self.inOrder(root.right,res)

4.2 二叉树的锯齿形层次遍历

层次遍历+反转奇数层

1. # Def

4.3 从前序与中序遍历序列构造二叉树

递归。可以分成根，左，右三个子问题。

root = TreeNode(preorder[0])

#root_index = inorder.index(preorder[0])

root.left = self.buildTree(preorder[1:root_index+1],inorder[:root_index])

root.right = self.buildTree(preorder[root_index+1:],inorder[root_index+1:])

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder)>0:
            #还有节点没有生成
            root = TreeNode(preorder[0])
            #找根节点位置
            root_index = inorder.index(preorder[0])
            #根据特性递归生成左右二叉树
            root.left = self.buildTree(preorder[1:root_index+1],inorder[:root_index])
            root.right = self.buildTree(preorder[root_index+1:],inorder[root_index+1:])
        else:
            root=None
        return root

4.4 填充每个节点的下一个右侧节点指针

层序遍历，，每层的最右边的没有next节点

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
 
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root == None:
            return root
        #层序遍历
        queue = [root]
        while queue:
            length = len(queue)
            pre = queue.pop(0)
            if pre.left:
              queue.append(pre.left)
              queue.append(pre.right)
 
            for i in range(length-1):
                t = queue.pop(0)
                if t.left:
                  queue.append(t.left)
                  queue.append(t.right)
                pre.next = t
                pre = t
        return root

4.5 二叉搜索树中第K小的元素

二叉搜索数满足左<根<右，所以中序遍历得到的就是升序的数组。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.count = 0
        self.res = 0
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = k
        #inorder
        self.inorder(root)
        return self.res
        
        
    def inorder(self, root):
        if root == None:
            return
        self.inorder(root.left)
        self.count -=1
        if self.count == 0:
            self.res = root.val
        
        self.inorder(root.right)

4.6 岛屿数量

深度优先。因为连着的陆地只算一个岛屿，所以发现一个陆地后，岛屿数量+1，并将连着的陆地('1')变为水('0')

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count +=1
                    self.dfs(i,j,grid)
        return count
        
    def dfs(self, i, j, grid):
        if i>=0 and i< len(grid) and j>=0 and j<len(grid[0]) and grid[i][j] == '1':
            grid[i][j] = '0'
            self.dfs(i+1,j,grid)
            self.dfs(i-1,j,grid)
            self.dfs(i,j-1,grid)
            self.dfs(i,j+1,grid)

5 回溯算法

回溯框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
 
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

5.1 电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        res = []
        if len(digits) == 0 :
            return res
        self.backtrack(res, phoneMap, digits, 0,  [])
        return res
    
    #深度优先
    def backtrack(self, res, phoneMap, digits,index, st):
        if index == len(digits):
            res.append("".join(st))
        else:
            digit = digits[index]
            letters = phoneMap.get(digit)
            for letter in letters:
                st.append(letter)
                self.backtrack(res, phoneMap, digits, index+1, st)
                st.pop(index)

5.2 括号生成

有限制条件的回溯，因为数据量小，也可以先无限制条件生成括号，在判断是否合法。

class Solution:
    
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.backtrack(n,0,0,[],res)
        return res
    
    def backtrack(self,n,left,right,tmp,res):
        if right == n:
            res.append(''.join(tmp))
            return
        if left< n:
            tmp.append('(')
            self.backtrack(n,left+1,right,tmp,res)
            tmp.pop()
        if right<left:
            tmp.append(')') 
            self.backtrack(n,left,right+1,tmp,res)
            tmp.pop()

5.3 全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(nums,[],res,len(nums))
        return res
 
    def backtrack(self,choices,tmp, res,n):
        if len(tmp) == n:
            res.append(tmp.copy())
            return
 
        for i in range(len(choices)):
            tmp.append(choices[i])
            choices.pop(i)  #
            self.backtrack(choices,tmp,res,n)
            choices.insert(i,tmp.pop())

5.4 子集

除了回溯也可以用位运算&做

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(nums,0,[],res)
        return res
 
    def backtrack(self,nums,start,tmp, res):
        res.append(tmp.copy())
        for i in range(start,len(nums)):
            tmp.append(nums[i])
            self.backtrack(nums,i+1,tmp,res)
            tmp.pop()

5.5 单词搜索

对每个棋子使用dfs。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board,word,i,j,0):
                    return True
        return False
 
    def dfs(self, board, word, i,j,index):
        if i >= len(board) or i < 0 or j >= len(board[0]) or j < 0 or board[i][j] != word[index]:
            return False
        if index == len(word)-1:
            return True
        
        tmp = board[i][j]
        board[i][j] = '.'
        res = self.dfs(board,word,i+1,j,index+1) or self.dfs(board,word,i-1,j,index+1) or\
              self.dfs(board,word,i,j+1,index+1) or self.dfs(board,word,i,j-1,index+1)
        board[i][j] = tmp
        return res

6 排序和搜索

6.1 颜色分类

由于只有3种元素，可以直接统计频率，然后重写nums。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        a = [0,0,0]
        for i in nums:
            a[i] += 1
        index = 0
        for i in range(len(a)):
            for j in range(a[i]):
                nums[index] = i
                index +=1

6.2 前k个高频元素

使用字典存频率，然后排序（sort很简单，也可以最小堆heapq）。

 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        mmap = dict()
        for num in nums:
            mmap[num] =  mmap[num]+1 if num in mmap else 1
        sort = sorted(zip(mmap.values(),mmap.keys()))
        sort.reverse()
        res = []
        for i in range(k):
            res.append(sort[i][1])
        return res

6.3 数组中的第K个最大元素

最大堆/直接排序

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        #res = heapq.nlargest(k,nums)
        #return res[-1]
        return sorted(nums)[-k]

6.4 寻找峰值

虽然不是有序数组，但问题的形式可以用二分法。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        length = len(nums)
        if  length == 1:
            return 0
        if  nums[0]>nums[1]:
            return 0
        if  nums[length-1]>nums[length-2]:
            return length-1 
        #二分查找
      
        left = 0
        right = length-1
        mid = (left+right)//2
        while left<right:
            mid = (left+right)//2
 
            if nums[mid]>nums[mid-1] and nums[mid]>nums[mid+1]:
                return mid
            elif nums[mid]<nums[mid-1]:
                right = mid
            elif nums[mid]<nums[mid+1]:
                left = mid
        return mid

6.5 在排序数组中查找元素的第一个和最后一个位置

遍历

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        if length == 0:
            return [-1,-1]
        first = -1
        for i in range(length):
            if nums[i] == target:
                first = i
                break
        last = -1 
        for i in range(length-1,first-1,-1):
            if nums[i] == target:
                last = i  
                break
        return first,last

二分

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        if length == 0:
            return [-1,-1]
        # first 
        first = -1 
        left = 0
        right = length-1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] == target:
                first = mid
                right = mid-1
            elif nums[mid] > target :
                right = mid-1
            elif nums[mid]< target:
                left = mid+1
        #last 
        last = -1 
        left = first
        right = length-1
        mid = (left+right)//2
        while left <= right:
            mid = (left+right)//2
            if nums[mid] == target:
                left = mid+1
                last = mid
            elif nums[mid]< target:
                left = mid+1
            elif nums[mid] > target :
                right = mid-1
        return first,last

二分，但是简化了一下

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        if length == 0 :
            return [-1,-1]
        first = -1  
        left,right = 0,length-1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] >= target:
                right = mid-1
            elif nums[mid]< target:
                left = mid+1
        first = left
        if first not in range(length) or nums[first]!= target:
            return[-1,-1]
        #last 
        last = -1 
        left, right = first, length-1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] <= target:
                left = mid+1
            elif nums[mid] > target :
                right = mid-1
        last = right
        return first,last

6.6 合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        length = len(intervals)
        if length <= 1:
            return intervals
        intervals.sort()
        tmp = intervals[0]
 
        res = []
        for num in intervals:
            if num[0] <= tmp[1] :
                tmp =[min(tmp[0],num[0]), max(tmp[1],num[1])]
            else:
                res.append(tmp)
                tmp = num
        print("res",res)
        if len(res)==0 or res[-1][1] < intervals[-1][0]:
            res.append(tmp) 
        return res

6.7 搜索旋转排序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # step1 找旋转点
        res = -1
        length = len(nums)
        if length == 0:
            return -1
        if length == 1:
            return -1 if nums[0] != target else 0
        left, right = 0, length - 1
        zz = length - 1
        mid = (left + right) // 2
        while mid != left:
            mid = (left + right) // 2
            if nums[mid] > nums[left]:
                left = mid
            else :
                right = mid
        zz = right
        print("zz", zz)
        # step2 二分查找
        if target >= nums[0]:
            left, right = 0, zz - 1
        else:
            left, right = zz, length - 1
 
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                res = mid
                break
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return res

6.8 搜索二维矩阵 II

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        low_row = 0
        high_row = row-1
        while low_row < row and matrix[low_row][-1] < target  :
            low_row += 1
        while  high_row > 0 and matrix[high_row][0] > target :
            high_row -= 1
        for i in range(low_row, high_row+1):
            if self.b_search(matrix[i],target):
                return True
        return False
    
    def b_search(self, nums, target):
        left = 0
        right = len(nums)-1
        while left <= right :
            mid = (left+right)//2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                left = mid +1
            elif nums[mid] > target:
                right = mid-1
        return False

7 动态规划

7.1 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length == 1:
            return True
        #dp[i]：i位置能走的最远距离
        dp = [0 for _ in range(length )] 
        for i in range(len(nums)):
            dp[i] = max(dp[i-1]-1,nums[i])
            if i+dp[i] >= length-1:
                return True
            if dp[i] == 0:
                return False

7.2 不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n)] for _ in range(m)] 
        for row  in range(1,m):
            for col in range(1,n):
                dp[row][col] = dp[row-1][col] + dp[row][col-1]
        
        return dp[m-1][n-1]

7.3 零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

7.4 最长上升子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        length = len(nums)
        dp = [1 for i in range(len(nums))]
        for i in range(length):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j]+1, dp[i])
        return max(dp)

8 设计问题

8.1 二叉树的序列化与反序列化

前序遍历

class Codec:
 
    def serialize(self, root):
 
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        res = []
        def preorder(root):
            if not root:
                res.append('#')
                return
            res.append(str(root.val))
            preorder(root.left)
            preorder(root.right)
 
        preorder(root)
        return ','.join(res)
 
        return res
 
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        arr = data.split(',')
        arr.reverse()
        def preorder(arr):
            if not arr:
                return
            if arr[-1] == '#':
                arr.pop()
                return
            root  = TreeNode(int(arr.pop()))
            root.left = preorder(arr)
            root.right = preorder(arr)
            return  root
        return  preorder(arr)

8.2 常数时间插入、删除和获取随机元素

使用字典记录元素

import random
 
 
class RandomizedSet:
 
    def __init__(self):
        self.arr = []
        self.length = 0
        self.mdict = {}
 
 
    def insert(self, val: int) -> bool:
        if val not in self.mdict:
            self.arr.append(val)
            self.mdict[val] = self.length
            self.length += 1
            return True
        else:
            return False
 
 
    def remove(self, val: int) -> bool:
        if val in self.mdict:
            index = self.mdict[val]
            del self.mdict[val]
            self.arr[index] = self.arr[-1]
            self.mdict[self.arr[-1]] = index
            self.arr.pop(-1)
            self.length -= 1
            return True
        else:
            return False
 
 
    def getRandom(self) -> int:
        return  random.choice(self.arr)
 
 
 
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

9 数学

9.1 快乐数

class Solution:
    def isHappy(self, n: int) -> bool:
        def getn2(n):
            sum_n2 = 0
            while n:
                sum_n2 +=(n %10)**2
                n //=10
            return sum_n2
        d  = {}
        while n != 1 :
            if n in d:
                return False
            else:
                d[n] = True
                n = getn2(n)
        return True

9.2 阶乘后的零

阶乘中结果中的0是 2*5产生的，所以问题转化成求有多少个5。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        res = 0
        while n>= 5:
            n //=5
            res += n
        return res

9.3 Excel表列序号

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        res = 0
        for col in columnTitle:
            res *= 26
            res += ord(col) - ord('A')+1 #ord获取字符ascii值
            print(col)
        return res

9.4 Pow(x, n)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        return x**n

9.5 x 的平方根

二分查找

class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x //2 if x >= 4 else x
        mid = (left+right)//2
        while left <= right:
            if  mid*mid <= x and (mid+1)*(mid+1) >x:
                return mid
            elif mid*mid > x:
                right = mid-1
            elif (mid+1)*(mid+1) <= x:
                left = mid+1
            mid = (left+right)//2
 
        return mid

9.6 两数相除

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return 0
        if dividend == -2**31 and divisor == -1: #-inf
            return 2**31-1 
        negative = (dividend ^ divisor) < 0 #符号位（最高位）不同，异或结果<0
        t = abs(dividend)
        d = abs(divisor)
        result = 0
        #转换成减法，利用移位的高效率
        for i in range(31,-1,-1):
            if (t>>i) >= d:
                result += 1<<i
                t -= d<<i
        return result if not negative else - result

9.7 分数到小数

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator % denominator == 0:
            return str(numerator//denominator)
        s= []
        if numerator^denominator < 0:
            s.append('-')
        
        #整数
        numerator = abs(numerator)
        denominator = abs(denominator)
        intPart = numerator//denominator
        s.append(str(intPart))
        s.append('.')
 
        #小数
        indexMap = {}
        remainder = numerator % denominator
        while remainder and remainder not in indexMap:
            indexMap[remainder] = len(s)
            remainder *= 10
            s.append(str(remainder//denominator))
            remainder %= denominator
        if remainder:
            insertIndex = indexMap[remainder]
            s.insert(insertIndex,'(')
            s.append(')')
        
        return ''.join(s)

10 其它

10.1 两整数之和

class Solution:
    def getSum(self, a: int, b: int) -> int:
        #return sum([a,b])
        #位运算 a^b 实现无进位加法，在用a&b，并<< 获得进位
        if not b:
            return a
        return add(a^b,(a&b)<<1)

10.2 逆波兰表达式求值

栈

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        res = 0
        for i in tokens:
            if i == '+' :
                a = stack.pop()
                b = stack.pop()
                stack.append(b+a)
            elif i == '-' :
                a = stack.pop()
                b = stack.pop()
                stack.append(b-a)
            elif i == '*' :
                a = stack.pop()
                b = stack.pop()
                stack.append(b*a)
            elif i == '/':
                a = stack.pop()
                b = stack.pop()
                stack.append(int(b/a))
            else :
                stack.append(int(i))
        return int(stack[-1])

10.3 多数元素

collection.Counter()

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        length = len(nums)
        freq = collections.Counter(nums)
    
        for k,v in freq.items():
            if v > length//2:
                return k

10.4 任务调度器

分析见官方题解。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks)
 
        maxExc = max(freq.values())
 
        maxCount = sum(1 for v in freq.values() if v == maxExc)
 
        return max((n+1)*(maxExc-1)+maxCount, len(tasks))

力扣中级算法（Python）