Java笔试编程题

谁践踏了优雅 2023-09-24 12:36 32阅读 0赞

> ####    [Fibonacci数列\_牛客题霸\_牛客网 (nowcoder.com)![icon-default.png_t_M85B][]https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking][Fibonacci_ _nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_18ecd0ecf5ef4fe9ba3f17f8d00d2d66_tpId_85_tqId_29846_rp_1_ru_activity_oj_qru_ta_2017test_question-ranking] ####
> 
> [合法括号序列判断\_牛客题霸\_牛客网 (nowcoder.com)![icon-default.png_t_M85B][]https://www.nowcoder.com/practice/d8acfa0619814b2d98f12c071aef20d4?tpId=8&&tqId=11039&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking][_nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_d8acfa0619814b2d98f12c071aef20d4_tpId_8_tqId_11039_rp_1_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]

### 描述 ###

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 数，这两个数分别取自距离 N 的最近的左边一个数 left 和右边一 个数right ，然后通过 min(n -left, right - n) 找到最小步数。

### **参考代码** ###

import java.util.Scanner;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextInt()) { // 注意 while 处理多个 case
               int n = in.nextInt();
               int right = 1;
               int left = 0;
               int ret = 0;
               while(n >= right) {
                   ret = right + left;
                   left = right;
                   right = ret;
               }
               int step = Math.min((right - n),(n-left));
                System.out.println(step);
            }
        }
    }

### 描述 ###

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

测试样例：

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

测试样例：

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

测试样例：

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

### **【解题思路】：**  ###

用栈结构实现，栈中存放左括号，当遇到右括号之后，检查栈中是否有左括号，如果有则出栈，如果没有，

则说明不匹配。

### **参考代码** ###

import java.util.*;
    
    public class Parenthesis {
        public boolean chkParenthesis(String A, int n) {
    
            if (n % 2 == 1) {
                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();
        }
    }

###  ###

[icon-default.png_t_M85B]: https://csdnimg.cn/release/blog_editor_html/release2.2.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M85B
[Fibonacci_ _nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_18ecd0ecf5ef4fe9ba3f17f8d00d2d66_tpId_85_tqId_29846_rp_1_ru_activity_oj_qru_ta_2017test_question-ranking]: https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[_nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_d8acfa0619814b2d98f12c071aef20d4_tpId_8_tqId_11039_rp_1_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]: https://www.nowcoder.com/practice/d8acfa0619814b2d98f12c071aef20d4?tpId=8&&tqId=11039&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking