134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

数据范围

• gas.length == n
• cost.length == n
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

分析

前缀和+双指针，只要满足大小为n的区间内，所有的加油站都能正常通过，预处理油和花费的前缀和，只需要保证每个点处油的前缀和比花费前缀和大就行，若有一个点不存在，则左指针到达他下一个加油站的位置。

代码

class Solution {
public:const static int N = 2e5 + 5;int pgas[N], pcost[N];int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int res = -1;int n = gas.size();for(int i = 1; i <= 2 * n; i ++ ) {if(i <= n) pgas[i] = pgas[i - 1] + gas[i - 1];else pgas[i] = pgas[i - 1] + gas[(i - 1) % n];if(i <= n) pcost[i] = pcost[i - 1] + cost[i - 1];else pcost[i] = pcost[i - 1] + cost[(i - 1) % n];}for(int i = n; i <= 2 * n; i ++ ) {int j = i - n + 1;int last = j;while(j <= i) {cout << i << " " << j << endl; int tcost = pcost[j] - pcost[last - 1];int tgas = pgas[j] - pgas[last - 1];if(tcost > tgas) break;else j ++ ;}if(j == i + 1) {res = i - n;return res;} i = j + n - 1;}return res;}
};

---

2435. 矩阵中和能被 K 整除的路径

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。

数据范围

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 5 * 104
• 1 <= m * n <= 5 * 104
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

分析

令$dp[i][j][k]$表示到达$(i,j)$后前缀和模$k$后的路径数量，状态转移如下

• $dp[i][j][k]+=dp[i-1][j][(k-grid[i][j])\%kk]+dp[i][j-1][(k-grid[i][j])\%kk]$

代码

class Solution {
public:const static int N = 55, mod = 1e9 + 7, M = 5e2 + 5;int n, m;int numberOfPaths(vector<vector<int>>& grid, int kk) {n = grid.size();m = grid[0].size();int dp[n + 2][m + 2][N];memset(dp, 0, sizeof(dp));dp[1][1][grid[0][0] % kk] = 1;for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= m; j ++ ) {for(int k = 0; k < kk; k ++ ) {int l = grid[i - 1][j - 1];if(j >= 2) dp[i][j][k] += dp[i][j - 1][((k - l % kk) % kk + kk) % kk];if(i >= 2) dp[i][j][k] += dp[i - 1][j][((k - l % kk) % kk + kk) % kk];dp[i][j][k] %= mod;}}}return dp[n][m][0];}
};