极客笔记Python3程序，用于找到具有相同左右旋转的数字的最长子序列
在这个问题中，我们将找到给定字符串的最长子序列的长度，使其具有相同的左右旋转。
我们可以通过找到给定字符串的所有子序列，并检查特定的子序列是否具有相同的左右旋转来解决这个问题。另一种方法是观察得出，只有包含单个字符或交替字符并且左边是偶数的字符串才能具有相同的左右旋转。
问题陈述 - 我们给定一个仅包含数字的alpha字符串。我们需要找到字符串的最长子序列的大小，该子序列具有相同的左右旋转。
样例示例
输入
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值，如果它小于子序列的长度。
步骤 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(N1010) ~ O(N) 用于遍历字符串。
空间复杂度 – O(1) 因为我们不使用额外的空间。
第一种方法是时间消耗较多的方法，因为我们找到了给定字符串的所有子序列。第二种方法是最佳方法之一，因为它具有最低的时间复杂度。程序员可以尝试找到具有相同左右旋转的最长子字符串以进行更多练习。