C++算法实现leetcode 1252奇数值单元格数目

目录
  • 题目描述
    • 整理题意
  • 解题思路分析
  • 具体实现
    • 复杂度分析
  • 代码实现
  • 总结

题目描述

题目链接:1252. 奇数值单元格的数目

给你一个 m x n 的矩阵,最开始的时候,每个单元格中的值都是 0。

另有一个二维索引数组 indices,indices[i] = [ri, ci] 指向矩阵中的某个位置,其中 ri 和 ci 分别表示指定的行和列(从 0 开始编号)。

对 indices[i] 所指向的每个位置,应同时执行下述增量操作:

  • ri 行上的所有单元格,加 1 。
  • ci 列上的所有单元格,加 1 。 给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后,返回矩阵中 奇数值单元格 的数目。

进阶: 你可以设计一个时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题吗?

提示:

1 <= m, n <= 50

1 <= indices.length <= 100

0 <= ri < m

0 <= ci < n

示例 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]],里面没有奇数。

整理题意

题目给定一个 m x n 的矩阵,矩阵中每个元素最开始都为 0,然后给定一个二维数组 indices,数组中每个元素包含两个值 indices[i][0] 和 indices[i][1],分别表示对 m x n 的矩阵的第 indices[i][0] 行和第 indices[i][1] 列进行加一操作。

在执行完所有 indices 指定的增量操作后,返回矩阵中 奇数值单元格 的数目。

需要注意行和列重叠的地方是累计加的

解题思路分析

观察题目数据范围较小,采用较为暴力的模拟也是可以通过的,但是我们这里按照进阶的标准来进行解题,时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题。

考虑到对于每一行和每一列来说,如果在 indices 中出现偶数次那么就相当于没有出现,所以我们可以统计在 indices 中行和列出现奇数的次数,这里令统计好的行和列分别记为:

  • 出现奇数次行的总和为 sumr
  • 出现奇数次列的总和为 sumc 那么可以通过数学计算的方式来得出最后执行完所有 indices 指定的增量操作后,返回矩阵中 奇数值单元格 的数目。
  • 因为对于统计出来出现奇数次的行和列来说,他们相交的部分为偶数次,所以只需要减去相交部分的单元格数量即可,那么最后答案就是 sumr * n + sumc * m - sumr * sumc * 2

为什么要 * 2:是因为在 sumr * n 和 sumc * m 的时候分别加了一次相交的部分,总共就是加了两次,所以需要 * 2

具体实现

  • 在统计 indices 中进行和列出现是否为奇数次时,我们可以使用两个一维数组进行统计 sr[m] 和 sc[n],分别表示行和列出现的次数。
  • 因为我们只需统计出现奇数次的行和列,那么我们可以采用异或 ^ 运算进行优化。
  • 最后统计行和列出现奇数次的个数即可。

复杂度分析

  • 时间复杂度:O(n + m + indices.length),n 和 m 分别为矩阵的长和宽,indices.length 为数组 indices 的长度。
  • 空间复杂度:O(n + m),仅需用于保存行和列的一维数组。

代码实现

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        //统计被加上奇数次的行和列
        int sr[m], sc[n];
        memset(sr, 0, sizeof(sr));
        memset(sc, 0, sizeof(sc));
        int sumr, sumc;
        sumr = sumc = 0;
        for(auto &v : indices){
            //如果为偶数次就是 0,奇数次为 1,用异或来变化0和1
            sr[v[0]] ^= 1;
            //统计奇数次的行
            if(sr[v[0]]) sumr++;
            else sumr--;
            sc[v[1]] ^= 1;
            //统计奇数次的列
            if(sc[v[1]]) sumc++;
            else sumc--;
        }
        //奇数次行个数加上奇数次列个数,减去相交为偶数次的点,因为加了两遍所以要 *2
        int ans = sumr * n + sumc * m - sumr * sumc * 2;
        return ans;
    }
};

总结

  • 该题难点在于如何优化时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题。
  • 通过统计行和列出现的次数便能进一步实现优化。核心思想在于计数。

测试结果:

以上就是C++实现leetcode 1252奇数值单元格的数目题解的详细内容,更多关于C++奇数值单元格的数目的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // returns true trie.search("app&

  • C++实现LeetCode数组练习题

    目录 1.存在重复元素 2.最大子序和 3.两数之和 4.合并两个有序数组 5.两个数组的交集II 6.买卖股票的最佳时机 7.杨辉三角 8.重塑矩阵 9.有效的数独 10.矩阵置零 总结 1.存在重复元素 排序数组,之后遍历是否有重复的元素 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return

  • C++LeetCode数据结构基础详解

    目录 一.只出现一次的数字 二.多数元素 三.三数之和 总结 一.只出现一次的数字 遍历一遍数组利用异或的特性来实现(相同为0,相异为1 ) 例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了 public int singleNumber(int[] nums) { int res=0; for(int i=0;i<nums.length;i++){ res=res^nums[i]; } return res; } 二.多数元素

  • C++ Leetcode实现从英文中重建数字

    目录 题目 分析 代码 题目 分析 首先我们先分析每个字母的组成,然后发现一些字符只在一个单词中出现,我们先去统计一下这些单词个数. z,w,u,x,g都只出现在一个数字中,也就是0,2,4,6,8,我们用哈希表统计一下s字符串中各个字符的数量,就可以知道0,2,4,6,8的数量,然后我们注意一下只在两个数字中出现的字符. h 只在 3,8 中出现.由于我们已经知道了 8 出现的次数,因此可以计算出 3 出现的次数. f 只在 4,5 中出现.由于我们已经知道了 4 出现的次数,因此可以计算出

  • C++实现LeetCode(648.替换单词)

    [LeetCode] 648.Replace Words 替换单词 In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another w

  • C++实现LeetCode(347.前K个高频元素)

    [LeetCode] 347. Top K Frequent Elements 前K个高频元素 Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume

  • C++算法实现leetcode 1252奇数值单元格数目

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1252. 奇数值单元格的数目 给你一个 m x n 的矩阵,最开始的时候,每个单元格中的值都是 0. 另有一个二维索引数组 indices,indices[i] = [ri, ci] 指向矩阵中的某个位置,其中 ri 和 ci 分别表示指定的行和列(从 0 开始编号). 对 indices[i] 所指向的每个位置,应同时执行下述增量操作: ri 行上的所有单元格,加 1 . ci 列上的所有单元格

  • DataGridView带图标的单元格实现代码

    目的: 扩展 C# WinForm 自带的表格控件,使其可以自动判断数据的上下界限值,并标识溢出. 这里使用的方法是:扩展 表格的列 对象:DataGridViewColumn. 1.创建类:DecimalCheckCell /// <summary> /// 可进行范围检查的 数值单元格 /// </summary> public class DecimalCheckCell : DataGridViewTextBoxCell { private bool checkMaxVal

  • 后端算法题解LeetCode前缀和示例详解

    目录 面试题 01.09. 字符串轮转 方法一:模拟 思路 题解 方法二:搜索子字符串 思路 题解 1480. 一维数组的动态和 方法一:前缀和 思路 题解 724. 寻找数组的中心下标 方法一:前缀和 思路 解题 面试题 01.09. 字符串轮转 面试题 01.09. 字符串轮转 难度:easy 字符串轮转.给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串). 示例1: 输入:s1 = "wa

  • JavaScript前端学算法题解LeetCode最大重复子字符串

    目录 最大重复子字符串 解题思路 知识点 这是LeetCode的第1668题:最大重复子字符串 最大重复子字符串 给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k .单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值.如果 word 不是 sequence 的子串,那么重复值 k 为 0 .给你一个字符串 sequence 和 word ,请你返回

  • jQuery实现HTML表格单元格的合并功能

    本文实例讲述了jQuery实现HTML表格单元格合并的方法.分享给大家供大家参考,具体如下: 运行效果截图如下: 合并前: 合并后: 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.

  • PHPExcel合并与拆分单元格的方法

    本文实例讲述了PHPExcel合并与拆分单元格的方法.分享给大家供大家参考,具体如下: $objPHPExcel; $filepath="c:\temp.xlsx"; try { $objReader = PHPExcel_IOFactory::createReader('Excel2007'); $objPHPExcel = $objReader->load($filepath); } catch (Exception $e) { die(); } $column_index

  • PHP使用PHPExcel删除Excel单元格指定列的方法

    本文实例讲述了PHP使用PHPExcel删除Excel单元格指定列的方法.分享给大家供大家参考,具体如下: 需求是这样的: 有一个系统仅公司内部和外部经销商使用,在一个导出功能中公司内部员工跟外部经销商导出的列是不一样的(某些数据是不能提供给经销商的) 因为导出的数据都是一样的(某些列外数据外部没有)因此并没有单独处理,而是统一生成然后根据不同的账户再删除没有权限的列 /** * @Author: HTL * @Description: 移出单元列 * @objPHPExcel: phpexec

  • HTML Table 空白单元格补全的简单实现

    在最初自学 Web 开发的时候,那时没有所谓的 DIV/CSS 布局,一概 Table 布局的天下.当时有个问题就来了,如何补全宫格空白的单元格呢?--这是我在弄公司产品页头痛的问题.因为我不是学程序出身的,碰到这稍带算法的问题,就束手无策了,呵呵.顺带说说,记得分页的算法还折腾了我一下呢. 所谓宫格,就是说表格,3 行x 4 列 = 共12 单元格.如果只有 10 个产品,就只能填充表格 10 个单元格,其余的为空白.虽然空白,但也要渲染 <td></td> 元素,不然 tabl

  • 基于jQuery的合并表格中相同文本的相邻单元格的代码

    ONE 已经生成的数据表格大致内容如下: 地区 地区 商品代码 商品名称 数量 有效期至 距效期(月) 产品批号 规格 单位 条形码 广东 深圳 00028 红花油               广东 深圳 00028 红花油               广东 深圳 00028 红花油               广东 广州 00027 白花油               广东 广州 00028 红花油               广东 深圳 00028 红花油               广东

  • 基于JQuery实现相同内容合并单元格的代码

    web前端开发的时候经常会遇到要做表单的页面或者做一些表格的效果如相同内容要同一个单元格里面显示,一般的方法是table里面在套table但是这种方法会增加页面的负担影响页面加载速度但是如果用DIV有不好控制写的css样式要很多,那怎么办呢?我们就中和下利用JQuery来和他一个table里面相同内容的单元格,这里代码跟大家分享下,希望对大家有用,如下: 头部JQuery代码 复制代码 代码如下: <script type="text/javascript"> jQuery

随机推荐