{"id":5812,"date":"2019-11-09T20:25:02","date_gmt":"2019-11-10T04:25:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5812"},"modified":"2019-11-13T02:08:46","modified_gmt":"2019-11-13T10:08:46","slug":"leetcode-1252-cells-with-odd-values-in-a-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1252-cells-with-odd-values-in-a-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1252. Cells with Odd Values in a Matrix"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1252 1253 1254 1255 Weekly Contest 162  - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/1XMpzhFUvco?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given&nbsp;<code>n<\/code>&nbsp;and&nbsp;<code>m<\/code>&nbsp;which are the dimensions of a matrix initialized by zeros and given an array&nbsp;<code>indices<\/code>&nbsp;where&nbsp;<code>indices[i] = [ri, ci]<\/code>. For each pair of&nbsp;<code>[ri, ci]<\/code>&nbsp;you have to increment all cells in row&nbsp;<code>ri<\/code>&nbsp;and column&nbsp;<code>ci<\/code>&nbsp;by 1.<\/p>\n\n\n\n<p>Return&nbsp;<em>the number of cells with odd values<\/em>&nbsp;in the matrix after applying the increment to all&nbsp;<code>indices<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/10\/30\/e1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, m = 3, indices = [[0,1],[1,1]]\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> Initial matrix = [[0,0,0],[0,0,0]].\nAfter applying first increment it becomes [[1,2,1],[0,1,0]].\nThe final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/10\/30\/e2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, m = 2, indices = [[1,1],[0,0]]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 50<\/code><\/li><li><code>1 &lt;= m &lt;= 50<\/code><\/li><li><code>1 &lt;= indices.length &lt;= 100<\/code><\/li><li><code>0 &lt;= indices[i][0] &lt;&nbsp;n<\/code><\/li><li><code>0 &lt;= indices[i][1] &lt;&nbsp;m<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O((n+m)*k + n*m)<br>Space complexity: O(n*m)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int oddCells(int n, int m, vector<vector<int>>& indices) {\n    vector<vector<int>> a(n, vector<int>(m));\n    for (const auto& idx : indices) {      \n      for (int x = 0; x < m; ++x) ++a[idx[0]][x];\n      for (int y = 0; y < n; ++y) ++a[y][idx[1]];\n    }\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < m; ++j)\n        ans += a[i][j] &#038; 1;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Counting<\/strong><\/h2>\n\n\n\n<p>For each row and column, compute how many times it will be increased (odd or even).<br>For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.<br>Time complexity: O(n*m + k)<br>Space complexity: O(n+m)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int oddCells(int n, int m, vector<vector<int>>& indices) {\n    vector<int> cols(m);\n    vector<int> rows(n);\n    for (const auto& idx : indices) {\n      rows[idx[0]] ^= 1;\n      cols[idx[1]] ^= 1;           \n    }\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < m; ++j)\n        ans += rows[i] ^ cols[j];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;n&nbsp;and&nbsp;m&nbsp;which are the dimensions of a matrix initialized by zeros and given an array&nbsp;indices&nbsp;where&nbsp;indices[i] = [ri, ci]. For each pair of&nbsp;[ri, ci]&nbsp;you have to increment&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[179,63],"class_list":["post-5812","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-simulation","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5812","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5812"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5812\/revisions"}],"predecessor-version":[{"id":5832,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5812\/revisions\/5832"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5812"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}