LeetCode 2020-04月每日一题

Contents

1 4月1日：有效括号的嵌套深度
2 4月2日：生命游戏
3 4月3日：字符串转换整数 (atoi)
4 4月4日：接雨水
5 4月5日：LFU缓存
6 4月6日：编辑距离
7 4月7日：旋转矩阵
8 4月8日：机器人的运动范围
9 4月9日：括号生成
10 4月10日：翻转字符串里的单词
11 4月11日：鸡蛋掉落
12 4月12日：交点
13 4月13日：设计推特
14 4月14日：两数相加 II
15 4月15日：01 矩阵
16 4月16日：合并区间
17 4月17日：跳跃游戏
18 4月18日：盛最多水的容器
19 4月19日：统计重复个数
20 4月20日：岛屿数量
21 4月21日：统计「优美子数组」
22 4月22日：二叉树的右视图
23 4月23日：硬币
24 4月24日：数组中的逆序对
25 4月25日：全排列
26 4月26日：合并K个排序链表
27 4月27日：搜索旋转排序数组
28 4月28日：数组中数字出现的次数
29 4月29日：山脉数组中查找目标值
30 4月30日：快乐数

4月1日：有效括号的嵌套深度

难度中等

题目描述

有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一：

空字符串
连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
嵌套，可以记作 (A)，其中 A 是有效括号字符串

类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

s 为空时，depth("") = 0
s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

给你一个有效括号字符串 seq，将其分成两个不相交的子序列 A 和 B，且 A 和 B 满足有效括号字符串的定义（注意：A.length + B.length = seq.length）。

现在，你需要从中选出任意一组有效括号字符串 A 和 B，使 max(depth(A), depth(B)) 的可能取值最小。

返回长度为 seq.length 答案数组 answer ，选择 A 还是 B 的编码规则是：如果 seq[i] 是 A 的一部分，那么 answer[i] = 0。否则，answer[i] = 1。即便有多个满足要求的答案存在，你也只需返回一个。

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

输入：seq = "(()())"

输出：[0,1,1,1,1,0]

示例 2：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]

输入：seq = "()(())()"

输出：[0,0,0,1,1,0,1,1]

题目链接

https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

思路:

　　4月难度加大了❓❓
　　因为要使max(depth(A), depth(B))最小，所以让A和B的深度越接近越好。假设S的深度为n，那么A的深度就为(n+1)//2。
　　深度优先搜索，S中的字符要么给A用，要么给B用，(总共 $C_n^{(n+1)//2}$ 种可能性，复杂度较高)。需要用以下几个条件剪枝：
　　① A和B当前的左括号数-右括号数必须大于0。
　　② A和B当前的左括号数-右括号数必须小于等于(n+1)//2。
　　③ 因为只要找到一种可能性就行了，因此采取贪心算法，让A的左括号尽量多(也就是深度尽量大)。

代码:

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        depth = 0
        max_depth = 0
        ls = len(seq)
        for s in seq:
            if s == '(':
                depth += 1
                max_depth = max(max_depth, depth)
            elif s == ')':
                depth -= 1

        d1 = (max_depth + 1) // 2
        ans = [None for i in range(ls)]
        def dfs(i, cnt1, cnt2):  # cnt1表示A当前的左括号-右括号数 cnt2表示B当前的左括号-右括号数
            if i >= ls:
                if cnt1 == 0:
                    return True
                return False 
            if cnt1 < 0 or cnt2 < 0: 
                return False

            if seq[i] == '(':
                if cnt1 < d1:
                    ans[i] = 0
                    if dfs(i+1, cnt1+1, cnt2):  # 用(
                        return True
                ans[i] = 1
                return dfs(i+1, cnt1, cnt2+1)  # 不用(
            elif seq[i] == ')': 
                if cnt1 >= d1 or cnt2 == 0:  # 必用)
                    ans[i] = 0
                    return dfs(i+1, cnt1-1, cnt2) 

                ans[i] = 1
                return dfs(i+1, cnt1, cnt2-1)  # 不用)

        dfs(0, 0, 0)
        return ans

class Solution:

def maxDepthAfterSplit(self, seq: str) -> List[int]:

depth = 0

max_depth = 0

ls = len(seq)

for s in seq:

if s == '(':

depth += 1

max_depth = max(max_depth, depth)

elif s == ')':

depth -= 1

d1 = (max_depth + 1) // 2

ans = [None for i in range(ls)]

def dfs(i, cnt1, cnt2): # cnt1表示A当前的左括号-右括号数 cnt2表示B当前的左括号-右括号数

if i >= ls:

if cnt1 == 0:

return True

return False

if cnt1 < 0 or cnt2 < 0:

return False

if seq[i] == '(':

if cnt1 < d1:

ans[i] = 0

if dfs(i+1, cnt1+1, cnt2): # 用(

return True

ans[i] = 1

return dfs(i+1, cnt1, cnt2+1) # 不用(

elif seq[i] == ')':

if cnt1 >= d1 or cnt2 == 0: # 必用)

ans[i] = 0

return dfs(i+1, cnt1-1, cnt2)

ans[i] = 1

return dfs(i+1, cnt1, cnt2-1) # 不用)

dfs(0, 0, 0)

return ans

4月2日：生命游戏

难度中等

题目描述

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：

输入： 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

输入：

[

[0,1,0],

[0,0,1],

[1,1,1],

[0,0,0]

]

输出：

[

[0,0,0],

[1,0,1],

[0,1,1],

[0,1,0]

]

进阶：

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

题目链接

https://leetcode-cn.com/problems/game-of-life/

思路:

　　原地算法：扫描每个位置的周围八个格子，用2表示即将死亡的活细胞，用-1表示即将复活的死细胞。根据正负判断细胞之前是活的还是死的。然后再扫描一次，将2替换成0，-1替换成1即可。

代码:

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]  # 8个方向
        m = len(board)
        if not m: return 
        n = len(board[0])

        for i in range(m):
            for j in range(n):
                cnt = 0
                for di, dj in arounds:
                    x, y = i + di, j + dj
                    if x < 0 or y < 0 or x >= m or y >= n:
                        continue
                    if board[x][y] > 0:  # 周围的活细胞
                        cnt += 1
                if board[i][j] > 0:
                    if cnt < 2 or cnt > 3:
                        board[i][j] = 2  # 活细胞死亡
                if board[i][j] <= 0:
                    if cnt == 3:
                        board[i][j] = -1  # 死细胞复活

        for i in range(m):
            for j in range(n):
                if board[i][j] == 2:
                    board[i][j] = 0
                elif board[i][j] == -1:
                    board[i][j] = 1

        return board

class Solution:

def gameOfLife(self, board: List[List[int]]) -> None:

"""

Do not return anything, modify board in-place instead.

"""

arounds = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] # 8个方向

m = len(board)

if not m: return

n = len(board[0])

for i in range(m):

for j in range(n):

cnt = 0

for di, dj in arounds:

x, y = i + di, j + dj

if x < 0 or y < 0 or x >= m or y >= n:

continue

if board[x][y] > 0: # 周围的活细胞

cnt += 1

if board[i][j] > 0:

if cnt < 2 or cnt > 3:

board[i][j] = 2 # 活细胞死亡

if board[i][j] <= 0:

if cnt == 3:

board[i][j] = -1 # 死细胞复活

for i in range(m):

for j in range(n):

if board[i][j] == 2:

board[i][j] = 0

elif board[i][j] == -1:

board[i][j] = 1

return board

4月3日：字符串转换整数 (atoi)

难度中等

题目描述

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

输入: "42"

输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

输入: " -42"

输出: -42

解释: 第一个非空白字符为 '-', 它是一个负号。

我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

输入: "4193 with words"

输出: 4193

解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

输入: "words and 987"

输出: 0

解释: 第一个非空字符是 'w', 但它不是数字或正、负号。

因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

输入: "-91283472332"

输出: -2147483648

解释: 数字 "-91283472332" 超过 32 位有符号整数范围。

因此返回 INT_MIN (−231) 。

题目链接

https://leetcode-cn.com/problems/string-to-integer-atoi/

思路:

　　Python处理这种整数越界的问题就很烦。

代码:

class Solution:
    def myAtoi(self, str: str) -> int:
        str = str.lstrip(' ')  # 去掉开头空格
        factor = 1  # 正数
        if str.startswith('-'):
            str = str[1:]
            factor = -1
        elif str.startswith('+'):
            str = str[1:]

        for i, s in enumerate(str):
            if not s.isdigit():
                str = str[:i]
                break

        try:
            num = factor * int(str)

            if num < -2147483648:
                return -2147483648
            elif num > 2147483647:
                return 2147483647
            return num
        except:
            return 0

class Solution:

def myAtoi(self, str: str) -> int:

str = str.lstrip(' ') # 去掉开头空格

factor = 1 # 正数

if str.startswith('-'):

str = str[1:]

factor = -1

elif str.startswith('+'):

str = str[1:]

for i, s in enumerate(str):

if not s.isdigit():

str = str[:i]

break

try:

num = factor * int(str)

if num < -2147483648:

return -2147483648

elif num > 2147483647:

return 2147483647

return num

except:

return 0

4月4日：接雨水

难度 困难

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/

思路：

　　先遍历一遍height，分别找到每个高度h的左侧最高点和右侧最高点，如果min(左侧最高点，右侧最高点) > h，则可以接雨水。将每个h接的雨水数累加。　　

代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        i, j = 0, 0
        n = len(height)
        if n <= 2:
            return 0
        left_maxes = [0 for i in range(n)]  # 表示左边最高点
        right_maxes = [0 for i in range(n)]  # 表示右边最高点
        temp = height[0]
        for i in range(1, n):
            left_maxes[i] = temp
            temp = max(temp, height[i])
        temp = height[-1]
        for i in range(n-2, -1, -1):
            right_maxes[i] = temp
            temp = max(temp, height[i])

        ans = 0
        for i in range(1, n-1):  # 第一个和最后一个不可能接雨水
            h = min(left_maxes[i], right_maxes[i])
            a = max(h - height[i], 0)
            ans += a

        return ans

class Solution:

def trap(self, height: List[int]) -> int:

i, j = 0, 0

n = len(height)

if n <= 2:

return 0

left_maxes = [0 for i in range(n)] # 表示左边最高点

right_maxes = [0 for i in range(n)] # 表示右边最高点

temp = height[0]

for i in range(1, n):

left_maxes[i] = temp

temp = max(temp, height[i])

temp = height[-1]

for i in range(n-2, -1, -1):

right_maxes[i] = temp

temp = max(temp, height[i])

ans = 0

for i in range(1, n-1): # 第一个和最后一个不可能接雨水

h = min(left_maxes[i], right_maxes[i])

a = max(h - height[i], 0)

ans += a

return ans

4月5日：LFU缓存

难度困难

题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) – 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) – 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶： 你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 去除 key 2

cache.get(2); // 返回 -1 (未找到key 2)

cache.get(3); // 返回 3

cache.put(4, 4); // 去除 key 1

cache.get(1); // 返回 -1 (未找到 key 1)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

题目链接

https://leetcode-cn.com/problems/lfu-cache/

思路:

　　首先要理解LFU的缓存机制：
　　① LFU缓存就是在缓存容量满时，将访问次数最少的key-value删除掉。
　　② get操作和put操作都会访问key，使key的访问次数+1。
　　③ 如果多个内容访问次数相同，则删除最先访问的(也就是最久没访问的)。
　　用字典+二分法写了个效率很低的实现。

代码:

<br />import bisect
from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.value = {}  # '2': 3次
        self.frequency = defaultdict(int)
        self.mem = set()
        self.queue = []  # [2,3,4,5]
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.value:
            return -1
        frequency = self.frequency[key]
        self.queue.remove((frequency, key))
        idx = bisect.bisect(self.queue, (frequency + 1 ,float('inf')))  # 查找应该插入的位置
        self.queue.insert(idx, (frequency + 1, key))
        self.frequency[key] += 1
        return self.value[key]


    def put(self, key: int, value: int) -> None:
        if not self.capacity:
            return
        if key in self.value:
            self.value[key] = value
            self.get(key)  # 访问
            return

        if len(self.queue) >= self.capacity:  # 满了
            freq, peek = self.queue.pop(0)
            self.frequency[peek] = 0
            self.value.pop(peek)

        idx = bisect.bisect(self.queue, (0 ,float('inf')))  # 查找应该插入的位置
        self.queue.insert(idx, (0, key))

        self.value[key] = value

<br />import bisect

from collections import defaultdict

class LFUCache:

def __init__(self, capacity: int):

self.value = {} # '2': 3次

self.frequency = defaultdict(int)

self.mem = set()

self.queue = [] # [2,3,4,5]

self.capacity = capacity

def get(self, key: int) -> int:

if key not in self.value:

return -1

frequency = self.frequency[key]

self.queue.remove((frequency, key))

idx = bisect.bisect(self.queue, (frequency + 1 ,float('inf'))) # 查找应该插入的位置

self.queue.insert(idx, (frequency + 1, key))

self.frequency[key] += 1

return self.value[key]

def put(self, key: int, value: int) -> None:

if not self.capacity:

return

if key in self.value:

self.value[key] = value

self.get(key) # 访问

return

if len(self.queue) >= self.capacity: # 满了

freq, peek = self.queue.pop(0)

self.frequency[peek] = 0

self.value.pop(peek)

idx = bisect.bisect(self.queue, (0 ,float('inf'))) # 查找应该插入的位置

self.queue.insert(idx, (0, key))

self.value[key] = value

4月6日：编辑距离

难度 困难

题目描述

给定两个单词 word1 和 word2 ，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入: word1 = "horse", word2 = "ros"

输出: 3

解释:

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

输入: word1 = "intention", word2 = "execution"

输出: 5

解释:

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u')

题目链接

https://leetcode-cn.com/problems/edit-distance/

思路：

　　动态规划，令dp[i][j]表示word1[:i]变成word2[:j]的最少操作数。

　　先考虑为空时的情况，word1为空时，''变成word2[:j]需要加上j个个字符。同样，word2为空时，word1[:i]变成''需要减去i个字符。因此，dp[0][j]=j，dp[i][0]=i。

　　考虑不为空的情况。如果两个字符串当前的末尾相同，即word1[i-1]==word2[j-1]，那么dp[i][j]=dp[i-1][j-1]。如下如所示：

　　如果两个字符串当前的末尾不同，那么有三种处理方式。即1. 删除word1末尾的元素，然后按dp[i-1][j]处理；2. 将word1末尾的元素替换成word2末尾的元素，然后按dp[i-1][j-1]处理；3. 在word1末尾添加word2末尾的元素，然后按dp[i][j-1]处理。如下图所示：

　　最终dp[i][j]的值为这三种操作的操作次数中最少的。即dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1。

代码：

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # word1[i] word2[j]
        # dp[i][j] 表示 word1[i] 变成 word2[j]的最少操作数
        l1, l2 = len(word1), len(word2)
        dp = [[0 for j in range(l2+1)]for i in range(l1+1)]
        for i in range(l1+1):
            for j in range(l2+1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i
                else:
                    if word1[i-1] == word2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        # print(dp)
        return dp[-1][-1]

class Solution(object):

def minDistance(self, word1, word2):

"""

:type word1: str

:type word2: str

:rtype: int

"""

# word1[i] word2[j]

# dp[i][j] 表示 word1[i] 变成 word2[j]的最少操作数

l1, l2 = len(word1), len(word2)

dp = [[0 for j in range(l2+1)]for i in range(l1+1)]

for i in range(l1+1):

for j in range(l2+1):

if i == 0:

dp[i][j] = j

elif j == 0:

dp[i][j] = i

else:

if word1[i-1] == word2[j-1]:

dp[i][j] = dp[i-1][j-1]

else:

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

# print(dp)

return dp[-1][-1]

4月7日：旋转矩阵

难度中等

题目描述

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

给定 matrix =

[

[1,2,3],

[4,5,6],

[7,8,9]

原地旋转输入矩阵，使其变为:

[

[7,4,1],

[8,5,2],

[9,6,3]

]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

给定 matrix =

[

[ 5, 1, 9,11],

[ 2, 4, 8,10],

[13, 3, 6, 7],

[15,14,12,16]

原地旋转输入矩阵，使其变为:

[

[15,13, 2, 5],

[14, 3, 4, 1],

[12, 6, 8, 9],

[16, 7,10,11]

]

题目链接

https://leetcode-cn.com/problems/rotate-matrix-lcci/

思路:

　　其实就是48. 旋转图像换了个标题，这也太不走心了。。(我也不走心地抄一下那题的题解)
　　

　　扣四个边界出来。四个边界对应的点交换。每遍历一层，就往里缩一个矩阵。

代码:

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = matrix
        n = len(m) - 1
        for l in range((n+1) // 2):  # 从外往里第几层
            for i in range(n - l * 2):
                m[l][l+i], m[i+l][n-l], m[n-l][n-l-i], m[n-l-i][l] =  m[n-l-i][l], m[l][l+i], m[l+i][n-l], m[n-l][n-l-i]

class Solution:

def rotate(self, matrix: List[List[int]]) -> None:

"""

Do not return anything, modify matrix in-place instead.

"""

m = matrix

n = len(m) - 1

for l in range((n+1) // 2): # 从外往里第几层

for i in range(n - l * 2):

m[l][l+i], m[i+l][n-l], m[n-l][n-l-i], m[n-l-i][l] = m[n-l-i][l], m[l][l+i], m[l+i][n-l], m[n-l][n-l-i]

4月8日：机器人的运动范围

难度中等

题目描述

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

输入：m = 2, n = 3, k = 1

输出：3

示例 1：

输入：m = 3, n = 1, k = 0
输出：1

输入：m = 3, n = 1, k = 0

输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

题目链接

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

思路:

　　dfs，当数位和大于k时返回。
　　

代码:

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        visited = [[False for _ in range(n)] for _ in range(m)]
        ans = 0

        def dfs(i, j):
            nonlocal ans
            if i < 0 or j < 0 or i >= m or j >= n or visited[i][j]:
                return 

            if sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) > k:  # 数位和
                return

            visited[i][j] = True
            ans += 1
            for di, dj in arounds:
                x, y = i + di, j + dj
                dfs(x, y)

        dfs(0, 0)
        return ans

class Solution:

def movingCount(self, m: int, n: int, k: int) -> int:

arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[False for _ in range(n)] for _ in range(m)]

ans = 0

def dfs(i, j):

nonlocal ans

if i < 0 or j < 0 or i >= m or j >= n or visited[i][j]:

return

if sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) > k: # 数位和

return

visited[i][j] = True

ans += 1

for di, dj in arounds:

x, y = i + di, j + dj

dfs(x, y)

dfs(0, 0)

return ans

4月9日：括号生成

难度中等

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

题目链接

https://leetcode-cn.com/problems/generate-parentheses/

思路:

　　dfs。在搜索的过程中注意满足以下两个条件：

　　① 当前右括号的数量不能大于左括号的数量；

　　② 当前左括号的数量不能大于n。

代码:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        temp = ['.'] * (n * 2)
        ans = []
        def dfs(i, count, count_left):  # 0, 0
            nonlocal n
            if i >= n * 2:
                ans.append(''.join(temp))
                return
            if count > 0:
                temp[i] = ')'
                dfs(i + 1, count - 1, count_left)  # 去掉一个括号
                temp[i] = '.'
            if count_left < n:
                temp[i] = '('
                dfs(i + 1, count + 1, count_left + 1)  # 去掉一个括号
                temp[i] = '.'

        dfs(0, 0, 0)
        return ans

class Solution:

def generateParenthesis(self, n: int) -> List[str]:

temp = ['.'] * (n * 2)

ans = []

def dfs(i, count, count_left): # 0, 0

nonlocal n

if i >= n * 2:

ans.append(''.join(temp))

return

if count > 0:

temp[i] = ')'

dfs(i + 1, count - 1, count_left) # 去掉一个括号

temp[i] = '.'

if count_left < n:

temp[i] = '('

dfs(i + 1, count + 1, count_left + 1) # 去掉一个括号

temp[i] = '.'

dfs(0, 0, 0)

return ans

4月10日：翻转字符串里的单词

难度中等

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

  输入: "the sky is blue"
  输出: "blue is sky the"

输入: "the sky is blue"

输出: "blue is sky the"

示例 2：

  输入: "  hello world!  "
  输出: "world! hello"
  解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

输入: " hello world! "

输出: "world! hello"

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

  输入: "a good   example"
  输出: "example good a"
  解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

输入: "a good example"

输出: "example good a"

解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

题目链接

https://leetcode-cn.com/problems/reverse-words-in-a-string/

思路:

　　遇到这种题当然是愉快地调库啦。

代码:

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip(' ')  # 去掉前后的空格
        reverse = filter(lambda x: x != '', s.split(' ')[::-1])
        return ' '.join(reverse)

class Solution:

def reverseWords(self, s: str) -> str:

s = s.strip(' ') # 去掉前后的空格

reverse = filter(lambda x: x != '', s.split(' ')[::-1])

return ' '.join(reverse)

4月11日：鸡蛋掉落

难度困难

题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

输入：K = 1, N = 2

输出：2

解释：

鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。

否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。

如果它没碎，那么我们肯定知道 F = 2 。

因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：

输入：K = 2, N = 6
输出：3

输入：K = 2, N = 6

输出：3

示例 3：

输入：K = 3, N = 14
输出：4

输入：K = 3, N = 14

输出：4

提示：

1 <= K <= 100
1 <= N <= 10000

题目链接

https://leetcode-cn.com/problems/super-egg-drop/

思路:

　　由于鸡蛋的数量有限，碎了的鸡蛋就不能再用了，因此使用动态规划求解。
　　如果只有一个鸡蛋🥚，那就只能从第一层开始一层一层试，哪一层会碎就找到了F，总共需要N次。如果有无限多的鸡蛋，用二分法即可。
　　方法一：朴素遍历。考虑在第i层扔鸡蛋，扔下去的结果两种，碎、不碎。
　　如果碎了，说明F在0~i-1之间，还需要在0~i-1即i-1层楼中搜索；
　　如果没有碎，说明F在i~N之间，还需要再i+1~N层即N-i层楼中搜索。
　　记dp[N][K]表示有k个鸡蛋，N层楼中确定F的具体值的最小搜索次数。那么，假设某次搜索在第i楼，根据上面的思路，在第i楼扔下，存在两种结果：碎、不碎。然后根据结果分别在i楼上面或者下面的搜索区间继续搜索F的值。
　　因此可以得到递推公式dp[N][K] =min{ max(dp[i-1][K-1], dp[N-i][K]) + 1 | 1<=i<=N }。
　　显然，k>=1，而i为0时，表示没有任何楼层，那么dp[0][k]=0；
　　当k=1，只有一个鸡蛋，只能线性搜索，dp[N][K] = N。

　　方法二：二分法。方法一中的i是在1~N之间逐层去试，复杂度较高。如果i第一次取N/2，然后每次用二分法向消耗鸡蛋多的半边靠近，可以减少复杂度。

　　方法三：换一种dp思路。
　　① 无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
　　② 无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
　　根据这个特点，可以写出下面的状态转移方程：
　　dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1。
　　dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数k不变，也就是鸡蛋没碎，扔鸡蛋次数m减一；
　　dp[k - 1][m - 1] 就是楼下的楼层数，因为鸡蛋个数k减一，也就是鸡蛋碎了，同时扔鸡蛋次数m减一。

代码:

　　方法一：(朴素遍历，超时)

<br />class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        from functools import lru_cache
        @lru_cache(None)
        def dp(N, K):
            if K == 1:  # 只有一个鸡蛋
                return N
            if N == 0:  # 没有任何楼层
                return 0

            ans = float('inf')

            for i in range(1, N+1):
                ans = min(ans, max(dp(i-1, K-1), dp(N-i, K)) + 1)  # 碎了 没碎

            return ans


        return dp(N, K)

<br />class Solution:

def superEggDrop(self, K: int, N: int) -> int:

from functools import lru_cache

@lru_cache(None)

def dp(N, K):

if K == 1: # 只有一个鸡蛋

return N

if N == 0: # 没有任何楼层

return 0

ans = float('inf')

for i in range(1, N+1):

ans = min(ans, max(dp(i-1, K-1), dp(N-i, K)) + 1) # 碎了没碎

return ans

return dp(N, K)

　　方法二：(二分，1944ms)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        from functools import lru_cache
        @lru_cache(None)
        def dp(k,n):
            if n == 0:return 0
            if k==1:return n
            ans = float('inf')

            lo,hi = 1,n
            while lo<=hi:
                mid = lo+(hi-lo)//2
                broke = dp(k-1,mid-1)
                not_broke = dp(k,n-mid)

                if broke>not_broke:
                    hi = mid-1
                    ans = min(ans,broke+1)
                else:
                    lo = mid+1
                    ans = min(ans,not_broke+1)

            return ans

        return dp(K,N)

class Solution:

def superEggDrop(self, K: int, N: int) -> int:

from functools import lru_cache

@lru_cache(None)

def dp(k,n):

if n == 0:return 0

if k==1:return n

ans = float('inf')

lo,hi = 1,n

while lo<=hi:

mid = lo+(hi-lo)//2

broke = dp(k-1,mid-1)

not_broke = dp(k,n-mid)

if broke>not_broke:

hi = mid-1

ans = min(ans,broke+1)

else:

lo = mid+1

ans = min(ans,not_broke+1)

return ans

return dp(K,N)

　　方法三：(换一种角度，172ms)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0 for _ in range(N+1)] for _ in range(K+1)]
        for i in range(N+1): dp[0][i] = 0
        for i in range(K+1): dp[i][0] = 0
        m = 0  # 需要几个鸡蛋
        while dp[K][m] < N:
            m += 1
            for k in range(1, K+1):
                dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1

        return m

class Solution:

def superEggDrop(self, K: int, N: int) -> int:

dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

for i in range(N+1): dp[0][i] = 0

for i in range(K+1): dp[i][0] = 0

m = 0 # 需要几个鸡蛋

while dp[K][m] < N:

m += 1

for k in range(1, K+1):

dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1

return m

4月12日：交点

难度困难

题目描述

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：

输入： line1 = {0, 0}, {1, 0} line2 = {1, 1}, {0, -1} 输出： {0.5, 0}

1
2
3
4
5

输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出： {0.5, 0}

示例 2：

输入： line1 = {0, 0}, {3, 3} line2 = {1, 1}, {2, 2} 输出： {1, 1}

1
2
3
4
5

输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出： {1, 1}

示例 3：

输入： line1 = {0, 0}, {1, 1} line2 = {1, 0}, {2, 1} 输出： {}，两条线段没有交点

1
2
3
4
5

输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出： {}，两条线段没有交点

提示：
- 坐标绝对值不会超过 2^7
- 输入的坐标均是有效的二维坐标
题目链接

https://leetcode-cn.com/problems/intersection-lcci/

思路:

　　写的头皮发麻。。
　　① 两直线斜率都不存在，单独考虑是否相交；
　　② 考虑某一条直线斜率不存在；
　　③ 考虑两直线平行，是否有重合部分；
　　④ 两直线不平行，是否相交。
　　斜率公式：
$\displaystyle k_1 = \frac{y_1'-y_1}{x_1'-x_1}, b_1 = y_1 - k_1x_1$ 　　(代码中x_表示x’)

代码:

  class Solution:
      def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
          if start1[0] > end1[0]:
              start1, end1 = end1, start1

          if start2[0] > end2[0]:
              start2, end2 = end2, start2

          x1, y1 = start1[0], start1[1]
          x1_, y1_ = end1[0], end1[1]  # 后端点
          x2, y2 = start2[0], start2[1]
          x2_, y2_ = end2[0], end2[1]

          if not x1_ - x1:
              k1 = float('inf')
          else:
              k1 = (y1_ - y1) / (x1_ - x1)
              b1 = y1 - k1 * x1  # y-kx

          if not x2_ - x2:
              k2 = float('inf')
          else:
              k2 = (y2_ - y2) / (x2_ - x2)
              b2 = y2 - k2 * x2  # y-kx

          if k1 == float('inf') and k2 == float('inf'):  # 两条线斜率都为正无穷
              if x1 != x2: return []
              x = x1
              if max(y1, y1_) >= min(y2, y2_) and min(y1, y1_) <= max(y2, y2_):
                  return [x, max(min(y1, y1_), min(y2, y2_))]
              else:
                  return []

          if k2 == float('inf'): # k2 斜率为正无穷，则把两条线段交换一下
              k1, k2 = k2, k1
              b1, b2 = b2, b1
              x1, y1, x2, y2 = x2, y2, x1, y1
              x1_, y1_, x2_, y2_ = x2_, y2_, x1_, y1_

          if k1 == float('inf'):  # 有一条线段斜率为正无穷
              x = x1
              y = k2 * x + b2
              if y1 <= y <= y1_:
                  return [x, y]
              return []

          if k1 == k2:  # 平行
              if b1 != b2:
                  return []
              if x1_ >= x2 and x1 <= x2_:
                  x = max(x1, x2)
                  return [x, k1 * x + b1]
              else:
                  return []

          # 不平行，斜率也都存在
          x = (b2 - b1) / (k1 - k2)
          y = k1 * x + b1
          if x1 <= x <= x1_ and x2 <= x <= x2_:
              return [x, y] 
          return []

class Solution:

def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:

if start1[0] > end1[0]:

start1, end1 = end1, start1

if start2[0] > end2[0]:

start2, end2 = end2, start2

x1, y1 = start1[0], start1[1]

x1_, y1_ = end1[0], end1[1] # 后端点

x2, y2 = start2[0], start2[1]

x2_, y2_ = end2[0], end2[1]

if not x1_ - x1:

k1 = float('inf')

else:

k1 = (y1_ - y1) / (x1_ - x1)

b1 = y1 - k1 * x1 # y-kx

if not x2_ - x2:

k2 = float('inf')

else:

k2 = (y2_ - y2) / (x2_ - x2)

b2 = y2 - k2 * x2 # y-kx

if k1 == float('inf') and k2 == float('inf'): # 两条线斜率都为正无穷

if x1 != x2: return []

x = x1

if max(y1, y1_) >= min(y2, y2_) and min(y1, y1_) <= max(y2, y2_):

return [x, max(min(y1, y1_), min(y2, y2_))]

else:

return []

if k2 == float('inf'): # k2 斜率为正无穷，则把两条线段交换一下

k1, k2 = k2, k1

b1, b2 = b2, b1

x1, y1, x2, y2 = x2, y2, x1, y1

x1_, y1_, x2_, y2_ = x2_, y2_, x1_, y1_

if k1 == float('inf'): # 有一条线段斜率为正无穷

x = x1

y = k2 * x + b2

if y1 <= y <= y1_:

return [x, y]

return []

if k1 == k2: # 平行

if b1 != b2:

return []

if x1_ >= x2 and x1 <= x2_:

x = max(x1, x2)

return [x, k1 * x + b1]

else:

return []

# 不平行，斜率也都存在

x = (b2 - b1) / (k1 - k2)

y = k1 * x + b1

if x1 <= x <= x1_ and x2 <= x <= x2_:

return [x, y]

return []

4月13日：设计推特

难度中等

题目描述

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：

postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户

示例:

Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);

// 用户1关注了用户2.
twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);

// 用户1取消关注了用户2.
twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).

twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.

twitter.getNewsFeed(1);

// 用户1关注了用户2.

twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).

twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].

// 推文id6应当在推文id5之前，因为它是在5之后发送的.

twitter.getNewsFeed(1);

// 用户1取消关注了用户2.

twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.

// 因为用户1已经不再关注用户2.

twitter.getNewsFeed(1);

题目链接

https://leetcode-cn.com/problems/design-twitter/

思路:

　　获取所有关注的人的前10条twitter，然后按时间排序后取前10条。

代码:

from collections import defaultdict
class Twitter:

    def __init__(self):
        self.usertwits = defaultdict(list)  # uid: [1,2,3]
        self.follows =  defaultdict(set)  # uid: [fid]
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.usertwits[userId].append((self.time, tweetId))
        self.time += 1  

    def getNewsFeed(self, userId: int) -> List[int]:
        follows = self.follows[userId]
        follows.add(userId)  # 自己的也算上
        ans = []
        for uid in follows:
            twits = self.usertwits[uid]
            n = len(twits)
            recent_10 = self.usertwits[uid][max(0, n-10): n]
            ans.extend(recent_10)

        ans.sort(reverse=True)
        return [a[1] for a in ans[:10]]


    def follow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].add(followeeId)


    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

from collections import defaultdict

class Twitter:

def __init__(self):

self.usertwits = defaultdict(list) # uid: [1,2,3]

self.follows = defaultdict(set) # uid: [fid]

self.time = 0

def postTweet(self, userId: int, tweetId: int) -> None:

self.usertwits[userId].append((self.time, tweetId))

self.time += 1

def getNewsFeed(self, userId: int) -> List[int]:

follows = self.follows[userId]

follows.add(userId) # 自己的也算上

ans = []

for uid in follows:

twits = self.usertwits[uid]

n = len(twits)

recent_10 = self.usertwits[uid][max(0, n-10): n]

ans.extend(recent_10)

ans.sort(reverse=True)

return [a[1] for a in ans[:10]]

def follow(self, followerId: int, followeeId: int) -> None:

self.follows[followerId].add(followeeId)

def unfollow(self, followerId: int, followeeId: int) -> None:

self.follows[followerId].discard(followeeId)

4月14日：两数相加 II

难度中等

题目描述

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。 进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 8 -> 0 -> 7

题目链接

https://leetcode-cn.com/problems/add-two-numbers-ii/

思路:

　　翻转l1和l2，相加后再翻转回来。

　　如果不能翻转，可以用栈来做，将两个链表对应元素的和入栈，到两个链表都结尾时再出栈并且加上进位。

代码:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def merge(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
        if not l1 and not l2:
            return None if not carry else ListNode(carry)

        val1, n1 = (l1.val, l1.next) if l1 else (0, None)
        val2, n2 = (l2.val, l2.next) if l2 else (0, None)
        num = val1 + val2 + carry
        ans = ListNode(num%10)
        ans.next = self.merge(n1, n2, num//10)
        return ans

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def reverse(head):
            node = head
            rever = None
            while node:
                node.next, rever, node = rever, node, node.next
            return rever

        merge = self.merge(reverse(l1), reverse(l2))
        return reverse(merge)

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def merge(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:

if not l1 and not l2:

return None if not carry else ListNode(carry)

val1, n1 = (l1.val, l1.next) if l1 else (0, None)

val2, n2 = (l2.val, l2.next) if l2 else (0, None)

num = val1 + val2 + carry

ans = ListNode(num%10)

ans.next = self.merge(n1, n2, num//10)

return ans

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

def reverse(head):

node = head

rever = None

while node:

node.next, rever, node = rever, node, node.next

return rever

merge = self.merge(reverse(l1), reverse(l2))

return reverse(merge)

4月15日：01 矩阵

难度中等

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

0 0 0
0 1 0
0 0 0

0 0 0

0 1 0

0 0 0

输出:

0 0 0
0 1 0
0 0 0

0 0 0

0 1 0

0 0 0

示例 2:

输入:

0 0 0
0 1 0
1 1 1

0 0 0

0 1 0

1 1 1

输出:

0 0 0
0 1 0
1 2 1

0 0 0

0 1 0

1 2 1

题目链接

https://leetcode-cn.com/problems/01-matrix/

思路:

　　方法一：bfs。将所有的"0"看做一个整体，向其他数字的位置腐蚀(将它们变成0)，当格子上所有数字都为"0"时结束循环。记录循环的深度就是结果。

　　方法二：动态规划，因为最近的"0"要么在左上方，要么在右下方。因此只要分别从左上角到右下角和从右下角到左上角动态规划一次，就得到了最终的结果。

　　其中从左上到右下的状态转移方程为dp[i][j] = min(dp[i][j], dp[i-1][j] + 1, dp[i][j-1] + 1)。

代码:

　　方法一：(bfs)

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右
        grid = matrix
        m = len(matrix)
        if not m: return []
        n = len(matrix[0])

        ans = [[0 for _ in range(n)] for _ in range(m)]
        temp = []

        def rot(x, y):
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
                return False
            if grid[x][y] != 0:  # 成功腐烂新鲜的橘子，返回True
                grid[x][y] = 0  
                temp.append((x, y))
                return True
            return False

        depth = 0
        queue = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:  # 腐烂的橘子
                    queue.append((i, j))

        while queue: 
            temp = []
            for i, j in queue:
                ans[i][j] = depth
                for di, dj in arounds:
                    rot(i + di, j + dj)

            depth += 1

            queue = temp

        return ans

class Solution:

def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:

arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右

grid = matrix

m = len(matrix)

if not m: return []

n = len(matrix[0])

ans = [[0 for _ in range(n)] for _ in range(m)]

temp = []

def rot(x, y):

if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):

return False

if grid[x][y] != 0: # 成功腐烂新鲜的橘子，返回True

grid[x][y] = 0

temp.append((x, y))

return True

return False

depth = 0

queue = []

for i in range(m):

for j in range(n):

if grid[i][j] == 0: # 腐烂的橘子

queue.append((i, j))

while queue:

temp = []

for i, j in queue:

ans[i][j] = depth

for di, dj in arounds:

rot(i + di, j + dj)

depth += 1

queue = temp

return ans

　　方法二：(dp)

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右
        grid = matrix
        m = len(matrix)
        if not m: return []
        n = len(matrix[0])

        dp = [[float('inf') for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    dp[i][j] = 0

        for i in range(m):  # 左上到右下
            for j in range(n):
                if i > 0:
                    dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
                if j > 0:
                    dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)

        for i in range(m-1,-1,-1):  # 右下到左上
            for j in range(n-1,-1,-1):
                if i < m-1:
                    dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
                if j < n-1:
                    dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)

        return dp

class Solution:

def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:

arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右

grid = matrix

m = len(matrix)

if not m: return []

n = len(matrix[0])

dp = [[float('inf') for _ in range(n)] for _ in range(m)]

for i in range(m):

for j in range(n):

if matrix[i][j] == 0:

dp[i][j] = 0

for i in range(m): # 左上到右下

for j in range(n):

if i > 0:

dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)

if j > 0:

dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)

for i in range(m-1,-1,-1): # 右下到左上

for j in range(n-1,-1,-1):

if i < m-1:

dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)

if j < n-1:

dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)

return dp

4月16日：合并区间

难度中等

题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,3],[2,6],[8,10],[15,18]]

输出: [[1,6],[8,10],[15,18]]

解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

输入: [[1,4],[4,5]]

输出: [[1,5]]

解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目链接

https://leetcode-cn.com/problems/merge-intervals/

思路:

　　先将intervals排序，令ans=[intervals[0]]，取intervals中的每一个元素尝试与ans的最后一个元素合并。如果重合，则合并后放回ans[-1]；如果不重合，则append到ans的最后。

代码:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        s = sorted(intervals)
        ans = [s[0]]
        for i in s[1:]:
            if i[0] <= ans[-1][1]:
                ans[-1] = [ans[-1][0], max(i[1], ans[-1][1])] 
            else:
                ans.append(i)

        return ans

class Solution:

def merge(self, intervals: List[List[int]]) -> List[List[int]]:

if len(intervals) == 0:

return []

s = sorted(intervals)

ans = [s[0]]

for i in s[1:]:

if i[0] <= ans[-1][1]:

ans[-1] = [ans[-1][0], max(i[1], ans[-1][1])]

else:

ans.append(i)

return ans

4月17日：跳跃游戏

难度 中等

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

输入: [2,3,1,1,4]

输出: true

解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

输入: [3,2,1,0,4]

输出: false

解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

题目链接

https://leetcode-cn.com/problems/jump-game/

思路：

　　方法一：贪心算法。与A45. 跳跃游戏II类似，每次都跳到最划算的位置。
　　方法二：从右往左遍历，如果某个位置能走到最后则截断后面的元素。如果某个元素为0则从前面找能走到它后面的。方法二比方法一用时短一些。

代码：

　　方法一：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True

        i = 0  # 当前位置
        while nums[i] != 0 and i < n-1:
            temp_indic = 0
            temp_max = -1
            for j in range(nums[i]):
                if i + j + 1 >= n - 1:
                    return True
                if nums[i + j + 1] + j > temp_max:
                    temp_indic = i + j + 1
                    temp_max = nums[i + j + 1] + j
            i = temp_indic

        return i >= n-1

class Solution:

def canJump(self, nums: List[int]) -> bool:

n = len(nums)

if n == 1:

return True

i = 0 # 当前位置

while nums[i] != 0 and i < n-1:

temp_indic = 0

temp_max = -1

for j in range(nums[i]):

if i + j + 1 >= n - 1:

return True

if nums[i + j + 1] + j > temp_max:

temp_indic = i + j + 1

temp_max = nums[i + j + 1] + j

i = temp_indic

return i >= n-1

　　方法二：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True

        j = 0
        for i in range(n-2,-1,-1):
            if nums[i] == 0 or j > 0:  # 出现了或之前出现过0，则每次都加一
                j += 1
            if nums[i] >= j:  # 如果当前位置能跳过最后一个0，则归0
                j = 0

        return j == 0

class Solution:

def canJump(self, nums: List[int]) -> bool:

n = len(nums)

if n == 1:

return True

j = 0

for i in range(n-2,-1,-1):

if nums[i] == 0 or j > 0: # 出现了或之前出现过0，则每次都加一

j += 1

if nums[i] >= j: # 如果当前位置能跳过最后一个0，则归0

j = 0

return j == 0

4月18日：盛最多水的容器

难度 中等

题目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

输入：[1,8,6,2,5,4,8,3,7]

输出：49

题目链接

https://leetcode-cn.com/problems/container-with-most-water/

思路：

　　方法一：用lefts记录heights从左到右所有比之前最高的还高的线，rights记录从右到左所有比之前最高的还高的线。遍历lefts和rights，其中必有一种组合能够容纳最多的水。
　　方法二：双指针，初始时设头指针和尾指针分别为i和j。我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

代码：

　　方法一：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        lefts = [0]
        rights = [len(height)-1]
        tmp = height[0]
        for i, num in enumerate(height):
            if num > tmp: 
                lefts.append(i)
                tmp = num


        tmp = height[-1]
        for i in range(len(height)-1,-1,-1):
            num = height[i]
            if num > tmp: 
                rights.append(i)
                tmp = num

        def calc(i1, i2):
            return (i2-i1) * (min(height[i1],height[i2]))

        l, r = len(lefts), len(rights)
        i, j = 0, 0
        ans = 0

        for ll in lefts:
            for rr in rights:
                temp = calc(ll,rr)
                if temp > ans:
                    ans = temp
        return ans

class Solution:

def maxArea(self, height: List[int]) -> int:

lefts = [0]

rights = [len(height)-1]

tmp = height[0]

for i, num in enumerate(height):

if num > tmp:

lefts.append(i)

tmp = num

tmp = height[-1]

for i in range(len(height)-1,-1,-1):

num = height[i]

if num > tmp:

rights.append(i)

tmp = num

def calc(i1, i2):

return (i2-i1) * (min(height[i1],height[i2]))

l, r = len(lefts), len(rights)

i, j = 0, 0

ans = 0

for ll in lefts:

for rr in rights:

temp = calc(ll,rr)

if temp > ans:

ans = temp

return ans

　　方法二：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = len(height)
        i, j = 0, l - 1
        ans = 0
        while i < j:
            h = min(height[i], height[j])
            ans = max(ans, h * (j-i))
            # 指针向所指的高较小的那个指针进行移动
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1

        return ans

class Solution:

def maxArea(self, height: List[int]) -> int:

l = len(height)

i, j = 0, l - 1

ans = 0

while i < j:

h = min(height[i], height[j])

ans = max(ans, h * (j-i))

# 指针向所指的高较小的那个指针进行移动

if height[i] < height[j]:

i += 1

else:

j -= 1

return ans

4月19日：统计重复个数

难度困难

题目描述

由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，["abc",3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，”abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

示例：

输入：
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回：
2

输入：

s1 ="acb",n1 = 4

s2 ="ab",n2 = 2

题目链接

https://leetcode-cn.com/problems/count-the-repetitions/

思路:

　　找循环节，将中间循环的部分、开头的部分和结尾的部分分别考虑，开头的a个s1包含b个s2，中间每m个s1包含n个s2，最后还剩x个s1包含y个s2。

　　则S1总共包含b + (n1-a-x)//m*n + y个s2。S1包含ans个s2，那么就包含ans // n2个S2。

代码:

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0
        s1cnt, index, s2cnt = 0, 0, 0
        recall = dict()
        while True:
            s1cnt += 1
            for ch in s1:
                if ch == s2[index]:
                    index += 1
                    if index == len(s2):
                        s2cnt, index = s2cnt + 1, 0

            if s1cnt == n1:
                return s2cnt // n2

            if index in recall:
                a, b = recall[index]
                # 前 a个 s1 包含了 b 个 s2
                pre_loop = (a, b)
                # 以后的每 m 个 s1 包含了 n 个 s2
                m, n = s1cnt - a, s2cnt - b
                in_loop = (m, n)
                break
            else:
                recall[index] = (s1cnt, s2cnt)

        ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]
        # S1 的末尾还剩下x个 s1，我们暴力进行匹配
        x = (n1 - pre_loop[0]) % in_loop[0]
        for i in range(x):
            for ch in s1:
                if ch == s2[index]:
                    index += 1
                    if index == len(s2):
                        ans, index = ans + 1, 0
        # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
        return ans // n2

class Solution:

def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:

if n1 == 0:

return 0

s1cnt, index, s2cnt = 0, 0, 0

recall = dict()

while True:

s1cnt += 1

for ch in s1:

if ch == s2[index]:

index += 1

if index == len(s2):

s2cnt, index = s2cnt + 1, 0

if s1cnt == n1:

return s2cnt // n2

if index in recall:

a, b = recall[index]

# 前 a个 s1 包含了 b 个 s2

pre_loop = (a, b)

# 以后的每 m 个 s1 包含了 n 个 s2

m, n = s1cnt - a, s2cnt - b

in_loop = (m, n)

break

else:

recall[index] = (s1cnt, s2cnt)

ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]

# S1 的末尾还剩下x个 s1，我们暴力进行匹配

x = (n1 - pre_loop[0]) % in_loop[0]

for i in range(x):

for ch in s1:

if ch == s2[index]:

index += 1

if index == len(s2):

ans, index = ans + 1, 0

# S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2

return ans // n2

4月20日：岛屿数量

难度中等

题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:

11110

11010

11000

00000

输出: 1

示例 2:

输入:

11000

00100

00011

输出: 3

题目链接

https://leetcode-cn.com/problems/number-of-islands/

思路:

　　经典dfs。遍历整个矩阵，从任意"1"的位置开始dfs，同时计数+1，搜索岛屿的过程中将搜索过的位置都置为"0"。最终计数的结果就是岛屿的数量。

代码:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右
        m = len(grid)
        if not m:
            return 0
        n = len(grid[0])

        ans = 0
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n:
                return
            if grid[i][j] == "0":
                return 

            grid[i][j] = "0"
            for di, dj in arounds:
                dfs(i + di, j + dj)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    ans += 1
                    dfs(i, j)

        return ans

class Solution:

def numIslands(self, grid: List[List[str]]) -> int:

arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右

m = len(grid)

if not m:

return 0

n = len(grid[0])

ans = 0

def dfs(i, j):

if i < 0 or j < 0 or i >= m or j >= n:

return

if grid[i][j] == "0":

return

grid[i][j] = "0"

for di, dj in arounds:

dfs(i + di, j + dj)

for i in range(m):

for j in range(n):

if grid[i][j] == "1":

ans += 1

dfs(i, j)

return ans

4月21日：统计「优美子数组」

难度中等

题目描述

给你一个整数数组 nums 和一个整数 k。

如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

输入：nums = [1,1,2,1,1], k = 3

输出：2

解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

输入：nums = [2,4,6], k = 1

输出：0

解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2

输出：16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

题目链接

https://leetcode-cn.com/problems/count-number-of-nice-subarrays/

思路:

　　方法一：双指针。维护一个滑动窗口，记录其中的奇数个数，如果奇数个数大于k，则左指针向右移。
　　方法二：这道题的本质是统计所有相隔为(k-1)的奇数的左右偶数的乘积的和。用一个字典mem记录第i个奇数的左边的偶数个数+1。利用第i个奇数右边的偶数=第i+1个奇数左边的偶数这个性质，只要计算所有mem[temp] * mem[temp-k]的和即可。

　　为了便于理解，以nums = [2,2,2,1,2,2,1,2,2,2]为例，nums中共有2个奇数。

mem[0] = 4
mem[1] = 3
mem[2] = 4  # 结尾的偶数也要计算进去
由于k=2， 因此ans = mem[2] * mem[2-k] = 16

mem[0] = 4

mem[1] = 3

mem[2] = 4 # 结尾的偶数也要计算进去

由于k=2，因此ans = mem[2] * mem[2-k] = 16

代码:

　　方法一：

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        left = 0
        cnt = 0
        ans = 0
        fist_right = 0
        nums.append(-1)
        for right, num in enumerate(nums):
            if num % 2 == 1:
                cnt += 1

            if cnt > k or right == len(nums):
                # 从right-1开始往左数偶数
                j = right - 1
                while j >= 0 and nums[j] % 2 == 0:
                    j -= 1

                i = left
                while left < right and nums[left] % 2 == 0:
                    left += 1  # 重复去掉偶数
                left += 1  # 再去掉一个奇数 使得窗口内的奇数个数仍然为k
                cnt -= 1

                ans += (right - j) * (left - i)

        return ans

class Solution:

def numberOfSubarrays(self, nums: List[int], k: int) -> int:

left = 0

cnt = 0

ans = 0

fist_right = 0

nums.append(-1)

for right, num in enumerate(nums):

if num % 2 == 1:

cnt += 1

if cnt > k or right == len(nums):

# 从right-1开始往左数偶数

j = right - 1

while j >= 0 and nums[j] % 2 == 0:

j -= 1

i = left

while left < right and nums[left] % 2 == 0:

left += 1 # 重复去掉偶数

left += 1 # 再去掉一个奇数使得窗口内的奇数个数仍然为k

cnt -= 1

ans += (right - j) * (left - i)

return ans

　　方法二：

from collections import defaultdict

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        nums.append(-1)
        mem = defaultdict(int)  # mem[i]=j 表示第i个奇数前面有j+1个偶数
        temp = 0
        cnt = 0
        ans = 0
        for num in nums:
            if num % 2 == 0:
                cnt += 1
            else:
                mem[temp] = cnt + 1
                if temp >= k:
                    ans += mem[temp] * mem[temp-k]

                temp += 1
                cnt = 0

        return ans

from collections import defaultdict

class Solution:

def numberOfSubarrays(self, nums: List[int], k: int) -> int:

nums.append(-1)

mem = defaultdict(int) # mem[i]=j 表示第i个奇数前面有j+1个偶数

temp = 0

cnt = 0

ans = 0

for num in nums:

if num % 2 == 0:

cnt += 1

else:

mem[temp] = cnt + 1

if temp >= k:

ans += mem[temp] * mem[temp-k]

temp += 1

cnt = 0

return ans

4月22日：二叉树的右视图

难度中等

题目描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

输入: [1,2,3,null,5,null,4]

输出: [1, 3, 4]

解释:

1 <---

/ \

2 3 <---

\ \

5 4 <---

题目链接

https://leetcode-cn.com/problems/binary-tree-right-side-view/

思路:

　　使用层序遍历，并只保留每层最后一个节点的值。

代码:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:

        if not root:
            return []

        queue = [root]
        ans = []
        while queue:
            temp = []
            ans.append(queue[-1].val)
            for q in queue:
                if q.left:
                    temp.append(q.left)
                if q.right:
                    temp.append(q.right)

            queue = temp

        return ans

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

def rightSideView(self, root: TreeNode) -> List[int]:

if not root:

return []

queue = [root]

ans = []

while queue:

temp = []

ans.append(queue[-1].val)

for q in queue:

if q.left:

temp.append(q.left)

if q.right:

temp.append(q.right)

queue = temp

return ans

4月23日：硬币

难度中等

题目描述

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

输入: n = 5

输出：2

解释: 有两种方式可以凑成总金额:

5=5

5=1+1+1+1+1

示例2:

 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

输入: n = 10

输出：4

解释: 有四种方式可以凑成总金额:

10=10

10=5+5

10=5+1+1+1+1+1

10=1+1+1+1+1+1+1+1+1+1

说明：

注意:

你可以假设：

0 <= n (总金额) <= 1000000

题目链接

https://leetcode-cn.com/problems/coin-lcci/

思路:

　　动态规划。先计算最大硬币为1的种类数，再依次计算最大硬币为5、10、25的种类数。

代码:

class Solution:
    def waysToChange(self, n):
        dp = [1] + [0] * n
        for c in [1, 5, 10, 25]:
            for i in range(c, n + 1):
                dp[i] += dp[i - c]
        return dp[-1] % (10**9 + 7)

class Solution:

def waysToChange(self, n):

dp = [1] + [0] * n

for c in [1, 5, 10, 25]:

for i in range(c, n + 1):

dp[i] += dp[i - c]

return dp[-1] % (10**9 + 7)

4月24日：数组中的逆序对

难度困难

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

输入: [7,5,6,4]

输出: 5

限制：

0 <= 数组长度 <= 50000

1 2	0 <= 数组长度 <= 50000

题目链接

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

思路:

　　方法一：二分法，维护一个升序数组asc，存放已有的数字。由于后放进去的数字下标大，找到asc中比它大的数有几个即可。

　　方法二：归并排序，先分别计算左右半边有多少逆序对，然后计算一个数在左边，一个数在右边的逆序对的个数。

代码:

　　方法一：(二分法，2020ms)

import bisect
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        asc = []
        ans = 0
        for num in nums:
            idx = bisect.bisect(asc, num)
            ans += len(asc) - idx
            bisect.insort(asc, num)

        return ans

import bisect

class Solution:

def reversePairs(self, nums: List[int]) -> int:

asc = []

ans = 0

for num in nums:

idx = bisect.bisect(asc, num)

ans += len(asc) - idx

bisect.insort(asc, num)

return ans

　　方法二：(归并排序，1464 ms)

import bisect
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(i, j):
            if j - i <= 1:  # 只有1个数或0个数
                return 0
            mid = (i + j)//2
            left = merge_sort(i, mid)
            right = merge_sort(mid, j)
            ans = left + right

            b = sorted(nums[mid:j])  # 左边比右边大

            for a in range(i, mid):
                idx = bisect.bisect_left(b, nums[a])
                ans += idx

            return ans

        return merge_sort(0, len(nums))

import bisect

class Solution:

def reversePairs(self, nums: List[int]) -> int:

def merge_sort(i, j):

if j - i <= 1: # 只有1个数或0个数

return 0

mid = (i + j)//2

left = merge_sort(i, mid)

right = merge_sort(mid, j)

ans = left + right

b = sorted(nums[mid:j]) # 左边比右边大

for a in range(i, mid):

idx = bisect.bisect_left(b, nums[a])

ans += idx

return ans

return merge_sort(0, len(nums))

4月25日：全排列

难度中等

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

题目链接

https://leetcode-cn.com/problems/permutations/

思路:

　　dfs。

代码:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        temp = []
        ans = []
        l = len(nums)
        def dfs(n):  # 0~2
            if n > l - 1:
                ans.append(temp.copy())
                return 

            for num in nums:
                if num in temp:
                    continue

                temp.append(num)
                dfs(n+1)
                temp.pop()  # 还原现场

        dfs(0)
        return ans

class Solution:

def permute(self, nums: List[int]) -> List[List[int]]:

temp = []

ans = []

l = len(nums)

def dfs(n): # 0~2

if n > l - 1:

ans.append(temp.copy())

return

for num in nums:

if num in temp:

continue

temp.append(num)

dfs(n+1)

temp.pop() # 还原现场

dfs(0)

return ans

4月26日：合并K个排序链表

难度困难

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

题目链接

https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路:

　　分治法，当只有一个链表时直接返回。否则：

　　① 合并左半边的链表，记为left；

　　② 合并右半边的链表，记为right；

　　③ 合并left和right(参考合并两个有序链表)。

　　时间复杂度O(nlog(k))，n是所有链表中元素的总和，k是链表个数。

代码:

class Solution:
    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:  # 合并两个链表
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l2.next, l1)
            return l2

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)
        if not n:
            return

        if n == 1:  # 只有一个，不用合并
            return lists[0]

        mid = n // 2  # 至少为1
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge(left, right)

class Solution:

def merge(self, l1: ListNode, l2: ListNode) -> ListNode: # 合并两个链表

if not l1: return l2

if not l2: return l1

if l1.val <= l2.val:

l1.next = self.merge(l1.next, l2)

return l1

else:

l2.next = self.merge(l2.next, l1)

return l2

def mergeKLists(self, lists: List[ListNode]) -> ListNode:

n = len(lists)

if not n:

return

if n == 1: # 只有一个，不用合并

return lists[0]

mid = n // 2 # 至少为1

left = self.mergeKLists(lists[:mid])

right = self.mergeKLists(lists[mid:])

return self.merge(left, right)

4月27日：搜索旋转排序数组

难度 中等

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

输入: nums = [4,5,6,7,0,1,2], target = 0

输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

输入: nums = [4,5,6,7,0,1,2], target = 3

输出: -1

题目链接

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

思路：

　　nums从中间切一半，必然有一半是有序的，另一半是无序的，对有序的一半二分查找，对无序的一半递归调用该算法。
　　如果第一个数nums[i] 小于中间的数nums[mid]，则左半边有序，否则右半边有序。

代码：

class Solution:
    def helper(self, nums: List[int], i, j, target):
        if j <= i:
            return -1
        n = j - i
        if n <= 2:
            for k in range(i, j):
                if nums[k] == target:
                    return k
            return -1

        middle = (i + j) // 2

        if nums[i] < nums[middle]:
            # 对左边进行二分查找，对右边递归
            start, end = middle, j
            j = middle
        else:
            # 对右边进行二分查找，对左边递归
            start, end = i, middle
            i = middle

        while i <= j and i < len(nums):
            mid = (i + j) // 2
            if nums[mid] > target:
                j = mid - 1
            elif nums[mid] < target:
                i = mid + 1
            else:
                if nums[mid] == target:
                    return mid

        return self.helper(nums, start, end, target)


    def search(self, nums: List[int], target: int) -> int:
        return self.helper(nums, 0, len(nums), target)

class Solution:

def helper(self, nums: List[int], i, j, target):

if j <= i:

return -1

n = j - i

if n <= 2:

for k in range(i, j):

if nums[k] == target:

return k

return -1

middle = (i + j) // 2

if nums[i] < nums[middle]:

# 对左边进行二分查找，对右边递归

start, end = middle, j

j = middle

else:

# 对右边进行二分查找，对左边递归

start, end = i, middle

i = middle

while i <= j and i < len(nums):

mid = (i + j) // 2

if nums[mid] > target:

j = mid - 1

elif nums[mid] < target:

i = mid + 1

else:

if nums[mid] == target:

return mid

return self.helper(nums, start, end, target)

def search(self, nums: List[int], target: int) -> int:

return self.helper(nums, 0, len(nums), target)

4月28日：数组中数字出现的次数

难度中等

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

输入：nums = [4,1,4,6]

输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

输入：nums = [1,2,10,4,1,4,3,3]

输出：[2,10] 或 [10,2]

限制：

2 <= nums <= 10000

题目链接

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

思路:

　　数组里面所有数异或 =目标两个数异或 。由于这两个数不同，所以异或结果必然不为0。

　　假设数组异或的二进制结果为10010，那么说明这两个数从右向左数第2位是不同的。

　　那么可以根据数组里面所有数的第二位为0或者1将数组划分为2个子数组。

　　这样做可以将目标数必然分散在不同的数组中，而且相同的数必然落在同一个数组中。

　　这两个数组里面的数各自进行异或，得到的结果就是答案。

代码:

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x = 0
        for num in nums:
            x ^= num

        lowbit = x & (-x)  # 最低位为1的二进制（从右到左）
        x1 = x2 = 0
        for num in nums:
            if num & lowbit:
                x1 ^= num
            else:
                x2 ^= num

        return [x1, x2]

class Solution:

def singleNumbers(self, nums: List[int]) -> List[int]:

x = 0

for num in nums:

x ^= num

lowbit = x & (-x) # 最低位为1的二进制（从右到左）

x1 = x2 = 0

for num in nums:

if num & lowbit:

x1 ^= num

else:

x2 ^= num

return [x1, x2]

4月29日：山脉数组中查找目标值

难度困难

题目描述

（这是一个 交互式问题 ）

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1] 你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
MountainArray.get(k) – 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() – 会返回该数组的长度 注意：

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。

示例 1：

输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

输入：array = [1,2,3,4,5,3,1], target = 3

输出：2

解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

示例 2：

输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

输入：array = [0,1,2,4,2,1], target = 3

输出：-1

解释：3 在数组中没有出现，返回 -1。

提示：

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

题目链接

https://leetcode-cn.com/problems/find-in-mountain-array/

思路:

　　先根据mountain[i]和mountaion[i-1]的大小关系，找到山脉⛰数组的顶峰。然后分别在左半边和右半边二分查找。

代码:

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()

        i, j = 0, n - 1
        while i <= j and i < n:
            mid = (i + j) // 2
            if mid >= 1 and mountain_arr.get(mid) < mountain_arr.get(mid-1):
                j = mid - 1  # 在左边找
            else:
                i = mid + 1  # 在右边找

        peek = j
        if mountain_arr.get(peek) == target:
            return peek

        # 在升序数组中查找
        i, j = 0, peek - 1
        while i <= j and i < peek:
            mid = (i + j) // 2
            search = mountain_arr.get(mid)
            if search > target:
                j = mid - 1  # 在左边找
            elif search < target:
                i = mid + 1  # 在右边找
            else:
                if search == target:
                    return mid
                else:
                    break

        # 在降序数组中查找
        i, j = peek + 1, n - 1
        while i <= j and i < n:
            mid = (i + j) // 2
            search = mountain_arr.get(mid)
            if search < target:
                j = mid - 1  # 在左边找
            elif search > target:
                i = mid + 1  # 在右边找
            else:
                if search == target:
                    return mid
                else:
                    return -1

        return -1

# """

# This is MountainArray's API interface.

# You should not implement it, or speculate about its implementation

# """

#class MountainArray:

# def get(self, index: int) -> int:

# def length(self) -> int:

class Solution:

def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:

n = mountain_arr.length()

i, j = 0, n - 1

while i <= j and i < n:

mid = (i + j) // 2

if mid >= 1 and mountain_arr.get(mid) < mountain_arr.get(mid-1):

j = mid - 1 # 在左边找

else:

i = mid + 1 # 在右边找

peek = j

if mountain_arr.get(peek) == target:

return peek

# 在升序数组中查找

i, j = 0, peek - 1

while i <= j and i < peek:

mid = (i + j) // 2

search = mountain_arr.get(mid)

if search > target:

j = mid - 1 # 在左边找

elif search < target:

i = mid + 1 # 在右边找

else:

if search == target:

return mid

else:

break

# 在降序数组中查找

i, j = peek + 1, n - 1

while i <= j and i < n:

mid = (i + j) // 2

search = mountain_arr.get(mid)

if search < target:

j = mid - 1 # 在左边找

elif search > target:

i = mid + 1 # 在右边找

else:

if search == target:

return mid

else:

return -1

4月30日：快乐数

难度简单

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

输入：19

输出：true

解释：

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

题目链接

https://leetcode-cn.com/problems/happy-number/

思路:

　　用集合判断下一个数字是否已经出现过了。

代码:

class Solution:
    def isHappy(self, n: int) -> bool:
        shown = set()
        shown.add(n)
        while n != 1:
            n = sum(map(lambda x:int(x)**2 ,list(str(n))))
            # print(n)
            if n in shown:
                return False
            shown.add(n)

        return True

class Solution:

def isHappy(self, n: int) -> bool:

shown = set()

shown.add(n)

while n != 1:

n = sum(map(lambda x:int(x)**2 ,list(str(n))))

# print(n)

if n in shown:

return False

shown.add(n)

return True

4月1日：有效括号的嵌套深度

题目描述

题目链接

思路:

代码:

4月2日：生命游戏

题目描述

题目链接

思路:

代码:

4月3日：字符串转换整数 (atoi)

题目描述

题目链接

思路:

代码:

4月4日：接雨水

题目描述

题目链接

思路：

代码：

4月5日：LFU缓存

题目描述

题目链接

思路:

代码:

4月6日：编辑距离

题目描述

题目链接

思路：

代码：

4月7日：旋转矩阵

题目描述

题目链接

思路:

代码:

4月8日：机器人的运动范围

题目描述

题目链接

思路:

代码:

4月9日：括号生成

题目描述

题目链接

思路:

代码:

4月10日：翻转字符串里的单词

题目描述

题目链接

思路:

代码:

4月11日：鸡蛋掉落

题目描述

题目链接

思路:

代码:

4月12日：交点

题目描述

题目链接

思路:

代码:

4月13日：设计推特

题目描述

题目链接

思路:

代码:

4月14日：两数相加 II

题目描述

题目链接

思路:

代码:

4月15日：01 矩阵

题目描述

题目链接

思路:

代码:

4月16日：合并区间

题目描述

题目链接

思路:

代码: