C++日常刷题积累
今日刷题汇总 - day009
1、添加逗号
1.1、题目
1.2、思路
读完题，知道让我们将一个大整数，以逗号为分割且三位数为基准，进行划分为若干份以便提升大数的读识。那么通过思考示例分析，可以将str原字符串遍历，遍历同时尾插到retstr字符串，且每三位就增加一个逗号即可。思路其实不难，只需要注意一些细节的处理即可，这里我记录我的笨办法目的是，应用一些接口，也提供我写完后觉得很冗余的优化，接下来，就是程序实现。
1.3、程序实现
首先，按照题目要求完成输入，然后笨办法就是，按照思路遍历str大数字符串，遍历一位就尾插一位到retstr中，且每三位就尾插一个逗号，然后输出retstr,，结果提交后发现不能通过全部样例与实际要求不符。因为逗号的添加是从前向后进行尾插的。值得注意的是，这里i需要等于1，开始遍历，所以下标str[i-1]才能正确尾插，是为了使得i%3避免进来就尾插逗号。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
string retstr;
size_t len = str.size();
for (size_t i = 1; i <= len; i++)
{
retstr += str[i-1];
if(i%3 == 0)
{
retstr += ',';
}
}
cout << retstr << endl;
return 0;
}
所以为了解决这个问题，我将原字符串先进行reverse逆置，再进行尾插操作。想着最后再逆置回来输出即可，然后提交发现，逗号虽然可以正确插入了，但是会将最开头的数字前也插入逗号。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
reverse(str.begin(),str.end());
string retstr;
size_t len = str.size();
for (size_t i = 1; i <= len; i++)
{
retstr += str[i-1];
if(i%3 == 0)
{
retstr += ',';
}
}
reverse(retstr.begin(),retstr.end());
cout << retstr << endl;
return 0;
}
当时，没想着控制边界，笨办法就是调用erase把开头多余的逗号删除再逆置输出，虽然解决了问题，但是很冗余，且没必要，不过想着记录一下思考历程，熟悉一些其它接口的使用，所以还是写一下这个过程。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
reverse(str.begin(),str.end());
string retstr;
size_t len = str.size();
for (size_t i = 1; i <= len; i++)
{
retstr += str[i-1];
if(i%3 == 0)
{
retstr += ',';
}
}
size_t retlen = retstr.size();
if (retstr[retlen-1] == ',')
retstr.erase(retstr.begin() + retlen -1, retstr.end());
reverse(retstr.begin(),retstr.end());
cout << retstr << endl;
return 0;
}
1.4、程序实现 – 优化1
基于笨办法的基础，思考后发现直接在尾插时就可以控制最后逗号尾插的边界问题，即使得i != len即可。不用调用erase删除了。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
reverse(str.begin(),str.end());
string retstr;
size_t len = str.size();
for(int i = 1;i <= len ;i++)
{
retstr += str[i-1];
if(i%3 == 0 && i != len)
retstr += ',';
}
reverse(retstr.begin(),retstr.end());
cout << retstr << endl;
return 0;
}
1.5、程序实现 – 优化2
继续思考，发现既然顺着控制3位是反着的，那么直接在尾插就以高位进行3位的控制不就行了吗？即，if((len-i-1)%3 == 0 && i != len-1)即可，且不用i从1开始了，也能正确尾插了。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
string retstr;
size_t len = str.size();
for(int i = 0;i < len ;i++)
{
retstr += str[i];
if((len-i-1)%3 == 0 && i != len-1)
retstr += ',';
}
cout << retstr << endl;
return 0;
}
2、跳台阶
2.1、题目
2.2、思路
读完题，知道青蛙跳台问题属于比较经典的dp动态规划问题，求青蛙对于n个台阶，最多有多少种跳法。既然如此，使用dp就需要分析dp的状态表示和状态转移方程，根据题目示例分析不难得出：可以dp[i]表示，跳到第i个台阶可以最多拥有的跳法；其次推导dp状态转移方程：dp[i] = dp[i-1] + dp[i-2];因为只能由前一个台阶或前两个台阶才能有机会跳到第i个台阶，所以递推得出即可。此外，对于前两个台阶的跳法，很快知道，dp[0] = 0;dp[1] = 1;dp[2] = 2;由此dp思路就完成了。另外，这里还可以用递归的写法，使用递归只需要注意递归的终止条件和划分为子问题求解，所以本质也属于动态规划法，那么递归就是利用封装一个func函数，不断调用字节进行求值返回即可。接下来，就是程序实现。
2.3、程序实现 – dp
比较简单，根据思路分析的需要定义dp[N]数组，然后正确输入n个台阶，初始化推导的dp[0~2]，所以直接从3个台阶开始累计即可。最后输出dp[n]就是n个台阶的最多方法。
#include <iostream>
using namespace std;
const int N = 41;
int dp[N];
int main()
{
int n;
cin >> n;
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[n] << endl;
return 0;
}
2.4、程序实现 – 递归
那么递归程序也是按照思路，封装func执行调用逻辑，利用n=0,1,2控制递归终止条件且划分子问题return返回输出即可。
#include <iostream>
using namespace std;
int func(int n)
{
if(n == 0)
return 0;
else if(n == 1)
return 1;
else if(n == 2)
return 2;
else
return func(n-1) + func(n-2);
}
int main()
{
int n;
cin >> n;
cout << func(n) << endl;
return 0;
}
3、扑克牌顺子
3.1、题目
3.2、思路
读完题，知道让判断在一组扑克牌中，是否有顺子，且大小王用0表示，并可以替换为任意牌；其次，AJQK数值大小分别是1，11，12，13最大，即范围[0,13]。那么，基本思路分析示例看出，不能存在相同的数，这样一定不是顺子，然后，如果是顺子，那么最大的数减去最小的数之差是等于4的，此外，主要是对于大小王的处理，如果是最大与最小的数直之差大于4，那么0代替任何数都无法组成顺子，所以只有差值小于4，大小王才能替换成顺子。另外，还存在一些细节，接下来，就是程序实现。
3.3、程序实现
首先，搞懂思路分析后明白，主要是处理重复值以及大小王的替换规则，那么先根据需求，定义一个hash[]数组表示，是否存在重复值，然后定义maxval 和 minval表示除大小王以外的最大值和最小值，然后利用范围for遍历，如果不是大小王就判断是否已标记（是否是重复值），不是就标记已出现一次，然后更新最大值和最小值，遍历完，最后根据思路分析的大小王的替换规则，判断最大值和最小值的差值，是否小于等于4即可。
class Solution {
public:
bool hash[14] = { false };
bool IsContinuous(vector<int>& numbers)
{
int maxval = -1;
int minval = 14;
for(auto e : numbers)
{
if(e)
{
if(hash[e])
return false;
hash[e] = true;
maxval = max(maxval,e);
minval = min(minval,e);
}
}
return maxval - minval <= 4;
}
};
