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];
    }
};