【超级详细解释】力扣每日一题 134.加油站 48. 旋转图像
134.加油站 力扣
这是一个很好的问题。这个思路其实基于一种贪心策略。我们从整个路径的油量变化来理解它，结合一个直观的“最低点法则”，来确保找到正确的起点。
问题的核心：油量差值的累积
对于每个加油站，我们有两个数组：gas（加油站提供的油量）和 cost（从当前加油站到下一个加油站所需的油量）。我们需要找到一个起点，使得可以绕行一圈回到该加油站，途中油量永远不为负数。
直观理解：寻找最低油量的原因
-
油量累积的曲线：
假设我们从某个加油站开始遍历整个环状加油站，每次计算当前的剩余油量累积，记为s（当前剩余油量）。每当我们经过一个加油站，我们就根据gas[i] - cost[i]来更新s，代表当前加油站加上油之后，减去到达下一个加油站的消耗。 -
最低点的特殊性：
在整个环中，油量累积s可能会上升或下降。如果我们画一条累积油量的曲线，从某个加油站出发计算到达其他加油站的油量变化，这条曲线中可能会有一些高点和低点。- 关键在于最低点：最低点代表了整个旅程中油量最匮乏的时刻。如果我们从其他加油站出发而不是这个最低点，意味着在到达最低点之前，我们已经有了更多的油量消耗，可能会在到达最低点之前出现负油量。因此，我们想要绕一圈成功的唯一可能，是从最低点之后开始，这样可以“错开”油量最紧张的时刻。
-
贪心选择最低点作为起点：
如果从最低点之后的某个加油站i + 1作为起点开始，意味着我们会在最低油量的地方重新开始计算油量变化，这样就可以确保从那时起油量逐步上升。换句话说，从最低点开始意味着我们从油量的最低点出发，此时“亏欠”的油量已经到达最低，我们后续不可能再遇到更差的情况，因此可以放心地从这里开始。
举例帮助理解
假设我们有以下油量情况：
gas = [1, 2, 3, 4, 5]cost = [3, 4, 5, 1, 2]
计算每个加油站的 gas[i] - cost[i] 的累积和：
- 第一个加油站开始：
s = 1 - 3 = -2 - 第二个加油站：
s = -2 + 2 - 4 = -4 - 第三个加油站：
s = -4 + 3 - 5 = -6 - 第四个加油站：
s = -6 + 4 - 1 = -3 - 第五个加油站：
s = -3 + 5 - 2 = 0
最低点是 -6，发生在第三个加油站之后，因此从第四个加油站（即 i + 1）作为起点开始，油量累积会逐步增加，最终可以保证绕一圈回到起点。
结论
在代码中，min_s 记录了油量的最低点，而 ans 则记录了从最低点之后开始的加油站。这样贪心地选择最低油量的下一个加油站作为起点，保证了我们可以绕完整个环。
从最低油量点的下一个加油站出发，可以让我们避免在已经处于最差的油量状态时出发，从而确保可以顺利走完一整圈。
```python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n,m,index=len(gas),0,0
if sum(gas)<sum(cost):
return -1
for i in range(n):
m+=gas[i]-cost[i]
if m<0:
index=i+1
m=0
return index
## 48.旋转图像
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
“”"
Do not return anything, modify matrix in-place instead.
“”"
n=len(matrix[0])
for i in range(n//2):
for j in range((n+1)//2):
tmp=matrix[i][j]
matrix[i][j]=matrix[n-1-j][i]
matrix[n-1-j][i]=matrix[n-1-i][n-1-j]
matrix[n-1-i][n-1-j]=matrix[j][n-1-i]
matrix[j][n-1-i]=tmp
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# 深拷贝 matrix -> tmp
tmp = copy.deepcopy(matrix)
# 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素
for i in range(n):
for j in range(n):
matrix[j][n - 1 - i] = tmp[i][j]
作者：Krahets
链接：https://leetcode.cn/problems/rotate-image/solutions/1228078/48-xuan-zhuan-tu-xiang-fu-zhu-ju-zhen-yu-jobi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
https://leetcode.cn/problems/rotate-image/solutions/1228078/48-xuan-zhuan-tu-xiang-fu-zhu-ju-zhen-yu-jobi