Java笔试编程题

Fibonacci数列_牛客题霸_牛客网 (nowcoder.com)

https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

合法括号序列判断_牛客题霸_牛客网 (nowcoder.com)

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();
    }
}