⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【斐波拉契数最小步数】和【合法括号序列判断】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️一个数到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

题目链接：一个数到Fibonacci数的最小步数

💡解题思路

基本思路：
构造+比较

解题思路：
根据斐波拉契数列公式： $f(i)=f(i-1)+f(i-2),i>2,f(1)=1,f(2)=1$通过循环构造斐波拉契数（有点动态规划的思想），在此同时，也比较目标数n与生成的斐波拉契数的大小关系，如果n两个相邻斐波拉契数中间，则n与两个斐波拉契数差值的绝对值最小的那个数就是n到斐波拉契数的最小步数。

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int a = 1;
        int b = 1;
        int fn = 2;
        while (n < a || n > b) {
            //如果n不在两个相邻斐波拉契数之间，就跳过，继续构造继续找
            fn = a + b;
            //更新a，b
            a = b;
            b = fn;
        }
        //出循环说明 a<n<b,最小步数就是n-a与b-n中较小的一个数
        int ret1 = n - a;
        int ret2 = b - n;
        int ans = ret1 < ret2 ? ret1 : ret2;
        System.out.println(ans);
    }
}

🌱总结

本题是斐波拉契数列的数列的应用，本质上还是构造斐波拉契数。
类似题：
剑指 Offer 10- I. 斐波那契数列
1137. 第 N 个泰波那契数
剑指 Offer 10- II. 青蛙跳台阶问题

⭐️合法括号序列判断⭐️

🔐题目详情

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

测试样例1：

"(()())",6
返回：true

测试样例2：

"()a()()",7
返回：false

测试样例3：

"()(()()",7
返回：false

题目链接：合法括号序列判断

💡解题思路

基本思路： 栈的运用

解题思路：
我们可以使用一个栈来模拟左右括号的匹配情况，遍历字符串，遇到(就将(入栈，遇到)就出栈，如果此时栈为空，说明左括号少了，直接返回false，还有一种情况就是遇到其他字符了，由于只能含有括号，直接返回false。

等待字符串中的字符都遍历完成了，如果栈为空，表示该字符串括号是匹配的，否则括号是不匹配的。

以栗子(()())为例，进行分析：

🔑源代码

import java.util.*;

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        char[] cs = A.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            //遇到( 就将(入栈 遇到) 就出栈 遇到其他 判断栈是否为空 为空返回false
            if (cs[i] == '(') {
                stack.push('(');
            } else if (cs[i] == ')') {
                //遇到) 栈为空 返回false
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            } else {
                return false;
            }
        }
        //最终栈为空 说明左右字符匹配
        return stack.isEmpty();
    }
}

🌱总结

对于括号匹配以及类似与括号匹配的问题可以使用数据结构栈进行模拟匹配。

类似题：20. 有效的括号