记力扣周赛348中一道有趣的思维题
作者在力扣周赛中遇到一道有趣的思维题，题目要求对N*N矩阵进行多次查询，每次修改整行或整列的值，最终求矩阵元素和。作者首先尝试模拟法，但因内存限制失败；随后采用状态压缩，但仍超时；最终通过逆向思维，从后往前遍历查询，利用哈希表记录已处理的行列，成功优化至O(M)时间复杂度，解决了问题。
文章目录
我平时周末有做力扣周赛的习惯，4道题目大部分时候只能做出3题，第四题大多数要么是较为复杂的数论/图论题，要么是较为困难的DP题，这两个类别都不是我的强项，所以想要拿一个好的名次只能从速度上下功夫，一般来说能在40分钟内做出前三题就勉强达到预期了。
而这周的周赛第三题是一道挺有趣的思维题，不仅题目本身有意思，数据规模和测试用例也给得恰到好处（咬牙切齿），最终我花了一小时，换了两次思路才将其做出来，记录一下做题思路。
思路一：模拟
一道题一开始没什么思路时，我倾向于先写出暴力算法的代码。题目要求我们对N * N的矩阵进行多次查询，每次会将对应行或列的所有元素修改成指定值，最后求矩阵所有元素的和，那么我们按照要求进行模拟：
class Solution { public long matrixSumQueries(int n, int[][] queries) { int[][] mat = new int[n][n]; // n*n矩阵 long ans = 0; for (int[] query : queries) { int index = query[1], val = query[2]; if (query[0] == 0) { for (int i = 0; i < n; i++) { ans += val - mat[i][index]; // 加上修改后增加的差值 mat[i][index] = val; } } else { for (int i = 0; i < n; i++) { ans += val - mat[index][i]; mat[index][i] = val; } } } return ans; }}以上代码时间复杂度为
空间复杂度为
提交之后MLE了，这倒是始料未及的，那么我们就必须想出一种方法避免构建完整的矩阵。
思路二：状态压缩
观察样例，我们可以看到每个元素的值只跟最后一次修改了对应行/列的查询有关，并且一次会将整列/整行的值的修改掉，所以我们不用构建完整的矩阵，只要用两个数组保存每一行和每一列的值就好了。
但是我们需要知道最后修改元素的查询是行还是列，所以我们需要额外的两个数组，保存每一行和每一列最后修改的时间。
所有查询完成之后，我们遍历矩阵中每一个坐标，判断值并求总和即可。
class Solution { public long matrixSumQueries(int n, int[][] queries) { int[] x_val = new int[n], y_val = new int[n]; // 储存行和列的值 int[] x_mod = new int[n], y_mod = new int[n]; // 储存行和列的最后修改时间 long ans = 0; int mod = 1; // 修改时间，每完成一次查询后自增一次 for (int[] query : queries) { int index = query[1], val = query[2]; if (query[0] == 0) { y_mod[index] = mod; y_val[index] = val; } else { x_mod[index] = mod; x_val[index] = val; } mod++; }
// 遍历每一个坐标、判断值并加入总和中 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans += y_mod[j] > x_mod[i] ? y_val[j] : x_val[i]; } } return ans; }}以上代码时间复杂度为
空间复杂度为
尝试提交，TLE了，卡在了最后一个测试用例。。。那我们就不能完整地遍历整个矩阵了。
思路三：逆向思维
参考思路二，每个元素的值只跟最后一次修改了对应行/列的查询有关，整个查询的过程就类似于往空白的墙上贴胶带，有横有竖，一道盖着一道，我们想要撕掉这些胶带，就得从最后一道开始往前撕。
求矩阵的元素和也类似，假设最后一次查询所修改的是第一行，该行的值已经确定，不会再更改了，所以可以直接求出该行的总和。
继续往前遍历，倒数第二次查询修改了第三列，除了与第一行的相交点（已经计算过）外，剩下的元素也可以直接求和。
还有一种情况，假设倒数第三次查询依旧修改了第三列，那么由于该次查询的值被后一次覆盖了并且已经求过和了，所以可以直接跳过。
至此思路就很清晰了，我们可以用两个哈希表来储存查询过的行和列，然后从后往前遍历查询数组，具体代码如下：
class Solution { public long matrixSumQueries(int n, int[][] queries) { long ans = 0; Set<Integer> x_vis = new HashSet<>(); Set<Integer> y_vis = new HashSet<>();
// 从后往前遍历 for (int i = queries.length - 1; i >= 0; i--) { int query = queries[i][0], index = queries[i][1], val = queries[i][2]; if (query == 0) { // 若该行已经在后面被计算过，则跳过 if (x_vis.contains(index)) continue;
// 除去和计算过的列的交点后求和 ans += val * (n - y_vis.size()); x_vis.add(index); } else { // 同上 if (y_vis.contains(index)) continue; ans += val * (n - x_vis.size()); y_vis.add(index); } } return ans; }}以上代码时间复杂度为
空间复杂度为
至此，本题完成，附上一份简洁一点的写法。
class Solution { public long matrixSumQueries(int n, int[][] queries) { long ans = 0; Set<Integer>[] vis = new Set[]{new HashSet<>(), new HashSet<>()}; for (int i = queries.length - 1; i >= 0; i--) { int query = queries[i][0], index = queries[i][1]; long val = queries[i][2]; if (vis[query].contains(index)) continue; ans += val * (n - vis[query ^ 1].size()); vis[query].add(index); } return ans; }}