1252. 奇数值单元格的数目 : 简单计数模拟题

网友投稿 608 2022-09-07

1252. 奇数值单元格的数目 : 简单计数模拟题

1252. 奇数值单元格的数目 : 简单计数模拟题

题目描述

这是 LeetCode 上的 ​​1252. 奇数值单元格的数目​​ ,难度为 简单。

Tag : 「模拟」、「位运算」、「计数」

示例 1:

输入:m = 2, n = 3, indices = [[0,1],[1,1]]输出:6解释:最开始的矩阵是 [[0,0,0],[0,0,0]]。第一次增量操作后得到 [[1,2,1],[0,1,0]]。最后的矩阵是 [[1,3,1],[1,3,1]],里面有 6

示例 2:

输入:m = 2, n = 2, indices = [[1,1],[0,0]]输出:0解释:最后的矩阵是 [[2,2],[2,2]],里面没有奇数。

提示:

基本分析

对于某个位置最终累加值为奇数的充要条件为「所在行被累加次数的奇偶性」与「所在列被累加次数的奇偶性」不同。

计数模拟

由于我们只需关系某个位置的奇偶性,而不关心具体的累加值,我们可以创建两个数组 ​​r​​​ 和 ​​c​​,统计每行和每列的累加值的奇偶性。

代码

class Solution { public int oddCells(int m, int n, int[][] ins) { boolean[] r = new boolean[m], c = new boolean[n]; int a = 0, b = 0; for (int[] info : ins) { a += (r[info[0]] = !r[info[0]]) ? 1 : -1; b += (c[info[1]] = !c[info[1]]) ? 1 : -1; } return

位运算

代码:

class Solution { public int oddCells(int m, int n, int[][] ins) { long c1 = 0, c2 = 0; for (int[] info : ins) { c1 ^= 1L << info[0]; c2 ^= 1L << info[1]; } int a = 0, b = 0; for (int i = 0; i < m; i++) a += ((c1 >> i) & 1); for (int i = 0; i < n; i++) b += ((c2 >> i) & 1); return

class Solution { public int oddCells(int m, int n, int[][] ins) { long c1 = 0, c2 = 0; for (int[] info : ins) { c1 ^= 1L << info[0]; c2 ^= 1L << info[1]; } int a = Long.bitCount(c1), b = Long.bitCount(c2); return

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.1252​​ 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:​​github.com/SharingSour…​​ 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:MySQL基础教程5 —— 操作符
下一篇:CAD网页中实现嵌套打印
相关文章

 发表评论

暂时没有评论,来抢沙发吧~