刷题_5：统计回文 and 连续最大和

迈不过友情╰ 2023-09-28 23:38 21阅读 0赞

### 一.统计回文 ###

**题目链接：**

> [统计回文][Link 1]

**题目描述：**

> **“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。  
> 例如：  
> A = “aba”，B = “b”。这里有4种把B插入A的办法：  
> 在A的第一个字母之前: “baba” 不是回文  
> 在第一个字母‘a’之后: “abba” 是回文  
> 在字母‘b’之后: “abba” 是回文  
> 在第二个字母’a’之后 “abab” 不是回文  
> 所以满足条件的答案为2**

**输入描述：**

> **每组输入数据共两行。  
> 第一行为字符串A  
> 第二行为字符串B  
> 字符串长度均小于100且只包含小写字母**

**输出描述：**

> **输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数**

**示例1：**

> **输入：  
> aba  
> b  
> 输出：  
> 2**

**个人思路：**

> **依次插入字符然后判断新字符是否是回文结构即可。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String A = sc.nextLine();
            String B = sc.nextLine();
            String temp = null;
            int cnt = 0;
            //这里循环判断条件为<=是因为对于一个长度为l的字符串 我们可选择的插入位置有l + 1个
            for (int i = 0; i <= A.length(); i++) {
        
                //拼接
                temp = A.substring(0, i) + B + A.substring(i);
                if (isPalindrome(temp)) {
        
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    
        public static boolean isPalindrome(String s) {
        
            int l = 0;
            int r = s.length() - 1;
            while (l < r) {
        
                if (s.charAt(l) != s.charAt(r)) {
        
                    return false;
                }
                l++;
                r--;
            }
            return true;
        }
    }

--------------------

### 二.连续最大和 ###

**题目链接：**

> [连续最大和][Link 2]

**题目描述：**

> **一个数组有 N 个元素，求连续子数组的最大和。 例如：\[-1,2,1\]，和最大的连续子数组为\[2,1\]，其和为 3**

**输入描述：**

> **输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。**

**输出描述：**

> **所有连续子数组中和最大的值。**

**示例1：**

> **输入：  
> 3  
> \-1 2 1  
> 输出：  
> 3**

**个人思路：**

> **一路求和并更新最大值res，当sum大于等于0时，sum与后面的数相加产生的是正面效果，我们一直累加即可；当sum小于0时，sum与后面的数相加会产生负面效果，会使总和变小，所以我们将sum置为0。最终统计的res即为连续最大和。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            //用来统计最大和
            int sum = 0;
            //用来记录最大值
            int res = -1;
            for (int i = 0; i < n; i++) {
        
                sum += sc.nextInt();
                //每次都更新res的值
                res = Math.max(res, sum);
                //如果sum加完这次之后小于0 那么它再与之后的数相加都会产生负面效果
                //所以我们重置sum = 0
                if (sum < 0) {
        
                    sum = 0;
                }
            }
            System.out.println(res);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/9d1559511b3849deaa71b576fa7009dc
[Link 2]: https://www.nowcoder.com/questionTerminal/5a304c109a544aef9b583dce23f5f5db