LeetCode#650 2 Keys Keyboard题解(C++版)

xiaoxiao2021-02-28  5

题干

原题网址: https://leetcode.com/problems/2-keys-keyboard/description/

题干解析

输入一个[1, 1000]之间的整数n,代表目标需要生成的A的个数。给你的文本上初始化有一个A,你对文本只能有以下两种操作,最后要让文本上有n个A,找出最小的操作次数。 操作1:Copy all,即复制当前文本的所有字符。 操作2:粘贴。

知识点

动态规划

难度

中等

解题思路

这道题可以用动态规划来解,也可以不用动态规划来解。 1.动态规划解版 因为只有两种操作,我们每一步做决策时只需要考虑如下两种情况:是要先复制一下再粘贴,还是不复制就粘贴。对于每一步,我们算出进行这种操作后,需要多少个操作能达到目标状态所需要的总次数(或者无法达到),然后取较小次数那一次便可。 2.非动态规划版 同上面所说,我们要么先复制再粘贴,要么不复制直接粘贴。而很显然,复制板上A的长度是只增不减的,且每次复制之后,复制板上A的长度是之前复制板上A的长度的倍数,所以如果复制后的复制板上的长度无法被剩下需要生成的A的个数所整除的话,我们就不可以复制,否则后面的A的长度要超过所需的长度,即无解。而如果可以被整除,我们为了得到较少的操作次数,就要先复制(想象一下,复制虽然会多了一次操作,但是复制后复制板上的A的长度至少是原先复制板上A的长度的两倍(如果上一次没有复制直接粘贴的话,长度不止两倍)。如果不复制,至少也要两次粘贴才能达到刚刚复制一次再粘贴一次的效果。所以,能复制的时候就尽管复制,顶多也就和不复制直接粘贴扯平)。因此,代码写起来非常简洁。

代码

//动态规划解法 int MAX = 1001; class Solution { public: int dp(int n, int have, int c) { //have代表已经有了几个A,c代表当前复制板上有几个A if (n == have) { // 如果已经到达目标,返回0 return 0; } else if (n < have) { // 如果超出了目标,则代表无解,返回MAX return MAX; } else if ((n - have) % c != 0) { // 如果已经不能被整除,无解(因为have一定是c的倍数,此时再复制也无意义) return MAX; } int temp1 = 2 + dp(n, have * 2, have); // 复制一次加粘贴一次 int temp2 = 1 + dp(n, have + c, c); // 不复制,只粘贴 if (temp1 > temp2) { //哪种操作次数少,返回哪一种 return temp2; } else { return temp1; } } int minSteps(int n) { if (n <= 1) { return 0; } return dp(n, 1, 1) + 1; } }; class Solution { public: int minSteps(int n) { if (n <= 1) { // 如果需要的长度小于等于1,那就不需要操作了,直接返回0 return 0; } int ans = 0; // 初始化操作的次数 int left = n - 1; // 剩下还未生成的A的个数 int paste = 1; // 复制板上A的个数,一开始肯定要先复制一下,初始化为1 left -= paste; // 第一次复制之后肯定要粘贴,所以剩下的未生成的A减1 ans += 2; // 一次复制一次粘贴,已经操作了两次 while (left > 0){ if (left % (n - left) == 0) { // 如果剩下的需要生成的A的个数能够整除当前A的个数,那么复制全部,然后粘贴一次 paste = n - left; left -= paste; ans += 2; } else { // 否则,因为复制版长度只增不减,若当下不能整除,复制后的复制版内容长度是当前的长度的倍数,同样不能整除。所以直接粘贴 left -= paste; ans += 1; } } return ans; } };
转载请注明原文地址: https://www.6miu.com/read-1400202.html

最新回复(0)