LeetCode 每日一题
162. 寻找峰值
问题
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
解答
显然需要二分法，二分的要点为：
- 确定区间形式，即 左闭右闭 还是 左闭右开，由此决定 终止条件 以及 左右指针如何变换
- 确定左右指针变化条件，本题可以观测 mid 左右形式，从而修改左右区间
- 确定 最终返回结果
代码：
class Solution:
# 因为希望遇到答案就停止，所以加了许多判断，不好说这会不会拖慢程序，
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
l, r = 0, n - 1
if n == 1:
return 0
mid = l + ((r - l) >> 1)
while l <= r:
if nums[l] > nums[ l + 1 ]:
return l
if nums[r] > nums[r - 1]:
return r
if nums[mid - 1] < nums[mid] and nums[mid + 1] < nums[mid]:
return mid
elif nums[mid - 1] < nums[mid] and nums[mid + 1] > nums[mid]:
l = mid + 1
else:
r = mid - 1
mid = l + ((r - l) >> 1)
拓展
依据灵神的网站题目顺序
926. 将字符串翻转到单调递增
问题
如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
返回使 s 单调递增的最小翻转次数。
解答
与 昨天那道题1864. 构成交替字符串需要的最小交换次数 不同
但开始的思考是一样的，先确定终止状态：第一个 1 之后的所有数都是 1
但是它的终止状态与初始状态的关系太为密切，我们无法确定它终止状态字符串的固定形态，不像那道题一样只有两种
确定操作，即 自我翻转，每个操作都只操作字符本身，不会影响前面的已经遍历过的字符串，且只会被前面的字符影响，这是很明显的 DP，因为这样的结构必然拥有 最优子结构。
另外，可以观测到在 终止状态 中，0 的前面必为 0，1 的前面为 1/0，所以可进行 DP，因为它下一个数是否翻转，与上一个数的关系密切。
从另外一个层面解释 DP：
我们假设 终止状态 是 全0 或 全1，那么只要比较字符串中 0/1 的数量即可，但是由于 终止状态 与 初始状态 的 整体关联很大，所以不能简单地比较字符串中 0/1 的数量，而是在遍历的时候记录 前面的满足 终止条件（0 的前面必为 0，1 的前面为 1/0） 的字符串，若满足，则划过，若不满足，则记录，我们只要记录 翻转的次数，因为有两种操作，即 变1 和 变0，所以需要两个数组记录，这也就导出了上述的 DP算法
代码：
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
# 记录 -1 到当前位置的最小翻转次数
# dp0 表示翻转为 0
# dp1 表示翻转为1
dp0 = dp1 = 0
for c in s:
dp0New, dp1New = dp0, min(dp0, dp1)
if c == '1':
dp0New += 1
else:
dp1New += 1
dp0, dp1 = dp0New, dp1New
return min(dp0, dp1)
作者：力扣官方题解
链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
拓展
2249. 统计圆内格点数目
问题
给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。
注意：
格点 是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。
解答
最为朴素的思想是转换为图的可达性问题，可以使用 BFS 或者 DFS 求解，其时间复杂度应为 \(O(\sum r_i^2)\)，而且空间复杂度也十分大，为 \(O(max(xi + ri) * max(yi + ri))\)，可以尝试使用数学方法优化
可以先求出 最大的圆的边界，然后再此基础上进行遍历，顺序遍历即可（它也避免了重复点问题），它的算法复杂度和上述算法的差不多，但是代码相当简洁
代码：
class Solution:
def countLatticePoints(self, circles: List[List[int]]) -> int:
ans = 0
circles.sort(key=lambda c: -c[2]) # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆
max_x = max(c[0] + c[2] for c in circles)
max_y = max(c[1] + c[2] for c in circles)
for i in range(max_x + 1):
for j in range(max_y + 1):
for x, y, r in circles:
if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:
ans += 1
break
return ans
作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-lattice-points-inside-a-circle/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
拓展
2447. 最大公因数等于 K 的子数组数目
问题
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
子数组 是数组中一个连续的非空序列。
数组的最大公因数 是能整除数组中所有元素的最大整数。
解答
- 最朴素的算法便是枚举，枚举每个子数组，根据 GCD 的传递性（gcd(a, b) = gcd(b, c)，则 gcd(a, b) = gcd(b, c) = gcd(a, b, c)），便能求出子数组的最大公约数是否是 k 了，它的 时间复杂度为 \(O(n^2 \log max(nums))\)
- 其次对于这种求子数组的属性，从 1508. 子数组和排序后的区间和 得到启发，可以用一个数组来记录 gcd(nums[i - 1], nums[i])，然后遍历求出其 连续的 k 的个数，再求出该区间的子数组个数加入 结果即可，然后可以反复这一过程（除不断 k 的都丢弃，用数组记录连续 k 的位置信息即可），直到所有数都被抛弃
代码：
def gcd(a:int, b:int) -> int:
if not b:
return a
return gcd(b, a % b)
# 很遗憾，代码暂时未能写出，不过这个想法和灵神的不谋而合，可以参考他的代码
class Solution:
def subarrayGCD(self, nums: List[int], k: int) -> int:
ans = 0
a = [] # [GCD，相同 GCD 区间的右端点]
i0 = -1
for i, x in enumerate(nums):
if x % k: # 保证后续求的 GCD 都是 k 的倍数
a = []
i0 = i
continue
# x 为当前值
# i 作为右边界
a.append([x, i])
# 原地去重，因为相同的 GCD 都相邻在一起
j = 0
for p in a:
p[0] = gcd(p[0], x)
if a[j][0] != p[0]:
j += 1
a[j] = p
else:
a[j][1] = p[1]
del a[j + 1:]
if a[0][0] == k: # a[0][0] >= k
ans += a[0][1] - i0
return ans
作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
拓展
1237. 找出给定方程的正整数解
问题
给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知，但它是单调递增函数，也就是说：
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
// Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
int f(int x, int y);
};
你的解决方案将按如下规则进行评判：
判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。
提示：
1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。
解答
- 首先看到矩阵递增，便要想起 二分法，以 l = 0，r = matrix[-1][-1]，不断二分，该算法会保证 mid 必定存在于矩阵中
- 由提示知：矩阵大小是常数 1000 * 1000，所以可以直接枚举
- 可以在每行中进行二分查找
代码：