目录
🔥编程题
1.合法括号序列判断
2.Fibonacci数列
文章来源地址https://www.toymoban.com/news/detail-422680.html
🔥编程题
1.合法括号序列判断
链接：合法括号序列判断__牛客网 (nowcoder.com)
给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。
测试样例：
"(()())",6
返回：true
测试样例：
"()a()()",7
返回：false
测试样例：
"()(()()",7
返回：false
🔎思路分析：
第一种：
1️⃣如果是奇数，直接返回 false
2️⃣如果是偶数，遇到左括号count++，如果遇到右括号count--
如果第一个是右括号且右括号多于左括号（即 count <0），则不符合，返回 false
如果存在处括号外其他字符，返回 false
3️⃣如果左右括号相等且符合先左后右即（count=0），则返回 true
public boolean chkParenthesis(String A, int n) {
int count = 0;
if (n % 2 == 1) {//奇数字符串
return false;
}
for (int i = 0; i < n; i++) {
char ch = A.charAt(i);
if (ch == '(') {
count++;
} else if (ch == ')') {
count--;
if (count < 0) {
return false;
}
} else {
return false;
}
}
if (count == 0) {
return true;
} else {
return false;
}
}第二种：使用栈
1️⃣如果字符串长度不为偶数的时候，那么直接返回 false
2️⃣当长度为偶数，遍历字符串，遇到左括号入栈，遇到右括号，看栈顶元素是否为左括号；如果是，左括号出栈，继续遍历；当字符串遍历结束，如果栈为空，那么字符串就是一个合法的括号串，返回true
3️⃣如果遍历到一个非括号字符，直接返回 false
public boolean chkParenthesis(String A, int n) {
if (n % 2 != 0) {//奇数
return false;
}
Stack<Character> stack = new Stack();
for (char ch : A.toCharArray()) {//遍历字符串
if (ch == '(') {
stack.push(ch);//入栈
} else if (ch == ')') {
//右括号先于左括号，不合法
if (stack.isEmpty()) {//栈为空
return false;
} else if (stack.peek() == '(') {//栈顶元素
stack.pop();//出栈
}
} else {//其他不合法
return false;
}
}
return stack.isEmpty();
}2.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数"
示例1
输入：15
输出：2
🔎分析思路：
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int f1 = 0;
int f2 = 1;
//斐波那契数
while (f2 < n) {
int f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
//循环结束 f1<n<=f2
int min = Math.min(n-f1, f2-n);
System.out.println(min);
}
}文章来源：https://www.toymoban.com/news/detail-422680.html
到了这里，关于【java】合法括号序列判断与Fibonacci数列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
