1. 把字符串转换成整数
描述:将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为 0 或者字符串不是一个合法的数值则返回 0
注意：
①字符串中可能出现任意符号，出现除 +/- 以外符号时直接输出 0
②字符串中可能出现 +/- 且仅可能出现在字符串首位。
输入描述：输入一个字符串,包括数字字母符号,可以为空
返回值描述：如果是合法的数值表达则返回该数字，否则返回0
1.1 思路
1. 其实也就是一位位把数字取下来然后再 加之前上一个数字 * 10
2. 然后就是边界的判断，和正负号的处理
1.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;
}
};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 代码实现
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<vector<int>> 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;
}
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 代码实现
#include<iostream>
#include<string>
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;
}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 代码实现
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> 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 <<endl;
}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<char> 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<char> 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<char> 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 <iostream>
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;
}
