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数"
通过先找到距离N最近的两个Fibonacci数,这两个数分别取自距离N的最近的左边一个数L和右边一个数R,然后通过min(N - L, R - N)找到最小步
//给你一个N,让其变成斐波那契数,每一步可以把当前数字变为X-1,或者X+1,最少需要多少步?
#include<iostream>
using namespace std;
//求斐波那契数
int main()
{
int a = 0;
int b = 1;
int c = 1;
int n = 0;
// 0 1 1
cin>>n;
while(1)
{
c = a+b;
if(c > n)
{
break;
}
a = b;
b = c;
}
//循环出来,n位于c和b之间,只需要n距离c和b哪个近即可
int x = c-n > n-b?n-b:c-n;
cout<<x<<endl;
return 0;
}
给定一个字符串A和其长度n,请返回一个bool值代表它是否为一个合法的括号串(只能由括号组成)。
"(()())",6
返回:true
"()a()()",7
返回:false
"()(()()",7
返回:false
用栈结构实现,栈中存放左括号,当遇到右括号之后,检查栈中是否有左括号,如果有则出栈,如果没有,则说明不匹配。
class Parenthesis {
public:
bool chkParenthesis(string A, int n)
{
// write code here
//给定一个字符串A和其长度n,返回一个bool值说明他是否为一个合法的括号串(只能由括号组成)
//栈结构:遇到(进栈,遇到)如果有(则出栈,如果没有,则说明不匹配。出栈,右括号与最近的左括号匹配
stack<char> st;
for(int i = 0;i < n;i++)
{
if((A[i] != '(' && A[i] != ')') || A[0] == ')')
{
return false;
}
if(A[i] == '(')
{
//遇到左括号进栈
st.push(A[i]);
}
else
{
//遇到右括号时左括号出栈,如果没有了左括号则返回错误
if(st.empty())
{
return false;
}
st.pop();
}
}
if(st.empty())
{
return true;
}
else
{
return false;
}
}
};
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/attemptendeavor/article/details/123276523
内容来源于网络,如有侵权,请联系作者删除!