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

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

注意：

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

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

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

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

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

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

class Solution {
public:
    int StrToInt(string str) {
        if(str.empty())
        {
            return 0;
        }
        int falg = 1;
        int ret = 0;
        if(str[0] == '-')
        {
            falg = -1;
            str[0] = '0';
        }
        else if(str[0] == '+')
        {
            falg = 1;
            str[0] = '0';
        }
        
        for(size_t i = 0;i < str.size();i++)
        {
            if(str[i] < '0'|| str[i] > '9')
            {
                return 0;
            }
            ret = ret * 10 + str[i] - '0';
        }
        return falg * ret;
    }
};

描述：二货小易有一个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)

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

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

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

#include
#include
using namespace std;
int main()
{
    vector> vv;
    int w = 0;
    int h = 0;
    int ret = 0;
    cin >> w >> h;
    vv.resize(w);
    
    for(auto &e : vv)
    {
        e.resize(h,1);
    }    
    
    for(int i = 0;i < w;i++)
    {
        for(int j = 0;j < h;j++)
        {
            if(vv[i][j] == 1)
            {
                if((i + 2) < w)
                {
                    vv[i + 2][j] = 0;
                }
                if((j + 2) < h)
                {
                    vv[i][j + 2] = 0;
                }
                ret++;
            }
        }
    }
    cout << ret << endl;
}

描述；“回文串”是一个正读和反读都一样的字符串，比如“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之后构成一个回文串的方法数

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

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

#include
#include
using namespace std;
bool IsCircleText(const string& s)
{
    int left = 0;
    int right = s.size() - 1;
    
    while(left < right)
    {
        if(s[left] == s[right])
        {
            ++left;
            --right;
        }
        else{
            return false;
        }  
    }
    return true;
}

int main()
{
    string s1;
    string s2;
    size_t count = 0;
    
    getline(cin,s1);
    getline(cin,s2);
    
   for(size_t i = 0;i <= s1.size();i++)
   {
       string s3 = s1;
       s3.insert(i, s2);
       if(IsCircleText(s3))
       {
           ++count;
       }
   }
    cout << count << endl;
}

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

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

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

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

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

#include
#include
#include
using namespace std;
int main()
{
    vector v;
    int n = 0;
    cin >> n;
    v.resize(n);
    
    for(int i = 0;i < v.size();++i)
    {
        cin >> v[i];
    }
    int sum = 0;
    int ret = v[0];
    
    for(auto &e : v)
    {   
        sum = max(e,e + sum);
        ret = max(ret,sum);
    }
    
    cout << ret < 
5. 合法括号序列判断 
描述
 
给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。
 
测试样例："(()())",6  返回：true
 
测试样例："()a()()",7  返回：false
 
测试样例："()(()()",7  返回：false
 
5.1 思路 
1. 牛客这个能简单点只是一个圆括号 那就左括号入栈 右括号查看栈顶元素是左括号则是匹配成功弹栈。
 
2. 如果是右括号或者其他则是不匹配成功直接返回false。
 
5.2 代码实现 
class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        // write code here
        stack s;
        
        for(auto &e : A)
        {
            switch (e)
            {
                case '(':
                    s.push('(');
                    break;
                case ')':
                    if(s.empty() || s.top() != '(')
                    {
                        return false;
                    }
                    else
                    {
                        s.pop();
                    }
                    break;
                default:
                    return false;
            }
        }
        return true;
    }
};
 
6. 有效的括号 
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
 
输入：s = "()"
 输出：true
 
输入：s = "()[]{}"
 输出：true
 
输入：s = "(]"
 输出：false
 
输入：s = "([)]"
 输出：false
 
输入：s = "{[]}"
 输出：true
  
 
6.1 思路 
1. 这比刚刚就多了两个括号只需要我们来判断一下就好了
 
2.无非就是三种 
 
                1. 栈为空 也就是全是左括号
 
                2. 是左括号 弹出栈
 
                3. 全部匹配完毕 栈为空
 
6.2 代码实现 
class Solution {
public:
    bool isValid(string s) {
        stack sta;
        if(s.size() % 2 == 1)
        {
            return false;
        }

        for(auto &e : s)
        {
            switch(e)
            {
                case '(':
                sta.push(e);
                break;

                case '{':
                sta.push(e);
                break;

                case '[':
                sta.push(e);
                break;

                case ')':
                if(sta.empty() || sta.top() != '(')
                {
                    return false;
                }
                else
                {
                    sta.pop();
                }
                break;

                case '}':
                if(sta.empty() || sta.top() != '{')
                {
                    return false;
                }
                else
                {
                    sta.pop();
                }
                break;

                case ']':
                if(sta.empty() || sta.top() != '[')
                {
                    return false;
                }
                else
                {
                    sta.pop();
                }
                break;
                default:
                    return false;
            }
        }
        return sta.empty();
    }
};
 
class Solution {
public:
    bool isValid(string s) {
        stack stk;
        if(s.empty()){
            return true;
        }
        for(const auto &c :s){
            if(c == '(' || c == '[' || c == '{'){
                stk.push(c);
            }
            else{

                if(stk.empty())
                {
                    return false;
                }
                else
                {
                    if(c == ')')
                    {
                        if(stk.top()!='(')
                        {
                            return false;
                        }
                        else
                        {
                            stk.pop();
                        }
                    }
                    else if(c == ']')
                    {
                        if(stk.top() != '[') 
                        {
                            return false;
                        }
                        else
                        {
                            stk.pop();
                        }
                    }
                    else if(c=='}')
                    {
                        if(stk.top() != '{')
                        {
                            return false;
                        }
                        else
                        {
                            stk.pop();
                        }
                    }
                }
            }
        }
        return stk.empty();
    }
};
 
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 代码实现 
#include 
using namespace std;
int main()
{
    int N, f, l = 0,r = 0,f0 = 0,f1 = 1;
    cin >> N;
    while(1){
        f = f0 + f1;
        f0 = f1;
        f1 = f;
        if(f < N)
        {
            l = N-f;
        }   
        else
        {
            r = f - N;
            break;
        }
    }
    cout << min(l,r) << endl;
    return 0;
}