• 【大摆子 做 摆烂题】【C++】

    1. 把字符串转换成整数

    描述:将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为 0 或者字符串不是一个合法的数值则返回 0

    注意：

    ①字符串中可能出现任意符号，出现除 +/- 以外符号时直接输出 0

    ②字符串中可能出现 +/- 且仅可能出现在字符串首位。

    输入描述：输入一个字符串,包括数字字母符号,可以为空

    返回值描述：如果是合法的数值表达则返回该数字，否则返回0

    1.1 思路

    1. 其实也就是一位位把数字取下来然后再 加之前上一个数字 * 10

    2. 然后就是边界的判断，和正负号的处理

    1.2 代码实现

    1. class Solution {
    2. public:
    3.     int StrToInt(string str) {
    4.         if(str.empty())
    5.         {
    6.             return 0;
    7.         }
    8.         int falg = 1;
    9.         int ret = 0;
    10.         if(str[0] == '-')
    11.         {
    12.             falg = -1;
    13.             str[0] = '0';
    14.         }
    15.         else if(str[0] == '+')
    16.         {
    17.             falg = 1;
    18.             str[0] = '0';
    19.         }
    20.         
    21.         for(size_t i = 0;i < str.size();i++)
    22.         {
    23.             if(str[i] < '0'|| str[i] > '9')
    24.             {
    25.                 return 0;
    26.             }
    27.             ret = ret * 10 + str[i] - '0';
    28.         }
    29.         return falg * ret;
    30.     }
    31. };

    2. 不要2

    描述：二货小易有一个W*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。
    对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:
    ( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根
    小易想知道最多可以放多少块蛋糕在网格盒子里。

    输入描述：每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)

    输出描述：输出一个最多可以放的蛋糕数

    2.1 思路

    1.给个二维数组 初始化的时候把蛋糕就全部放好 也就是 == 1

    2.遍历一次二维数组把当前蛋糕对应不能放蛋糕的地方 == 0

    2.2 代码实现

    1. #include<iostream>
    2. #include<vector>
    3. using namespace std;
    4. int main()
    5. {
    6.     vector<vector<int>> vv;
    7.     int w = 0;
    8.     int h = 0;
    9.     int ret = 0;
    10.     cin >> w >> h;
    11.     vv.resize(w);
    12.     
    13.     for(auto &e : vv)
    14.     {
    15.         e.resize(h,1);
    16.     }    
    17.     
    18.     for(int i = 0;i < w;i++)
    19.     {
    20.         for(int j = 0;j < h;j++)
    21.         {
    22.             if(vv[i][j] == 1)
    23.             {
    24.                 if((i + 2) < w)
    25.                 {
    26.                     vv[i + 2][j] = 0;
    27.                 }
    28.                 if((j + 2) < h)
    29.                 {
    30.                     vv[i][j + 2] = 0;
    31.                 }
    32.                 ret++;
    33.             }
    34.         }
    35.     }
    36.     cout << ret << endl;
    37. }

    3. 统计回文

    描述；“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
    例如：A = “aba”，B = “b”。这里有4种把B插入A的办法：
            * 在A的第一个字母之前: "baba" 不是回文
            * 在第一个字母‘a’之后: "abba" 是回文
            * 在字母‘b’之后: "abba" 是回文
            * 在第二个字母'a'之后 "abab" 不是回文
            所以满足条件的答案为2

    输入描述：每组输入数据共两行。 第一行为字符串A 第二行为字符串B 字符串长度均小于100且只包含小写字母

    输出描述：输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

    3.1 思路

    1. 先实现一个用双指针的方法检测此对象是不是回文。

    2. 每次插入后检测是否为回文，是的话count++ 。

    3.2 代码实现

    1. #include<iostream>
    2. #include<string>
    3. using namespace std;
    4. bool IsCircleText(const string& s)
    5. {
    6.     int left = 0;
    7.     int right = s.size() - 1;
    8.     
    9.     while(left < right)
    10.     {
    11.         if(s[left] == s[right])
    12.         {
    13.             ++left;
    14.             --right;
    15.         }
    16.         else{
    17.             return false;
    18.         }  
    19.     }
    20.     return true;
    21. }
    22.  
    23. int main()
    24. {
    25.     string s1;
    26.     string s2;
    27.     size_t count = 0;
    28.     
    29.     getline(cin,s1);
    30.     getline(cin,s2);
    31.     
    32.    for(size_t i = 0;i <= s1.size();i++)
    33.    {
    34.        string s3 = s1;
    35.        s3.insert(i, s2);
    36.        if(IsCircleText(s3))
    37.        {
    38.            ++count;
    39.        }
    40.    }
    41.     cout << count << endl;
    42. }

    4. 连续最大和

    描述：一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

    输入描述：输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

    输出描述：所有连续子数组中和最大的值。

    4.1 思路

    1. 直接给出状态转移很简单的dp    f(i)=max{f(i−1)+nums[i],nums[i]}

    2. 说人话就是还是找那个dp表---->也就是以i结尾子数组的连续最大和,因为可能我第i位就比你前面总和的大所以用一个max函数，ret返回值的更新也是用的max函数。

    4.2 代码实现

    1. #include<iostream>
    2. #include<vector>
    3. #include<algorithm>
    4. using namespace std;
    5. int main()
    6. {
    7.     vector<int> v;
    8.     int n = 0;
    9.     cin >> n;
    10.     v.resize(n);
    11.     
    12.     for(int i = 0;i < v.size();++i)
    13.     {
    14.         cin >> v[i];
    15.     }
    16.     int sum = 0;
    17.     int ret = v[0];
    18.     
    19.     for(auto &e : v)
    20.     {   
    21.         sum = max(e,e + sum);
    22.         ret = max(ret,sum);
    23.     }
    24.     
    25.     cout << ret <<endl;
    26. }

    5. 合法括号序列判断

    描述

    给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。

    测试样例："(()())",6  返回：true

    测试样例："()a()()",7  返回：false

    测试样例："()(()()",7  返回：false

    5.1 思路

    1. 牛客这个能简单点只是一个圆括号 那就左括号入栈 右括号查看栈顶元素是左括号则是匹配成功弹栈。

    2. 如果是右括号或者其他则是不匹配成功直接返回false。

    5.2 代码实现

    1. class Parenthesis {
    2. public:
    3.     bool chkParenthesis(string A, int n) {
    4.         // write code here
    5.         stack<char> s;
    6.         
    7.         for(auto &e : A)
    8.         {
    9.             switch (e)
    10.             {
    11.                 case '(':
    12.                     s.push('(');
    13.                     break;
    14.                 case ')':
    15.                     if(s.empty() || s.top() != '(')
    16.                     {
    17.                         return false;
    18.                     }
    19.                     else
    20.                     {
    21.                         s.pop();
    22.                     }
    23.                     break;
    24.                 default:
    25.                     return false;
    26.             }
    27.         }
    28.         return true;
    29.     }
    30. };

    6. 有效的括号

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

    输入：s = "()"
    输出：true

    输入：s = "()[]{}"
    输出：true

    输入：s = "(]"
    输出：false

    输入：s = "([)]"
    输出：false

    输入：s = "{[]}"
    输出：true
     

    6.1 思路

    1. 这比刚刚就多了两个括号只需要我们来判断一下就好了

    2.无非就是三种 

                    1. 栈为空 也就是全是左括号

                    2. 是左括号 弹出栈

                    3. 全部匹配完毕 栈为空

    6.2 代码实现

    1. class Solution {
    2. public:
    3.     bool isValid(string s) {
    4.         stack<char> sta;
    5.         if(s.size() % 2 == 1)
    6.         {
    7.             return false;
    8.         }
    9.  
    10.         for(auto &e : s)
    11.         {
    12.             switch(e)
    13.             {
    14.                 case '(':
    15.                 sta.push(e);
    16.                 break;
    17.  
    18.                 case '{':
    19.                 sta.push(e);
    20.                 break;
    21.  
    22.                 case '[':
    23.                 sta.push(e);
    24.                 break;
    25.  
    26.                 case ')':
    27.                 if(sta.empty() || sta.top() != '(')
    28.                 {
    29.                     return false;
    30.                 }
    31.                 else
    32.                 {
    33.                     sta.pop();
    34.                 }
    35.                 break;
    36.  
    37.                 case '}':
    38.                 if(sta.empty() || sta.top() != '{')
    39.                 {
    40.                     return false;
    41.                 }
    42.                 else
    43.                 {
    44.                     sta.pop();
    45.                 }
    46.                 break;
    47.  
    48.                 case ']':
    49.                 if(sta.empty() || sta.top() != '[')
    50.                 {
    51.                     return false;
    52.                 }
    53.                 else
    54.                 {
    55.                     sta.pop();
    56.                 }
    57.                 break;
    58.                 default:
    59.                     return false;
    60.             }
    61.         }
    62.         return sta.empty();
    63.     }
    64. };
    1. class Solution {
    2. public:
    3.     bool isValid(string s) {
    4.         stack<char> stk;
    5.         if(s.empty()){
    6.             return true;
    7.         }
    8.         for(const auto &c :s){
    9.             if(c == '(' || c == '[' || c == '{'){
    10.                 stk.push(c);
    11.             }
    12.             else{
    13.  
    14.                 if(stk.empty())
    15.                 {
    16.                     return false;
    17.                 }
    18.                 else
    19.                 {
    20.                     if(c == ')')
    21.                     {
    22.                         if(stk.top()!='(')
    23.                         {
    24.                             return false;
    25.                         }
    26.                         else
    27.                         {
    28.                             stk.pop();
    29.                         }
    30.                     }
    31.                     else if(c == ']')
    32.                     {
    33.                         if(stk.top() != '[') 
    34.                         {
    35.                             return false;
    36.                         }
    37.                         else
    38.                         {
    39.                             stk.pop();
    40.                         }
    41.                     }
    42.                     else if(c=='}')
    43.                     {
    44.                         if(stk.top() != '{')
    45.                         {
    46.                             return false;
    47.                         }
    48.                         else
    49.                         {
    50.                             stk.pop();
    51.                         }
    52.                     }
    53.                 }
    54.             }
    55.         }
    56.         return stk.empty();
    57.     }
    58. };

    7. Fibonacci数列

    描述：Fibonacci数列是这样定义的：
    F[0] = 0
    F[1] = 1
    for each i ≥ 2: F[i] = F[i-1] + F[i-2]
    因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

    输入描述：输入为一个正整数N(1 ≤ N ≤ 1,000,000)

    输出描述：输出一个最小的步数变为Fibonacci数"

    7.1 思路 

    1.找到比N小且距离N最近的数，求出距离

    2.找到比N大且距离N最近的数，求出距离

    3.求最小

    7.2 代码实现

    1. #include <iostream>
    2. using namespace std;
    3. int main()
    4. {
    5.     int N, f, l = 0,r = 0,f0 = 0,f1 = 1;
    6.     cin >> N;
    7.     while(1){
    8.         f = f0 + f1;
    9.         f0 = f1;
    10.         f1 = f;
    11.         if(f < N)
    12.         {
    13.             l = N-f;
    14.         }   
    15.         else
    16.         {
    17.             r = f - N;
    18.             break;
    19.         }
    20.     }
    21.     cout << min(l,r) << endl;
    22.     return 0;
    23. }
  • 相关阅读:
    洛谷-P7910 [CSP-J 2021]-插入排序（详细讲解）
    两台Linux机器scp不输密码
    第十七章《MySQL数据库及SQL语言简介》第3节：数据库管理
    [山东科技大学OJ]1487 Problem B: 编写函数：字符串的查找字符 之二 (Append Code)
    Linux用户管理与文件权限
    白杨SEO：SEO转型系列之十一，传统SEO从业人员如何转行社群运营/营销？
    vue集成百度地图vue-baidu-map
    2023年上半年系统集成项目管理工程师什么时候报考?（附具体报名步骤）
    微信公众号模板消息api
    wordpress 安装主题显示要配置FTP的解决办法
  • 原文地址：https://blog.csdn.net/qq_50119037/article/details/124942947