Java 程序求具有相同左右旋转的数字的最长子序列
在这个问题中，我们需要找到具有相同左右旋转的最长子序列的长度。
我们可以使用蛮力方法解决这个问题，找到给定字符串的所有可能子序列，并逐个检查每个子序列以查看它是否具有相同的左右旋转。我们找到这种子序列的最大长度。这种方法的问题在于它非常耗时，因为它的时间复杂度是 O(2N)。
因此，我们将学习用这种方法编写优化代码。
问题陈述– 我们给出了包含 N 个数字字符的字符串 str。我们需要找到给定字符串中具有相同左旋转和右旋转的最长子序列。
示例
输入– str = "9898798"
输出– 6
解释– 我们有具有相同左旋转和右旋转的最长子序列，即 989898。
输入– str = '12345678'
输出– 2
解释– 我们可以选择任何长度为 2 的子序列，因为它始终具有相同的左旋转和右旋转。
输入– '327787767777'
输出– 8
解释– 具有相同左旋转和右旋转的最长子序列是'77777777'。
方法 1
在这种方法中，我们将根据特定观察来解决问题。只有当字符串的所有数字都相等或交替包含两位数字，并且字符串长度为偶数时，字符串的左右旋转才相同。
在这里，我们将尝试找到相同或交替数字的子序列。
算法
用字符串长度初始化"len"变量，用0初始化"cnt"变量以存储子序列的最大长度。
使用两个嵌套循环从0到9遍历并获取每个数字的组合。
定义"cur_len"变量以存储当前子序列的长度。此外，定义"firstDigit"变量来跟踪下一个数字是变化数字序列中的第 p 位还是第 q 位。
使用第三个嵌套循环遍历数字字符串。
如果 firstDigit == 0 && str.charAt(k) - '0' ==pI 为真，则将 firstDigit 的值更改为 1，并将 cur 增加 1。
如果 firstDigit == 1 && str.charAt(k) - '0' == q 为真，则将 firstDigit 的值更改为 0，并将"cur_len"增加 1。
如果 p 和 q 不相同，并且"cur_len"的值为奇数，则将"cur_len"减少 1。
如果"cnt"的值'cur_len' 大于 'cnt' 值。
返回 'cnt' 值。
示例
import java.util.*;
public class Main {
static int findLongestSub(String str) {
int len = str.length(), cnt = 0;
// 遍历字符串的每个组合。
for (int p = 0; p < 10; p++) {
for (int q = 0; q < 10; q++) {
int cur_len = 0, firstDigit = 0;
// 寻找交替序列
for (int r = 0; r < len; r++) {
if (firstDigit == 0 && str.charAt(r) - '0' == p) {
firstDigit = 1;
// add 1
cur_len++;
} else if (firstDigit == 1 && str.charAt(r) - '0' == q) {
firstDigit = 0;
// add 1
cur_len++;
}
}
// 如果当前值为奇数，则减 1
if (p != q && cur_len % 2 == 1)
cur_len--;
// 更新cnt值
cnt = Math.max(cur_len, cnt);
}
}
// 返回结果
return cnt;
}
public static void main(String[] args) {
String str = "9898798";
System.out.print("左右旋转相同的最长子序列的长度为"
+ findLongestSub(str));
}
}
输出
具有相同左和右旋转的最长子序列的长度为 6
时间复杂度 – O(N)，因为我们遍历长度为 K 的数字字符串。
空间复杂度 – O(1)，因为我们不使用任何动态空间。
在本教程中，我们学习了如何找到具有相同左和右旋转的子序列的最大长度。程序员可以尝试使用蛮力方法来解决，方法是使用代码查找给定字符串的所有可能子序列。
