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