前言：
大家好，我是良辰丫，今天是刷题的第五篇,牛客网选择题+编程题统计回文+连续最大值(暴力解法+动态规划),每天都去努力,选一个方向，定一个时间；剩下的只管努力与坚持，时间会给我们最后的答案。!!!💞💞

🧑个人主页：良辰针不戳
📖所属专栏：百日冲大厂
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
💌作者能力有限，可能也会出错，欢迎大家指正。
💞愿与君为伴，共探Java汪洋大海。

目录

• 1. 选择题
• • 1.1 单选题
  • 1.2 多选
• 2. 编程题
• • 2.1 统计回文
  • 2.2 连续最大值
  • • 2.2.1 暴力解法
    • 2.2.2 动态规划解法

1. 选择题

1.1 单选题

• 右移相当于除法,但是大家需要注意细节.
• 右移一位相当于除以二,也就是5>>2就是5/2/2 = 1
• 1>>>2 相当于1/2/2 = 0

operate方法中的参数是传引用.

• 其中x.append(y)修改了x的指向的内容.
• 而y = x只是修改了引用的指向.

this(x)调用其它类的构造方法,固定格式.this().

局部变量使用的时候需要初始化.

java中switch语句的参数可以为char,byte,short,int,String等.

关于类名基本概念.

try-catch结构比较特殊,其中的finally块中的语句一定最后执行.

void为关键字,不能作为标识符.

• change方法的参数为引用,修改引用的指向不会修改原来的内容
• 但是ch[0] = 'g’是修改其中的内容,这样会影响原来的内容.

1.2 多选

final可以用于声明属性和方法,分别表示属性的不可变及其方法的不可重写,是不可重写,不是不可继承哦.

2. 编程题

2.1 统计回文

做题链接:
链接: 统计回文

题目描述:

做题思路:

• 输入两个字符串,第二个字符串插入第一个字符串的各个位置,例如字符串23与1,插入之后可以变成123,213,231.由此我们可以看出来,插入的方式的数量是第一个字符串长度加1.
• 我们自己写一个插入方法可行嘛?当然可行,但是很麻烦,为什么我们不直接调用库中的方法呢?java有StringBuffer和StringBuilder,它们就拥有插入方法.既然如此,为什么我们要给自己找麻烦的.在以后比试的时候,尽量要培养一个思想,看库方法中是否有该功能.当然,大家在平时练习的时候自己可以用代码实现这些方法,培养自己的写代码能力.
• 我们还需要写一个判断是否是回文的方法,我们采取双指针的方式,首尾遍历然后提取首尾元素进行判断.

注意:
有的小伙伴可能会想到库里面的翻转函数reverse,殊不知大家可能会犯错,reverse把原字符串的内容修改了,两个相同的字符串进行比较,永远都是相同的.

public class Main {
    private static boolean isHuiwen(String str){
        int left = 0;
        int right = str.length()-1;
        while(left < right){
            char ch1 = str.charAt(left);
            char ch2 = str.charAt(right);
            if(ch1 != ch2){
                return false;
            } else{
                left++;
                right--;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        int count = 0;
        for(int i = 0;i<=str1.length();i++){
            StringBuffer str = new StringBuffer(str1);
            str.insert(i,str2);
            String s = str.toString();
            if(isHuiwen(s)){
                count++;
            }

        }
        System.out.println(count);        
    }
}

2.2 连续最大值

做题链接:
链接: 连续最大值

题目描述:

做题思路:

• 这道题大家很容易想到暴力解法,两个循环,求取最大值,时间复杂度为O(n*n)
• 动态规划解法,遍历一次就能得出结果,时间复杂度为O(n),动态规划是什么呢?不要着急,下面会给大家讲解.

2.2.1 暴力解法

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int sum = 0;        
        for(int i = 0;i<n;i++){
            arr[i] = in.nextInt();
        }
        int as = Integer.MIN_VALUE;
        for(int i = 0;i<arr.length;i++){
            sum = 0;
            for(int j = i;j < arr.length;j++){
                sum+=arr[j];
                as = Math.max(as,sum);
            }
        }
        System.out.println(as);        
    }

我们惊喜的发现有一组数据未通过,当数据足够多的话,就会超时,看来出题人不想让你用暴力哈.

2.2.2 动态规划解法

说白了动态规划相当于一个缓存,缓存你想要的结果,如果你想要最大值,他就存储最大值,并且在遍历的过程中可能会刷新,寻找最大值.动态规划一般用数组来进行缓存的.

• 明确数组的含义,比如f[i]要表示什么,在这里我们表示遍历到第i个位置的时候,缓存的最大值.但是这道题这样表示不容易做,我们需要有一个变量去存储最大值.
• 找到关系式,也就是状态转移方程.刚开始接触听不懂没关系,慢慢来,熟能生巧.状态转移方程其实可以理解为我们的找规律.咱们这里的规律是自己本身加上遍历到的数字,相加后与最大值进行比较,选取真正的最大值.
• 绝大多数情况都需要弄初始值,从哪里开始遍历.

上述这些并不是真正的动态规划套路,我只是稍微总结了一下,帮助大家理解.

public class Main {
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] array = new int[size];
        for(int i = 0; i< size;i++) {
            array[i] = sc.nextInt();
        }
        //赋予初始值
        int sum = array[0];
        int max = array[0];
        for(int i = 1;i < size;i++) {
        //sum取较大值,注意是较大值,区域内的较大值
            sum = Math.max(sum + array[i], array[i]); //状态方程
            //满足条件的时候,max进行更新,max总是取遍历到某个位置之前的最大值
            if (sum >= max)
                max = sum;
        }
        //遍历完所有数据,max真正取到自己的最大值.
        System.out.println(max);
    }
}