算法笔记day06

目录

1.添加逗号

 2.跳台阶

3.扑克牌顺子

1.添加逗号

添加逗号_牛客题霸_牛客网

 算法思路：

按照提议模拟即可，从后向前遍历字符串，遍历三个字符之后，将其插入将这三个字符插入到新的字符串中再加上逗号。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    reverse(ret.begin(), ret.end());
    cout << ret << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

 2.跳台阶

跳台阶_牛客题霸_牛客网

算法思路：

动态规划的入门题

1.状态分析： dp[i] i级台阶的跳法

2.状态转移方程：以最后一步的状态推出状态转移方程，青蛙只能跳一步或者两步，所以到达i位置无非就是两种情况从i-1跳或者从i-2跳 dp[i] = dp[i -1] + dp[i - 2]。

#include <iostream>
using namespace std;

// 1 2 3 4
// a b c
//   a b c
int main() 
{
    int n = 0; 
    cin >> n;
    int a = 1, b = 1,c = 0;

    for(int i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    if(n ==0 || n == 1)
    cout << n << endl;
    else
    cout << c << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

3.扑克牌顺子

扑克牌顺子_牛客题霸_牛客网

算法思路：

这道题可以使用逆向思维，哪5张扑克牌不能组成顺子。

1.出现重复的牌，一定组不成顺子。

2.5张扑克，最大的牌 - 最小的牌 差值大于 4 也一定组不成顺子。

#include <functional>
class Solution {
public:
//2 0 0 4 6
    bool IsContinuous(vector<int>& numbers) 
    {
        int Max = 0;
        int Min = 14;
        int n = numbers.size();
        bool hash[14] = {0};
       for(auto a : numbers)
       {
        if(a != 0)
        {
            if(hash[a])
            {
                return false;
            }
            hash[a] = true; 
            Max = max(a, Max);
            Min = min(a,Min);       
        }
       }
        return Max - Min <= 4;
    }
};