数据结构与算法（实践篇）

代码基于Python，简单易读

数组

O(1)插入删除元素

遇到需要逐个遍历判断并删除集合内元素的情况，可以逆序进行遍历，这样就能避免删除后元素减少而越界
删除一样的元素：

def removeDuplicates(self, nums: List[int]) -> int:
    for i in range(len(nums) - 1, 0, -1):
        if nums[i] == nums[i - 1]:
            del nums[i]
    return len(nums)

注意del函数比较耗时，所以有更好的办法最好不用

常数时间插入删除元素：

class RandomizedSet:

    def __init__(self):
        self.dict_ = {}
        self.nums = []

    def insert(self, val: int) -> bool:
        if val not in self.dict_:
            self.dict_[val] = len(self.nums)
            self.nums.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        if val in self.dict_:
            index = self.dict_[val]
            self.nums[index] = self.nums[-1]
            self.dict_[self.nums[-1]] = index
            self.nums.pop()
            del self.dict_[val]
            return True
        return False

    def getRandom(self) -> int:
        return choice(self.nums)

使用栈和队列

# 都可以这样定义,前后插入删除时间复杂度O(n)
s = [] #栈
q = [] #队列
s.append(1)#1入栈
q.append(1)#1入队
s.pop()#出栈
q.pop(0)#出队

# 时间复杂度较低的方法,这是一个双向链表，可做栈和队列
# 前后插入删除的时间复杂度为O(1)
s = collections.deque()
a.append(1)  #入栈或入队
s.popleft()  #出队
s.popright() #出栈

抵消重复元素（线性时间复杂度），寻找单一元素

抵消重复的元素的时候可以用异或
找出唯一一个不重复的元素，重复的元素仅重复两次：

def singleNumber(self, nums: List[int]) -> int:
    s = 0
    for i in range(len(nums)):
        s = s ^ nums[i]
    return s

哈希表寻找单一元素
先遍历一次数组，把名称记为键，重复次数记为值。第二次遍历检查值为1的

class Solution:
    def firstUniqChar(self, s: str) -> int:
        a = {}
        for i in range(len(s)):
            if s[i] in a:
                a[s[i]] += 1
            else:
                a[s[i]] = 1

        for i in range(len(s)):
            if a[s[i]] == 1:
                return i
        return -1

只寻找键或值

a = {}

for i in a.keys()

for i in a.values()

判断数字是否在数组中

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            res = target-nums[i]
            if res in nums[i+1:]:  
                return [i, nums[i+1:].index(res)+i+1]

使用哈希表存储数据（查询速度快，空间换时间）

哈希表在python中为{},判断键是否在哈希表中方法和数组一致

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        mp = {}
        for i in range(n):
            t = target - nums[i]
            if t in mp:
                return [mp[t], i]
            # 存放nums[i]
            mp[nums[i]] = i
        return []

位运算检查重复元素

位运算运行速度极快，因此用位运算存储数据和检查重复很实用

shift = 1 << 8   # 如果第一位表示1，这里左移8位存一个9进去
if((line[i] & shift) > 0   # 如果之前的数据与shift重复，则与不为0
line[i] |= shift  # 把数据保存

检查数独是否有效（不检查是否有解）:

def isValidSudoku(self, board: List[List[str]]) -> bool:
    shift = 0
    line = [0,0,0,0,0,0,0,0,0]
    column = [0,0,0,0,0,0,0,0,0]
    cell = [0,0,0,0,0,0,0,0,0]
    for i in range(9):
        for j in range(9):
            if(board[i][j] == '.'): continue
            shift = 1 << int(int(board[i][j]) - 1)
            k = int(int(i / 3) * 3 + j / 3)
            if((line[i] & shift) > 0 or (column[j] & shift) > 0 or (cell[k] & shift) > 0):
                return False
            line[i] |= shift
            column[j] |= shift
            cell[k] |= shift
    return True

矩阵的旋转

矩阵旋转90度相当于上下翻转后对角线翻转

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        l = len(matrix)
        for i in range(int(l/2)):
            for j in range(l):
                temp = matrix[i][j]
                matrix[i][j] = matrix[l-i-1][j]
                matrix[l-i-1][j] = temp
        for i in range(l):
            for j in range(l):
                if i > j:
                    temp = matrix[i][j]
                    matrix[i][j] = matrix[j][i]
                    matrix[j][i] = temp

数组数字和字符串排序

调用API的两种方式

st = "asldfjslkdjf"
# 第一种
st = sorted(st)
# 第二种
st.sort()

自己写的话参考快速排序

倒序

数组倒序：

s[:] = s[::-1]

数字倒序
假设输入数字c

res = 0
while c != 0:
    res = res * 10 + c % 10
    c = int(c / 10)

三数之和，排序加双指针

我的遍历和双指针写法，时间复杂的较高：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        answer = []
        for i in range(len(nums)-2):
            begin = i + 1
            end = len(nums) - 1
            while  begin < end:
                if nums[begin] + nums[end] == -nums[i]:
                    if [nums[i],nums[begin],nums[end]] not in answer:
                        answer.append([nums[i],nums[begin],nums[end]])
                    begin += 1
                    end -= 1
                elif nums[begin] + nums[end] < -nums[i]:
                    begin += 1
                elif nums[begin] + nums[end] > -nums[i]:
                    end -= 1
        return answer

去重优化写法，不要用not in：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if(not nums or n<3):    return []
        nums.sort()
        answer = []
        for i in range(n-2):
            if nums[i]>0:  return answer
            if i!=0 and nums[i] == nums[i-1]: continue
            begin = i + 1
            end = n - 1
            while  begin < end:
                if nums[begin] + nums[end] == -nums[i]:
                    answer.append([nums[i],nums[begin],nums[end]])
                    while begin < end and nums[begin] == nums[begin+1]:
                        begin += 1
                    while begin < end and nums[end] == nums[end-1]:
                        end -= 1
                    begin += 1
                    end -= 1

                elif nums[begin] + nums[end] < -nums[i]:
                    begin += 1
                else:
                    end -= 1
        return answer

字典存数据方法，用了二分查找，耗时是上面的五十分之一：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        counts = {}
        for i in nums:
            counts[i] = counts.get(i, 0) + 1
        nums = sorted(counts)
        for i, num in enumerate(nums):
            if counts[num] > 1:
                if num == 0:
                    if counts[num] > 2:
                        ans.append([0, 0, 0])
                        continue
                else:
                    if -num * 2 in counts:
                        ans.append([num, num, -2 * num])
            if num < 0:
                two_sum = -num
                left = bisect.bisect_left(nums, (two_sum - nums[-1]), i + 1)
                for j in nums[left: bisect.bisect_right(nums, (two_sum // 2), left)]:
                    k = two_sum - j
                    if k in counts and k != j:
                        ans.append([num, j, k])

        return ans

除自身以外的乘积

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = len(nums)
        ans = [1] * l
        currentleft = 1
        currentright = 1
        for i in range(l):
            ans[i] *= currentleft
            currentleft *= nums[i]
            ans[l-1-i] *= currentright
            currentright *= nums[l-1-i]
        return ans

螺旋矩阵

我的方法：用hashset存格子

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        a = set()
        row = 0
        column = 0
        thisposition = (row,column)
        outputs = [matrix[0][0]]
        a.add((0,0))
        islast = False
        while len(outputs) < len(matrix) * len(matrix[0]):
            if not islast:
                if column + 1 < len(matrix[0]) and (row,column+1) not in a:
                    column += 1
                elif row + 1 < len(matrix) and (row+1,column) not in a:
                    row += 1
                elif column - 1 >= 0 and (row,column-1) not in a:
                    column -= 1
                elif (row-1,column) not in a:
                    row -= 1
                    islast = True
            else:
                if (row-1,column) not in a:
                    row -= 1
                else:
                    islast = False
                    continue
            outputs.append(matrix[row][column])
            a.add((row,column))
        return outputs

方法二：存行和列开始和结束位置，性能更优

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rowbegin = 0
        columnbegin = 0
        rowend = len(matrix) - 1
        columnend = len(matrix[0]) - 1
        outputs = [matrix[0][0]]
        state = 0  # 右，下，左，上
        row = 0
        column = 0
        while len(outputs) < len(matrix) * len(matrix[0]):
            if state == 0:
                if column + 1 <= columnend:
                    column += 1
                else:
                    state += 1
                    rowbegin += 1
                    continue
            elif state == 1:
                if row + 1 <= rowend:
                    row += 1
                else:
                    state += 1
                    columnend -= 1
                    continue
            elif state == 2:
                if column - 1 >= columnbegin:
                    column -= 1
                else:
                    state += 1
                    rowend -= 1
                    continue
            elif state == 3:
                if row - 1 >= rowbegin:
                    row -= 1
                else:
                    state = 0
                    columnbegin += 1
                    continue
            outputs.append(matrix[row][column])

        return outputs

字符串

字符串保留字母数字、转换为大小写、处理空白

s = "saldjfgs1324343"
s.upper() # 大写
s.lower() # 小写
for i in s:
    if i.isdigit():  # 判断是否为数字

    if i.isalpha():  # 判断是否为字母

s = s.strip()  # 处理前后空白

合理利用截断字符串的方式判断相同前缀

def longestCommonPrefix(self, strs: List[str]) -> str:
       ans = strs[0]
       for i in range(1,len(strs)):
           while (ans != strs[i][0:len(ans)]):
               ans = ans[:-1]
       
       return ans

字典解决两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d  = {}
        for i in range(len(nums)):
            if target - nums[i] in d:
                return [i,d[target - nums[i]]]
            d[nums[i]] = i

defaultdict分类问题

将 字母异位词 组合在一起。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
defaultdict 是 dict 的一个子类。通常 Python 中字典(dict)这种数据类型是通过键值对来存取的，当索引一个不存在的键时，就会引发 keyerror 异常。那么，defaultdict 就可以解决这个问题，它可以实现为不存的键值返回一个默认值。defaultdict(list),会构建一个默认value为list的字典
defaultdict接受一个工厂函数作为参数，这个factory_function可以是list、set、str等等，作用是当key不存在时，返回的是工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 利用字典
        dict_ = defaultdict(list)
        for i in strs:
            key = ''.join(sorted(list(i)))  # 可简化为str(sorted(i))
            dict_[key].append(i)
        return list(dict_.values())

无重复最长子串

双指针我的数组存储写法：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxlen = 0
        begin = 0
        end = 0
        strs = []
        while end < len(s):
            end += 1
            while s[end-1] in strs:
                strs.pop(0)
                begin += 1
            strs.append(s[end-1])
            if len(strs) > maxlen:
                maxlen = len(strs)
        return maxlen

字典存储（速度快）：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        match = {} # 每个字符的最大位置
        maxx = 0 # 最长长度
        left = 0 # 无重复字符的最小位置
        for i in range(len(s)):
            if s[i] in match:
                left = max(match[s[i]]+1, left)
            match[s[i]] = i
            maxx = max(maxx, i-left+1) # 以当前位置为结尾的最长无重复字符的长度
        return maxx

最长回文子串

三种解法，暴力判断每个子串，两边扩散法，动态规划，两边扩散法速度最快

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == "": return ""
        maxlen = 1
        maxstr = s[0]
        # # 暴力解法
        # for i in range(len(s)):
        #     for j in range(len(s)-1,i,-1):
        #         if j-i+1 > maxlen and self.judge(s[i:j+1]):
        #             maxlen = j-i+1
        #             maxstr = str(s[i:j+1])
        # return maxstr
        #两边扩散法
        for i in range(1,len(s)):
            if (len(s)-i)*2+1 <= maxlen: break
            begin = i
            end = i
            while begin-1 >= 0 and s[begin-1] == s[begin]:
                begin -= 1
            while end+1 <= len(s)-1 and s[end+1] == s[end]:
                end += 1
            while begin >= 0 and end <= len(s)-1:
                if begin-1 < 0 or end+1 > len(s)-1:
                    if maxlen < end - begin + 1:
                        maxlen = end - begin + 1
                        maxstr = s[begin:end+1]
                    break
                begin -= 1
                end += 1
                if s[begin] != s[end]:
                    if maxlen < end - begin - 1:
                        maxlen = end - begin - 1
                        maxstr = s[begin+1:end]
                    break
        return maxstr

        # # 动态规划
        # if len(s) < 2:
        #     return s
        # start = 0
        # length = len(s)
        # # 创建二维数组
        # dp = [([False] * length) for i in range(length) ]
        # for right in range(1,length):
        #     for left in range(right):
        #         if (s[left] != s[right]):
        #             continue
        #         if  right == left:
        #             dp[left][right] = True
        #         elif right - left <= 2:
        #             dp[left][right] = True
        #         else :
        #             dp[left][right] = dp[left + 1][right - 1]
                
        #         if dp[left][right] and right - left + 1 > maxlen:
        #             maxlen = right - left + 1
        #             start = left
        # return s[start:start+maxlen]

    def judge(self,s:str) -> bool:
        if len(s) == 1: return True
        begin = 0
        end = len(s) - 1
        while end > begin:
            if s[begin] != s[end]:
                return False
            begin += 1
            end -= 1
        return True

链表

链表中每一个节点为一个对象，对象中包含两个成员变量，第一个是val，代表链表的值，第二个是next，它指向下一个节点，是下一个节点对象的引用。

删除节点

只知道一个节点的情况：

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

反转链表

普通方法：

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    newHead = None
    while head != None:
        temp = head.next
        head.next = newHead
        newHead = head
        head = temp
    return newHead

1
使用栈解决:
一定要注意让尾巴节点next指针为空，否则将形成环：

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    if head == None:
        return None
    a = []
    while head != None:
        a.append(head)
        head = head.next
    head = a.pop()
    b = head
    while len(a) > 0:
        n = a.pop()
        b.next = n
        b = n
    b.next = None

        return head

合并两个有序链表

我的答案，全部放入数组中进行排序后重新生成链表：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 == None:
            return list2
        elif list2 == None:
            return list1

        if list1.val > list2.val:
            head = list2
        else:
            head = list1
        a = []
        while list1 != None:
            a.append(list1)
            list1 = list1.next
        while list2 != None:
            a.append(list2)
            list2 = list2.next
        a = sorted(a,key=lambda x:x.val)
        h = a.pop(0)
        while len(a)> 0:
            next = a.pop(0)
            h.next = next
            h = next
        return head

递归：

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if list1 is None: return list2
    if list2 is None: return list1
    if list1.val <= list2.val:
        list1.next = self.mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = self.mergeTwoLists(list1,list2.next)
        return list2

判断链表是否有环

我的直观解法：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        a = []
        while head != None:
            if head not in a:
                a.append(head)
                head = head.next
            else:
                return True
        return False

快慢指针：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        head1 = head
        head2 = head
        while head1 != None and head2 != None and head2.next != None:
            head1 = head1.next
            head2 = head2.next.next
            if head1 == head2:
                return True
        return False

二叉树

序列化和反序列化

前序遍历，时间较长

class Codec:
    def serialize(self, root):
        def xianxu(root):
            if root == None: 
                self.a.append("None")
            else:
                self.a.append(str(root.val))
                xianxu(root.left)
                xianxu(root.right)
            
        self.a = []
        xianxu(root)
        return ",".join(self.a)

    def deserialize(self, data):
        def reserialize(array):
            if not array: return
            if array[0] == "None":
                array.pop(0)
                return
            head = TreeNode(int(array.pop(0)))
            head.left = reserialize(array)
            head.right = reserialize(array)
            return head

        a = data.split(",")
        return reserialize(a)

层序遍历，使用collection.deque，时间大大减少；

class Codec:
    def serialize(self, root):
        # 层序遍历
        q = collections.deque()
        a = []
        q.append(root)
        while q:
            node = q.popleft()
            if node == None:
                a.append("None")
            else:
                a.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
        return ",".join(a)


    def deserialize(self, data):
        # 层序遍历
        data = data.split(",")
        if not data or data[0] == "None":
            return None
        q = collections.deque()
        head = TreeNode(int(data[0]))
        q.append(head)
        index = 1
        while q:
            node = q.popleft()
            if node != None:
                if data[index] != "None":
                    node.left = TreeNode(int(data[index]))                    
                    q.append(node.left)
                index += 1
                if data[index] != "None":
                    node.right = TreeNode(int(data[index]))
                    q.append(node.right)
                index += 1
        return head

最大深度

自己写的直观递归：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        leftdepth = 1
        rightdepth = 1
        if root.left != None:
            leftdepth += self.maxDepth(root.left)            
        if root.right != None:
            rightdepth += self.maxDepth(root.right)
        
        return max(leftdepth,rightdepth)

一行递归：

return 0 if root == None else (max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1)

用队列一层层遍历：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        q = []
        count = 0
        q.append(root)
        while len(q) > 0:
            # 重新计算下一层的节点个数
            l = len(q)
            while l > 0:
                a = q.pop(0)
                l = l - 1
                if a.left != None:
                    q.append(a.left)
                if a.right != None:
                    q.append(a.right)
            # 这一层的元素遍历完毕
            count += 1
        return count

验证二叉搜索树

中序递归

class Solution:
    def __init__(self):
        self.prev = None
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 中序遍历递归
        if root == None:
            return True

        if not self.isValidBST(root.left):
            return False
        if self.prev != None and self.prev.val >= root.val:
            return False
        self.prev = root
        if not self.isValidBST(root.right):
            return False

        return True

中序非递归，利用栈做存储

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        s = []
        s.append(root)
        pre = None
        while len(s) > 0:
            while root.left != None:
                s.append(root.left)
                root = root.left

            a = s.pop()
            if pre != None and a.val <= pre.val:
                return False
            pre = a
            
            if a.right != None:
                root = a.right
                s.append(root)

        return True

直接递推

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        minn = -(1<<32)
        maxx = 1<<32
        return self.evaluate(root,minn,maxx)

    def evaluate(self,root,minn,maxx):
        if root == None:
            return True
        if root.val <= minn or root.val >= maxx:
            return False

        return self.evaluate(root.left,minn,root.val) and self.evaluate(root.right,root.val,maxx)

对称二叉树

递归法，从上往下一对对遍历：

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.bijiao(root.left,root.right)
        

    def bijiao(self,left,right):
        if left == None and right == None:
            return True
        if left == None or right == None or left.val != right.val:
            return False
        return self.bijiao(left.left,right.right) and self.bijiao(left.right,right.left)

非递归法，使用队列的方式，两两添加进队列中：

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if root.left == None and root.right == None:
        return True
    q = []
    q.append(root.left)
    q.append(root.right)
    while len(q) > 0:
        a = q.pop(0)
        b = q.pop(0)
        if a == None and b == None:
            continue
        if (a != None and b == None) or (a == None and b != None):
            return False
        if a.val != b.val:
            return False
        q.append(a.left)
        q.append(b.right)
        q.append(a.right)
        q.append(b.left)
    return True
            

层序遍历

参考深度检测中的代码可以进行层序遍历,这其实是宽度优先搜索：

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = []
        l = []
        q.append(root)
        while len(q) > 0:
            thisfloor = []
            for i in range(len(q)):
                a = q.pop(0)
                if a == None: continue
                thisfloor.append(a.val)
                q.append(a.left)
                q.append(a.right)
            if thisfloor != []:
                l.append(thisfloor)
        return l

填充右侧指针节点：

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root == None: return None
        q = []
        q.append(root)
        while len(q) > 0:
            lastone = None
            for i in range(len(q)):
                node = q.pop(0)
                if node.left != None: q.append(node.left)
                if node.right != None: q.append(node.right)
                if lastone != None: lastone.next = node
                lastone = node
        return root

不用队列的方式（每个节点右指针赋值）：

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root == None or root.left == None: return root
        origin = root
        head = root
        while head.left != None:
            lastone = None
            headn = head
            while headn != None:
                thisone = headn.left
                headn.left.next = headn.right
                if lastone != None:
                    lastone.next = headn.left
                lastone = headn.right
                headn = headn.next
            head = head.left
        return origin

数组构建平衡二叉树

要求每个节点左右子树高度差不超过1
递归法：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # nums = sorted(nums)
        headindex = int(len(nums) / 2) 
        head = TreeNode(nums[headindex])
        if headindex > 0:
            head.left = self.sortedArrayToBST(nums[:headindex])
        if headindex+1 < len(nums):
            head.right = self.sortedArrayToBST(nums[headindex+1:])
        return head

中序遍历

中序遍历相当于左根右

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        outputs = []
        self.bianli(root,outputs)
        return outputs

    def bianli(self,root,outputs):
        if root == None: return
        self.bianli(root.left,outputs)
        outputs.append(root.val)
        self.bianli(root.right,outputs)

递归法

前序和中序遍历中得到二叉树

递归方法

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(inorder) == 0: return None
        #if len(inorder) == 1: return TreeNode(inorder[0])
        head = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        head.left = self.buildTree(preorder[1:index+1],inorder[:index])
        head.right = self.buildTree(preorder[index+1:],inorder[index+1:])

        return head

电话号码的数字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

这里可以看成是一颗n叉树，有3到4个子节点，返回所有的叶子节点的值，可以用广度搜索（层序遍历）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dict_ = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        if len(digits) == 0: 
            return []
        elif len(digits) == 1: 
            return list(dict_[digits[0]])  
        # n叉数层序遍历
        q = list(dict_[digits[0]])
        a = 1
        while len(q) != 0:
            # 遍历一层
            for i in range(len(q)):
                out = q.pop(0)
                for j in range(len(dict_[digits[a]])):
                    q.append(out+dict_[digits[a]][j])
            a += 1
            if a == len(digits):
                return q

图

岛屿数量

给定数组如
a = [[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]]
1代表陆地，0代表海水，求岛屿数量，被上下左右围绕的一整块陆地为一个岛屿
方法是采用深度优先搜索，搜索到1后把1和相邻的1都置0，完成一个岛屿的搜索，再去搜索下一个岛屿

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


    def zhiling(self,grid,row,column):
        if row > 0 and grid[row-1][column] == '1':
            grid[row-1][column] = '0'
            self.zhiling(grid,row-1,column)
        if column > 0 and grid[row][column-1] == '1':
            grid[row][column-1] = '0'
            self.zhiling(grid,row,column-1)
        if row < len(grid)-1 and grid[row+1][column] == '1':
            grid[row+1][column] = '0'
            self.zhiling(grid,row+1,column)
        if column < len(grid[0])-1 and grid[row][column+1] == '1':
            grid[row][column+1] = '0'
            self.zhiling(grid,row,column+1)

回溯算法

电话号码的数字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []

        phone = {'2':['a','b','c'],
                 '3':['d','e','f'],
                 '4':['g','h','i'],
                 '5':['j','k','l'],
                 '6':['m','n','o'],
                 '7':['p','q','r','s'],
                 '8':['t','u','v'],
                 '9':['w','x','y','z']}
                
        def backtrack(conbination,nextdigit):
            if len(nextdigit) == 0:
                res.append(conbination)
            else:
                for letter in phone[nextdigit[0]]:
                    backtrack(conbination + letter,nextdigit[1:])

        res = []
        backtrack('',digits)
        return res

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 选取n个左括号和n个右括号，任何时候选取的右括号个数不超过左括号
        # # 逐个选取括号递归
        # self.outputs = []
        # self.selectkuohao(n,n,'')
        # return self.outputs
        # 递推公式 dp[i]="("+dp[m]+")"+dp[k]   其中m+k=i-1
        if n == 0: return [""]
        outputs = []
        for i in range(n):
            a = self.generateParenthesis(i) 
            b = self.generateParenthesis(n-1-i)
            for j in a:
                for k in b:
                    outputs.append("("+j+")"+k)
        return outputs


    def selectkuohao(self,right,left,strs):
        if left == 0 and right == 0:
            self.outputs.append(strs)
        if left > 0:
            self.selectkuohao(right,left-1,strs+"(")
        if left != right:
            self.selectkuohao(right-1,left,strs+")")

生成所有子集

逐个选择递归，这题可以用递推递归

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.outputs = []
        self.selectnumber(nums,[],0)
        return self.outputs

    def selectnumber(self,nums,l,start):
        self.outputs.append(l)
        for i in range(start,len(nums)):
            self.selectnumber(nums,l+[nums[i]],i+1)

位运算方法，子集个数为2的n次方，n为数组长度

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        outputs = []
        length = 1 << len(nums)
        for i in range(length):
            a = []
            for j in range(len(nums)):
                if i >> j & 1 == 1:
                    a.append(nums[j])
            outputs.append(a)c
        return outputs

图搜索组合成单词

给定图board和单词word，如果单词存在图中，则返回true，否则为false，单词在图中可以沿着上下左右遍历，遍历的格子不允许重复

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.a = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    self.select(board,i,j,word,1)
                if self.a == 1: return True
        return False

    def select(self,board,row,column,word,i):
        if i == len(word): 
            self.a = 1 
            return
        board[row][column] = ""
        if row > 0 and word[i] == board[row-1][column]:
            self.select(board,row-1,column,word,i+1)
        if column > 0 and word[i] == board[row][column-1]:
            self.select(board,row,column-1,word,i+1)
        if row < len(board)-1 and word[i] == board[row+1][column]:
            self.select(board,row+1,column,word,i+1)
        if column < len(board[0])-1 and word[i] == board[row][column+1]:
            self.select(board,row,column+1,word,i+1)
        board[row][column] = word[i-1]

排序和搜索

前k个高频元素（字典内部进行排序）

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_ = defaultdict(int)
        for i in range(len(nums)):
            dict_[nums[i]] += 1
        sortdict = sorted(dict_.items(),key=lambda x:x[1],reverse=True)
        outputs = []
        for i in range(k):
            outputs.append(sortdict[i][0])
        return outputs

第k大元素（n时间复杂度、构建堆）

堆排序：

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
      # 堆排序
        length = len(nums)

        def max_heap(nums, start, end):
            dad = start
            son = dad * 2 + 1
            while son <= end:
                if son + 1 <= end and nums[son] < nums[son+1]:
                    son += 1
                if nums[dad] >= nums[son]:
                    return
                else:
                    nums[dad], nums[son] = nums[son], nums[dad]
                    dad = son
                    son = dad * 2 + 1
        # 构建大顶堆
        for i in range(length//2, -1, -1):
            max_heap(nums, i, length-1)
        coun = 0
        # 堆顶与最后元素交换
        for i in range(length-1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            coun += 1
            if coun == k:
                break
                # 再次构建堆
            max_heap(nums, 0, i-1)
        return nums[-k]

优化方法：构建容量为k的小顶堆，更换堆顶元素即可

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 构建容量为k的小顶堆
        def min_heap(nums, start, end):
            dad = start
            son = dad * 2 + 1
            while son <= end:
                if son + 1 <= end and nums[son] > nums[son+1]:
                    son += 1
                if nums[dad] <= nums[son]:
                    return
                else:
                    nums[dad], nums[son] = nums[son], nums[dad]
                    dad = son
                    son = dad * 2 + 1

        for i in range(k//2, -1, -1):
            min_heap(nums, i, k-1)
        for i in range(k,len(nums)):
            if nums[i] < nums[0]:
                continue
            nums[0],nums[i] = nums[i],nums[0]
            min_heap(nums, 0, k-1)
        return nums[0]

搜索有序矩阵

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        column = len(matrix[0]) - 1
        row = 0
        while row < len(matrix) and column >= 0:
            if matrix[row][column] < target:
                row += 1
            elif matrix[row][column] > target:
                column -= 1
            else:
                return True
        return False 

二分法

找bug

用start和end不断逼近范围，最后输出start的index

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start = 1
        end = n
        while start < end:
            mid = int((start+end) / 2)
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1
        return start

找非递减序列中的目标值开始和结束的位置

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0: return [-1, -1]
        left, right, first = 0, len(nums) - 1, -1
        # 先找第一个出现的位置
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                first = mid
                right = mid - 1    # 往前找还有没有
            if nums[mid] < target:
                left = mid + 1
            if nums[mid] > target:
                right = mid - 1
        if first == -1: return [-1, -1]  # 如果找不到，就不用找了
        # 再找最后出现的位置,这时候边界为[first,len-1]
        left, right, last = first, len(nums) - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                last = mid
                left = mid + 1   # 往后找还有没有
            if nums[mid]<target:
                left = mid+1
            if nums[mid]>target:
                right = mid-1
        return [first,last]

找一个经过一次旋转的有序数组中的元素下标

有序数组从中断开左右进行过一次交换

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        begin = 0
        end = len(nums) - 1
        while end >= begin:
            mid = (begin+end)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                if nums[end] >= nums[mid] or (nums[mid] >= nums[begin] and target >= nums[begin]):
                    end = mid - 1
                else:
                    begin = mid + 1
            else:
                if nums[mid] >= nums[begin]or (nums[mid] <= nums[end] and target <= nums[end]):
                    begin = mid + 1
                else:
                    end = mid - 1
        return -1

动态规划

走楼梯

爬n阶楼梯，每次走一到两阶，共有几种走法：

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = []
        dp.append(0)
        dp.append(1)
        dp.append(2)
        for i in range(n - 2):
            dp.append(dp[-1] + dp[-2])
        return dp[n]

买卖股票

计算什么时候获买卖一次股票得最大收益

def maxProfit(self, prices: List[int]) -> int:
    maxPro = 0
    minprice = 10000
    for i in range(len(prices)):
        if prices[i] < minprice:
            minprice = prices[i]
        elif prices[i] - minprice > maxPro:
            maxPro = prices[i] - minprice
    return maxPro

数相加

连续n个数相加的最大值，这里需要额外存一个包含最后一个元素的最大值用来比较：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxsum = nums[0]
        lastmaxsum = nums[0]
        for i in range(1,len(nums)):
            lastmaxsum = nums[i] if nums[i] > lastmaxsum + nums[i] else lastmaxsum + nums[i]
            maxsum = maxsum if maxsum > lastmaxsum else lastmaxsum
        return maxsum

计算全部不连续的n个正数相加的最大值：
我的直观写法：

class Solution:
    def rob(self, nums: List[int]) -> int:
        maxprofit = nums[0]
        lastmax = nums[0]
        preonemax = 0
        pretwomax = 0
        for i in range(1,len(nums)):
            temp = preonemax
            preonemax = lastmax
            lastmax = temp + nums[i] if temp + nums[i]>pretwomax + nums[i] else pretwomax + nums[i]
            maxprofit = max(lastmax, preonemax, maxprofit)
            pretwomax = temp

        return maxprofit

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1

本质需要计算dp[amount]，dp[i] = min(dp[i-coin[0]],dp[i-coin[1]]…,dp[i-coin[j]])+1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        a = [0] + [1<<31] * amount
        for i in range(1,len(a)):
            minn = 1 << 31
            for j in range(len(coins)):
                if i-coins[j] >= 0 and a[i-coins[j]]+1 < minn:
                    minn = a[i-coins[j]]+1
            a[i] = minn
        if a[amount] != 1<<31:
            return a[amount]
        else:
            return -1

找递增子集最大长度(二分法)

动态规划，时间复杂度n^2

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

贪心算法+二分法：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > d[-1]:
                d.append(nums[i])
            else:
                begin = 0
                end = len(d) - 1
                while end > begin:
                    mid = (begin + end) // 2
                    if d[mid] >= nums[i]:
                        end = mid
                    elif d[mid] < nums[i]:
                        begin = mid + 1
                d[begin] = nums[i]
        return len(d)

最优解法，不用append极限省时间：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d,res = [0] * len(nums), 0
        for i in range(len(nums)):
            begin,end = 0,res
            while end > begin:
                mid = (begin + end) // 2
                if d[mid] >= nums[i]:
                    end = mid
                else:
                    begin = mid + 1
            d[begin] = nums[i]
            if begin == res:
                res += 1
        return res
                

设计问题

等可能打乱数组

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def reset(self) -> List[int]:
        return self.nums

    def shuffle(self) -> List[int]:
        newlist = self.nums.copy()
        for i in range(len(newlist)-1):
            a = random.randint(i, len(newlist)-1)
            if a == i: continue
            temp = newlist[i]
            newlist[i] = newlist[a]
            newlist[a] = temp
        return newlist

设计一个检索到最小元素的栈

无脑方法，耗时超越5%Python程序

class MinStack:
    def __init__(self):
        self.s = []

    def push(self, val: int) -> None:
        self.s.append(val)

    def pop(self) -> None:
        self.s.pop()

    def top(self) -> int:
        return self.s[-1]

    def getMin(self) -> int:
        m = 1 << 31
        for i in range(len(self.s)):
            if self.s[i] < m:
                m = self.s[i]
        return m

使用链表，用时64ms，超过70%Python程序

class Node:
    def __init__(self,val=None,nxt=None):
        self.val = val
        self.next = nxt
        self.min = val

class MinStack:
    def __init__(self,val=None,nex=None):
        self.head = None

    def push(self, val: int) -> None:
        if self.head == None:
            n = Node(val)
        else:
            n = Node(val,self.head)
            if n.min > self.head.min:
                n.min = self.head.min
        self.head = n

    def pop(self) -> None:
        if self.head != None:
            self.head = self.head.next

    def top(self) -> int:
        return self.head.val

    def getMin(self) -> int:
        return self.head.min

数学

加减乘除的本质

应对python无限制扩展位数的方法

# 限制变量为32位
def int32(value):
    return -(value & 0x80000000) | (value & 0x7FFFFFFF)

加法,本位+进位

def add(a, b):
    while b:
        carry = a & b
        a = a ^ b
        b = carry << 1
    return a

减法，本位-借位

def subtract(a, b):
    while b:
        borrow = (~a) & b
        a = a ^ b
        b = borrow << 1
    return a

乘法

def multiply(a, b):
    result = 0
    neg = a < 0 and b > 0 or a > 0 and b < 0
    a, b = abs(a), abs(b)
    while b:
        if b & 1:
            result = add(result, a)
        a <<= 1
        b >>= 1
    return -result if neg else result

除法

def divide(a, b):
    if b == 0:
        raise ValueError("除数不能为零")
    neg = a < 0 and b > 0 or a > 0 and b < 0
    a, b = abs(a), abs(b)
    result = 0
    while a >= b:
        temp, i = b, 1
        while a >= (temp << 1):
            temp <<= 1
            i <<= 1
        a = subtract(a, temp)
        result = add(result, i)
    return -result if neg else result

选出n以内的质数

如果按照一般质数的定义（不能被前面所有的质数整除）逐一筛选，时间太长，算法超时

埃氏筛选法：
默认所有数为质数，把合数筛出来，剩下质数。筛选方法如下，从2开始循环，默认质数，那么22每隔2都是合数。3没被筛，所以是质数，33开始，每隔3是合数筛选出来，以此类推。

class Solution:
    # 埃式筛选法
    def countPrimes(self, n: int) -> int:
        a = [True] * n
        count = 0
        for i in range(2,n):
            if a[i]:
                count += 1
                for j in range(i*i,n,i):
                    a[j] = False
        return count

读罗马数字

class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        ret = 0
        for i in range(len(s)-1,-1,-1):
            if ret>4*dic[s[i]]:
                ret -= dic[s[i]]
            else:
                ret += dic[s[i]]
        return ret

乘阶后有几个零

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # 计算有几个5和10,25记作两个
        count = 0
        while n >= 5:
            count += int(n/5)
            n /= 5
        return count

分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。如果小数部分为循环小数，则将循环的部分括在括号内。

用字典存余数和对应商在数组的下标，用数组存商，判断余数是否重复出现，在数组对应的位置加括号即可

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0: return "0"
        if numerator % denominator == 0:
            return str(numerator//denominator)
        neg = (numerator>0) ^ (denominator>0)
        numerator,denominator = abs(numerator),abs(denominator)
        a = []
        if neg: a.append("-")
        a.append(str(int(numerator//denominator)))
        a.append(".")
        d = {}

        Quotient = numerator // denominator
        remainder = numerator % denominator
        while remainder != 0:
            remainder = remainder * 10
            Quotient = remainder // denominator
            remainder = remainder % denominator
            if remainder in d:
                a.insert(d[remainder]+1,"(")
                a.append(str(Quotient))
                a.append(")")
                return "".join(a)
            d[remainder] = len(a)
            a.append(str(Quotient))

        return "".join(a)

其他

倒转二进制

class Solution:
    def reverseBits(self, n: int) -> int:
        sum = 0
        for i in range(32):
            sum <<= 1
            sum |= n & 1
            n >>= 1

        return sum

杨辉三角

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        outputs = [[1]]
        lastrow = [1]
        for i in range(2,numRows+1):
            thisrow = []
            for j in range(len(lastrow)+1):
                if j == 0 or j == len(lastrow):
                    thisrow.append(1)
                else:
                    thisrow.append(lastrow[j-1] + lastrow[j])
            outputs.append(thisrow)
            lastrow = thisrow
        return outputs

有效括号

class Solution:
    def isValid(self, s: str) -> bool:
        d = {")":"(","]":"[","}":"{"}
        stack = []
        for i in range(len(s)):
            if s[i] == "(" or s[i] == "[" or s[i] == "{":
                stack.append(s[i])
            elif not stack or d[s[i]] != stack[-1]:
                    return False
            else:
                stack.pop()
        if stack: return False
        return True

寻找缺失数字，可用异或抵消大法：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        a = 0
        for i in range(len(nums)):
            a = a ^ nums[i] ^ (i+1)
        return a

任务调度器：
输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        dict_ = defaultdict(int)
        for i in range(len(tasks)):
            dict_[tasks[i]] += 1
        sortdict = sorted(dict_.values(),reverse=True)
        count = sortdict[0] + (sortdict[0] - 1) * n
        for i in range(1,len(sortdict)):
            if sortdict[0] != sortdict[i]:
                break
            count += 1
        return max(len(tasks),count)