30 day question brushing plan (III)

Insist on Duck ！！！ 

Catalog

1. Statistical palindrome

2. Continuous maximum sum

3. No two

4. String to integer

---

1. Statistical palindrome

Statistical palindrome _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/9d1559511b3849deaa71b576fa7009dc?tpId=85&&tqId=29842&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

① Topics and examples ：

 ② Method resolution ：

This question mainly focuses on palindrome judgment and how to insert . Here we can use double pointers to judge palindromes , For string insertion , We can use str.insert(i,str2) Method , Namely the str2 This string is inserted str A string of i Location .

a. Use double pointers to judge palindromes ：

The code is as follows ：

import java.util.*;
 public class Main {
    public static boolean huiwen(StringBuffer str){
        int left=0;
        int right=str.length()-1;
        while(left<=right){
            if(str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        int count=0;
        int i=0;
        for(i=0;i<=str1.length();i++){
            StringBuffer str = new StringBuffer(str1);
            str.insert(i, str2);
            if(huiwen(str)){
                count++;
            }
        }
        System.out.println(count);
    }
}

b. Using inversion , Invert the inserted string , Then judge whether the content of the string is consistent with that before insertion , Here we use equal() Method to operate . The code is as follows ：

import java.util.*;
 public class Main {
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        int count=0;
        int i=0;
        for(i=0;i<=str1.length();i++){
            StringBuffer str = new StringBuffer(str1);
            str.insert(i, str2);
            StringBuffer tmp=new StringBuffer(str);
            StringBuffer str3=tmp.reverse();
//equals It's a string method , and toString Here is the general stringBuilder Converts to string type , To use this method .
            if(str.toString().equals(str3.toString())){
                count++;
            }
    }
        System.out.println(count);
}
 }

2. Continuous maximum sum

Continuous maximum sum _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=85&&tqId=29858&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

① Topics and examples ：

 ② Method resolution ：

This problem is mainly a dynamic programming problem .

Before we solve the problem , You need to know what the equation of state is ？

Equation of state ： max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] ) ;

among ,dp[i] I mean from 0 Start adding i This position ,arr[i] Indicates the subscript of the current element . So we can get the following code ：

import java.util.*;
 public class Main {
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        int []array=new int[num];
        for(int i=0;i<array.length;i++){
            array[i]=sc.nextInt();
        }
        int max=array[0];
        int max1=0;
        int sum=array[0];
        for(int i=1;i<array.length;i++){
            max1=(sum+array[i])>array[i]?(sum+array[i]):array[i];
            sum=max1;
            if(sum>=max){
                max=sum;// Because it's using max To store the final maximum 
            }
        }
        System.out.println(max);
    }
}

3. No two

No two _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/1183548cd48446b38da501e58d5944eb?tpId=85&&tqId=29840&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

① Topics and examples ：

 ② Method resolution ：

According to the title , We can easily find that this is a two-dimensional array , We square the square root of the arithmetic to get

(x1-x2) * (x1-x2) + (y1-y2) * (y1-y2)=4; namely

(x1-x2)^2+(y1-y2)^2=4, We take the critical value , We can know

0+4=4;

4+0=4;

If 2+2=4 Then it does not satisfy the integer situation . So we get x1=x2 and y1-y2=2 or x1-x2=2 and y1=y2;

That means when there's a cake somewhere , It can't put cake in these two positions .

We initially set the value of the entire array to 0, Then use one for each cake count Count , The place where you can't put the cake is 1.

The code is as follows ：

import java.util.*;
public class Main{
public static void main(String[]args){
 Scanner sc=new Scanner(System.in);
    int W=sc.nextInt();
    int H=sc.nextInt();
    int count=0;
    // Set the size of all values of the two-dimensional array to 0, When it can store cakes ,count++; If you can't put the cake, set it to 1
    int [][]tmp=new int[W][H];
    for(int i=0;i<W;i++){
        for(int j=0;j<H;j++){
            if(tmp[i][j]==0){
                count++;
         // When the cake has been put here , Then the Euclidean distance from it cannot exceed 2
            // situation ①： Same as i;j+2, Judge j Is it across the border? 
                if(j+2<H){
                    tmp[i][j+2]=1;
                }
                // situation ②： Same as j,i+2; Judge i Is it across the border? 
                if(i+2<W){
                    tmp[i+2][j]=1;
                }
            }
        }
    }
    System.out.println(count);
}
}

4. String to integer

Convert a string to an integer _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&&tqId=11202&rp=6&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

① Topics and examples ：

 ② Method resolution ：

Title , We mainly consider that the first character of the string is +, still -; Because for the plus sign , Its value is equal to itself , For the minus sign, its value is equal to its opposite number , utilize flg==1/flg==-1 To restore the last value . But what we need to know is , We can't get rid of the number at the beginning of it , You can only set that position to an empty position , But remember to subtract when you finally calculate , Because for symbols , The calculation is ASCLL value , Just subtract that placeholder . Because for toCharArray() In terms of method , Copying the past is just a copy . It is also a character type , So at this point -‘0’ It is equivalent to itself .

The code is as follows ：

public class Solution {
    public int StrToInt(String str) {
 char[]tmp=str.toCharArray();
        int flg=1;
        // When the array is empty or the array length is 0 when , There's no need to go down , Go straight back to 0
        if(tmp==null||tmp.length==0){
            return 0;
        }
        // If the first position is +
        if(tmp[0]=='+'){
            flg=1;
            // At the same time, set this position to empty 
            tmp[0]='0';
        }
        // If the first position is -
        if(tmp[0]=='-'){
            flg=-1;
            tmp[0]='0';
        }
        int sum=0;
        for(int i=0;i<tmp.length;i++){
         if(tmp[i]<'0'||tmp[i]>'9'){
            return 0;
         }else{
             sum=sum*10+tmp[i]-'0';// Subtract the placeholder 0
         }
        }
        return sum*flg;
    }
}