Leetcode 【48、926、1014】

题目描述：【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