力扣第92场双周赛

2482. 行和列中一和零的差值

给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。

我们按照如下过程，定义一个下标从 0 开始的 m x n 差值矩阵 diff ：

令第 i 行一的数目为 onesRowi 。
令第 j 列一的数目为 onesColj 。
令第 i 行零的数目为 zerosRowi 。
令第 j 列零的数目为 zerosColj 。
diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

请你返回差值矩阵 diff 。

示例 1：

输入：grid = [[1,1,1],[1,1,1]]
输出：[[5,5,5],[5,5,5]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

C++

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> r1(m), r0(m), c0(n), c1(n);
        for(int i = 0; i< m; i ++) {
            for(int j = 0; j < n; j ++) {
                if(grid[i][j]) {
                    r1[i] ++;
                    c1[j] ++;
                }else {
                    r0[i] ++;
                    c0[j] ++;
                }
            }
        }

        auto res = grid;
        for(int i = 0; i< m; i ++) {
            for(int j = 0; j < n; j ++) {
                res[i][j] = r1[i] + c1[j] - r0[i] - c0[j];
            }
        }
        return res;
    }
};

2483. 商店的最少代价

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。
如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：

在开门期间，如果某一个小时没有顾客到达，代价增加 1 。
在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价最小的前提下，商店的最早关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

示例 1：

输入：customers = "YYNY"
输出：2
解释：
- 第 0 小时关门，总共 1+1+0+1 = 3 代价。
- 第 1 小时关门，总共 0+1+0+1 = 2 代价。
- 第 2 小时关门，总共 0+0+0+1 = 1 代价。
- 第 3 小时关门，总共 0+0+1+1 = 2 代价。
- 第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。

示例 2：

输入：customers = "NNNNN"
输出：0
解释：最优关门时间是 0 ，因为自始至终没有顾客到达。

示例 3：

输入：customers = "YYYY"
输出：4
解释：最优关门时间是 4 ，因为每一小时均有顾客到达。

提示：

1 <= customers.length <= 105
customers 只包含字符 'Y' 和 'N' 。

C++

// 也就是计算：前(包括自己)0 + 后1
class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();
        vector<int> v(n + 1, 0); // v[i] 表示第i个小时前（包括这个小时）1的个数
        for(int i = 1; i <= n; i ++){
            v[i] = v[i - 1];
            if(customers[i - 1] == 'Y') v[i] ++;
        }

        int cost = 1e8; // 代价
        int res; // 返回的时间
        for(int i = n; i >= 0; i--){
            int tmp = i - v[i] + v[n] - v[i];
            if(tmp <= cost){
                res = i;
                cost = tmp;
            }
        }
        return res ; 
    }
};