LeetCode-Go 题解1252. Cells with Odd Values in a Matrix奇数值单元格计数双解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoLeetCode 1252 题要求在一个初始全 0 的 n×m 矩阵上按给定的行列索引逐一累加最终统计值为奇数的单元格数量。本文以 LeetCode-Go 仓库中 1252 题 README 为主体结合仓库内 官方解法源码 与 单元测试讲解「全矩阵模拟」与「行列计数 奇偶性判定」两种思路帮助你同时掌握暴力模拟与数学推导两类解题能力。题目回顾中英对照与核心题意题目英文原题Givennandmwhich are the dimensions of a matrix initialized by zeros and given an arrayindiceswhereindices[i] [ri, ci]. For each pair of[ri, ci]you have to increment all cells in rowriand columnciby 1.Returnthe number of cells with odd valuesin the matrix after applying the increment to allindices.题目大意中文解读给你一个 n 行 m 列的矩阵最开始的时候每个单元格中的值都是 0。另有一个索引数组indicesindices[i] [ri, ci]中的ri和ci分别表示指定的行和列从 0 开始编号。你需要将每对[ri, ci]指定的行和列上的所有单元格的值加 1。请你在执行完所有indices指定的增量操作后返回矩阵中「奇数值单元格」的数目。这里有一个容易被忽略的细节当某一对[ri, ci]执行时行ri与列ci的交点单元格(ri, ci)会被同时加两次一次来自整行 1一次来自整列 1这一点在后续的模拟拆解中会再次印证。示例与约束条件分析示例一Input: n 2, m 3, indices [[0,1],[1,1]] Output: 6 Explanation: Initial matrix [[0,0,0],[0,0,0]]. After applying first increment it becomes [[1,2,1],[0,1,0]]. The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.最终矩阵[[1,3,1],[1,3,1]]中的 6 个元素全部为奇数因此输出 6。示例二Input: n 2, m 2, indices [[1,1],[0,0]] Output: 0 Explanation: Final matrix [[2,2],[2,2]]. There is no odd number in the final matrix.两条索引分别作用后每个单元格恰好被加了两次行、列各一次最终矩阵全部为偶数因此输出 0。约束范围1 n 501 m 501 indices.length 1000 indices[i][0] n0 indices[i][1] m矩阵尺寸与索引数量都相当小最大 50×50 与 100 条索引这意味着即使是最直接的暴力模拟在时间与空间上也没有任何压力两种解法都能轻松通过。解法一全矩阵模拟oddCells这是 README 中标注的「解法一 暴力法」思路完全按照题意来先把矩阵建出来再逐条索引给整行、整列 1最后遍历矩阵统计奇数。实现思路用make([][]int, n)初始化 n 行矩阵每行再make([]int, m)开辟 m 个 0 值单元格遍历indices对每条[ri, ci]先给第ri行的 m 个单元格各 1再给第ci列的 n 个单元格各 1遍历整个矩阵用位运算v1 1判断奇数并累加计数。仓库源码仓库中实现位于 1252. Cells with Odd Values in a Matrix.go// 解法一 暴力法 func oddCells(n int, m int, indices [][]int) int { matrix, res : make([][]int, n), 0 for i : range matrix { matrix[i] make([]int, m) } for _, indice : range indices { for i : 0; i m; i { matrix[indice[0]][i] } for j : 0; j n; j { matrix[j][indice[1]] } } for _, m : range matrix { for _, v : range m { if v1 1 { res } } } return res }执行过程拆解以示例一为例以n 2, m 3, indices [[0,1],[1,1]]为例初始矩阵[[0,0,0],[0,0,0]]处理[0,1]第 0 行全体 1 得[[1,1,1],[0,0,0]]第 1 列全体 1 得[[1,2,1],[0,1,0]]。其中交点(0,1)从 0 直接变为 2印证了「交点被加两次」处理[1,1]第 1 行全体 1 得[[1,2,1],[1,2,1]]第 1 列全体 1 得[[1,3,1],[1,3,1]]逐格统计奇数1,3,1,1,3,1共 6 个返回 6。复杂度分析设索引数量为k len(indices)初始化矩阵O(n·m)每条索引的行列递增行需O(m)、列需O(n)合计O(k·(nm))最终统计O(n·m)。时间复杂度O(n·m k·(nm))空间复杂度O(n·m)需要保存整个矩阵。解法二行列增量计数 奇偶性判定oddCells1这是 README 中标注的「解法二 暴力法」但它并不真正去修改矩阵而是利用了一个关键观察单元格(i,j)的最终值等于rows[i] cols[j]其中rows[i]是第 i 行被累加的总次数cols[j]是第 j 列被累加的总次数。于是奇偶性完全由rows[i] cols[j]决定不再需要维护矩阵。核心观察一个单元格的值只可能来自「它所在的行被加了若干次」与「它所在的列被加了若干次」两部分之和因此先分别统计每行的累加次数rows[i]与每列的累加次数cols[j]再遍历所有(i,j)只要(rows[i]cols[j]) % 2 1即为奇数单元格。仓库源码实现位于 1252. Cells with Odd Values in a Matrix.go// 解法二 暴力法 func oddCells1(n int, m int, indices [][]int) int { rows, cols, count : make([]int, n), make([]int, m), 0 for _, pair : range indices { rows[pair[0]] cols[pair[1]] } for i : 0; i n; i { for j : 0; j m; j { if (rows[i]cols[j])%2 1 { count } } } return count }复杂度分析设k len(indices)统计行列次数O(k)双重循环判定奇偶O(n·m)。时间复杂度O(k n·m)空间复杂度O(n m)仅需两个一维数组相比解法一省去了整个矩阵。两解法对比与进一步推导维度解法一 oddCells解法二 oddCells1核心思想全矩阵模拟逐行逐列真实 1行列次数统计 奇偶性推导时间复杂度O(n·m k·(nm))O(k n·m)空间复杂度O(n·m)O(n m)代码可读性直观、贴近题意略抽象但更快更省在本题的约束n、m ≤ 50k ≤ 100下两者差距并不明显但解法二的空间优势与思路推广价值更值得体会。奇偶性公式推导从解法二可进一步推断观察解法二中的判定条件(rows[i]cols[j])%2 1可以进一步推断出单元格(i,j)为奇数当且仅当rows[i]与cols[j]奇偶性不同一奇一偶。因此答案还可以用如下组合计数公式直接算出answer 奇数行数 × 偶数列数 偶数行数 × 奇数列数即先数出rows中有多少奇数行oddRowscols中有多少奇数列oddCols然后answer : oddRows*(m-oddCols) (n-oddRows)*oddCols这个公式把统计从O(n·m)进一步降到O(n m)是解法二思路的自然延伸也是面试中常见的加分推导注该公式为本文基于仓库源码逻辑的推导延伸仓库中并未包含此实现。仓库中的测试与验证测试用例结构仓库为本题提供了独立的单元测试位于 1252. Cells with Odd Values in a Matrix_test.go其组织方式与 LeetCode-Go 仓库其他题目保持一致para1252结构体封装输入参数n、m、indicesans1252结构体封装期望答案onequestion1252将二者绑定为一条完整用例Test_Problem1252中内置了题目的两个官方示例用例并在循环中对oddCells打印输入输出同时调用oddCells1覆盖第二条实现路径以便仓库的覆盖率统计覆盖到全部解法。两个用例分别对应{para1252{2, 3, [][]int{{0, 1}, {1, 1}}}, ans1252{6}}, // 示例一 {para1252{2, 2, [][]int{{1, 1}, {0, 0}}}, ans1252{0}}, // 示例二如何运行测试仓库根目录的 go.mod 声明了模块名github.com/halfrost/LeetCode-Go与 Go 版本要求go 1.19因此在仓库根目录下可直接执行# 仅运行本题的测试 go test -v ./leetcode/1252.Cells-with-Odd-Values-in-a-Matrix/ # 运行 leetcode 目录下全部题目的测试并统计覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...第二条命令正是仓库根目录 gotest.sh 的核心逻辑它对./leetcode/...一次性执行带覆盖率收集的测试产出单一合法的coverage.txt文件这也是仓库宣称 100% 测试覆盖率的统计基础——每一道题都配有与题目示例对齐的测试用例本题自然也不例外。小结LeetCode 1252 是一道典型的「模拟 观察」题解法一忠实还原题意适合作为第一直觉的保底方案解法二通过把矩阵值拆解为「行次数 列次数」避免了矩阵的构造与维护时间与空间双双更优。结合 LeetCode-Go 仓库的 README、双解法源码 与 测试用例你可以直接运行测试验证两种实现的正确性并把「奇偶性组合计数」这一推导技巧迁移到其他矩阵类题目中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考