Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数

这篇具有很好参考价值的文章主要介绍了Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Every day a Leetcode

题目来源:3071. 在矩阵上写出字母 Y 所需的最少操作次数

解法1:模拟

统计 Y 中的元素出现次数,记到一个长为 3 的数组 cnt1 中。统计不在 Y 中的元素出现次数,记到一个长为 3 的数组 cnt2 中。

计算最多可以保留多少个元素不变,设这个值为 maxNotChange。

在 0,1,2 中枚举 i 和 j,其中 i≠j。让 Y 中的元素都变成 i,不在 Y 中的元素都变成 j,那么 maxNotChange 就是 cnt1[i]+cnt2[j] 的最大值。

最后返回 n2−maxNotChange,即最少要修改的元素个数。

代码:

/*
 * @lc app=leetcode.cn id=3071 lang=cpp
 *
 * [3071] 在矩阵上写出字母 Y 所需的最少操作次数
 */

// @lc code=start
class Solution
{
public:
    int minimumOperationsToWriteY(vector<vector<int>> &grid)
    {
        int n = grid.size();    // n 为奇数
        vector<int> cnt1(3, 0); // 字母 Y 单元格各数字的出现次数
        vector<int> cnt2(3, 0); // 非字母 Y 单元格各数字的出现次数

        auto isY = [&](int i, int j) -> bool
        {
            if (i < 0 || i > n || j < 0 || j > n)
                return false;
            if (i == j && i <= n / 2)
                return true;
            if (i + j == n - 1 && i <= n / 2)
                return true;
            if (i >= n / 2 && j == n / 2)
                return true;
            return false;
        };

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                int x = grid[i][j];
                if (isY(i, j))
                    cnt1[x]++;
                else
                    cnt2[x]++;
            }

        int max_not_change = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (i != j)
                    max_not_change = max(max_not_change, cnt1[i] + cnt2[j]);

        return n * n - max_not_change;
    }
};
// @lc code=end

结果:

Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数,Every day a LeetCode,C++,数据结构与算法,leetcode,模拟

复杂度分析:

时间复杂度:O(n2+k2),其中 n 为 grid 的长度,k=3。

空间复杂度:O(k),其中 k=3。文章来源地址https://www.toymoban.com/news/detail-841168.html

到了这里,关于Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MATLAB计算程序运行所需的时间

    在使用MATLAB进行计算时,用户有时需要了解程序运行所花费的四件,以此来评价程序的执行效率,从而对代码进行优化 可以使用3种方法来得到程序运行所需要的时间 1.使用tic和toc命令 将tic和toc命令相结合来得到程序的运行时间 ①tic命令:启动一个定时器 ②toc命令:停止由

    2024年02月11日
    浏览(40)
  • Windows运行Spark所需的Hadoop安装

    解压文件  复制bin目录         找到winutils-master文件hadoop对应的bin目录版本         全部复制替换掉hadoop的bin目录文件  复制hadoop.dll文件         将bin目录下的hadoop.dll文件复制到System32目录下    配置环境变量  修改hadoop-env.cmd配置文件 注意jdk装在非C盘则完全没问题,

    2024年02月10日
    浏览(42)
  • 嵌入式设备逆向所需的工具链

    导语:本文介绍了嵌入式设备逆向所需的工具链。 相关的应用程序或工具有: UART(Universal Asynchronous Receiver Transmitter,通用异步收发器): UBoot; Depthcharge; SPI (Serial Peripheral Interface,串行外设接口): Flashrom; I2C(Inter-Integrated Circuit,集成电路总线): i2cdetect; i2cdump; JTAG (

    2024年02月03日
    浏览(47)
  • AD20打样所需的Gerber文件输出

    打样前2步必须要有,第3步IPC网表的输出可有可无。 所有步骤源于凡亿教育,在此进行笔记记录。 点击 文件 → 制造输出 → Gerber Files 通用 :单位选择 英寸 ,格式选择 2:5 (精度为0.01mil) 层 : 绘制层 选择 选择使用的 , 镜像层 选择 全部去掉 ,勾选 包括未连接的中间层

    2024年02月15日
    浏览(41)
  • 技术写作者所需的关键技能和知识

    成为一名优秀的技术写作者需要以下核心技能: 写作技巧: 优秀的语言和语法掌握能力 出色的拼写能力 对标点符号的理解 技术知识: 对复杂技术概念有很好的理解 将复杂概念转换为易于理解的内容 研究技能: 识别最终用户的需求 快速理解新概念和技术的能力 工具技能: 熟练

    2024年02月04日
    浏览(46)
  • 在stm32中,所需的库函数有那些

    使用库函数中封装的函数来访问外设可以使得stm32开发更加方便,省去了查寄存器位操作,只用查库函数就可以了 但是使用库函数时要记住真正的其本质是获取寄存器的地址然后设置其中的位 库函数一般添加到自己创建的Lib文件夹中 库函数实际上分成了两块,分别是CSMIS和标

    2024年04月26日
    浏览(37)
  • leetcode 1806. 还原排列的最少操作步数

    题目链接:leetcode 1806 给你一个偶数 n​​​​​​ ,已知存在一个长度为 n 的排列 perm ,其中 perm[i] == i​(下标 从 0 开始 计数)。 一步操作中,你将创建一个新数组 arr ,对于每个 i : 如果 i % 2 == 0 ,那么 arr[i] = perm[i / 2] 如果 i % 2 == 1 ,那么 arr[i] = perm[n / 2 + (i - 1) / 2]

    2024年02月20日
    浏览(33)
  • 如何用手机快速获得真人手办所需的人像模型

    伴随网络生活覆盖面的增大,越来越多的领域需要三维模型 ,比如最近爆火的真人手办就必须用到人像模型 。 真人手办的制作过程其实非常简单,在专门搭建的摄影棚内进行全身3D扫描,获得3D人体模型,然后进行修模,最后3D打印出来,一个真人手办就诞生了。 想快速做一

    2024年02月11日
    浏览(628)
  • Python:下载python的库所需的国内下载源

    一、常用的国内镜像源 国内的一些下载源,可以加快下载速度。 二、使用方法 pip install -i https://pypi.doubanio.com/simple/ 包名 举例:安装numpy库

    2024年02月05日
    浏览(44)
  • macOS黑苹果安装提示未能安装所需的固件更新

    macOS big sur 、macOS Monterey 黑苹果安装跳出个更新助理然后提示未能安装所需的固件更新解决办法。 OpenCore引导解决方法: 1.config.plist — PlatformInfo — Generic,更换一个比较新的SMBIOS机型; 2.config.plist — PlatformInfo — Generic 勾选 AdviseFeatures; 然后保存重启即可解决。 这两天帮同

    2024年02月09日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包