2 Keys Keyboard“编程题”
程序员文章站
2023-10-28 20:10:04
题目描述
解题思路
题目大意自不必说,至于说解法,这道题目有想过往动态规划方面去想,但想着想着就被可爱的某婷带偏了,不过最后还竟另辟蹊径,通过对数字本身的研究而解出本题。大致思路如下:
对于n个字...
题目描述
解题思路
题目大意自不必说,至于说解法,这道题目有想过往动态规划方面去想,但想着想着就被可爱的某婷带偏了,不过最后还竟另辟蹊径,通过对数字本身的研究而解出本题。大致思路如下:
对于n个字符a,如果想要找出最小的复制粘贴步数,为何不从它的因数找起呢?以42为例,42=21*2=7*3*2,也就是说我要先复制初始的一个a,粘贴得到一个a之后,再复制这两个a,粘贴2次得到6个a,再复制这6个a,粘贴6次就可以得到42个a啦,当然关于这理论的证明我暂时无法给出,不过accept证实我这个想法是ok的。
c++代码实现
class solution { public: int minsteps(int n) { int t = 2; int a[1000], p = -1;; while (n != 1) { while (n % t != 0) { t++; } a[++p] = t; n = n / t; } int result = 0; for (int i = 0; i <= p; ++i) { result += a[i]; } return result; } };
运行结果显示
后来又查看了题目解析,重新构思动态规划的方法后发现有异曲同工之妙,即令dp[i]表示要想生成i个字符所需要的步数,初始值dp[0]=dp[1]=0;状态转移方程为dp[i]=min(dp[i],dp[j]+i/j),i>1,j
class solution { public: int minsteps(int n) { vector dp(n+1,1000000); dp[0] = dp[1] = 0; for(int i=2;i
上一篇: Android GridView实现滚动到指定位置的方法
下一篇: 丑了还可以医美整容
推荐阅读
-
2 Keys Keyboard“编程题”
-
Java编程题(1):n个数里出现次数大于等于n/2的数
-
2018 Bytedance AI Camp 编程题2: Split Array Largest Sum
-
2 Keys Keyboard“编程题”
-
C++基础编程题(40)“有两个矩阵a和b,均为2行3列。求两个矩阵之和。重载运算符“+”,使之能用于矩阵相加
-
2019携程校园招聘编程题(2)取满足条件订单号
-
Python练习题答案: *分配【难度:2级】--景越Python编程实例训练营,1000道上机题等你来挑战
-
编程作业 50 2题 编写一个程序求100以内的全部素数
-
2020年4月2日华为消费者BG部门Android安卓第一次面试经验(一面,面经,编程代码题)
-
Java经典编程题--求1+2!+3!+...+20!的和