LeetCode 2020-03月每日一题

Contents

1 3月1日：用队列实现栈
2 3月2日：反转链表
3 3月3日：合并排序的数组
4 3月4日：腐烂的橘子🍊
5 3月5日：分糖果II
6 3月6日：和为s的连续正数序列
7 3月7日：队列的最大值
8 3月8日：零钱兑换
9 3月9日：买卖股票的最佳时机
10 3月10日：二叉树的直径
11 3月11日：将数组分成和相等的三个部分
12 3月12日：字符串的最大公因子
13 3月13日：多数元素
14 3月14日：最长上升子序列
15 3月15日：岛屿的最大面积
16 3月16日：字符串压缩
17 3月17日：拼写单词
18 3月18日：矩形重叠
19 3月19日：最长回文串
20 3月20日：最小的k个数
21 3月21日：水壶问题
22 3月22日：使数组唯一的最小增量
23 3月23日：链表的中间结点
24 3月24日：按摩师
25 3月25日：三维形体的表面积
26 3月26日：车的可用捕获量
27 3月27日：卡牌分组
28 3月28日：单词的压缩编码
29 3月29日：地图分析
30 3月30日：圆圈中最后剩下的数字(约瑟夫环)
31 3月31日：排序树组

3月1日：用队列实现栈

　　使用队列实现栈的下列操作：
　　
　　push(x) — 元素 x 入栈
　　pop() — 移除栈顶元素
　　top() — 获取栈顶元素
　　empty() — 返回栈是否为空

思路：
　　见代码。。。

代码：

    def __init__(self):
        self.data = []

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

    def pop(self) -> int:
        ans = self.data[-1]
        self.data = self.data[:-1]
        return ans

    def top(self) -> int:
        return self.data[-1]  # 取最后一个元素并返回


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

def __init__(self):

self.data = []

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

self.data.append(x)

def pop(self) -> int:

ans = self.data[-1]

self.data = self.data[:-1]

return ans

def top(self) -> int:

return self.data[-1] # 取最后一个元素并返回

def empty(self) -> bool:

return len(self.data) == 0

3月2日：反转链表

　　反转一个单链表。
　　
　　示例:
　　输入: 1->2->3->4->5->NULL
　　输出: 5->4->3->2->1->NULL

思路：

　　使用两个指针，一个在原链表中移动，另一个插入到新链表中。

代码： 递归的方法：

class Solution:

    def helper(self, node: ListNode, next: ListNode) -> ListNode:
        if not node: 
            self.ans = next
            return
        else:
            tmp = node.next
            node.next = next
            self.helper(tmp, node)

    def reverseList(self, head: ListNode) -> ListNode:
        self.ans = None
        if not head:
            return None

        self.helper(head, None)
        return self.ans

class Solution:

def helper(self, node: ListNode, next: ListNode) -> ListNode:

if not node:

self.ans = next

return

else:

tmp = node.next

node.next = next

self.helper(tmp, node)

def reverseList(self, head: ListNode) -> ListNode:

self.ans = None

if not head:

return None

self.helper(head, None)

return self.ans

网友给的迭代的方法：

class Solution:
    def reverseList(self, head):
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev

class Solution:

def reverseList(self, head):

p, rev = head, None

while p:

rev, rev.next, p = p, rev, p.next

return rev

3月3日：合并排序的数组

　　给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。
　　
　　初始化 A 和 B 的元素数量分别为 m 和 n。
　　
　　
　　示例:
　　输入:
　　A = [1,2,3,0,0,0], m = 3
　　B = [2,5,6], n = 3
　　
　　输出: [1,2,2,3,5,6]

思路：
　　将B中的元素用insert插入到A中即可。注意A为空时可能会越界异常。

代码：

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        if m == 0:
            A[:] = B[:]
            return

        temp = A[:m]
        i = 0 
        j = 0
        for j in range(n):
            while temp[i] < B[j]:
                i += 1
                if i >= len(temp):
                    break

            temp.insert(i, B[j])

        A[:] = temp[:]

class Solution:

def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:

if m == 0:

A[:] = B[:]

return

temp = A[:m]

i = 0

j = 0

for j in range(n):

while temp[i] < B[j]:

i += 1

if i >= len(temp):

break

temp.insert(i, B[j])

A[:] = temp[:]

3月4日：腐烂的橘子🍊

　　在给定的网格中，每个单元格可以有以下三个值之一：
　　
　　值 0 代表空单元格；
　　值 1 代表新鲜橘子；
　　值 2 代表腐烂的橘子。
　　每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
　　
　　返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
　　
　　示例 1：
　　
　　输入：[[2,1,1],[1,1,0],[0,1,1]]
　　输出：4
　　
　　示例 2：
　　输入：[[2,1,1],[0,1,1],[1,0,1]]
　　输出：-1
　　解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
　　
　　示例 3：
　　输入：[[0,2]]
　　输出：0
　　解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

思路：
　　BFS，维护一个(滚动的)列表rottings，记录每一轮新腐烂的橘子。
　　每一轮中，rottings中的所有橘子🍊，都会尝试腐烂周围的橘子。如果某一轮不能腐烂新的橘子，则结束循环。
　　结束循环后，如果还有未腐烂的橘子，则返回-1，否则返回轮数ans。　　

代码：

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 四个方向

        if len(grid) == 0:
            return 0

        rottings = []
        for i, line in enumerate(grid):
            for j, row in enumerate(line):
                if row == 2:
                    rottings.append((i,j))  # 刚开始时腐烂的橘子

        ans = 0

        new_rotting = []
        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] == 1:
                grid[x][y] = 2  # 成功腐烂新鲜的橘子，返回True
                new_rotting.append((x,y))
                return True

            return False

        while True:
            new_rotting.clear()
            has_new_rotting = False  # 这一轮是否腐烂了新的橘子
            for i, j in rottings:
                for i1, j1 in arounds:
                    if rot(i + i1, j + j1):
                        has_new_rotting = True

            if not has_new_rotting:
                for line in grid:
                    if line.count(1) != 0:
                        return -1
                return ans

            rottings = new_rotting.copy()
            ans += 1

class Solution:

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

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

if len(grid) == 0:

return 0

rottings = []

for i, line in enumerate(grid):

for j, row in enumerate(line):

if row == 2:

rottings.append((i,j)) # 刚开始时腐烂的橘子

ans = 0

new_rotting = []

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] == 1:

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

new_rotting.append((x,y))

return True

return False

while True:

new_rotting.clear()

has_new_rotting = False # 这一轮是否腐烂了新的橘子

for i, j in rottings:

for i1, j1 in arounds:

if rot(i + i1, j + j1):

has_new_rotting = True

if not has_new_rotting:

for line in grid:

if line.count(1) != 0:

return -1

return ans

rottings = new_rotting.copy()

ans += 1

3月5日：分糖果II

　　排排坐，分糖果。
　　
　　我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
　　
　　给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
　　
　　然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
　　
　　重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
　　
　　返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
　　
　　示例 1：
　　输入：candies = 7, num_people = 4
　　输出：[1,2,3,1]
　　解释：
　　第一次，ans[0] += 1，数组变为 [1,0,0,0]。
　　第二次，ans1 += 2，数组变为 [1,2,0,0]。
　　第三次，ans[2] += 3，数组变为 [1,2,3,0]。
　　第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
　　
　　示例 2：
　　输入：candies = 10, num_people = 3
　　输出：[5,2,3]
　　解释：
　　第一次，ans[0] += 1，数组变为 [1,0,0]。
　　第二次，ans1 += 2，数组变为 [1,2,0]。
　　第三次，ans[2] += 3，数组变为 [1,2,3]。
　　第四次，ans[0] += 4，最终数组变为 [5,2,3]。

思路：
　　i表示第几个小朋友，j表示分几颗糖果。
　　 代码：

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        ans = [0 for i in range(num_people)]
        i = 0  # 第一个小朋友
        j = 1  # 分几颗糖
        while candies >= j:
            candies -= j
            ans[i] += j
            j += 1
            i = (i + 1) % (num_people)

        i = (i + 1) % (num_people)
        if candies:
            ans[i-1] += candies
        return ans

class Solution:

def distributeCandies(self, candies: int, num_people: int) -> List[int]:

ans = [0 for i in range(num_people)]

i = 0 # 第一个小朋友

j = 1 # 分几颗糖

while candies >= j:

candies -= j

ans[i] += j

j += 1

i = (i + 1) % (num_people)

if candies:

ans[i-1] += candies

return ans

3月6日：和为s的连续正数序列

　　输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
　　
　　序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
　　
　　示例 1：
　　输入：target = 9
　　输出：[[2,3,4],[4,5]]
　　
　　示例 2：
　　输入：target = 15
　　输出：[[1,2,3,4,5],[4,5,6],[7,8]]

思路：
　　等差数列的和，target=平均值 × 序列长度length。
　　序列长度一定为target × 2的因子并且大于1，遍历target × 2的因子寻找序列长度即可。
　　序列越长的首个数字越小。

代码：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        s = target * 2
        #  (a + b) * (b-a+1) / 2
        ans = []
        for length in range(int(math.sqrt(s)), 1, -1):
            if s % length == 0:
                ave = (s // length + 1) // 2  # 平均值
                start = ave - length // 2  # 第一个数
                line = [i for i in range(start, length + start)]
                if sum(line) == target:  # 反向判断一下是否正确
                    ans.append(line)

        return ans

class Solution:

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

s = target * 2

# (a + b) * (b-a+1) / 2

ans = []

for length in range(int(math.sqrt(s)), 1, -1):

if s % length == 0:

ave = (s // length + 1) // 2 # 平均值

start = ave - length // 2 # 第一个数

line = [i for i in range(start, length + start)]

if sum(line) == target: # 反向判断一下是否正确

ans.append(line)

return ans

3月7日：队列的最大值

　　请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
　　
　　若队列为空，pop_front 和 max_value 需要返回 -1
　　
　　
　　示例 1：
　　输入:
　　[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
　　[[],1,[2],[],[],[]]
　　输出: [null,null,null,2,1,2]
　　
　　示例 2：
　　输入:
　　[“MaxQueue”,”pop_front”,”max_value”]
　　[[],[],[]]
　　输出: [null,-1,-1]

思路：
　　维护一个主队列q和一个辅助队列helper。主队列就是正常的队列，负责push和pop；辅助队列helper是一个双端队列。
　　push_back操作时，如果新的value大于helper队尾的元素，则一直弹出helper队尾的元素。之后再将value加到helper队尾。
　　pop_front操作时，如果q的对头元素value等于helper的对头元素，则弹出helper对头的元素。
　　max_value操作时，如果辅助队列不为空，则返回辅助队列对头的元素。

例如：[3, 1, 2, 4]

　　初始，q=[], helper=[]。
　　入队列，q=[3], helper=[3];
　　入队列，q=[3, 1], helper=[3, 1];
　　入队列，q=[3, 1, 2], helper=[3, 2];
　　入队列，q=[3, 1, 2, 4], helper=[4];
　　出队列，q=[1, 2, 4], helper=[4];
　　出队列，q=[2, 4], helper=[4];
　　出队列，q=[4], helper=[4];
　　出队列，q=[], helper=[];

代码：

class MaxQueue:

    def __init__(self):
        self.q = []
        self.helper = []

    def max_value(self) -> int:
        if len(self.helper) == 0:
            return -1
        return self.helper[0]

    def push_back(self, value: int) -> None:
        self.q.append(value)
        while len(self.helper) > 0 and value > self.helper[-1]:
            self.helper = self.helper[:-1]  # pop_right
        self.helper.append(value)


    def pop_front(self) -> int:
        if len(self.q) == 0:
            return -1
        q0 = self.q[0]
        self.q = self.q[1:]  # pop_left
        if len(self.helper) > 0 and self.helper[0] == q0:
            self.helper = self.helper[1:]  # pop_left

        return q0

class MaxQueue:

def __init__(self):

self.q = []

self.helper = []

def max_value(self) -> int:

if len(self.helper) == 0:

return -1

return self.helper[0]

def push_back(self, value: int) -> None:

self.q.append(value)

while len(self.helper) > 0 and value > self.helper[-1]:

self.helper = self.helper[:-1] # pop_right

self.helper.append(value)

def pop_front(self) -> int:

if len(self.q) == 0:

return -1

q0 = self.q[0]

self.q = self.q[1:] # pop_left

if len(self.helper) > 0 and self.helper[0] == q0:

self.helper = self.helper[1:] # pop_left

return q0

3月8日：零钱兑换

　　给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
　　
　　示例 1:
　　输入: coins = [1, 2, 5], amount = 11
　　输出: 3
　　解释: 11 = 5 + 5 + 1
　　
　　示例 2:
　　输入: coins = [2], amount = 3
　　输出: -1

思路：
　　背包🎒问题。
　　1. 如果已知所有amount - coin所需的最少硬币个数，那么amount所需的最少硬币个数为 min(coinChange(amount - coin_i) + 1)，coin_i∈coins。
　　2. coinChange[0] = 0。

代码：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        ans = [-1 for i in range(amount + 1)]
        ans[0] = 0

        for i in range(1, amount+1):
            ansi = 99999999
            if ans[i] == -1:
                for coin in coins:
                    left = i - coin
                    if left >= 0:
                        if ans[left] != -1:
                            ansi = min(ansi, ans[left]+1)

                ansi = -1 if ansi == 99999999 else ansi

                ans[i] = ansi

        return ans[amount]

class Solution:

def coinChange(self, coins: List[int], amount: int) -> int:

ans = [-1 for i in range(amount + 1)]

ans[0] = 0

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

ansi = 99999999

if ans[i] == -1:

for coin in coins:

left = i - coin

if left >= 0:

if ans[left] != -1:

ansi = min(ansi, ans[left]+1)

ansi = -1 if ansi == 99999999 else ansi

ans[i] = ansi

return ans[amount]

3月9日：买卖股票的最佳时机

　　给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
　　
　　如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
　　
　　注意你不能在买入股票前卖出股票。
　　
　　
　　示例 1:
　　输入: [7,1,5,3,6,4]
　　输出: 5
　　解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
　　注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
　　
　　示例 2:
　　输入: [7,6,4,3,1]
　　输出: 0
　　解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路：
　　今天国际原油跌了近30%，美股熔断，这道题来的真是时候啊❄️。。。
　　使用双指针，i表示买入时的下标，j表示卖出时的下标，ans存放全局利润最大值。如果卖出价格<=买入价格，则将买入价格更新为卖出价格。否则j不断向后移，如果prices[j]-prices[i]大于ans，则更新全局的ans。

代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i, j = 0, 1
        l = len(prices)
        ans = 0
        while True:
            if j >= l:
                return ans
            buy = prices[i]
            sell = prices[j]
            if sell <= buy:  # 卖出价格小于买入价格，则以卖出价格买入
                i = j
                j = j + 1
            else:
                ans = max(ans, sell - buy)  # 如果有更大利润则更新利润
                j += 1

        return ans

class Solution:

def maxProfit(self, prices: List[int]) -> int:

i, j = 0, 1

l = len(prices)

ans = 0

while True:

if j >= l:

return ans

buy = prices[i]

sell = prices[j]

if sell <= buy: # 卖出价格小于买入价格，则以卖出价格买入

i = j

j = j + 1

else:

ans = max(ans, sell - buy) # 如果有更大利润则更新利润

j += 1

return ans

3月10日：二叉树的直径

　　给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
　　
　　
　　示例 :

/ \

2 3

/ \

4 5

　　返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

思路：
　　有点像第21场双周赛的第4题，不过稍微简单一点。。
　　dfs。遍历时计算每个结点向左走的路径最大值，向右走的路径最大值，以及直径。
　　其中 向左走的路径最大值 = max(左孩子向左走的路径最大值,左孩子向右走的路径最大值) + 1。
　　向右走的路径最大值 = max(右孩子向左走的路径最大值,右孩子向右走的路径最大值) + 1。
　　直径 = max(左孩子的直径,右孩子的直径,向左走的路径最大值 + 向右走的路径最大值)。

代码：

class Solution:
    def dfs(self, root: TreeNode):
        to_left, to_right, diameter = 0, 0, 0
        if root.left:
            left_to_left, left_to_right, left_diameter = self.dfs(root.left)
            to_left = max(left_to_left, left_to_right) + 1
            diameter = max(diameter, left_diameter)

        if root.right:
            right_to_left, right_to_right, right_diameter = self.dfs(root.right)
            to_right = max(right_to_left, right_to_right) + 1
            diameter = max(diameter, right_diameter)

        diameter = max(diameter, to_left + to_right)
        return to_left, to_right, diameter

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        to_left, to_right, diameter = self.dfs(root)
        return diameter

class Solution:

def dfs(self, root: TreeNode):

to_left, to_right, diameter = 0, 0, 0

if root.left:

left_to_left, left_to_right, left_diameter = self.dfs(root.left)

to_left = max(left_to_left, left_to_right) + 1

diameter = max(diameter, left_diameter)

if root.right:

right_to_left, right_to_right, right_diameter = self.dfs(root.right)

to_right = max(right_to_left, right_to_right) + 1

diameter = max(diameter, right_diameter)

diameter = max(diameter, to_left + to_right)

return to_left, to_right, diameter

def diameterOfBinaryTree(self, root: TreeNode) -> int:

if not root:

return 0

to_left, to_right, diameter = self.dfs(root)

return diameter

3月11日：将数组分成和相等的三个部分

　　给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
　　
　　形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A1 + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length – 1]) 就可以将数组三等分。
　　
　　
　　示例 1：
　　输出：[0,2,1,-6,6,-7,9,1,2,0,1]
　　输出：true
　　解释：0 + 2 + 1 = -6 + 6 – 7 + 9 + 1 = 2 + 0 + 1
　　
　　示例 2：
　　输入：[0,2,1,-6,6,7,9,-1,2,0,1]
　　输出：false
　　
　　示例 3：
　　输入：[3,3,6,5,-2,2,5,1,-9,4]
　　输出：true
　　解释：3 + 3 = 6 = 5 – 2 + 2 + 5 + 1 – 9 + 4

思路：
　　先计算sum(A)，如果sum(A)不能被3整除，则直接返回False。
　　令ave = sum(A) // 3，也就是每一段的和都为ave。
　　遍历数组A并求累计和，如果累计和为ave则count += 1。
　　当count == 3时，说明已经有三段和为ave了，未使用的元素和须为0才返回True。
　　遍历结束后，当count == 3且没有多余数字时返回True。

代码：

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        total = sum(A)
        # 不能被3整除直接返回False
        if total % 3 != 0:
            return False

        ave = total // 3  # 每段的值

        # 0呢
        ans = False
        sums, count = 0, 0
        for i, num in enumerate(A):
            sums += num
            if count == 3:  # 如果已经有三段和为ave了，那么之后的和必须为0
                return sum(A[i:]) == 0

            if sums == ave:
                count += 1
                sums = 0

        return count == 3 and sums == 0  # 三段并且没有多余的数字

class Solution:

def canThreePartsEqualSum(self, A: List[int]) -> bool:

total = sum(A)

# 不能被3整除直接返回False

if total % 3 != 0:

return False

ave = total // 3 # 每段的值

# 0呢

ans = False

sums, count = 0, 0

for i, num in enumerate(A):

sums += num

if count == 3: # 如果已经有三段和为ave了，那么之后的和必须为0

return sum(A[i:]) == 0

if sums == ave:

count += 1

sums = 0

return count == 3 and sums == 0 # 三段并且没有多余的数字

3月12日：字符串的最大公因子

　　对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
　　
　　返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
　　
　　
　　示例 1：
　　输入：str1 = “ABCABC”, str2 = “ABC”
　　输出：”ABC”
　　
　　示例 2：
　　输入：str1 = “ABABAB”, str2 = “ABAB”
　　输出：”AB”
　　
　　示例 3：
　　输入：str1 = “LEET”, str2 = “CODE”
　　输出：””

思路：
　　类似于辗转相减法，如果两字符串相同，则最大公因子为任何一个字符串。
　　假设str1长度大于str2，计算str1-str2，然后再递归gcdOfStrings(str1-str2, str2)。其中字符串相减定义为从开头减去，如果str1不以str2开头，则直接返回空字符串。

代码：

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str1) == 0 or len(str2) == 0:
            return ''  # 两字符串都为空
        if len(str1) == len(str2):
            if str1 != str2:  # 两字符串长度相同，但内容不相同
                return ''
            else:
                return str1

        if len(str1) < len(str2):  
            str1, str2 = str2, str1  # 保证str1的长度更长

        l2 = len(str2)
         # 做"减法"
       if not str1.startswith(str2):
            return ''
        delta = str1[l2:] 

        return self.gcdOfStrings(str2 ,delta)

class Solution:

def gcdOfStrings(self, str1: str, str2: str) -> str:

if len(str1) == 0 or len(str2) == 0:

return '' # 两字符串都为空

if len(str1) == len(str2):

if str1 != str2: # 两字符串长度相同，但内容不相同

return ''

else:

return str1

if len(str1) < len(str2):

str1, str2 = str2, str1 # 保证str1的长度更长

l2 = len(str2)

# 做"减法"

if not str1.startswith(str2):

return ''

delta = str1[l2:]

return self.gcdOfStrings(str2 ,delta)

3月13日：多数元素

　　给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
　　
　　你可以假设数组是非空的，并且给定的数组总是存在多数元素。
　　
　　示例 1:
　　输入: [3,2,3]
　　输出: 3
　　
　　示例 2:
　　输入: [2,2,1,1,1,2,2]
　　输出: 2

思路：
　　方法一：用一个字典(哈希表)记录每个数出现的次数，如果大于n//2则返回该数。
　　方法二：网友给出的摩尔投票法：从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个。
代码：
　　方法一

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        helper = {}
        n = len(nums) // 2
        if n == 0:
            return nums[0]

        for num in nums:
            if num in helper:
                helper[num] += 1
                if helper[num] > n:
                    return num
            else:
                helper[num] = 1

class Solution:

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

helper = {}

n = len(nums) // 2

if n == 0:

return nums[0]

for num in nums:

if num in helper:

helper[num] += 1

if helper[num] > n:

return num

else:

helper[num] = 1

　　方法二

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 1
        ans = nums[0]
        for i, num in enumerate(nums[1:]):
            if num == ans:
                count += 1
            else:
                count -= 1
                if not count:
                    ans = nums[i+2]

        return ans

class Solution:

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

count = 1

ans = nums[0]

for i, num in enumerate(nums[1:]):

if num == ans:

count += 1

else:

count -= 1

if not count:

ans = nums[i+2]

return ans

3月14日：最长上升子序列

　　给定一个无序的整数数组，找到其中最长上升子序列的长度。
　　
　　示例:
　　输入: [10,9,2,5,3,7,101,18]
　　输出: 4
　　解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
　　说明:
　　
　　可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
　　你算法的时间复杂度应该为 O(n2) 。
　　进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路：
　　方法一：用一个辅助数组orders记录以每个数为最大的数字时，最长上升子序列的长度。如示例中[10,9,2,5,3,7,101,18]对应的orders=[1,1,1,2,1,3,4,4]。
　　初始状态orders全为1，统计nums中某个数字之前所有比它小的数字的orders的最大值 + 1即为order[i]新的值。复杂度为O(n^2)。
　　方法二：维护一个升序的结果数组results。如果num大于结果数组中的所有元素，就将num插入到结果数组的最后。否则用num替换results中第一个大于等于num的数。
　　最终results的长度即为结果。复杂度为O(nlogn)。

代码：
　　方法一：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if not n:
            return 0
        orders = [1 for i in range(n)]  # 以nums[i]为最大s\数的最长上升子序列长度
        ans = 1
        i = 0
        for i in range(n-1):
            if nums[i+1] > nums[i]:
                orders[i+1] = 2
                ans = 2
                break

        for i in range(i+2, n):
            order_i = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    order_i = max(order_i, orders[j]+1)
            orders[i] = order_i
            ans = max(ans, order_i)

        return ans

class Solution:

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

n = len(nums)

if not n:

return 0

orders = [1 for i in range(n)] # 以nums[i]为最大s\数的最长上升子序列长度

ans = 1

i = 0

for i in range(n-1):

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

orders[i+1] = 2

ans = 2

break

for i in range(i+2, n):

order_i = 1

for j in range(i):

if nums[j] < nums[i]:

order_i = max(order_i, orders[j]+1)

orders[i] = order_i

ans = max(ans, order_i)

return ans

　　方法二：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        results = []
        for num in nums:
            if len(results) == 0 or num > results[-1]:
                results.append(num)
            else:
                for i, re in enumerate(results):
                    if re >= num:
                        results[i] = num
                        break

        print(results)
        return len(results)

class Solution:

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

if len(nums) == 0:

return 0

results = []

for num in nums:

if len(results) == 0 or num > results[-1]:

results.append(num)

else:

for i, re in enumerate(results):

if re >= num:

results[i] = num

break

print(results)

return len(results)

3月15日：岛屿的最大面积

　　给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
　　
　　找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
　　
　　
　　示例 1:
　　[[0,0,1,0,0,0,0,1,0,0,0,0,0],
　　 [0,0,0,0,0,0,0,1,1,1,0,0,0],
　　 [0,1,1,0,1,0,0,0,0,0,0,0,0],
　　 [0,1,0,0,1,1,0,0,1,0,1,0,0],
　　 [0,1,0,0,1,1,0,0,1,1,1,0,0],
　　 [0,0,0,0,0,0,0,0,0,0,1,0,0],
　　 [0,0,0,0,0,0,0,1,1,1,0,0,0],
　　 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
　　对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
　　
　　
　　示例 2:
　　[[0,0,0,0,0,0,0,0]]
　　对于上面这个给定的矩阵, 返回 0。

思路：
　　经典dfs。遍历整个矩阵，从任意岛屿的任意位置开始dfs，搜索过程中累计该岛屿的面积，并将该岛屿搜索过的位置都置为水。

代码：

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        m = len(grid)
        if not m:
            return 0
        n = len(grid[0])

        iland_count = 0  # 记录当前遍历岛的面积
        def dfs(i, j):
            nonlocal m, n, iland_count, ans

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

            iland_count += 1
            ans = max(ans, iland_count)

            grid[i][j] = 0
            dfs(i-1, j)
            dfs(i+1, j)
            dfs(i, j+1)
            dfs(i, j-1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    iland_count = 0
                    dfs(i, j)

        return ans

class Solution:

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

ans = 0

m = len(grid)

if not m:

return 0

n = len(grid[0])

iland_count = 0 # 记录当前遍历岛的面积

def dfs(i, j):

nonlocal m, n, iland_count, ans

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

return

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

return

iland_count += 1

ans = max(ans, iland_count)

grid[i][j] = 0

dfs(i-1, j)

dfs(i+1, j)

dfs(i, j+1)

dfs(i, j-1)

for i in range(m):

for j in range(n):

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

iland_count = 0

dfs(i, j)

return ans

3月16日：字符串压缩

　　字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
　　
　　
　　示例1:
　　输入：”aabcccccaaa”
　　输出：”a2b1c5a3″
　　
　　示例2:
　　输入：”abbccd”
　　输出：”abbccd”
　　解释：”abbccd”压缩后为”a1b2c2d1″，比原字符串长度更长。

思路：
　　用now记录重复的字符，count记录重复的次数。如果当前字符不为now，则将now更新为当前字符，count则重新开始计数。

代码：

class Solution:
    def compressString(self, S: str) -> str:
        if not S:
            return ''

        now = ''
        ans = ''
        count = 0
        for s in S:
            if s != now:
                if count:
                    ans += str(count)
                now = s
                count = 1
                ans += s
            else:
                count += 1

        if count:
            ans += str(count)

        return ans if len(ans) < len(S) else S

class Solution:

def compressString(self, S: str) -> str:

if not S:

return ''

now = ''

ans = ''

count = 0

for s in S:

if s != now:

if count:

ans += str(count)

now = s

count = 1

ans += s

else:

count += 1

if count:

ans += str(count)

return ans if len(ans) < len(S) else S

3月17日：拼写单词

　　给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
　　
　　假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
　　
　　注意：每次拼写时，chars 中的每个字母都只能用一次。
　　
　　返回词汇表 words 中你掌握的所有单词的长度之和。
　　
　　
　　示例 1：
　　输入：words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
　　输出：6
　　解释：
　　可以形成字符串 “cat” 和 “hat”，所以答案是 3 + 3 = 6。
　　
　　示例 2：
　　输入：words = [“hello”,”world”,”leetcode”], chars = “welldonehoneyr”
　　输出：10
　　解释：
　　可以形成字符串 “hello” 和 “world”，所以答案是 5 + 5 = 10。

思路：
　　用一个字典记录每个字母出现的次数，对于words中的一个单词，每使用一个字母该字母的剩余次数就减1，如果字母够用则能够拼写该单词。
代码：

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        char_dict = {}
        for char in chars:
            if char not in char_dict:
                char_dict[char] = 1
            else:
                char_dict[char] += 1

        ans = 0                
        for word in words:
            can_spell = True
            char_temp = char_dict.copy()
            for letter in word:
                if letter not in char_temp or char_temp[letter] == 0:
                    can_spell = False
                else:
                    char_temp[letter] -= 1
            if can_spell:
                ans += len(word)

        return ans

class Solution:

def countCharacters(self, words: List[str], chars: str) -> int:

char_dict = {}

for char in chars:

if char not in char_dict:

char_dict[char] = 1

else:

char_dict[char] += 1

ans = 0

for word in words:

can_spell = True

char_temp = char_dict.copy()

for letter in word:

if letter not in char_temp or char_temp[letter] == 0:

can_spell = False

else:

char_temp[letter] -= 1

if can_spell:

ans += len(word)

return ans

3月18日：矩形重叠

　　矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
　　
　　如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
　　
　　给出两个矩形，判断它们是否重叠并返回结果。
　　
　　
　　示例 1：
　　输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
　　输出：true
　　
　　示例 2：
　　输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
　　输出：false

思路：
　　方法一：通过中心点计算，分别在x和y方向上比较两个矩形中心的距离和它们的边长之和。(这种方法一般也用来判断两个圆是否重合)。
　　方法二：卡死几种不相交的情况，其他都为True。

代码： 方法一：

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        c_1 = [(rec1[0] + rec1[2]) / 2., (rec1[1] + rec1[3]) / 2.]  # 计算中点
        c_2 = [(rec2[0] + rec2[2]) / 2., (rec2[1] + rec2[3]) / 2.]
        x = (rec2[2] - rec2[0] + rec1[2] - rec1[0]) / 2. > abs(c_1[0] - c_2[0])
        y = (rec2[3] - rec2[1] + rec1[3] - rec1[1]) / 2. > abs(c_1[1] - c_2[1])
        return x and y

class Solution:

def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:

c_1 = [(rec1[0] + rec1[2]) / 2., (rec1[1] + rec1[3]) / 2.] # 计算中点

c_2 = [(rec2[0] + rec2[2]) / 2., (rec2[1] + rec2[3]) / 2.]

x = (rec2[2] - rec2[0] + rec1[2] - rec1[0]) / 2. > abs(c_1[0] - c_2[0])

y = (rec2[3] - rec2[1] + rec1[3] - rec1[1]) / 2. > abs(c_1[1] - c_2[1])

return x and y

方法二：

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        if rec2[1] >= rec1[3] or rec1[1] >= rec2[3]:
            return False

        if rec1[0] >= rec2[2] or rec1[2] <= rec2[0]:
            return False

        return True

class Solution:

def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:

if rec2[1] >= rec1[3] or rec1[1] >= rec2[3]:

return False

if rec1[0] >= rec2[2] or rec1[2] <= rec2[0]:

return False

return True

3月19日：最长回文串

　　给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
　　
　　在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
　　
　　注意:
　　假设字符串的长度不会超过 1010。
　　
　　
　　示例 1:
　　输入:
　　”abccccdd”
　　
　　输出:
　　7
　　
　　解释:
　　我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

思路：
　　统计s中的字母，出现偶数次的全部使用，出现奇数次的少使用一次。最后还可以用一个出现奇数次的字母放在回文串的正中间。
代码：

　　方法一：

class Solution:
    def longestPalindrome(self, s: str) -> int:
        has_odd = False  # 记录是否有奇数次的字母
        alpha_dict = {}
        for char in s:
            if char not in alpha_dict:
                alpha_dict[char] = 1
            else:
                alpha_dict[char] += 1

        ans = 0
        for k in alpha_dict:
            if alpha_dict[k] % 2 == 0:
                ans += alpha_dict[k]
            else:
                ans += alpha_dict[k] - 1
                has_odd = True

        if has_odd:  # 如果有出现奇数次的字母，就拿一个放在回文串的正中间
            ans += 1

        return ans

class Solution:

def longestPalindrome(self, s: str) -> int:

has_odd = False # 记录是否有奇数次的字母

alpha_dict = {}

for char in s:

if char not in alpha_dict:

alpha_dict[char] = 1

else:

alpha_dict[char] += 1

ans = 0

for k in alpha_dict:

if alpha_dict[k] % 2 == 0:

ans += alpha_dict[k]

else:

ans += alpha_dict[k] - 1

has_odd = True

if has_odd: # 如果有出现奇数次的字母，就拿一个放在回文串的正中间

ans += 1

return ans

　　网友给出的一行代码的实现方法：

class Solution:
    def longestPalindrome(self, s: str) -> int:
        len(s) - max(0, sum([s.count(i) % 2 for i in set(s)]) - 1)

class Solution:

def longestPalindrome(self, s: str) -> int:

len(s) - max(0, sum([s.count(i) % 2 for i in set(s)]) - 1)

3月20日：最小的k个数

　　输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
　　
　　示例 1：
　　输入：arr = [3,2,1], k = 2
　　输出：[1,2] 或者 [2,1]
　　
　　示例 2：
　　输入：arr = [0,1,2,1], k = 1
　　输出：[0]

思路：
　　方法一：排序，时间复杂度O(nlogn)。
　　方法二：利用快速排序中的partition，由于每次partition后左边的数必小于右边的数，因此只需要对k所在的半边继续partition即可。时间复杂度<O(nlogn)。
　　方法三：构建最小堆，然后取前k个：时间复杂度O(n+klogn)。
代码：
　　方法一：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

class Solution:

def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

arr.sort()

return arr[:k]

　　方法二：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

        def partition(nums, low, high):
            pivot = nums[low];
            while low < high:
                while low < high and nums[high] >= pivot:
                    high -= 1
                nums[low] = nums[high]
                while low < high and nums[low] <= pivot:
                    low += 1
                nums[high] = nums[low]

            nums[low]=pivot
            return low

        low, high = 0, len(arr)-1
        while low < high:
            i = partition(arr,low,high)
            if i >= k:
                high = i - 1
            if i <= k:
                low = i + 1

        return arr[:k]

class Solution:

def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

def partition(nums, low, high):

pivot = nums[low];

while low < high:

while low < high and nums[high] >= pivot:

high -= 1

nums[low] = nums[high]

while low < high and nums[low] <= pivot:

low += 1

nums[high] = nums[low]

nums[low]=pivot

return low

low, high = 0, len(arr)-1

while low < high:

i = partition(arr,low,high)

if i >= k:

high = i - 1

if i <= k:

low = i + 1

return arr[:k]

　　方法三：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        heap = []
        for a in arr:
            heapq.heappush(heap, a)

        ans = []
        for i in range(k):
            if heap:            
                heap_min = heapq.heappop(heap)  # 弹出最小的值
                ans.append(heap_min)

        return ans

class Solution:

def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

heap = []

for a in arr:

heapq.heappush(heap, a)

ans = []

for i in range(k):

if heap:

heap_min = heapq.heappop(heap) # 弹出最小的值

ans.append(heap_min)

return ans

3月21日：水壶问题

　　有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？
　　
　　如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。
　　
　　你允许：
　　
　　装满任意一个水壶
　　清空任意一个水壶
　　从一个水壶向另外一个水壶倒水，直到装满或者倒空
　　
　　示例 1: (From the famous “Die Hard” example)
　　输入: x = 3, y = 5, z = 4
　　输出: True
　　
　　示例 2:
　　输入: x = 2, y = 6, z = 5
　　输出: False

思路：
　　找到x和y的最大公约数能否z被整除。另外要保证z <= x + y。
代码：

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z == 0:
            return True
        if x == 0:
            return y == z
        if y == 0:
            return x == z

        def gcd(a, b):
            if a < b:
                a, b = b, a
            while b != 0:
                a, b = b, a % b
            return a

        g = gcd(x, y)
        return z % g == 0 and z <= x + y

class Solution:

def canMeasureWater(self, x: int, y: int, z: int) -> bool:

if z == 0:

return True

if x == 0:

return y == z

if y == 0:

return x == z

def gcd(a, b):

if a < b:

a, b = b, a

while b != 0:

a, b = b, a % b

return a

g = gcd(x, y)

return z % g == 0 and z <= x + y

3月22日：使数组唯一的最小增量

　　给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
　　
　　返回使 A 中的每个值都是唯一的最少操作次数。
　　
　　示例 1:
　　输入：[1,2,2]
　　输出：1
　　解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
　　
　　示例 2:
　　输入：[3,2,1,2,1,7]
　　输出：6
　　解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
　　可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

思路：
　　先将A排序，然后令cur=A[0]，cur每次+1，cur和A[i]的差即为A[i]所需要的增量。
　　当A[i]大于cur时，说明A[i]不需要增量也不会重复了，令cur=A[i]。
　　例如A=[1,1,2,2,3,7]时：
　　cur=[1,2,3,4,5,7], ans=(2-1)+(3-2)+(4-2)+(5-3)=6。
　　

代码：

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        if len(A) == 0:
            return 0

        cur = A[0]
        ans = 0
        for i in A[1:]:
            cur += 1
            if i > cur:
                cur = i
            ans += cur - i

        return ans

class Solution:

def minIncrementForUnique(self, A: List[int]) -> int:

A.sort()

if len(A) == 0:

return 0

cur = A[0]

ans = 0

for i in A[1:]:

cur += 1

if i > cur:

cur = i

ans += cur - i

return ans

3月23日：链表的中间结点

　　给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
　　
　　如果有两个中间结点，则返回第二个中间结点。
　　
　　
　　示例 1：
　　输入：[1,2,3,4,5]
　　输出：此列表中的结点 3 (序列化形式：[3,4,5])
　　返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
　　注意，我们返回了一个 ListNode 类型的对象 ans，这样：
　　ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
　　
　　示例 2：
　　输入：[1,2,3,4,5,6]
　　输出：此列表中的结点 4 (序列化形式：[4,5,6])
　　由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：
　　先遍历一遍算出链表的长度，然后再重新从头取一半返回。
代码：

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        temp = head
        i = 0
        while temp:
            temp = temp.next
            i += 1  # 长度
        for j in range(i//2):  # 长度的一半
            head = head.next
        return head

class Solution(object):

def middleNode(self, head):

"""

:type head: ListNode

:rtype: ListNode

"""

temp = head

i = 0

while temp:

temp = temp.next

i += 1 # 长度

for j in range(i//2): # 长度的一半

head = head.next

return head

3月24日：按摩师

　　一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
　　
　　注意：本题相对原题稍作改动
　　
　　
　　示例 1：
　　输入： [1,2,3,1]
　　输出： 4
　　解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
　　
　　示例 2：
　　输入： [2,7,9,3,1]
　　输出： 12
　　解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
　　
　　示例 3：
　　输入： [2,1,4,5,3,1,1,3]
　　输出： 12
　　解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

思路：
　　动态规划，dp[i]表示如果第i个做了，最大值是多少。因为第i个做了，要么第i-2个也做，要么第i-3个也做。因此有递推公式dp[i]=nums[i-1]+max(dp[i-2], dp[i-3])。
代码：

class Solution:
    def massage(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n < 3:
            return max(nums)

        dp = [0 for i in range(n+1)]
        dp[0] = 0  # dp[i] 表示第i个做了的最大值
        dp[1] = nums[0]
        dp[2] = nums[1]
        # nums(0~i]
        ans = max(dp[1], dp[2])
        for i in range(3, n+1):
            dp[i] = nums[i-1] + max(dp[i-2], dp[i-3])  # 要么做i-2，要么做i-3
            ans = max(ans, dp[i])

        return ans

class Solution:

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

n = len(nums)

if n == 0:

return 0

if n < 3:

return max(nums)

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

dp[0] = 0 # dp[i] 表示第i个做了的最大值

dp[1] = nums[0]

dp[2] = nums[1]

# nums(0~i]

ans = max(dp[1], dp[2])

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

dp[i] = nums[i-1] + max(dp[i-2], dp[i-3]) # 要么做i-2，要么做i-3

ans = max(ans, dp[i])

return ans

3月25日：三维形体的表面积

　　在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。
　　
　　每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
　　
　　请你返回最终形体的表面积。
　　
　　示例 1：
　　输入：[[2]]
　　输出：10
　　
　　示例 2：
　　输入：[[1,2],[3,4]]
　　输出：34
　　
　　示例 3：
　　输入：[[1,0],[0,2]]
　　输出：16
　　
　　示例 4：
　　输入：[[1,1,1],[1,0,1],[1,1,1]]
　　输出：32
　　
　　示例 5：
　　输入：[[2,2,2],[2,1,2],[2,2,2]]
　　输出：46

思路：
　　先不考虑左右相邻的情况，高度为h的正方体有4 * h+2个面。
　　考虑两个相邻，矮的会和高的重叠，减少min_height * 2个面。
代码：

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if not m: return 0
        n = len(grid[0])

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    ans += grid[i][j] * 4 + 2
                if i > 0:
                    ans -= min(grid[i-1][j], grid[i][j]) * 2  # 两个相邻，矮的会和高的重叠，损失min_height * 2个面
                if j > 0:
                    ans -= min(grid[i][j-1], grid[i][j]) * 2

        return ans

class Solution:

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

m = len(grid)

if not m: return 0

n = len(grid[0])

ans = 0

for i in range(m):

for j in range(n):

if grid[i][j]:

ans += grid[i][j] * 4 + 2

if i > 0:

ans -= min(grid[i-1][j], grid[i][j]) * 2 # 两个相邻，矮的会和高的重叠，损失min_height * 2个面

if j > 0:

ans -= min(grid[i][j-1], grid[i][j]) * 2

return ans

3月26日：车的可用捕获量

　　在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。
　　
　　车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。
　　
　　返回车能够在一次移动中捕获到的卒的数量。
　　
　　
　　示例 1：
　　
　　输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”R”,”.”,”.”,”.”,”p”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
　　输出：3
　　解释：
　　在本例中，车能够捕获所有的卒。
　　
　　示例 2：
　　
　　输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”B”,”R”,”B”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
　　输出：0
　　解释：
　　象阻止了车捕获任何卒。
　　
　　示例 3：
　　
　　输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“p”,”p”,”.”,”R”,”.”,”p”,”B”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”B”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
　　输出：3
　　解释：
　　车可以捕获位置 b5，d6 和 f5 的卒。

思路：
　　先找到车的位置，再上下左右各自移动判断就好了。

代码：

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        ans = 0
        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    for k in range(j+1, 8):  # 右
                        if board[i][k] == 'p':
                            ans += 1
                        if board[i][k] != '.':
                            break
                    for k in range(i+1, 8):  # 下
                        if board[k][j] == 'p':
                            ans += 1
                        if board[k][j] != '.':
                            break
                    for k in range(j-1,-1,-1):  # 左
                        if board[i][k] == 'p':
                            ans += 1
                        if board[i][k] != '.':
                            break
                    for k in range(i-1, -1, -1):  # 上
                        if board[k][j] == 'p':
                            ans += 1
                        if board[k][j] != '.':
                            break

        return ans

class Solution:

def numRookCaptures(self, board: List[List[str]]) -> int:

ans = 0

for i in range(8):

for j in range(8):

if board[i][j] == 'R':

for k in range(j+1, 8): # 右

if board[i][k] == 'p':

ans += 1

if board[i][k] != '.':

break

for k in range(i+1, 8): # 下

if board[k][j] == 'p':

ans += 1

if board[k][j] != '.':

break

for k in range(j-1,-1,-1): # 左

if board[i][k] == 'p':

ans += 1

if board[i][k] != '.':

break

for k in range(i-1, -1, -1): # 上

if board[k][j] == 'p':

ans += 1

if board[k][j] != '.':

break

return ans

3月27日：卡牌分组

　　给定一副牌，每张牌上都写着一个整数。
　　
　　此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
　　
　　每组都有 X 张牌。
　　组内所有的牌上都写着相同的整数。
　　仅当你可选的 X >= 2 时返回 true。
　　
　　
　　示例 1：
　　输入：[1,2,3,4,4,3,2,1]
　　输出：true
　　解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
　　
　　示例 2：
　　输入：[1,1,1,2,2,2,3,3]
　　输出：false
　　解释：没有满足要求的分组。
　　
　　示例 3：
　　输入：1
　　输出：false
　　解释：没有满足要求的分组。
　　
　　示例 4：
　　输入：[1,1]
　　输出：true
　　解释：可行的分组是 [1,1]
　　
　　示例 5：
　　输入：[1,1,2,2,2,2]
　　输出：true
　　解释：可行的分组是 [1,1]，[2,2]，[2,2]

思路：
　　先计数，再求所有出现次数的最大公约数。
代码：

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        n = len(deck)
        if n <= 1: return False
        dict = {}
        # 计数
        for d in deck:
            if d in dict:
                dict[d] += 1
            else:
                dict[d] = 1

        l = list(dict.values())

        return reduce(math.gcd, l) > 1

class Solution:

def hasGroupsSizeX(self, deck: List[int]) -> bool:

n = len(deck)

if n <= 1: return False

dict = {}

# 计数

for d in deck:

if d in dict:

dict[d] += 1

else:

dict[d] = 1

l = list(dict.values())

return reduce(math.gcd, l) > 1

3月28日：单词的压缩编码

　　给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
　　
　　例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。
　　
　　对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。
　　
　　那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
　　
　　
　　示例：
　　输入: words = [“time”, “me”, “bell”]
　　输出: 10
　　说明: S = “time#bell#” ， indexes = [0, 2, 5] 。

思路：
　　其实意思就是计算有几个后缀不同的单词。暴力计算会超时。
　　将每个字符串都倒序，然后排序，这样就只需要比较相邻的字符串即可。
代码：

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        # 倒序后排序
        words = [word[::-1] for word in words]
        words.sort()
        n = len(words)

        ans = 0
        for i in range(1, n):
            # 下一个startswith上一个就不要上一个
            if not words[i].startswith(words[i-1]):
                ans += len(words[i-1]) + 1

        ans += len(words[-1]) + 1  # 算上最后一个

        return ans

class Solution:

def minimumLengthEncoding(self, words: List[str]) -> int:

# 倒序后排序

words = [word[::-1] for word in words]

words.sort()

n = len(words)

ans = 0

for i in range(1, n):

# 下一个startswith上一个就不要上一个

if not words[i].startswith(words[i-1]):

ans += len(words[i-1]) + 1

ans += len(words[-1]) + 1 # 算上最后一个

return ans

3月29日：地图分析

　　你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
　　
　　我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 – x1| + |y0 – y1| 。
　　
　　如果我们的地图上只有陆地或者海洋，请返回 -1。
　　
　　
　　示例 1：
　　
　　输入：[[1,0,1],[0,0,0],[1,0,1]]
　　输出：2
　　解释：
　　海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
　　
　　示例 2：
　　
　　输入：[[1,0,0],[0,0,0],[0,0,0]]
　　输出：4
　　解释：
　　海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

思路：
　　跟腐烂的橘子🍊类似，就直接复制它的代码了。
代码：

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        arounds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        sums = sum([sum(line) for line in grid])
        if sums == 0 or sums == m * n: return -1  # 没有海洋或没有陆地

        lands = []

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    lands.append((i, j))  # 所有陆地

        new_rotting = []
        def rot(x, y):
            if x < 0 or y < 0 or x >= m or y >= n:
                return False 

            if grid[x][y] == 0:
                grid[x][y] = 1  # 成功腐烂新鲜的橘子，返回True
                new_rotting.append((x,y))
                return True

            return False

        ans = 0
        while True:
            new_rotting.clear()
            has_new_rotting = False  # 这一轮是否腐烂了新的橘子
            for i, j in lands:
                for i1, j1 in arounds:
                    if rot(i + i1, j + j1):
                        has_new_rotting = True

            if not has_new_rotting:
                return ans

            lands = new_rotting.copy()
            ans += 1

class Solution:

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

m = len(grid)

n = len(grid[0])

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

sums = sum([sum(line) for line in grid])

if sums == 0 or sums == m * n: return -1 # 没有海洋或没有陆地

lands = []

for i in range(m):

for j in range(n):

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

lands.append((i, j)) # 所有陆地

new_rotting = []

def rot(x, y):

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

return False

if grid[x][y] == 0:

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

new_rotting.append((x,y))

return True

return False

ans = 0

while True:

new_rotting.clear()

has_new_rotting = False # 这一轮是否腐烂了新的橘子

for i, j in lands:

for i1, j1 in arounds:

if rot(i + i1, j + j1):

has_new_rotting = True

if not has_new_rotting:

return ans

lands = new_rotting.copy()

ans += 1

3月30日：圆圈中最后剩下的数字(约瑟夫环)

　　0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
　　
　　例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
　　
　　
　　示例 1：
　　输入: n = 5, m = 3
　　输出: 3
　　
　　示例 2：
　　输入: n = 10, m = 17
　　输出: 2
　　
　　限制：
　　
　　1 <= n <= 10^5
　　1 <= m <= 10^6

思路：
　　约瑟夫环。
　　方法一：给每个数字一个标记代表它有没有被删除，每次都逐个遍历，当没有删除的数字累计到m时，就删除当前数字。由于题目数据量大必定会超时。
　　方法二：模拟数字的删除，每次删除就把该元素从数组中移除，通过计算下标来获取下一个要删除的位置。(耗时2000ms)
　　方法三：公式法。f(N,M)=(f(N−1,M)+M)%N。(耗时80ms)

代码：
　　方法二：

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        circle = [i for i in range(n)]
        l = n
        t = (m-1) % l
        for i in range(n-1):
            circle.pop(t)
            l -= 1
            t = (t - 1 + m) % l

        return circle[0]

class Solution:

def lastRemaining(self, n: int, m: int) -> int:

circle = [i for i in range(n)]

l = n

t = (m-1) % l

for i in range(n-1):

circle.pop(t)

l -= 1

t = (t - 1 + m) % l

return circle[0]

　　方法三：

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        res = 0
        for i in range(2, n + 1):
            res = (res + m ) % i
        return(res)

class Solution:

def lastRemaining(self, n: int, m: int) -> int:

res = 0

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

res = (res + m ) % i

return(res)

3月31日：排序树组

　　给你一个整数数组 nums，将该数组升序排列。
　　
　　
　　示例 1：
　　输入：nums = [5,2,3,1]
　　输出：[1,2,3,5]
　　
　　示例 2：
　　输入：nums = [5,1,1,2,0,0]
　　输出：[0,0,1,1,2,5]
　　
　　提示：
　　
　　1 <= nums.length <= 50000
　　-50000 <= nums[i] <= 50000

思路：
　　nums[i]是有范围的，使用计数排序比直接sorted快。

代码：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        mem = [0 for i in range(100010)]
        for num in nums:
            mem[num+50000] += 1

        ans = []
        for i, count in enumerate(mem):
            while count:
                ans.append(i-50000)
                count -= 1

        return ans

class Solution:

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

mem = [0 for i in range(100010)]

for num in nums:

mem[num+50000] += 1

ans = []

for i, count in enumerate(mem):

while count:

ans.append(i-50000)

count -= 1

return ans

　　
3月的终于刷完啦~~~撒花✿✿✿
　　