30天刷题计划（三）

坚持鸭！！！ 

目录

1.统计回文

2.连续最大和

3.不要二

4.字符串转成整数

---

1.统计回文

统计回文_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/9d1559511b3849deaa71b576fa7009dc?tpId=85&&tqId=29842&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

①题目及示例：

 ②方法解析：

本题主要考察的是回文判断以及如何插入。这里我们可以用双指针来进行回文的判断，对于字符串的插入，我们可以用str.insert(i,str2)方法，即把str2这个字符串插入str字符串的i位置。

a.利用双指针来判断回文：

代码如下：

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.利用逆置，将插入后的字符串进行逆置，然后判断与插入前的字符串的内容是否是一致的，这里用equal()方法来进行操作。代码如下：

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是字符串的方法，而toString这里是将stringBuilder转换成字符串类型，才能用这个方法。
            if(str.toString().equals(str3.toString())){
                count++;
            }
    }
        System.out.println(count);
}
 }

2.连续最大和

连续最大和_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=85&&tqId=29858&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

①题目及示例：

 ②方法解析：

本题主要是采用动态规划问题。

我们在解题之前，要知道状态方程是什么？

状态方程式： max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] ) ；

其中，dp[i]的意思是从0开始加到i这个位置，arr[i]表示的是当前元素的下标。所以我们可以得到下面的代码：

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[i]=sc.nextInt();
        }
        int max=array[0];
        int max1=0;
        int sum=array[0];
        for(int i=1;i
            max1=(sum+array[i])>array[i]?(sum+array[i]):array[i];
            sum=max1;
            if(sum>=max){
                max=sum;//因为是用max来存放最终的最大值
            }
        }
        System.out.println(max);
    }
}

3.不要二

不要二_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/1183548cd48446b38da501e58d5944eb?tpId=85&&tqId=29840&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

①题目及示例：

 ②方法解析：

根据题目，我们可以很容易发现这是一个二维数组，我们将其算数平方根进行平方后可得

(x1-x2) * (x1-x2) + (y1-y2) * (y1-y2)=4；即

(x1-x2)^2+(y1-y2)^2=4,我们通过取临界值，我们可以知道

0+4=4；

4+0=4；

要是2+2=4的话就不满足整数的情况。所以我们得到了x1=x2和y1-y2=2或x1-x2=2和y1=y2;

这就说明当某处放了蛋糕后，它的这两个位置就不能放入蛋糕。

我们初始将整个数组的值置为0，然后每存放一个蛋糕用一个count计数，不能放蛋糕的地方置为1。

代码如下：

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;
    //把二维数组所有的值的大小置为0，当它能存放蛋糕时，count++;不能放蛋糕的位置就置为1
    int [][]tmp=new int[W][H];
    for(int i=0;i
        for(int j=0;j
            if(tmp[i][j]==0){
                count++;
         //当此处已经放了蛋糕，那么距离它的欧几里得距离就不能超过2
            //情况①：同i;j+2,判断j是否越界
                if(j+2
                    tmp[i][j+2]=1;
                }
                //情况②：同j,i+2;判断i是否越界
                if(i+2
                    tmp[i+2][j]=1;
                }
            }
        }
    }
    System.out.println(count);
}
}

4.字符串转成整数

把字符串转换成整数_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&&tqId=11202&rp=6&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

①题目及示例：

 ②方法解析：

题目中，我们主要考虑的是字符串首字符是+，还是-；因为对于加号而言，其值等于其本身，而对于减号而言其值等于其相反数，利用flg==1/flg==-1来对最后的值进行还原。但是我们需要知道的是，我们无法去掉它开头的数，只能够把那个位置设置为空位置，但最后计算的时候记得减去，因为对于符号而言，计算的是ASCLL值，就减去那个占位就行。因为对于toCharArray()方法而言，复制过去的只是一个副本。也是字符类型，所以这个时候-‘0’就相当于其本身。

代码如下：

public class Solution {
    public int StrToInt(String str) {
 char[]tmp=str.toCharArray();
        int flg=1;
        //当数组为空或者数组长度为0时，没有必要再向下，直接返回0
        if(tmp==null||tmp.length==0){
            return 0;
        }
        //如果第一个位置是+
        if(tmp[0]=='+'){
            flg=1;
            //同时将这个位置置为空
            tmp[0]='0';
        }
        //如果第一个位置是-
        if(tmp[0]=='-'){
            flg=-1;
            tmp[0]='0';
        }
        int sum=0;
        for(int i=0;i
         if(tmp[i]<'0'||tmp[i]>'9'){
            return 0;
         }else{
             sum=sum*10+tmp[i]-'0';//减去占位的0
         }
        }
        return sum*flg;
    }
}