刷题_7：Fibonacci数列 and 合法括号序列判断

淩亂°似流年 2023-09-28 23:42 10阅读 0赞

### 一.Fibonacci数列 ###

**题目链接：**

> [Fibonacci数列][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**

**个人总结：**

> **找到比数n小的Fibonacci数a和比数n大的Fibonacci数b，然后返回相减的较小值。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            System.out.println(minChange(n));
        }
    
        public static int minChange(int n) {
        
            int a = 0;
            int b = 1;
            int c = 0;
            while (b < n) {
        
                c = a + b;
                a = b;
                b = c;
            }
            return Math.min(n - a, b - n);
        }
    }

--------------------

### 二.合法括号序列判断 ###

**题目链接：**

> [合法括号序列判断][Link 1]

**题目描述：**

> **给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。**

**输入描述：**

> **无**

**输出描述：**

> **无**

**示例1：**

> **输入：  
> “(()())”,6  
> 输出：  
> true**

**示例2：**

> **输入：  
> “()a()()”,7  
> 输出：  
> false**

**示例3：**

> **输入：  
> “()(()()”,7  
> 输出：  
> false**

**个人总结：**

> **简单模拟，可以不采用栈，使用leftCount统计左括号数就行了，可以降低空间复杂度。**

**代码实现：**

import java.util.*;
    
    public class Parenthesis {
        
        public boolean chkParenthesis(String A, int n) {
        
            // write code here
            if (n <= 1) {
        
                return false;
            }
            int leftCount = 0;
            for (int i = 0; i < n; i++) {
        
                char c = A.charAt(i);
                if (c == '(') {
        
                    leftCount++;
                } else if (c == ')' && leftCount != 0) {
        
                    leftCount--;
                } else {
        
                    return false;
                }
            }
            return leftCount == 0;
        }
    }

[Fibonacci]: https://www.nowcoder.com/questionTerminal/18ecd0ecf5ef4fe9ba3f17f8d00d2d66
[Link 1]: https://www.nowcoder.com/questionTerminal/d8acfa0619814b2d98f12c071aef20d4