【nowcoder】统计回文、连续最大和

统计回文

统计回文

判断回文：

1. 写一个判断是否回文的函数，每次调用函数判断
2. 将字符串逆置，如果逆置完和之前是一样的，就是回文的

思路：

1. 找到合适的位置进行插入

2. 判断回文

不要在str1里插入，这样会使str1发生变化，再重新创建一个字符串来插入

import java.util.*;

public class Main{
    public static boolean isPalindrome(String 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 scanner = new Scanner(System.in);
        String A = scanner.nextLine();
        String B = scanner.nextLine();
        int count = 0;//记录回文次数
        for(int i = 0; i <= A.length();i++){  //注意是小于等于，因为最后一个位置也要插入
            StringBuffer s = new StringBuffer(A);
            s.insert(i,B);
            if(isPalindrome(s.toString())){
                count++;
            }
        }
        System.out.println(count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这是用正常判断回文的方法

下面用 逆置的方法 来判断

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String A = scanner.nextLine();
        String B = scanner.nextLine();
        int count = 0;//记录回文次数
        for(int i = 0; i <= A.length();i++){
            StringBuffer s = new StringBuffer(A);
            s.insert(i,B);
            StringBuffer tmp = new StringBuffer(s);//引入临时变量
            StringBuffer s2 = tmp.reverse();//reverse这个函数会把原本字符串也逆置           
            if(s2.toString().equals(s.toString())){
                count++;
            }
        }
        System.out.println(count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

连续最大和

连续最大和

此题最容易想到的就是暴力累加，但是时间复杂度是O(n^2)，怎么做到更优化呢？ 我们要把它看成一个动规问题

本题是一个经典的动规问题，简称dp问题，题意很简单，就是求哪一段的子数组的和最大

【思路】

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

dp[i] 就是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾

现在我们开始细细品一下上面这个递推式，求dp[i]的时候有两种可能

• 要么就是像上面的dp[3]一样，dp[2]求出来是1了，再加上自己array[3]是最大的

• 那么还有一种可能就是说如果dp[2]我求出来是 -100，那如果我也是dp[2]+array[3]的话是-93， 这时候dp[2]反而是累赘，最大就是自己。

public class Main{
    public static int getMax(int a,int b){
        return a>b? a:b;
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for(int i = 0 ; i< n ; i++){
            array[i] = scanner.nextInt();
        }
        int sum = array[0];
        int max = array[0];
        for(int i = 1 ;i <n ;i++){
            sum = getMax(sum+array[i],array[i]); // 状态方程
            if(sum >= max){
                max = sum;
            }
        }
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22