java基础编程题day05--每日两题

 

目录

连续子数组最大和_流利说笔试题_牛客网

统计回文__牛客网

---

输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

动态规划，分三步：
1.定义dp数组的含义：dp[i]代表0-i下标范围内的子数组最大和。
2.找dp关系：dp[i] = Math.max(dp[i - 1]+arr[i],arr[i]);
3.找初始条件：
        dp[0] = arr[0];
        int max = arr[0];

代码实现：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < arr.length; ++i){
            arr[i] = scanner.nextInt();
        }

        //dp[i],代表0-i下标中连续子数组的最大和
        //初始条件
        int[] dp = new int[n];
        dp[0] = arr[0];
        int max = arr[0];

        for(int i = 1; i < arr.length; ++i){
            //找dp关系
            dp[i] = Math.max(dp[i - 1]+arr[i],arr[i]);
            if(dp[i] > max){
                max = dp[i];
            }
        }
        System.out.println(max);
    }
}

统计回文__牛客网

输入字符串1和字符串2，将字符串2插入到字符串1的每一个位置，并每次判断是否是回文，输出是回文的总次数。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
* 在A的第一个字母之前: "baba" 不是回文
* 在第一个字母‘a’之后: "abba" 是回文
* 在字母‘b’之后: "abba" 是回文
* 在第二个字母'a'之后 "abab" 不是回文
所以满足条件的答案为2

思路：利用StringBuffer中的插入方法insert()和回文方法reverse()，1.利用插入方法即可插入到字符串1的所有位置。2.利用reverse()方法可以是否是回文 
注意点：StringBuffer中的equals方法只是判断是否是同一个对象，因此要先转成字符串，通过字符串的equals方法去判断字符串是否相等。

//把第二行插入到第一行，判断是否是回文
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        //str2插入到str1当中
        int count = 0;
        for(int i = 0; i <= str1.length(); i++){
            StringBuffer stringBuffer = new StringBuffer(str1);
            stringBuffer.insert(i,str2);
            //错误写法if(stringBuffer.equals(stringBuffer.reverse()))
            if(stringBuffer.toString().equals(stringBuffer.reverse().toString())){
                count++;
            }
        }
        System.out.println(count);
    }
}