数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 程序，用于查找具有相同左右旋转的数字的最长子序列
我们将实现一段代码，以在 JavaScript 编程语言中找到给定数字的最长子序列，该子序列具有相同的左右旋转。给定数字的左右旋转是指，对于左旋转，我们必须将数字的最左边的数字移动到末尾位置或最右边的位置。类似地，对于右旋转，我们必须将数字的最右边的数字移动到第一个位置或最左边的位置。我们将看到完整的代码及其实现。
问题介绍
在这个问题中，我们给定一个数字，我们需要找到一个子序列（可以从给定数字或字符串中删除一些字符或数字而找到的数字或字符串的子序列），该子序列具有相同的左旋转和右旋转，如果有多个，则需要提供长度最大的那个。
例如 -
如果给定的数字是 100310801，那么我们可以得到许多具有相同左右旋转的序列 -
所有大小为 1 或长度为 1 的序列都具有相同的左右旋转。
所有大小为 2 且两个数字相同的序列也具有相同的左右旋转。
我们可以有值为 1010 和 0000 或大小为 4 的序列，它们可以具有相同的左右旋转。
我们有两种方法可以解决这个问题，让我们看看这两种方法 -
朴素方法
直接而简单的方法是蛮力法，其中我们可以最终找到给定数字的所有子序列，然后对于每个子序列，我们可以找到其左旋转和右旋转并进行匹配。如果两者相同，我们将检查子序列的长度。如果当前子序列的长度大于先前存储的长度，则可以更新它。
这种方法存在一个问题，即时间复杂度。对于具有 N 位数字的给定数字找到每个子序列的时间复杂度为 2 的 N 次方，然后查找左旋转和右旋转将额外花费 N 的时间，这使得总时间复杂度为 O()。对于大于 20 的数字，这在合理的时间内不容易轻松计算，这使得这种方法效率低下。
主要方法
在主要方法中，我们将通过从示例中简单的观察来采用一种最佳方法：如果子序列的大小为 1，则始终存在左旋转和右旋转相等的情况。另一个观察结果是，给定数字中的数字长度或位数必须为偶数，并且所有出现在奇数位置的数字都相同，所有出现在偶数位置的数字都必须相同。例如，898989、78、656565 等，这些类型的数字始终具有相同的左右旋转。
目标是找到最大的数字或最大的子序列，为此我们将遵循以下步骤 -
示例
// creating function to just pass the string
// or number to get the result
function findAltSubSeq(str){
// Length of the given string
var num = str.length
// answer variable to store the answer
var ans = -1;
// Iterate for all possible combinations
// of a two-digit numbers
var digits = 10
for (var i = 0; i < digits; i++) {
for (var j = 0; j < digits; j++) {
var current = 0
var temp = 0
// Check for alternate occurrence
// of current combination
for (var k = 0; k < num; k++) {
if (temp == 0 && str[k] - '0' == i) {
temp = 1;
// Increment the current value
current++;
}
else if (temp== 1 && str[k] - '0' == j) {
temp = 0;
// Increment the current value
current++;
}
}
// If alternating sequence is
// obtained of odd length
if (i != j && current % 2 == 1)
// Reduce to even length
current--;
// Update answer to store
// the maximum
ans = Math.max(current, ans);
}
}
// Return the answer
return ans;
}
// calling the function
// taking the number in string version
var str = "100210601";
console.log("Subsequcne with the maximum length is of length: " + findAltSubSeq(str));
时间和空间复杂度
上面代码的时间复杂度为 O(N)，其中 N 是给定数字的长度。程序的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。
注意：在上面的代码中，我们使用字符串而不是数字数据类型作为数字，因为与 JavaScript 中的数字相比，使用字符串更容易操作，因此如果给定数字，最好将其转换为字符串。
结论
在本文中，我们实现了一段代码，以在 JavaScript 编程语言中找到给定数字的最长子序列，该子序列具有相同的左右旋转。左旋转是将最右边的元素或数字移动到最左边的位置，右旋转正好相反。我们讨论了两种方法，一种是简单的蛮力法，另一种是高效的两指针方法，时间复杂度为 O(N)，空间复杂度为 O(1)。
158 次查看
