30天刷题计划（四）

坚持！！！

目录

1.Fibonacci数列

2.合法括号序列判断

3.两种排序方法

4.求最小公倍数

---

1.Fibonacci数列

Fibonacci数列_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

①题目及示例：

 ②方法解析：

这个题的意思就是说给我们一个数，我们来找到它最小步数变为斐波那契数的这个最小值。而我们知道无非是大于其或者小于其的数中的一个。

我们这里不采用递归的方法，而是采用相邻三个数间存在的关系，当n跳出循环后，就说明此时f2刚好是刚刚超过了n本身的斐波那契数，而此时f1正是f2的前一个斐波那契数，因此，我们就可以知道此时f1<N<f2.所以这个时候我们只需要比较差值，选取差值较小的数即可。代码如下：

import java.util.*;
public class Main {
   public static void main(String[]args){
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int f1=0;
       int f2=1;
       while(n>f2){
           int f3=f1+f2;
            f1=f2;
            f2=f3;
       }
       int min=Math.min(n-f1,f2-n);
       System.out.println(min);   
}
}

2.合法括号序列判断

合法括号序列判断_牛客题霸_牛客网 (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

①题目及示例：

 ②方法解析：

判断括号是否合法。要考虑以下几点。第一，必须全是括号，不能出现字母等其他非括号。且如果合法，那么必然左右括号成对出现，则数目必然相等。我们采用两种方式来求。

a.直接求解：

import java.util.*;
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        int count1=0;
        int count2=0;
        for(int i=0;i<A.length();i++){
            if(A.charAt(i)!='('&&A.charAt(i)!=')'){
                return false;
            }
            if(A.charAt(i)=='('){
                count1++;
            }
        if(A.charAt(i)==')'){
                count2++;
            }
    }
        if(count1==count2){
            return true;
        }
        return false;
}
}

b.通过栈来求：将左括号入栈，当遇到右括号时，判断一下是否为空栈，不为空栈，则出一个，一直到栈为空为止。最后只需要判断下栈是否为空，为空表示已经出完了，return true；反之。

import java.util.*;
public class Main {
    public  static boolean chkParenthesis(String A, int n) {
        // write code here
        if(n%2!=0){ return false; }
        Stack<Character>stack=new Stack<>();
        for(int i=0;i<n;i++){
            //当是'('时就入栈
            if(A.charAt(i)=='('){
                stack.push(A.charAt(i));
                //当是')'时就判断栈是否为空，若是栈为空，则表明数量不匹配，即匹配不了
                // 栈不为空的话，判断栈顶元素是否是'('
            }else if(A.charAt(i)==')'){
                if(stack.isEmpty()){
                    return false;
                }else //if(stack.peek()=='(')，不用判断这一句，因为本来入栈的都是左括号，只要栈不为空，那么栈顶元素必然为'('
                     {
                    stack.pop();
                }
                //则表示输入的既不是左括号，也不是右括号
            }else{
                return false;
            }
        }
        return stack.isEmpty();
    }
     public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
        String A=sc.nextLine();
        int n=sc.nextInt();
        System.out.println(chkParenthesis(A, n));
    }
}

3.两种排序方法

两种排序方法_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/839f681bf36c486fbcc5fcb977ffe432?tpId=85&&tqId=29844&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

①题目及示例：

 ②方法解析：

本题主要考查字符串的比较，一是通过compareTo来进行字典形式的比较，二是通过字符串的长度来比较。需要注意的是将输入的字符串放入的是同一个字符串数组，然后根据下标值来对各个值进行比较。同时说明一下代码中的几个方法的含义。

（1）BufferedReader是为了提供读的效率而设计的一个包装类，它可以包装字符流。可以从字符输入流中读取文本，缓冲各个字符，从而实现字符、数组和行的高效读取。这里直接是在输入字节流的时候读取的。

（2)readLine()方法，注意使用的时候要抛出异常

（3）Integer.parseInt ()方法：把字符串s解析成有符号的int基本类型。

 同时，Integer.valueOf(s)：把字符串s解析成Integer对象类型。

这里是一个装箱过程。

可以参考一下这位博主的博客：(3条消息) Integer.parseInt(s)与Integer.valueOf(s)的区别_HD243608836的博客-CSDN博客

代码如下：

import java.util.*;
import java.io.*;
public class Main {
    public static boolean lexicographically(String[] str){
        for(int i=0;i<str.length-1;i++){
            if(str[i].compareTo(str[i+1])>0){
                return false;
            }
        }return true;
    }
    public static boolean lengths(String []str){
        for(int i=0;i<str.length-1;i++){
            if(str[i].length()>str[i+1].length()){
                return false;
            }
        }return true;
    }
 public static void main(String[]args)throws IOException{
  BufferedReader re=new BufferedReader(new InputStreamReader(System.in)); 
     int n=Integer.parseInt(re.readLine()); 
     String[] str=new String[n]; 
     for(int i=0;i<n;i++){
         str[i]=re.readLine();
     }
     if(lengths(str)&&(lexicographically(str))){
         System.out.println("both");
     }else if(lengths(str)){
        System.out.println("lengths");
     }else if(lexicographically(str)){
         System.out.println("lexicographically");
     }else{
         System.out.println("none");
     }
 }   
        }

4.求最小公倍数

求最小公倍数_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3?tpId=37&&tqId=21331&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

①题目及示例：

 ②方法解析：

我们首先需要知道，要求最小公倍数的话，可以用这两个数的乘积/这两个数的最大公约数。

而两个数的最大公约数可以通过辗转相除法来实现。辗转相除法的核心是用除数除以余数，直到余数为0时的除数就是最大公约数。所以，代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int times=a*b;
        int max=0;//最大公因数
        //要求最小公倍数，就用成绩除以最大公约数
        //最大公约数又可以用辗转相除法来求得
        if(a<b){
            int tmp=a;
            a=b;
            b=tmp;
        }
        while(a%b!=0){//利用辗转相除法来求最大公因数
            int tmp=b;
             b=a%b;
             a=tmp;
        }
        System.out.println(times/b);
    }
}

除此之外，我们可以通过递归的方式求最大公因数，代码如下：

import java.util.*;
 class Main {
     public static int digui(int x,int y){
         if(y==0){
             return x;
         }else {
             return digui(y,x%y);
         }
     }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
       int max=digui(a,b);
        System.out.println(max);
    }
}

这里有点难饶，需要好好注意一下。