【笔试强化】Day 7

文章目录

一、单选
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
二、编程
- 1. 合法括号序列判断
- - 解法1：（统计数量）
  - - 代码：
  - 解法2：（栈）
  - - 代码：
- 2. Fibonacci数列
- - 解法：
  - 代码：

一、单选

1.

在这里插入图片描述

正确答案：D

2.

在这里插入图片描述

正确答案：B

3.

在这里插入图片描述

正确答案：D

4.

在这里插入图片描述

正确答案：C

5.

在这里插入图片描述

正确答案：A

6.

在这里插入图片描述

正确答案：B

7.

在这里插入图片描述

正确答案：D

8.

在这里插入图片描述

正确答案：D

9.

在这里插入图片描述

正确答案：B

10.

在这里插入图片描述

正确答案：D

二、编程

1. 合法括号序列判断

在这里插入图片描述
原题链接

解法1：（统计数量）

这里先用一种很简单的做法
统计左括号的数量，再统计右括号的数量
对比，如果两个的数量相同，就是合法括号

代码：

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        char[] ch = A.toCharArray();
        int m = ch.length;
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < m; i++) {
            if(ch[i] == '(') {
                count1++;
            }
            if(ch[i] == ')') {
                count2++;
            }
        }
        if(count1 == count2) {
            return true;
        }else {
            return false;
        }
    }
}

在这里插入图片描述

解法2：（栈）

栈中存放左括号，当遇到右括号之后，检查栈中是否有左括号，如果有则出栈，如果没有，则说明不匹配

代码：

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        if (n % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        char[] ch = A.toCharArray();
        for (int i = 0; i < A.length(); i++) {
            if (ch[i] == '(') {
                stack.push(ch[i]);
            }else if (ch[i] == ')') {
                if (stack.isEmpty()) {
                    return false;
                }else if (stack.peek() == '('){
                    stack.pop();
                }
            }else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

在这里插入图片描述

2. Fibonacci数列

在这里插入图片描述
原题链接

解法：

先找到距离N最近的两个Fibonacci数
这两个数分别取自距离N的最近的左边一个数L和右边一个数R
然后通过min(N - L, R - N)找到最小步数

代码：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int f1 = 0;
        int f2 = 1;

        while(n > f2) {
            int f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }

       System.out.println(Math.min((n - f1),(f2 - n))); 
    }
}