汕头自助建站系统,美声广告网站建设,做视频网站要多大的带宽,销售外包服务134.加油站 力扣 这是一个很好的问题。这个思路其实基于一种贪心策略。我们从整个路径的油量变化来理解它#xff0c;结合一个直观的“最低点法则”#xff0c;来确保找到正确的起点。
问题的核心#xff1a;油量差值的累积
对于每个加油站#xff0c;我们有两个数组结合一个直观的“最低点法则”来确保找到正确的起点。
问题的核心油量差值的累积
对于每个加油站我们有两个数组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,indexlen(gas),0,0if sum(gas)sum(cost):return -1for i in range(n):mgas[i]-cost[i]if m0:indexi1m0return index
## 48.旋转图像
class Solution: def rotate(self, matrix: List[List[int]]) - None: “” Do not return anything, modify matrix in-place instead. “” nlen(matrix[0]) for i in range(n//2): for j in range((n1)//2): tmpmatrix[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
