資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學Python3程式：查詢具有相同左右旋轉的最長子序列
在這個問題中，我們將找到給定字串的最長子序列的長度，該子序列具有相同的左右旋轉。
我們可以透過找到給定字串的所有子序列並檢查特定子序列是否具有相同的左右旋轉來解決問題。另一種方法是利用觀察結果，即如果字串包含單個字元或交替字元且左側為偶數，則字串只能具有相同的左右旋轉。
問題陳述 – 我們給定一個僅包含數字字元的字母字串。我們需要找到字串的最長子序列的大小，該子序列具有相同的左右旋轉。
示例
輸入
alpha = "700980503"
輸出
4
解釋 – 具有相同左右旋轉的最長子序列是 '0000'。
輸入
alpha = ‘19199019’
輸出
6
解釋 – 結果子序列是 '191919'。
輸入
alpha = ‘13141115611171’
輸出
9
解釋 – 具有相同左右旋轉的最長子序列是 '111111111'。
方法 1
在這種方法中，我們將找到給定字串的所有子序列。之後，我們將使用 Python 陣列切片來檢查子序列是否具有相同的左右旋轉。
演算法
步驟 1 – 將 'maxLen' 初始化為 -1 以儲存子序列的最大長度。
步驟 2 – 呼叫 getSubs() 函式以獲取給定字串的所有子序列。
步驟 2.1 – 在 getSubs() 函式中，將 'allSubs' 陣列初始化為單個空字串元素。
步驟 2.2 – 開始遍歷字串，並在 'temp' 變數中建立陣列的副本。
步驟 2.3 – 遍歷 'temp' 陣列並將 'ch' 字元追加到 temp 陣列的子序列中。之後，將新的子序列插入到 'allSubs' 陣列中。
步驟 2.4 – 返回 'allSubs' 陣列。
步驟 3 – 獲取所有子序列後，遍歷子序列陣列。
步驟 4 – 使用 subseq[1:] + subseq[:1] 切片子序列以獲取左旋轉。同樣，使用 subseq[str_len - 2:] + subseq[:str_len - 2] 切片子序列以獲取右旋轉。
步驟 5 – 如果左右旋轉相同，則如果 maxLen 值小於子序列的長度，則更新 maxLen 值。
步驟 6 – 返回 'maxLen' 變數的值。
示例
def getSubs(alpha):
allSubs = ['']
for ch in alpha:
# Create a copy of the array containing all subsequences
temp = allSubs[:]
# Append character to each subsequence of the array to generate new subsequences
for subseq in temp:
allSubs.append(subseq + ch)
return allSubs
def maxSubSeqLen(alpha):
maxLen = -1
str_len = len(alpha)
allSubs = getSubs(alpha)
# Traverse all subsequences
for subseq in allSubs:
# check if the subsequence has the same left and right rotation
if subseq[1:] + subseq[:1] == subseq[str_len - 2:] + subseq[:str_len - 2]:
maxLen = max(maxLen, len(subseq))
# Return the answer
return maxLen
alpha = "1919019"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
輸出
The maximum length of subsequence having the same left and right rotations is - 6
時間複雜度 – O(2N)，因為我們找到了給定字串的所有子序列。
空間複雜度 – O(2N)，因為我們儲存了給定字串的所有子序列。
方法 2
在這種方法中，我們將使用基於問題輸入和輸出的觀察結果。只有當字串包含所有相同的字元或長度為偶數且包含交替字元時，字串才能具有相同的左右旋轉。
因此，我們將根據這兩種條件找到最長的子序列。
演算法
步驟 1 – 將 'maxLen' 變數初始化為 -1。
步驟 2 – 使用迴圈從 0 遍歷到 9。此外，使用另一個巢狀迴圈從 0 遍歷到 9。在這裡，我們配對數字，例如 00、01、02、… 01、12、13、14、… 97、98、99 等。因此，我們將找到給定字串中的數字對並獲取子序列的最大長度。
步驟 3 – 將 'currMax' 和 'isSecond' 變數初始化為 0 以儲存給定字串中存在的數字對的總數，並跟蹤在字串中查詢對的第一個或第二個字元以建立交替子序列。
步驟 4 - 開始遍歷字串。如果 'isSecond' 等於 0，並且字元等於 'p'，則將 'isSecond' 更改為 1 並將 'currMax' 值增加 1。
步驟 5 - 如果 'isSecond' 等於 1，並且字元等於 'q'，則將 'isSecond' 更改為 0 並將 'currMax' 值增加 1。
步驟 6 – 如果 p 和 q 不相同，並且 'currMax' 為奇數，則將其值減 1。
步驟 7 – 如果 'maxLen' 小於 'currMax' 變數的值，則更新 'maxLen' 的值。
步驟 8 – 返回 'maxLen' 值。
示例
def maxSubSeqLen(alpha):
# Length of the string
str_len = len(alpha)
maxLen = -1
# Travere the string
for p in range(10):
for q in range(10):
currMax, isSecond = 0, 0
# Find an alternate combination of p and q
for k in range(str_len):
# Finding the p
if (isSecond == 0 and ord(alpha[k]) - ord('0') == p):
isSecond = 1
# Increase the current value by 1
currMax += 1
# Finding q
elif (isSecond == 1 and ord(alpha[k]) - ord('0') == q):
isSecond = 0
# Increase the current value by 1
currMax += 1
# For odd length of resultant subsequence.
if p != q and currMax % 2 == 1:
# Decrease the value of currMax by 1
currMax -= 1
# Get maximum length
maxLen = max(currMax, maxLen)
# Return the answer
return maxLen
# Driver code
alpha = "700980503"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
輸出
The maximum length of subsequence having the same left and right rotations is - 4
時間複雜度 – O(N*10*10) ~ O(N) 用於遍歷字串。
空間複雜度 – O(1)，因為我們不使用額外的空間。
第一種方法在時間上開銷很大，因為我們找到了給定字串的所有子序列。第二種方法是最佳方法之一，因為它具有最低的時間複雜度。程式設計師可以嘗試查詢具有相同左右旋轉的最長子字串以進行更多練習。
74 次檢視
