admin管理员组

文章数量:1440489

​​​48days强训——day9

第一题:添加逗号

链接:添加逗号_牛客题霸_牛客网

描述 对于一个较大的整数 N(1<=N<=2,000,000,000) 比如 980364535,我们常常需要一位一位数这个数字是几位数,但是如果在这 个数字每三位加一个逗号,它会变得更加易于朗读。 因此,这个数字加上逗号成如下的模样:980,364,535请写一个程序帮她完成这件事情 输入描述: 一行一个整数 N 输出描述: 一行一个字符串表示添加完逗号的结果 示例1 输入: 980364535 输出: 980,364,535 备注: 1≤n≤2,000,000,000

题解一:利用取模,将每一位数放在字符串里,然后每三位添加一个逗号,最后进行逆置。

题解二:n - i - 1 计算的是从当前字符到字符串末尾的距离,当能被3取模则添加逗号。

代码:

代码语言:javascript代码运行次数:0运行复制
#include <bits/stdc++.h>
using namespace std;

int main() 
{
    long long s;
    cin >> s;
    string ret;
    int count = 0;
    while (s!=0) 
    {   
        count++;
        int t = s % 10;
        ret += t+'0';
        if(count % 3 == 0)
        {
            count = 0;
            ret += ',';
        }
        s /= 10;
    }
    if(ret[ret.size()-1] == ',')ret.pop_back();
    reverse(ret.begin(),ret.end());
    cout << ret << endl;
    return 0;
}


#include <bits/stdc++.h>
using namespace std;

int main() 
{
    string s;
    cin >> s;
    string ret;
    int n = s.size();
    for (int i = 0; i < n; i++) 
    {
        ret += s[i];
        if ((n - i - 1) % 3 == 0 && i != n - 1) ret += ',';
    }
    cout << ret << endl;
    return 0;
}

第二题:DP2 跳台阶

链接:.2415.3001.5331

描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 数据范围:0≤n≤400≤n≤40 要求:时间复杂度:O(n)O(n) ,空间复杂度: O(1)O(1) 输入描述: 本题输入仅一行,即一个整数 n 输出描述: 输出跳上 n 级台阶有多少种跳法 示例1 输入: 2 输出: 2 说明: 青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2 示例2 输入: 7 输出: 21

题解:简单动态规划。

代码:

代码语言:javascript代码运行次数:0运行复制
#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int n;
    cin >> n;
    vector<int> dp(n+1);

    dp[0] = 1,dp[1] = 2;
    for(int i = 2; i < n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n-1];
    return 0;
}

第三题:JZ61 扑克牌顺子

链接:扑克牌顺子_牛客题霸_牛客网

描述 现在有2副扑克牌,从扑克牌中随机五张扑克牌,我们需要来判断一下是不是顺子。 有如下规则: 1. A为1,J为11,Q为12,K为13,A不能视为14 2. 大、小王为 0,0可以看作任意牌 3. 如果给出的五张牌能组成顺子(即这五张牌是连续的)就输出true,否则就输出false。 4.数据保证每组5个数字,每组最多含有4个零,数组的数取值为 [0, 13] 要求:空间复杂度 O(1)O(1),时间复杂度 O(nlogn)O(nlogn),本题也有时间复杂度 O(n)O(n) 的解法 输入描述: 输入五张扑克牌的值 返回值描述: 五张扑克牌能否组成顺子。 示例1 输入: [6,0,2,0,4] 返回值: true 说明: 中间的两个0一个看作3,一个看作5 。即:[6,3,2,5,4] 这样这五张牌在[2,6]区间连续,输出true 示例2 输入: [0,3,2,6,4] 返回值: true 示例3 输入: [1,0,0,1,0] 返回值: false 示例4 输入: [13,12,11,0,1] 返回值: false

题解: 统计非零牌的最大最小值差是否≤4且无重复。万能牌0可填补空缺,只要非零牌极差≤4即能组成顺子。

代码:

代码语言:javascript代码运行次数:0运行复制
class Solution 
{
    bool hash[14] = {false};
public:
    bool IsContinuous(vector<int>& numbers) 
    {
        int maxval = 0,minval = 14;
        for(auto x : numbers)
        {
            if(x)
            {
                if(hash[x]) return false;
                hash[x] = true;
                minval = min(minval,x);
                maxval = max(maxval,x);
            }
        }
        return maxval-minval <= 4;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。 原始发表:2025-04-10,如有侵权请联系 cloudcommunity@tencent 删除int程序动态规划数据字符串

本文标签: ​​​48days强训day9