输出一个数组组合之后的最大数
@Test
public void test(){
int[] num = {1,2,3,4,5,27};
String reduce = Arrays.stream(num).mapToObj(String::valueOf)
.sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
.reduce("", (s1, s2) -> (s1 + s2));
System.out.println(reduce.charAt(0) =='0'?0:reduce);
}
查找数组中具有最大和的连续子数组。
解释
定义了一个整数数组 xx 存储了一组整数。 maxSum 用于记录当前已经遍历过的子数组的最大和，初始化为整型最小值 Integer.MIN_VALUE。 maxB 和 maxE 用于记录当前最大子数组的起始索引和结束索引。 tsum 用于记录当前正在累积的子数组的和。 使用 for 循环遍历数组 xx： 在每次迭代中，将当前元素加到 tsum 中，表示累积当前子数组的和。 如果 tsum 大于 maxSum，更新 maxSum 和 maxE，以记录找到的更大的子数组和以及结束索引。 如果 tsum 小于等于 0，表示当前累积的子数组和不再对后续的和有正向贡献，因此更新 maxB，以重新开始计算下一个子数组的和。 使用第二个 for 循环将找到的最大子数组的元素加入到 ll 列表中。 最后打印输出 ll 列表，即找到的具有最大和的连续子数组。 这段代码的核心思想是利用动态规划的思想，在遍历数组的过程中不断更新当前的最大子数组和以及起始和结束索引，从而得到整个数组中具有最大和的连续子数组。
@Test
public void test(){
int[] xx = {-1,2,4,-2,0,10,-3,6,-7,5,-10};
int maxSum = Integer.MIN_VALUE;
int maxB = 0;
int maxE = 0;
int tsum = 0;
for (int i = 0; i < xx.length; i++) {
tsum += xx[i];
if (tsum > maxSum) {
maxE = i;
maxSum = tsum;
}
if (tsum <= 0) {
maxB = i+1;
}
}
List<Integer> ll = new ArrayList<>();
for (int i = maxB; i <=maxE ; i++) {
ll.add(xx[i]);
};
System.out.println(ll);
}
最大乘积子数组
public int maxProduct3(int[] nums) {
int n = nums.length;
int maxProduct = nums[0]; // 记录当前最大乘积
int minProduct = nums[0]; // 记录当前最小乘积
int result = nums[0]; // 记录最终结果
for (int i = 1; i < n; i++) {
// 如果当前元素为负数，则交换最大乘积和最小乘积
if (nums[i] < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
// 更新最大乘积和最小乘积
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);
// 更新最终结果
result = Math.max(result, maxProduct);
}
return result;
}
最长回文子数组
- 从中间往两边遍历。
- 使用 boolean[][] 数组记录 i到j 是否是回文数组。
- 因为是从中间往两边遍历，所以：
- charArray[j] == charArray[i] 判断当前的ij 是否是回文，再判断 2、或者3
- i-j <= 2 代表 组成 回文的最小单位 1个：a 单个字符 也是回文 、2个 aa 两个字符 是回文 、3个 aba 三个字符 是回文
- mark[j+1][i-1] 代表前一个已经判断过的子数组 是否是回文 判断 i-j+1 > maxL 记录 最长回文的maxb 起始下标、结尾下标、长度 当长度 大于 之前的最大长度时就记录当前的 j 为开头 i 为结尾 maxL 为长度 最后 s.substring(maxb,maxE + 1) 这个方法是左闭右开的 所以需要 是 maxE + 1
@Test
public void test(){
String xx = "abcbadeoeda";
int maxB = 0;
int maxE = 0;
int maxL = 1;
char[] charArray = xx.toCharArray();
boolean[][] mark = new boolean[charArray.length][charArray.length];
for (int i = 1; i < charArray.length; i++) {
for (int j = 0; j < i; j++) {
if (charArray[j] == charArray[i] && (i-j<=2 || mark[j+1][i-1])) {
mark[j][i] = true;
if (i-j+1 > maxL) {
maxL = i-j +1;
maxB = j;
maxE = i;
}
}
}
}
System.out.println(xx.substring(maxB,maxE +1));
}
最接近的三数之和
@Test
public void testNearestThreeNumbersSum(){
int[] nums = {1,2,3,4,5,6,7,8,9};
int target = 17;
Arrays.sort(nums);
int x = 0;
for (int i = 0; i < nums.length; i++) {
int l = x+1,r = nums.length-1;
while (l<r) {
int t = nums[l] + nums[i]+ nums[r];
if (Math.abs(target - t) < Math.abs(target -x)) {
x = t;
}
if (t > target) {
r--;
}else {
l++;
}
}
}
System.out.println(x);
}
三数之和
https://leetcode.cn/problems/1fGaJU/description/
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
解答:
@Test
public void test(){
int[] nums = {-1,0,1,2,-1,-4};
Arrays.sort(nums);
List<List<Integer>> lists = new ArrayList<List<Integer>>();
for (int i = 0; i < nums.length; i++) {
int l = i + 1,r = nums.length-1;
while (l<r) {
int t = nums[i] + nums[l] + nums[r];
if( t==0) {
ArrayList<Integer> integers1 = new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[r]));
lists.add(integers1);
if (nums[l] == nums[l++] || nums[r]== nums[r--]) {
break;
}
l ++;
r --;
} else if (t < 0) {
l++;
}else {
r--;
}
}
}
System.out.println(lists);
}
最长不重复子字符串的长度
@Test
public void test(){
String a = "abcexaecdfpg";
int x = 0;
Queue<Character> q = new LinkedList<>();
for (int i = 0; i < a.length(); i++) {
while (q.contains(a.charAt(i))) {
q.poll();
}
q.add(a.charAt(i));
x = Math.max(x,q.size());
}
System.out.println(x);
Object[] array = q.toArray();
System.out.println(Arrays.toString(array));
}
最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/description/
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(),n2 = text2.length();
int[][] pb = new int[n1+1][n2+1];
for(int i = 1;i<=n1;i++) {
for( int j = 1;j<=n2;j++) {
if (text1.charAt(i-1) == text2.charAt(j-1)) {
pb[i][j] = pb[i-1][j-1] + 1;
}else {
pb[i][j] = Math.max(pb[i-1][j],pb[i][j-1]);
}
}
}
return pb[n1][n2];
}
当解决字符串问题时，最长公共子序列（Longest Common Subsequence，简称 LCS）是一类经典的问题。这个问题的目标是找到两个字符串中最长的共同子序列的长度。子序列是指字符串中按相对顺序但不一定是连续的字符组成的序列。
这段 Java 代码采用动态规划（Dynamic Programming）的方法来解决最长公共子序列问题。让我们逐步解释这个算法：
1. **初始化：**
- `n1` 和 `n2` 分别是两个输入字符串 `text1` 和 `text2` 的长度。
- `dp` 是一个二维数组，`dp[i][j]` 表示 `text1.substring(0, i)` 和 `text2.substring(0, j)` 的最长公共子序列的长度。
- 通过 `int[][] dp = new int[n1 + 1][n2 + 1];` 初始化一个二维数组，多出的一行和一列是用于处理边界情况的。
2. **动态规划递推：**
- 使用两个嵌套的循环遍历字符串 `text1` 和 `text2` 中的每个字符。注意，由于 `dp` 数组多出一行和一列，因此在遍历字符串时，要从索引 `1` 开始，而在 `dp` 数组中的索引是从 `0` 开始。
- 对于每一对字符 `text1.charAt(i - 1)` 和 `text2.charAt(j - 1)`：
- 如果它们相等，表示找到了一个公共字符，将 `dp[i][j]` 设置为左上角对角元素 `dp[i - 1][j - 1]` 的值加一。
- 如果它们不相等，表示当前字符不在最长公共子序列中，将 `dp[i][j]` 设置为其上方元素 `dp[i - 1][j]` 和左方元素 `dp[i][j - 1]` 中的较大值。
- 这样，通过逐步填充二维数组 `dp`，我们能够得到包含全部字符的两个字符串的最长公共子序列的长度。
3. **返回结果：**
- 最后，返回 `dp[n1][n2]`，这个值就是 `text1` 和 `text2` 的最长公共子序列的长度。
这个算法的核心思想是利用动态规划保存中间状态，避免重复计算，从而有效地解决了最长公共子序列问题。