【java】合法括号序列判断与Fibonacci数列

让我们来探讨一下如何处理这个编程问题：判断一个括号字符串是否合法以及将给定数转换为最近的斐波那契数的最小步骤。这些问题看似简单，但涉及到算法的效率和正确性，需要仔细思考。

首先，看看合法括号判断的问题。合法括号字符串必须满足两个条件：每个左括号都有一个对应的右括号，而且正确的闭合顺序。这里我用了栈的方法。当遇到左括号就入栈，遇到右括号就出栈，这样最后如果栈为空，说明是合法的。这种方法直观且高效，适合处理这种结构性的问题。

接下来是斐波那契数转换问题。斐波那契数列的特性使得我们可以通过生成足够多的斐波那契数，找到离目标数最近的一个。具体来说，生成直到斐波那契数超过目标值，然后计算前一个和后一个斐波那契数到目标数的距离，取较小的作为结果。这种方法简单直接，避免了不必要的计算，效率较高。

整体而言，这些问题都强调了正确性和效率的平衡，在处理算法题时，不仅要考虑解决问题的方法，还要关注实现的简洁性和高效性。

目录

🔥编程题

1.合法括号序列判断

2.Fibonacci数列

🔥编程题

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<=f2int min = Math.min(n-f1, f2-n);System.out.println(min);}
}