斐波拉契数最小步数与合法括号序列判断

2022 年 7 月 12 日
本文字数：1534 字
阅读完需：约 5 分钟

⭐️一个数到 Fibonacci 数的最小步数⭐️

🔐题目详情

描述

Fibonacci 数列是这样定义的：F[0] = 0F[1] = 1for 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

输入：

复制代码

输出：

复制代码

题目链接：一个数到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. 有效的括号

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/7a7d4dd9f480d7a7d8661c188】。文章转载请联系作者。

未见花闻

关注

坚持+努力=诗+远方 2021.11.15 加入

一位热爱技术热爱分享的大学生！

发布

暂无评论

创作场景

斐波拉契数最小步数与合法括号序列判断

⭐️一个数到 Fibonacci 数的最小步数⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结

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

🔐题目详情

💡解题思路

🔑源代码

🌱总结

未见花闻

评论