两个字符串的最长公共子序列（Longest Common Subsequence, LCS）、荷兰国旗问题、合并两个有序数组、约瑟夫环

1. 两个字符串的最长公共子序列（Longest Common Subsequence, LCS）

问题描述:
给定两个字符串str1和str2，输出两个字符串的最长公共子序列的长度。如果最长公共子序列为空，则返回"0"。目前给出的数据，仅仅会存在 一个最长的公共子序列
输入描述:
输入: “1A2C3D4B56”,“B1D23A456A”
输出描述:
输出: 6
输入样例:
1A2C3D4E56
A1B2345C6D
输出样例:
6
求两个字符串的最长公共子序列（Longest Common Subsequence, LCS）长度的问题，可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。

动态规划思路

1. 状态转移方程
如果 $str1[i-1]==str2[j-1]$，则$dp[i][j]=dp[i-1][j-1]+1$
如果 $str1[i-1]!=str2[j-1]$，则$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
2.边界条件
$dp[0][j]=0$，$dp[i][0]=0$，表示空字符串和任何字符串的 LCS 长度为 0

public class LongestCommonSubsequence {public static int longestCommonSubsequence(String str1, String str2) {int m = str1.length();int n = str2.length();// 创建 dp 数组，dp[i][j] 表示 str1 前 i 个字符和 str2 前 j 个字符的 LCS 长度int[][] dp = new int[m + 1][n + 1];// 填充 dp 数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1.charAt(i - 1) == str2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回两个字符串的最长公共子序列的长度return dp[m][n];}public static void main(String[] args) {String str1 = "1A2C3D4B56";String str2 = "B1D23A456A";int result = longestCommonSubsequence(str1, str2);System.out.println(result);  // 输出: 6}
}

代码解释

初始化:
创建二维数组 dp，大小为 (m+1) x (n+1)，用于存储每个子问题的解，其中 m 和 n 分别是 str1 和 str2 的长度。
dp[i][j] 表示 str1 前 i 个字符与 str2 前 j 个字符的最长公共子序列的长度。
状态转移:
遍历 str1 和 str2，对于每一对字符 str1[i-1] 和 str2[j-1]：
如果相等，则当前的最长公共子序列长度等于之前的 dp[i-1][j-1] + 1。
如果不相等，则取 dp[i-1][j] 和 dp[i][j-1] 的较大值。
结果:
最后，dp[m][n] 即为 str1 和 str2 的最长公共子序列的长度。

2. 荷兰国旗问题

问题描述

荷兰国旗问题（Dutch National Flag Problem）由计算机科学家 Edsger Dijkstra 提出。问题描述如下：给定一个数组，数组中的元素仅有三种颜色：红色、白色和蓝色。我们用整数 0、1、2 分别表示这三种颜色。要求将数组进行排序，使得相同颜色的元素相邻，并按照红、白、蓝的顺序排列。

解决思路

由于数组中只有三种元素，我们可以使用一次线性扫描（O(n) 时间复杂度）和常数级别的额外空间（O(1) 空间复杂度）来解决此问题。这种方法被称为 “三路划分” 或 “双指针” 技巧。

双指针法

我们定义三个指针：
1.low：指向红色（0）的下一个位置。
2.mid：当前正在考虑的元素。
3.high：指向蓝色（2）的前一个位置。
初始时，low 和 mid 指向数组的起始位置，high 指向数组的末尾。我们遍历数组，具体操作如下：
1.当 nums[mid] 为 0 时，表示这个元素属于红色区域。我们将 mid 指向的元素与 low 指向的元素交换，然后将 low 和 mid 都向右移动一位。
2.当 nums[mid] 为 1 时，表示这个元素属于白色区域。我们不需要做交换，只需将 mid 向右移动一位。
3.当 nums[mid] 为 2 时，表示这个元素属于蓝色区域。我们将 mid 指向的元素与 high 指向的元素交换，然后将 high 向左移动一位。注意，这时 mid 不移动，因为交换过来的元素需要重新判断。
这个过程会一直进行，直到 mid 超过 high。

算法步骤

1.初始化 low 为 0，mid 为 0，high 为 nums.length - 1。
2.遍历数组，直到 mid 超过 high：
如果 nums[mid] == 0，交换 nums[low] 和 nums[mid]，然后 low++，mid++。
如果 nums[mid] == 1，mid++。
如果 nums[mid] == 2，交换 nums[mid] 和 nums[high]，然后 high–。

代码实现

public class DutchNationalFlag {public static void sortColors(int[] nums) {int low = 0;int mid = 0;int high = nums.length - 1;while (mid <= high) {if (nums[mid] == 0) {// 交换 nums[low] 和 nums[mid]int temp = nums[low];nums[low] = nums[mid];nums[mid] = temp;low++;mid++;} else if (nums[mid] == 1) {mid++;} else {// 交换 nums[mid] 和 nums[high]int temp = nums[mid];nums[mid] = nums[high];nums[high] = temp;high--;}}}public static void main(String[] args) {int[] nums = {2, 0, 2, 1, 1, 0};sortColors(nums);for (int num : nums) {System.out.print(num + " ");}}
}

3.合并两个有序数组

问题描述

给定两个有序整数数组 A 和 B，将 B 合并到 A 中，使得 A 成为一个有序数组。具体要求如下：
数组 A 的初始元素数量为 m，数组 B 的元素数量为 n。
数组 A 有足够的空间（大于或等于 m + n）来容纳 B 中的所有元素。
最终结果需要使 A 中的元素按照升序排列。

解决思路

由于数组 A 和 B 都已经是有序的，我们可以利用这一特性从后向前进行归并，避免移动数组元素。具体策略如下：
双指针法：使用两个指针分别指向 A 和 B 的最后一个有效元素。一个指针 p1 指向 A 中的第 m-1 个位置，另一个指针 p2 指向 B 中的第 n-1 个位置。
从后向前合并：我们从 A 数组的末尾开始填充元素，比较 A[p1] 和 B[p2] 的大小，将较大的元素放到 A 的末尾，并移动相应指针。
填充剩余元素：当 B 中仍有剩余元素时，将它们填充到 A 中。因为 A 已经是有序的，如果 B 中的元素都被合并完了，那么 A 剩余的部分已经是有序的，无需再处理。

算法步骤

1.初始化指针 p1 为 m - 1，p2 为 n - 1，tail 为 m + n - 1，用于指向 A 合并后的位置。
2.从尾部开始，比较 A[p1] 和 B[p2]：
如果 A[p1] > B[p2]，将 A[p1] 放入 A[tail]，然后 p1–。
否则，将 B[p2] 放入 A[tail]，然后 p2–。
3.将 tail–，重复上述步骤直到 p2 < 0。
4.如果 p2 仍然有剩余元素，则将 B 中剩余元素拷贝到 A 中。

代码实现

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 初始化指针 p1 指向 nums1 最后一个有效元素，p2 指向 nums2 最后一个元素int p1 = m - 1, p2 = n - 1;// tail 指向 nums1 的末尾位置int tail = m + n - 1;int cur;// 从后往前进行合并while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {// 如果 nums1 已经遍历完，将 nums2 中的元素拷贝过去cur = nums2[p2--];} else if (p2 == -1) {// 如果 nums2 已经遍历完，直接结束cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {// 如果 nums1[p1] > nums2[p2]，将 nums1[p1] 放到 tail 位置cur = nums1[p1--];} else {// 否则，将 nums2[p2] 放到 tail 位置cur = nums2[p2--];}nums1[tail--] = cur;}}
}

4. 约瑟夫环

问题描述

约瑟夫环（Josephus Problem）是一个经典的数学问题。问题描述如下：
在一个圆圈中有 n 个人（标号从 0 到 n-1）。每个人按顺序编号，第一个人从 0 开始。每隔 k-1 个人，当前的人将被淘汰。最后一个剩下的人是赢家。我们需要找出最后一个人所在的初始位置。

解决思路

约瑟夫环问题可以通过递归和非递归两种方法解决。我们将首先介绍递归的方法，然后展示其非递归实现。
递归方法
递归方法基于如下公式：
递归关系：假设我们知道 n-1 个人时最后一个人所在的位置，记作 J(n-1, k)，那么在 n 个人的情况下，我们可以通过以下公式计算：
$J(n,k)=(J(n-1,k)+k)$
其中 J(1, k) = 0 是基础情况，即只有一个人时，他的初始位置自然是 0。
这个公式的含义是，当前的安全位置（最后剩下的位置）是在去掉一个人后的安全位置的基础上，再加上 k（即每次淘汰的间隔），然后对当前人数取模，以确保位置在当前圈的范围内。
非递归方法
递归方法虽然简洁，但对于较大的 n，可能会出现栈溢出的问题。因此，非递归方法是一种更实际的解决方案。非递归的方法通过迭代来实现：
从 1 人开始（即基础情况），最后一个人位置是 0。
逐步增加人数，每次增加一个人时，根据递归关系更新最后剩下的位置。

代码实现

递归方法

public class Josephus {public int josephusRecursive(int n, int k) {if (n == 1) {return 0;} else {return (josephusRecursive(n - 1, k) + k) % n;}}public static void main(String[] args) {Josephus josephus = new Josephus();int n = 5;int k = 3;int position = josephus.josephusRecursive(n, k);System.out.println("最后一个剩下的位置是: " + position);}
}

非递归方法

public class Josephus {public int josephusIterative(int n, int k) {int result = 0; // 基础情况：只有一个人时，最后剩下的位置是 0for (int i = 2; i <= n; i++) {result = (result + k) % i;}return result;}public static void main(String[] args) {Josephus josephus = new Josephus();int n = 5;int k = 3;int position = josephus.josephusIterative(n, k);System.out.println("最后一个剩下的位置是: " + position);}
}

【整数列表求三的倍数】
问题描述: 给定一个从1到n的整数列表，从第一个数字开始计数，遇到3的倍数时，将该数从列表中删除，直至列表末尾。
在剩下的数字中，从第一个数字开始，继续之前的计数值，同样遇到3的倍数时，删除该数。
循环上面的步骤，直到列表中只剩下一个数字。
根据指定的数字n，来判断最后剩下的数字是哪个。

import java.util.LinkedList;
import java.util.List;public class RemoveMultiplesOfThree {public static int findLastRemaining(int n) {// 创建一个从1到n的列表List<Integer> numbers = new LinkedList<>();for (int i = 1; i <= n; i++) {numbers.add(i);}int index = 0; // 从列表的第一个数字开始计数int count = 0; // 用于计数是否为3的倍数while (numbers.size() > 1) {count++;if (count % 3 == 0) {// 如果当前计数是3的倍数，移除当前数字numbers.remove(index);// 注意: 删除元素后，索引index不变，因为列表整体向前移动} else {// 如果不是3的倍数，移动到下一个数字index++;}// 如果索引超过列表末尾，循环回到开头if (index >= numbers.size()) {index = 0;}}// 返回列表中最后剩下的数字return numbers.get(0);}public static void main(String[] args) {int n = 5; // 输入样例int result = findLastRemaining(n);System.out.println(result); // 输出: 4}
}