30 day question brushing plan (IV)

insist ！！！

Catalog

1.Fibonacci The sequence

2. Legal bracket sequence judgment

3. Two sort methods

4. Find the least common multiple

---

1.Fibonacci The sequence

Fibonacci The sequence _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

① Topics and examples ：

 ② Method resolution ：

The meaning of this question is to give us a number , Let's find the minimum value that its minimum number of steps becomes Fibonacci number . And we know that it is nothing more than one of the numbers greater than it or less than it .

We don't use recursive method here , Instead, we use the relationship between three adjacent numbers , When n After jumping out of the loop , It means that at this time f2 It just surpassed n Fibonacci number of itself , And then f1 It is f2 The previous Fibonacci number of , therefore , We can know at this time f1<N<f2. So at this time, we just need to compare the difference , Select a number with a small difference . The code is as follows ：

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. Legal bracket sequence judgment

Legal bracket sequence judgment _ Niuke Tiba _ Cattle from (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

① Topics and examples ：

 ② Method resolution ：

Judge whether the brackets are legal . Consider the following . First of all , Must be all parentheses , Letters and other non parentheses cannot appear . And if it's legal , Then the left and right parentheses must appear in pairs , Then the number must be equal . We use two ways to find .

a. Solve directly ：

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. Ask through the stack ： Put the left bracket on the stack , When you encounter a close bracket , Determine whether the stack is empty , Not empty stack , Then one , Until the stack is empty . Finally, you only need to judge whether the next stack is empty , Empty indicates that it is over ,return true; conversely .

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++){
            // when '(' Stack when 
            if(A.charAt(i)=='('){
                stack.push(A.charAt(i));
                // when ')' Determine whether the stack is empty , If the stack is empty , It indicates that the quantity does not match , That is, it can't match 
                //  If the stack is not empty , Determine whether the top element of the stack is '('
            }else if(A.charAt(i)==')'){
                if(stack.isEmpty()){
                    return false;
                }else //if(stack.peek()=='('), Don't judge this sentence , Because the original stack is the left parenthesis , As long as the stack is not empty , Then the top element of the stack must be '('
                     {
                    stack.pop();
                }
                // It means that the input is neither the left parenthesis , It's not a right parenthesis 
            }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. Two sort methods

Two sort methods _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/839f681bf36c486fbcc5fcb977ffe432?tpId=85&&tqId=29844&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

① Topics and examples ：

 ② Method resolution ：

This question mainly examines the comparison of strings , One is to pass. compareTo To compare dictionary forms , The second is to compare by the length of the string . It should be noted that the input string is put into the same string array , Then compare the values according to the subscript value . At the same time, explain the meaning of several methods in the code .

（1）BufferedReader It is a packaging class designed to provide reading efficiency , It can wrap character streams . Text can be read from the character input stream , Buffer individual characters , So as to realize the character 、 Efficient reading of arrays and rows . This is read directly when inputting byte stream .

（2)readLine() Method , Pay attention to throwing exceptions when using

（3）Integer.parseInt () Method ： Put the string s Parse into signed int Basic types .

  meanwhile ,Integer.valueOf(s)： Put the string s It can be interpreted as Integer object type .

Here is a packing process .

You can refer to the blogger's blog ：(3 Bar message ) Integer.parseInt(s) And Integer.valueOf(s) The difference between _HD243608836 The blog of -CSDN Blog

The code is as follows ：

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. Find the least common multiple

Find the least common multiple _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3?tpId=37&&tqId=21331&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

① Topics and examples ：

 ② Method resolution ：

We need to know first , If the least common multiple is required , You can use the product of these two numbers / The greatest common divisor of these two numbers .

The greatest common divisor of two numbers can be achieved by rolling and dividing . The core of the rolling division method is to divide the divisor by the remainder , Until the remainder is 0 The divisor of time is the greatest common divisor . therefore , The code is as follows ：

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;// The greatest common factor 
        // The least common multiple is required , Just divide your grades by the greatest common divisor 
        // The greatest common divisor can be obtained by rolling and dividing 
        if(a<b){
            int tmp=a;
            a=b;
            b=tmp;
        }
        while(a%b!=0){// Use the rolling division method to find the greatest common factor 
            int tmp=b;
             b=a%b;
             a=tmp;
        }
        System.out.println(times/b);
    }
}

besides , We can find the greatest common factor recursively , The code is as follows ：

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

It's a little difficult here , You need to pay attention .