資料結構
網路
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 次檢視
