30 day question brushing training (I)

Catalog

1. Team competition

2. Delete public characters

3. Inverted string

4. Sort subsequence

---

1. Team competition

Team competition _ Niu Ke's written test questions _ Cattle from Team competition ,【2017】 An examination of the cow model （ The three mode ） Programming problem set https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b?orderByHotValue=1&page=1&onlyReference=false

① Topics and examples ：

 ② Method resolution ：（ The algorithm involved in this problem is greedy algorithm ）

a. According to the meaning , You can't find the largest , Go back and find the second largest number . Then we get through relationship , The subscript of the second largest number should be array[array.length-(2*(i+1))]; among i Is the number of trips . So the code is as follows ：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
        int n=sc.nextInt();
        int []array= new int[3*n];
        for(int i=0;i<(3*n);i++){
            array[i]=sc.nextInt();
        }
        Arrays.sort(array);
            long sum=0;
;        for(int i=0;i<n;i++){
            sum+=array[array.length-(2*(i+1))];
        }
        System.out.println(sum);
    }
    }
}

A few noteworthy places ：

（1）hasNext（） Usage of ：

When there is no input , It will be blocked . Or block

（2） Right in the title a_i The numerical requirement of is <10^6, however int The approximate value range of is 10^6-10^7, So this place is still usable int To embellish .

b. Use to remove the smallest in each group , Then find the smaller of the remaining two values and add them . After sorting, we can directly remove the front n Number , Because before necessity n The number is the smallest , Then use the subscript separation to find the smaller value of the two numbers . The code is as follows ：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
        int n=sc.nextInt();
        int []array= new int[3*n];
        for(int i=0;i<(3*n);i++){
            array[i]=sc.nextInt();
        }
        Arrays.sort(array);
            long sum=0;
        // 1、 Before removal n A smaller number 
        // 2、 Take the rest  2*n  Combine numbers in pairs 
        // 3、 Take the smaller number in each group , Sum up 
;        for(int i=n;i<array.length;i+=2){
            sum+=array[i];
        }
        System.out.println(sum);
    }
    }
}

2. Delete public characters

Delete public characters _ Niuke Tiba _ Cattle from 【 Niuke Tiba 】 Collect high-frequency school recruitment pen interview questions from enterprises , With official explanation , Online Baidu Alibaba Tencent Netease and other Internet famous enterprises written interview simulation test practice , Discuss the classic test questions with Niu Ren , Improve your technical ability in an all-round way https://www.nowcoder.com/practice/f0db4c36573d459cae44ac90b90c6212?tpId=85&&tqId=29868&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

 ① Topics and examples ：

  ② Method resolution ：

Reverse thinking , For the output to be . Do not consider deleting , Because deleting means reordering , Instead, it increases the time complexity . We can record what we want to remove , Then words that do not involve records in the whole exist in another string . At this time, we use hash map To do this . Here are the methods involved .

a.map.put(key,value);

b.map.get(key); Used to get key The number of times it exists

c.map.containsKey(i); Boolean type , Used to determine whether the value exists

d.s.length() Method is used to find the length of a string

e.s.charAt（i）; Reduce string s, And return to its number i Characters

The difference between the following two methods , It depends on whether to splice strings directly or construct a StringBuffer object , Use it append Methods to solve . Obviously , The former costs less , It's also something we need to learn .

（1） The string splicing code is as follows ：

import java.util.*;
public class Main{
    public static void main(String[]args){
       Scanner sc=new Scanner(System.in);
        String m=sc.nextLine();
        String n=sc.nextLine();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<n.length();i++){
            if(map.get(n.charAt(i))==null){
            map.put(n.charAt(i),1);
            }else{
                map.put(n.charAt(i),map.get(n.charAt(i))+1);
            }
        }
        String sbu="";
        for(int i=0;i<m.length();i++){
            if(!map.containsKey(m.charAt(i))){
                sbu+=m.charAt(i);
            }
        }
        System.out.println(sbu);
    }
}

（2） utilize StringBuilder/StringBuffer To create object solutions ：

import java.util.*;
public class Main{
    public static void main(String[]args){
       Scanner sc=new Scanner(System.in);
        String m=sc.nextLine();
        String n=sc.nextLine();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<n.length();i++){
            if(map.get(n.charAt(i))==null){
            map.put(n.charAt(i),1);
            }else{
                map.put(n.charAt(i),map.get(n.charAt(i))+1);
            }
        }
        StringBuffer sbu=new StringBuffer();
        for(int i=0;i<m.length();i++){
            if(!map.containsKey(m.charAt(i))){
                sbu.append(m.charAt(i));
            }
        }
        System.out.println(sbu);
    }
}

3. Inverted string

Inverted string _ Niuke Tiba _ Cattle from 【 Niuke Tiba 】 Collect high-frequency school recruitment pen interview questions from enterprises , With official explanation , Online Baidu Alibaba Tencent Netease and other Internet famous enterprises written interview simulation test practice , Discuss the classic test questions with Niu Ren , Improve your technical ability in an all-round way https://www.nowcoder.com/practice/ee5de2e7c45a46a090c1ced2fdc62355?tpId=85&&tqId=29867&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

 ① Topics and examples ：

 ② Method resolution ：

We analyze the whole string , It's just that each word as a whole is inverted , In fact, there is no inversion inside each word , So we can have the following two ideas to complete this problem .

a. Use between words to “ ” Separated , So we use split function , Divide it into words to form an array , Then use string splicing to splice from back to front , After each word , add “ ”; Finally, in order to ensure preciseness , Remove the blanks before and after the sentence , Use trim Method to do .

The code is as follows ：

import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String ret=sc.nextLine();
    String []array=ret.split(" ");
    String str="";
    for(int i=0;i<array.length;i++){
        str+=array[array.length-1-i];
        str=str+" ";
    }
    // Remove the spaces before and after the sentence , Keep the space in the middle 
    String str1=str.toString().trim();
    System.out.println(str1);
     }
}

b. First, the whole is reversed , Then partially reverse . Use the double pointer method to solve this problem . Pay attention to two variables when local inversion i,j Change position of . Mainly used the following methods .

（1）s.toCharArray(); Return a copy of the data to the array you need , At the bottom is an array .

  The code is as follows ：

import java.util.Scanner;
import java.util.*;
public class Main{
      public static void reverse(char[]array,int left,int right){
            while(left<=right){
                char tmp=array[left];
                array[left]=array[right];
                array[right]=tmp;
                left++;
                right--;
 }
      }
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String ret=sc.nextLine();
    char[] ch=ret.toCharArray();
    reverse(ch,0,ch.length-1);
    int i=0;
    while(i<ch.length){
        int j=i;
        while(j<ch.length&&ch[j]!=' '){
            j++;
        }
        if(j<ch.length){
            reverse(ch,i,j-1);
            i=j+1;
            j++;   
        }else{
            reverse(ch,i,j-1);
            i=j;
        }
    }
    String str = new String(ch); 
    System.out.println(str);
    }
}

4. Sort subsequence

Sort subsequence _ Niu Ke's written test questions _ Cattle from Sort subsequence ,【2017】 An examination of the cow model （ The three mode ） Programming problem set https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471?orderByHotValue=1&page=1&onlyReference=false

① Topics and examples ：

 ② Method resolution ：

This topic mainly lies in the understanding of the meaning of the topic . among , What does non increasing and non decreasing represent respectively . Then there is flexible use if and while In the cycle , It is worth noting that , When a condition is not met , Whether it is not satisfied until it is finished in another condition , This is a key point .

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 []array=new int[n+1];
            // Assign values to arrays 
            for(int i=0;i<n;i++){
                array[i]=sc.nextInt();
            }
            int i=0;// use i To move 
            int count=0;// use count To count 
            while(i<n){
                // The decreasing 
                if(array[i]<array[i+1]){
                    while(i<n&&array[i]<=array[i+1]){
                        i++;// When a i When not satisfied , First, jump out of the current cycle , Then execute the if
                        // After the sentence in, make a subsequent judgment 
                    }
                    count++;
                        i++;
                }// The same situation will not change the results before and after 
                else if(array[i]==array[i+1]){
                    i++;
                }// Non-increasing 
                else if(array[i]>array[i+1]){
                    while(i<n&&array[i]>=array[i+1]){
                        i++;
                            
                    }
                    count++;
                    i++;
                }
            }
            System.out.println(count);
        }
}

insist ！！！！