【LeetCode】650. 只有两个键的键盘

news/2024/12/4 17:30:17/

650. 只有两个键的键盘(中等)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. 思路

    • 不同于以往通过加减实现的动态规划,这里需要乘除法计算位置。因为粘贴操作是倍数增加,使一个一维数组 dp,其中位置 i 表示延展到长度 i 的最少操作次数。
    • 对于每个位置 j ,如果 j 可以被 i 整除,那么长度 i 就可以由长度 j 得到,其操作次数等价于把一个长度为 1 的 A 延展到长度为 i/j ,因此递推公式为:dp[i] = dp[j] + dp[i/j]; 。比如 i = 10 ,可以在 i=5 的时候,选择复制全部字符并粘贴,就扩展为 10 个 A。
  2. 代码

    class Solution {
    public:int minSteps(int n) {vector<int> dp(n+1, 0);for(int i=2; i<=n; ++i){dp[i] = i;for(int j=2; j*j<=i; ++j){if(i % j == 0){dp[i] = dp[j] + dp[i/j]; break;}}}return dp[n];}
    };
    
  3. 收获

    • 理解起来有点难,自己跟着代码算一下比较好理解。
    • 我自己模拟的时候,计算错了,忘记复制全部字符,而我每次复制的字符都是之前复制的两倍(即 2 - 4 - 8 - …)。

http://www.ppmy.cn/news/52642.html

相关文章

WMS是什么?

WMS&#xff08;Warehouse Management System&#xff09;中文译作仓库管理系统&#xff0c;是一种专用于物流仓储管理的IT系统。它主要应用于企业物流中心、配送中心、供应商物料储备中心、电子商务配送中心等仓库管理过程中。 WMS系统可以帮助企业管理和控制其物流仓储流程。…

HOG+SVM分类器实践

文章目录 HOGSVM分类器实践制作SVM分类器导入所需的库提取HOG特征读取正样本和负样本训练分类器定义主函数小结 测试SVM分类器相关疑问1. 提取HOG特征为什么不能彩色图像呢&#xff1f;2. 出现如下错误3. 测试代码中&#xff0c;当我传入100*100的图片时候&#xff0c;为什么im…

玩机搞机----mtk芯片机型 另类制作备份线刷包的方式 读写分区等等

前面分享了几期高通和mtk芯片机型备份字库的几种方法教程。这些针对与很多没有线刷包资源的手机机型玩机操作。前面对接一个友商的mtk芯片杂牌机。和另外一个国外mtk芯片级都是来制作线刷包。因为&#xff0c;这些机型没有固件流出。而同一批机型中安卓版本高低不固定。支持的资…

战争教育策略游戏 MiracleGame,开启新阶段重塑生态和玩法

香港 Web3 区块链周刚刚在一片喧嚣中结束。各路大V、KOL 们的 report 都对 GameFi 的前景非常自信。2021-2023年期间&#xff0c;大量资金涌入 GameFi 赛道&#xff0c;GameFi 一旦爆发将会是现象级的出圈事件。 MiracleGame 是一款基于 BNB Chain 构建的英雄和元神主题的战争教…

13共模电感

目录 一、原理 二、差模噪声和共模噪声主要来源 三、共模电感如何抑制共模信号 四、共模电感的选取 一、原理 在介绍共模电感之前先介绍扼流圈&#xff0c;扼流圈是一种用来减弱电路里面高频电流的低阻抗线圈。为了提高其电感扼流圈通常有一软磁材料制的核心。共模扼流圈有…

Samba

Samba 文章目录 Samba1.samba简介2. samba访问3. 实例 1.samba简介 Samba是在Linux和UNIX系统上实现SMB协议的一个免费软件&#xff0c;由服务器及客户端程序构成。 在此之前我们已经了解了NFS&#xff0c;NFS与samba一样&#xff0c;也是在网络中实现文件共享的一种实现&…

【设计模式】工厂模式

目录 一、说明二、简单工厂模式2.1 说明2.2 简单工厂代码示例2.3 静态工厂代码示例 三、工厂方法模式3.1 说明3.2 工厂方法代码示例 四、抽象工厂模式4.1 说明4.2 抽象工厂代码示例 五、通过配置获取 一、说明 1.如果使用对象的时候直接new该对象&#xff0c;就会对该对象耦合严…

数字化转型中的石头和沙子问题

作者介绍 朱金衡&#xff0c;西门子Mendix 高级技术咨询顾问及架构师&#xff0c;Mendix Certified 中级培训讲师以及TOGAF Certified 企业架构师。作为专家服务架构师提供咨询服务&#xff0c;如方案设计、开发辅导、故障排除、应用程序审查等&#xff0c;同时创造了许多专门…