题目描述：【Math】48. Rotate Image
解题思路：
这道题不让使用额外的空间，将一个图像方阵顺时针旋转 90° 。
如果使用常规方法，需要找规律得到每个位置变换后的位置，比较繁琐。一种巧妙的方法是将图像旋转 90° 等价于先将图像转置，然后再将每一行数字反转。因此，需要遍历两次 matrix，先转置再反转每一行，时间复杂度为 O(n)。
Python3 实现：
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix)
for i in range(N): # 先转置
for j in range(i+1, N):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(N): # 再反转每一行
for j in range(N//2):
matrix[i][j], matrix[i][N-1-j] = matrix[i][N-1-j], matrix[i][j]
题目描述：【Brute Force、DP】926. Flip String to Monotone Increasing
解题思路：
刚开始拿到题目的想法是从左到右遍历，找到第一个 1 的位置，然后去统计从第一个 1 位置开始，后面的字符串中 0 和 1 的个数，把最少的个数的数字翻转过来。但是这种想法是错误的！！！因为，此题中的 0 可能变为 1，1 也可能变为 0，比如 S="010110"，将第二个 1 变成 0，将最后一个 0 变成 1 可以得到最小翻转次数 2。
方法1（Brute Force）：
其实最开始是想到暴力求解的，即根据字符串 S 的每个位置 i，将字符串划分为前后两部分，前面一部分的 1 全部变为 0，后面一部分的 0 全部变为 1。对于每个位置，更新最小翻转次数。但是感觉这样做是 O(n^2) 的时间复杂度，就没继续考虑。
但是实际上，按照暴力求解的思想，是可以达到 O(n) 时间复杂度的级别的。
- 首先，在遍历的过程中，我们可以用一个变量 cnt1 去记录位置 i 之前有多少个 1，这样前面一部分的 1 全部变为 0 的次数正好是 cnt1，时间复杂度就为 O(1)。
- 那后面一部分将 0 全部变为 1 怎么做呢？其实可以在最开始时就统计好 S 中总共有多少个 0 和 1，存在 dic['0'] 和 dic['1'] 中；在遍历的过程中，再用一个变量 cnt0 去记录位置 i 之前有多少个 0，这样后面一部分的 1 全部变为 0 的次数正好是 dic['0']-cnt0，时间复杂度也是 O(1)。
这样，采用暴力求解的方法总时间复杂度就可以控制在 O(n) 的时间内了。
Python3 实现：
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
dic = dict() # 存储S中0和1的总数
dic['0'] = dic['1'] = 0
for s in S:
dic[s] += 1
cnt0 = cnt1 = 0 # 记录位置i之前0和1的个数
min_ = min(dic.values())
for s in S:
if s == '0':
cnt0 += 1
else:
cnt1 += 1
min_ = min(min_, cnt1 + (dic['0'] - cnt0)) # 对于每个位置，更新最少翻转次数
return min_
方法2（DP）：
思路是大牛的，可以学习一下：
- 用
dp[i]表示前 i 个字符按照升序所需要的最少翻转次数； - 如果第 i 个位置为字符 '1'，它不需要翻转，即
dp[i] = dp[i-1]；（因为在这个 '1' 前面可能为 '000'、'001'、'111'，再往后加个 '1' 不会增加最少次数）； - 如果第 i 个位置为字符 '0'，那这个 '0' 可能翻转也可能不翻转；如果这个 '0' 翻转（这个 '0' 前面可能是 '00'、'011' 这种），那么就增加一次翻转次数，即
dp[i] = dp[i-1] + 1；如果这个 '0' 不翻转（这个 '0' 前面可能是 '000'、'111' 这种），那么就要把这个 '0' 之前所有的 '1' 都要翻转，即dp[i] = sum(S[:i])；取两者最小：dp[i] = min(dp[i-1]+1, sum(S[:i]))。
因为 dp[i] 只依赖 dp[i-1]，因此只需要一个变量来更新 dp 即可。同时，要用一个变量 pre1 来记录位置 i 之前 1 的个数。时间复杂度为 O(n)。
Python3 实现：
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
min_ = pre1 = 0
for s in S:
pre1 += int(s) # 位置i之前1的个数
if s == '0': # 如果为'0'，需要更新min_
min_ = min(min_+1, pre1)
return min_
题目描述：【Math】1014. Best Sightseeing Pair
解题思路：
这道题实际上是求 max(A[i] + A[j] + i - j)，因此可以想到 Leetcode 【DP】121. Best Time to Buy and Sell Stock 这道题。我们定义此题的数学理解：
该问题的一般形式为：求 A[i] + A[j] + i - j 的最大值，对于 j > i。
该问题的解决方式为：先将问题变形为求解 (A[i] + i) + (A[j] - j) 的最大值，在遍历的过程中，每次更新 A[i] + i 的最大值和整体的最大值即可。
Python3 实现：
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
pre_max = A[0] + 0 # A[i]+i的最大值
tot_max = float("-inf") # 整体的最大值
for i in range(1, len(A)):
tot_max = max(tot_max, pre_max + (A[i] - i))
pre_max = max(pre_max, A[i] + i)
return tot_max
