🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🌍1. 连续子数组的最大和
描述
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
编辑
解题思路：
🎈1. 思路一：根据题意，我们可以快速提炼出每个dp[i] 中 可以存储(dp[i -1] + dp[i]) 并判断其大小，因此我们可以使用dp（动态规划）完成
a.定义状态 f(i): 以i下标结尾的最大连续子序列的和
b.状态递推：f(i) = max(f(i-1)+array[i], array[i]) （这里一定要注意连续关键字）
c.状态初始化：f(0) = array[0], maxSum= array[0]
🎈2. 思路二：思路一可以进行优化，我们可以设置一个sum值和maxSum值，maxSum一直存储sum的最大值；sum 一直加上array[i]，如果sum > 0，继续sum += array[i]，当sum < 0 时，更新sum = array[i]，遍历结束，return maxSum即可
🛹思路一：代码如下：
// 方法一 动态规划 public static int FindGreatestSumOfSubArray1(int[] array) { int[] dp = new int[array.length]; // 初始化 int maxSum = array[0]; dp[0] = array[0]; // 遍历 for (int i = 1; i < dp.length; i++) { // dp[i] 中一直存储的是((dp[i-1]+array[i]) 和 array[i]) 中的较大值 dp[i] = Math.max(dp[i-1]+array[i],array[i]); // 更新最大值 maxSum = Math.max(maxSum,dp[i]); } return maxSum; }
🛹思路二：代码如下：
// 方法二 public static int FindGreatestSumOfSubArray(int[] array) { // 初始化 int maxSum = array[0]; int sum = array[0]; // 遍历 for (int i = 1; i < array.length; i++) { if(sum < 0){ // 当sum < 0 时，更新sum sum = array[i]; }else { // 当sum > 0 时，继续sum+=array[i] sum += array[i]; } // maxSum一直存储sum的最大值 maxSum = Math.max(maxSum,sum); } return maxSum; }
🌍2. 回文数索引
描述
给定一个仅由小写字母组成的字符串。现在请找出一个位置，删掉那个字母之后，字符串变成回文。请放心总会有一个合法的解。如果给定的字符串已经是一个回文串，那么输出-1。
编辑
解题思路：
🎈1. 思路一：我们在进行字符串回文判断时可以从字符串两侧开始，如果遇到左右两个字符不同，则删除任意一个，再判定是否是回文，如果是，该删除的下标就是删除数据的下标，如果不是，该删除的下标就是另一个元素的下标。
🛹思路一：代码如下：
public class PalindromeIndex_26 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); while (num > 0){ StringBuilder sb = new StringBuilder(in.next()); // temp 中存储两个不同字符的下标 int[] temp = new int[2]; temp[0] = -1; temp[1] = -1; // 判断是否是回文字符串 if(isPalindrome(sb,temp)){ // 若是，直接输出-1 System.out.println(-1); }else { // 如不是，则先删除左侧不是回文的索引字符 sb.deleteCharAt(temp[0]); if(isPalindrome(sb,temp)){ // 删除后，字符串是回文了，则左侧不是回文的索引字符就是应该删除的字符索引位置 System.out.println(temp[0]); }else { // 删除后，字符串不是回文了，则右侧不是回文的索引字符就是应该删除的字符索引位置 System.out.println(temp[1]); } } // 判断下一条字符串 num--; } } // 判读是否是回文字符串 private static boolean isPalindrome(StringBuilder sb, int[] temp) { int i = 0; int j = sb.length()-1; while (i <= j){ if(sb.charAt(i) != sb.charAt(j)){ // 如果左右两个字符不同，则不是回文字符串，存储左右两个不同字符的下标 if(temp[0] == -1) temp[0] = i; if(temp[1] == -1) temp[1] = j; return false; } i++; j--; } return true; } }
🌍3. 把数组排成最小的数
描述
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如
输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
解题思路：
🎈1. 思路一：核心理解是我们对于排序算法的理解，通常我们所理解的排序是比较大小的
如：升序排序的序列意思是：序列中任何一个数字，都比前面的小，比后面的大
我们把说法换一下，对于本题，我们要的有效序列是：序列中任何一个元素y，和它前的任何一个元素x进行有序组合形成 xy，比和他后面的任何一个元素z进行有效序列组合yz，满足条件xy < yz（采用字典序列排序）
如{32，31}，有效组合是3132，所以我们拍完序列之后序列变成{31, 32}
a. 所以我们先创建一个list集合，并将所有元素添加到list集合中
b. 然后进行list集合排序，这里，我们可以重写compare 方法
c. 排序后的list 集合就是我们需要的集合
🛹思路一：代码如下：
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class SortArrToMin_27 { public String PrintMinNumber(int [] numbers) { // a. 所以我们先创建一个list集合，并将所有元素添加到list集合中 ArrayList<Integer> list = new ArrayList<>(); for(int i:numbers){ list.add(i); } // b. 然后进行list集合排序，这里，我们可以重写compare 方法 Collections.sort(list, new Comparator<Integer>() { @Override public int compare(Integer x, Integer y) { // 序列中任何一个元素y，和它前的任何一个元素x进行有序组合形成 xy String xy = x +""+ y; // 他后面的任何一个元素z进行有效序列组合yz String yx = y +""+ x; // 满足条件xy < yz（采用字典序列排序） return xy.compareTo(yx); } }); // c. 排序后的list 集合就是我们需要的集合 String str =""; for(Integer i:list){ str+=i; } return str; } }
