204. Count Primes

• 思路
  • example

  • 素数筛选法

    
    

n/2 + n/3 + n/5 + n/7 + … = n × (1/2 + 1/3 + 1/5 + 1/7…)
括号中是素数的倒数。其最终结果是 O(N * loglogN)

• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True for _ in range(n)]
        for i in range(2, int(n**0.5)+1):
            if isPrime[i]:
                for j in range(2*i, n, i):
                    isPrime[j] = False  
        res = 0
        for j in range(2, n):
            if isPrime[j]:
                res += 1
        return res  

382. Linked List Random Node

• 思路
  • example
  • xxx
• 复杂度. 时间：O(?), 空间: O(?)

code

384. Shuffle an Array

• 思路
  • example
  • 洗牌法

random.randrange(x, y) # [x, y)

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums 
        self.original = nums.copy()

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

    def shuffle(self) -> List[int]:
        n = len(self.nums)  
        for i in range(n):
            j = random.randrange(i, n) # 左开右闭
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]  
        return self.nums 


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

398. Random Pick Index

25. Reverse Nodes in k-Group

870. Advantage Shuffle

将齐王nums1和田忌nums2的马按照战斗力排序，然后按照排名一一对比。如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。

• O(nlogn)

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        nums1.sort()
        maxpq = [(-val, i) for i, val in enumerate(nums2)]
        heapq.heapify(maxpq) 

        left, right = 0, n-1  
        res = [0 for _ in range(n)]
        while maxpq:
            val, i = heapq.heappop(maxpq)
            maxval = -val  
            if nums1[right] > maxval: # 用当前最好的匹配对方最好的
                res[i] = nums1[right]
                right -= 1
            else: # 用当前最差的匹配对方最好的 （下等马）
                res[i] = nums1[left]
                left += 1
        return res  

241. Different Ways to Add Parentheses

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        n = len(expression)
        op_set = {'+', '-', '*'}
        res = []
        for i in range(n):
            if expression[i] in op_set:
                left = expression[:i] 
                right = expression[i+1:]
                left_result = self.diffWaysToCompute(left) 
                right_result = self.diffWaysToCompute(right) 
                for x in left_result:
                    for y in right_result:
                        if expression[i] == '+':
                            res.append(x+y)
                        elif expression[i] == '-':
                            res.append(x-y)
                        elif expression[i] == '*':
                            res.append(x*y)  
        if res == []: # base case  
            res.append(int(expression))
        return res  

• 记忆化

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        memo = {}
        def diffWays(expression):
            if expression in memo:
                return memo[expression]
            n = len(expression)
            op_set = {'+', '-', '*'}
            res = []
            for i in range(n):
                if expression[i] in op_set:
                    left = expression[:i] 
                    right = expression[i+1:]
                    left_result = self.diffWaysToCompute(left) 
                    right_result = self.diffWaysToCompute(right) 
                    for x in left_result:
                        for y in right_result:
                            if expression[i] == '+':
                                res.append(x+y)
                            elif expression[i] == '-':
                                res.append(x-y)
                            elif expression[i] == '*':
                                res.append(x*y)  
            if res == []: # base case  
                res.append(int(expression))
            memo[expression] = res  
            return res  
        return diffWays(expression)

486. Predict the Winner

• 博弈问题, DP

区间DP
dp[i][j][0]: nums[i,...,j]先手能获得的最高分数
dp[i][j][1]: nums[i,...,j]后手能获得的最高分数
dp[i][j][0] = max(nums[i] + dp[i+1][j][1], nums[j] + dp[i][j-1][1]) ---- i-逆序遍历，j-顺序遍历
dp[i][j][1] = ?
left = nums[i] + dp[i+1][j][1]
right = nums[j] + dp[i][j-1][1]
if left < right:
dp[i][j][1] = dp[i][j-1][0]
else:
dp[i][j][1] = dp[i+1][j][0]

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = nums[i]
            dp[i][i][1] = 0 
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                left = nums[i] + dp[i+1][j][1]
                right = nums[j] + dp[i][j-1][1]
                if left < right:
                    dp[i][j][0] = right 
                    dp[i][j][1] = dp[i][j-1][0]
                else:
                    dp[i][j][0] = left  
                    dp[i][j][1] = dp[i+1][j][0]
        return dp[0][n-1][0] - dp[0][n-1][1] >= 0

877. Stone Game

1584. Min Cost to Connect All Points

• 标准的最小生成树问题：每个点就是无向加权图中的节点，边的权重就是曼哈顿距离，连接所有点的最小费用就是最小生成树的权重和。

Prim最小生成树
Kruskal 算法是在一开始的时候就把所有的边排序，然后从权重最小的边开始挑选属于最小生成树的边，组建最小生成树。
Prim 算法是从一个起点的切分（一组横切边）开始执行类似 BFS 算法的逻辑，借助切分定理和优先级队列动态排序的特性，从这个起点「生长」出一棵最小生成树。时间复杂度是 O(ElogE).
切分定理：对于任意一种切分，其中权重最小的那条横切边一定是构成最小生成树的一条边。
“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中.

import heapq

class Prim:
    # 核心数据结构，存储「横切边」的优先级队列
    def __init__(self, graph: List[List[int]]):
        self.graph = graph
        self.pq = [] # PriorityQueue<int[]> 的实现
        self.inMST = [False] * len(graph) # 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
        self.weightSum = 0 # 记录最小生成树的权重和
        
        self.inMST[0] = True # 随便从一个点开始切分都可以，我们不妨从节点 0 开始
        self.cut(0) 
        
        # 不断进行切分，向最小生成树中添加边
        while self.pq:
             # 按照边的权重从小到大排序
            edge = heapq.heappop(self.pq)
            to = edge[1] # 表示相邻节点
            weight = edge[2] # 表示这条边的权重
            if self.inMST[to]: # 节点 to 已经在最小生成树中，跳过。否则这条边会产生环
                continue
            self.weightSum += weight # 将边 edge 加入最小生成树
            self.inMST[to] = True 
            self.cut(to) # 节点 to 加入后，进行新一轮切分，会产生更多横切边
    
    # 将 s 的横切边加入优先队列
    def cut(self, s):
        for edge in self.graph[s]: # 遍历 s 的邻边
            to = edge[1] # 相邻的节点
            if self.inMST[to]: # 相邻接点 to 已经在最小生成树中，跳过
                continue
            heapq.heappush(self.pq, edge) # 加入横切边队列
    
    # 最小生成树的权重和
    def weightSum(self) -> int:
        return self.weightSum

    # 判断最小生成树是否包含图中的所有节点
    def allConnected(self) -> bool:
        for i in range(len(self.inMST)):
            if not self.inMST[i]:
                return False
        return True

两个算法的比较:
Kruskal算法时间复杂度为O(M*log(M)), M为边数, 适合于稀疏图
Prim算法的时间复杂度为O(N^2), N为顶点数量, 适合于稠密图或者完全图
Kruskal算法的基本步骤: 以边为主导. 让边从小到大, 依次考虑是否加入到最小生成树里面, 如果加入这个边, 没有生成环路, 那么, 就可以加入进来, 否则, 就不应该加入进来. 判断是否生存环路的方法是使用并查集, 如果边的两个顶点都是已经加入的顶点, 那么, 就会形成环路.
Prim算法的基本步骤: 以顶点为主导. 初始状态下, 随便让一个顶点加入进来. 每一轮下, 加入一个未加入的顶点, 具体方法是: 计算未加入顶点与加入顶点之间的最小值, 将最小值对应的未加入顶点加入.进行n轮.

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        #Prim算法
        n = len(points)
        d = [float("inf")] * n # 表示各个顶点与加入最小生成树的顶点之间的最小距离.
        vis = [False] * n # 表示是否已经加入到了最小生成树里面
        d[0] = 0
        ans = 0
        for _ in range(n):
            # 寻找目前这轮的最小d (对应node)
            M = float("inf") 
            for i in range(n):
                if not vis[i] and d[i] < M:
                    node = i
                    M = d[i]
            vis[node] = True
            ans += M
            # 更新与这个顶点相连接的顶点的d.
            for i in range(n):
                if not vis[i]:
                    d[i] = min(d[i], abs(points[i][0] - points[node][0]) + abs(points[i][1] - points[node][1]))
        return ans

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        visited = [False for _ in range(n)]
        dist = [float('inf') for _ in range(n)]
        dist[0] = 0
        res = 0
        for i in range(n):
            min_dist = float('inf')
            for j in range(n):
                if visited[j] == False and dist[j] < min_dist:
                    min_dist = dist[j]
                    node = j 
            res += min_dist 
            visited[node] = True # 加入node进已访问
            for j in range(n):
                # dist[j] 包含了与已访问节点的最小距离!!!
                if visited[j] == False:
                    dist[j] = min(dist[j], abs(points[j][0]-points[node][0]) + abs(points[j][1]-points[node][1]))
        return res  

355. Design Twitter

合并多个有序链表的算法和面向对象设计（OO design）结合

class Twitter:
    timestamp = 0

    class Tweet:
        """Tweet类用于定位tweet"""
        pass

    class User:
        """User类用于记录用户信息"""
        pass

    def __init__(self):
        """初始化，创建一个字典，用于userId和user对象的映射"""
        self.userMap = {}

    def postTweet(self, userId: int, tweetId: int) -> None:
        """用户userId发表一条tweet"""
        if userId not in self.userMap:
            self.userMap[userId] = User(userId)
        u = self.userMap[userId]
        u.post(tweetId)

    def follow(self, followerId: int, followeeId: int) -> None:
        """用户followerId关注用户followeeId"""
        if followerId not in self.userMap:
            u = User(followerId)
            self.userMap[followerId] = u

        if followeeId not in self.userMap:
            u = User(followeeId)
            self.userMap[followeeId] = u

        self.userMap[followerId].follow(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """用户followerId取消关注用户followeeId"""
        if followerId in self.userMap:
            flwer = self.userMap[followerId]
            flwer.unfollow(followeeId)

    def getNewsFeed(self, userId: int) -> List[int]:
        """返回该用户关注的人最近的动态，最多10条"""
        pass

• 两类Tweet and User, 合并有序链表，大顶堆

class Tweet:
    def __init__(self, tweetId, time):
        self.tweetId = tweetId
        self.time = time
        self.next = None
    
    def __lt__(self, other):
        return (self.time > other.time)

class User:
    def __init__(self, userId):
        self.userId = userId
        self.followed = set()
        self.followed.add(userId)
        self.tweets = None
    
    def follow(self, followeeId):
        self.followed.add(followeeId)
    
    def unfollow(self, followeeId):
        if followeeId != self.userId and followeeId in self.followed:
            self.followed.remove(followeeId)
    
    def post(self, tweetId, time):
        new = Tweet(tweetId, time)
        new.next = self.tweets
        self.tweets = new

class Twitter:
    import heapq
    def __init__(self):
        self.timestamp = 0
        self.userMap = dict() # uderId --> User object

    def postTweet(self, userId: int, tweetId: int) -> None:
        # 若 userId 不存在，则新建
        if userId not in self.userMap:
            self.userMap[userId] = User(userId)
        curUser = self.userMap[userId]
        curUser.post(tweetId, self.timestamp)
        self.timestamp += 1
        

    def getNewsFeed(self, userId: int) -> List[int]:
        if userId not in self.userMap:
            return []
        user = self.userMap[userId]
        result = []
        pq = []
        followeeIds = list(user.followed)
        for i in followeeIds:
            t = self.userMap[i].tweets
            if t:
                heapq.heappush(pq, t)
        while pq:
            if len(result) == 10:
                break
            t = heapq.heappop(pq)
            result.append(t.tweetId)
            if t.next:
                heapq.heappush(pq, t.next)
        return result
        

    def follow(self, followerId: int, followeeId: int) -> None:
        # 若 follower 不存在，则新建
        if followerId not in self.userMap:
            self.userMap[followerId] = User(followerId)
        # 若 followee 不存在，则新建
        if followeeId not in self.userMap:
            self.userMap[followeeId] = User(followeeId)
        follower = self.userMap[followerId]
        follower.follow(followeeId)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.userMap:
            follower = self.userMap[followerId]
            follower.unfollow(followeeId)

• 简洁版本 hash

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.users = dict()  # key:value分别对应用户 userId(int) 和 其关注者(list)
        self.posts = []  # 发布的帖子，每个元素格式为 [userId, tweetId]

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.posts.append([userId, tweetId])  # 将帖子加入 posts 列表
        if not self.users.get(userId):  # 同步更新用户列表，如果 userId 在字典中的值不存在，则设为初始值 [],否则不操作
            self.users[userId] = []

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        if userId not in self.users.keys():  # 检查 userId 的合法性,如果该用户不存在，直接返回
            return
        else:  # 用户存在
            ids = [userId] + self.users.get(userId)  # 计算待排查id，包括用户自身 id 还有他 follow 的人的 id
            tmp = []  # 待返回的结果集
            count = 10  # 计数器：排查最新的10条
            for post in self.posts[-1:-(len(self.posts) + 1):-1]:  # 开始排查，并将 tweetId 加入结果集
                if count > 0:
                    if post[0] in ids:
                        tmp.append(post[1])
                        count -= 1
            return tmp

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        if followerId not in self.users.keys():  # 检查 followerId 用户的 id 合法性，如果没在 self.users 中出现过，则设为初始值
            self.users[followerId] = []
            self.users[followerId].append(followeeId)
        else:  # followerId 如果在 self.users 中出现过，则直接将 followeeId 直接加入
            self.users[followerId].append(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        if followerId not in self.users.keys():  # 检查合法性，如果 followerId 未曾出现，则直接返回
            return
        else:
            if followeeId in self.users[followerId]:  # 检查被移除的 id 的合法性，如果存在直接删除
                self.users[followerId].remove(followeeId)
            else:  # 被移除的 id 不存在，返回
                return

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

55. Jump Game

• 贪心

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        farlest = 0
        for i in range(n):
            if farlest >= n-1:
                return True  
            if farlest < i: 
                return False  
            farlest = max(farlest, i + nums[i]) 

45. Jump Game II

• DP
• BFS 或滑窗

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, 0 # left closed, right closed
        steps = 0
        while right - left >= 0:
            if right >= n - 1:
                return steps 
            temp = right
            for i in range(left, right+1):
                right = max(right, i + nums[i])
            steps += 1
            left = temp 

43. Multiply Strings

num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置

def multiply(num1: str, num2: str) -> str:
    m, n = len(num1), len(num2)
    # 结果最多为 m + n 位数
    res = [0] * (m + n)
    # 从个位数开始逐位相乘
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            # 乘积在 res 对应的索引位置
            p1, p2 = i + j, i + j + 1
            # 叠加到 res 上
            sum = mul + res[p2]
            res[p2] = sum % 10
            res[p1] += sum // 10 #  这里不用考虑进位
    # 结果前缀可能存的 0（未使用的位）
    i = 0
    while i < len(res) and res[i] == 0:
        i += 1
    # 将计算结果转化成字符串
    res_str = ''.join(str(e) for e in res[i:])
    return res_str if res_str else '0'

• p1, p2 都考虑进位

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        res = [0 for _  in range(m+n)]
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                mul = (ord(num1[i])-ord('0')) * (ord(num2[j])-ord('0'))
                p1, p2 = i+j, i+j+1
                sum_ = res[p2] + mul  
                res[p2] = sum_ % 10 
                res[p1] = res[p1] + sum_ // 10
                while res[p1] >= 10:
                    res[p1-1] += res[p1]//10
                    res[p1] = res[p1]%10
                    p1 -= 1
        i = 0 
        while i < len(res) and res[i] == 0:
            i += 1
        res = ''.join(str(e) for e in res[i:])
        return res if res else '0' 

将A[i] * B[j]的结果累加到C[i + j]中

232. Implement Queue using Stacks

• 双栈实现队列

class MyQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []


    def push(self, x: int) -> None:
        self.stack1.append(x) 

    def pop(self) -> int:
        self.peek()
        return self.stack2.pop()

    def peek(self) -> int:
        if len(self.stack2) == 0:
            while len(self.stack1) != 0:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self) -> bool:
        return len(self.stack1) == 0 and len(self.stack2) == 0 

225. Implement Stack using Queues

• 两个队列实现栈

class MyStack:

    def __init__(self):
        self.que1 = collections.deque()
        self.que2 = collections.deque()

    def push(self, x: int) -> None:
        self.que2.append(x)
        while self.que1:
            self.que2.append(self.que1.popleft())
        while self.que2:
            self.que1.append(self.que2.popleft())

    def pop(self) -> int:
        return self.que1.popleft()

    def top(self) -> int:
        return self.que1[0]

    def empty(self) -> bool:
        return len(self.que1) == 0 

• 一个队列实现栈

class MyStack:

    def __init__(self):
        self.que = collections.deque()

    def push(self, x: int) -> None:
        self.que.append(x)
        for _ in range(len(self.que)-1):
            self.que.append(self.que.popleft())

    def pop(self) -> int:
        return self.que.popleft()

    def top(self) -> int:
        return self.que[0]

    def empty(self) -> bool:
        return len(self.que) == 0 

372. Super Pow

(a * b) % k = (a % k) * (b % k) % k

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        def myPow(a, k):
            if k == 0:
                return 1 
            a %= 1337 
            res = 1
            for _ in range(k):
                res *= a 
                res %= 1337
            return res 
        if b == []:
            return 1
        last = b.pop()
        part1 = myPow(a, last) 
        part2 = myPow(self.superPow(a, b), 10) 
        return (part1 * part2) % 1337

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        def myPow(a, k):
            if k == 0:
                return 1 
            a %= 1337 
            if k % 2 == 1:
                return (a * myPow(a, k-1)) % 1337
            else: 
                x = myPow(a, k//2) 
                return (x*x) % 1337
        if b == []:
            return 1
        last = b.pop()
        part1 = myPow(a, last) 
        part2 = myPow(self.superPow(a, b), 10) 
        return (part1 * part2) % 1337