字符串的最小复制粘贴次数

2024-05-11 19:08

本文主要是介绍字符串的最小复制粘贴次数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed). 
Paste: You can paste the characters which are copied last time. 
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1: 
Input: 3 
Output: 3 
Explanation: 
Intitally, we have one character ‘A’. 
In step 1, we use Copy All operation. 
In step 2, we use Paste operation to get ‘AA’. 
In step 3, we use Paste operation to get ‘AAA’. 
Note: 
The n will be in the range [1, 1000].

当n = 1时,已经有一个A了,我们不需要其他操作,返回0

当n = 2时,我们需要复制一次,粘贴一次,返回2

当n = 3时,我们需要复制一次,粘贴两次,返回3

当n = 4时,这就有两种做法,一种是我们需要复制一次,粘贴三次,共4步,另一种是先复制一次,粘贴一次,得到AA,然后再复制一次,粘贴一次,得到AAAA,两种方法都是返回4

当n = 5时,我们需要复制一次,粘贴四次,返回5

当n = 6时,我们需要复制一次,粘贴两次,得到AAA,再复制一次,粘贴一次,得到AAAAAA,共5步,返回5

通过分析上面这6个简单的例子,我想我们已经可以总结出一些规律了,首先对于任意一个n(除了1以外),我们最差的情况就是用n步,不会再多于n步,但是有可能是会小于n步的,比如n=6时,就只用了5步,仔细分析一下,发现时先拼成了AAA,再复制粘贴成了AAAAAA。那么什么情况下可以利用这种方法来减少步骤呢,分析发现,小模块的长度必须要能整除n,这样才能拆分。对于n=6,我们其实还可先拼出AA,然后再复制一次,粘贴两次,得到的还是5。分析到这里,我想解题的思路应该比较清晰了,我们要找出n的所有因子,然后这个因子可以当作模块的个数,我们再算出模块的长度n/i,调用递归,加上模块的个数i来更新结果res即可,

这里的递归函数值得是已经有n个字符串,下一步应该怎么做,很明了的递归思路,很值得学习和反思

 

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
#include <iomanip>using namespace std;class Solution 
{
public:int minSteps(int n){if (n == 1)return 0;else{int res = n;for (int i = n - 1; i >=2; i--){if (n%i == 0)res = min(res, minSteps(n / i) + i);}return res;}}
};


--------------------- 
作者:JackZhangNJU 
来源:CSDN 
原文:https://blog.csdn.net/jackzhang_123/article/details/78865357 
版权声明:本文为博主原创文章,转载请附上博文链接!

 

dp 方法待理解

思路: 
这道题是动态规划题,状态转移方程不是很明显,需要仔细分析。 
先把dp的最小不走都设置为无穷大(0x7FFFFFFF), 初始化条件为:dp[0]=dp[1]=0 ,状态转移方程为: 
dp[i]=min(dp[i],dp[j]+i/j),i>1,j<i且i是j的整数倍 
上述状态转移方程表示:如果i是j的倍数,那么i可以通过粘贴(i/j-1)次j 得到, 再加上一次复制操作,那么可以通过dp[j]+i/j 次操作得到dp[i] .C++代码如下:class Solution {
public:int minSteps(int n) {vector<int> dp(n+1,0x7FFFFFFF);dp[0] = dp[1] = 0;for(int i=2;i<n+1;++i){for(int j=1;j<i;++j){if(i%j==0){dp[i] = min(dp[i], dp[j]+i/j);}}}return dp[n];}
};

 

这篇关于字符串的最小复制粘贴次数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/980399

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为