有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
示例：
image
输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
输入：board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
思路：数独，要求每行每列都是1-9没有重复，且每个3x3的格子内也没有重复的即可，代码如下：
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 检查 行
for i in range(9):
s = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
for j in range(9):
if board[i][j] == '.':
continue
else:
if board[i][j] in s:
s.remove(board[i][j])
else:
return False
# 检查 列
for i in range(9):
s = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
for j in range(9):
if board[j][i] == '.':
continue
else:
if board[j][i] in s:
s.remove(board[j][i])
else:
return False
# 检查 3x3
for i in range(0, 9, 3):
for j in range(0, 9, 3):
s = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
for k in range(3):
for l in range(3):
if board[i + k][j + l] == '.':
continue
else:
if board[i + k][j + l] in s:
s.remove(board[i + k][j + l])
else:
return False
return True
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
输入：nums = [1]
输出：1
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
思路：
前缀和思路吧，逐个相加，如果前缀和小于0，那就重置前缀和，在此过程中不断把较大的前缀和更新res。代码如下：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = float('-inf')
tmp = 0
for i in range(len(nums)):
tmp += nums[i]
res = max(tmp, res)
if tmp < 0:
tmp = 0
return res
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1和 nums2，另有两个整数 m 和 n ，分别表示 nums1和 nums2中的元素数目。请你 合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2的长度为 n 。
示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
思路：
题目要求是，将数组2合并到到数组1，不用返回值，合并后的数组1是非递减顺序。思路一：把数组2覆盖掉数组1后面的空数值，然后进行原地排序，代码如下：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(n):
nums1[m + i] = nums2[i]
nums1.sort()
还有另一个思路，分治思想，思路和合并排序一致，代码如下：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2 = m - 1, n - 1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
从后往前插入，可以避免覆盖问题。所有玩家都全力向前冲刺, 却不知道向后才是胜利之门。-《头号玩家》
买卖股票的最佳时机
给定一个数组 prices，它的第 i 个元素prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
思路：
在遍历过程中不断更新当前的最小值，找到当前最高的价格。代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
low = float('inf')
for i in range(len(prices)):
low = min(low, prices[i])
result = max(result, prices[i] - low)
return result
