有没有一种方法可以计算镜像时相同的最长子字符串或子列表

Question

所以我需要找到可以镜像的最长子列表，知道元素 ex 的数量：n = 5my_list = [1,2,3,2,1]这是我的代码：n = int(input())my_list = list(map(int, input().split()))c = 0s1 = my_listx = 0i = 0while i < n:    s2 = s1[i:]    if s2 == s2[::-1]:        if c <= len(s2):            c = len(s2)    if i >= n-1:        i = 0        n = n - 1        s1 = s1[:-1]    i += 1print(c)正如我们所看到的，镜像时列表是相同的，但是当结果不是预期的n = 10时。my_list = [1,2,3,2,1,332,6597,6416,614,31]35

Answer 1

我的解决方案是将每次迭代中的数组拆分为左数组和右数组，然后反转左数组。接下来，比较每个数组中的每个元素，并在元素相同时将长度变量加一。

def longest_subarr(a):

    longest_exclude = 0

    for i in range(1, len(a) - 1):

        # this excludes a[i] as the root

        left = a[:i][::-1]

        # this also excludes a[i], needs to consider this in calculation later

        right = a[i + 1:] 

        max_length = min(len(left), len(right))

        length = 0

        while(length < max_length and left[length] == right[length]):

            length += 1

        longest_exclude = max(longest_exclude, length)

    # times 2 because the current longest is for the half of the array

    # plus 1 to include to root

    longest_exclude = longest_exclude * 2 + 1

    longest_include = 0

    for i in range(1, len(a)):

        # this excludes a[i] as the root

        left = a[:i][::-1]

        # this includes a[i]

        right = a[i:] 

        max_length = min(len(left), len(right))

        length = 0

        while(length < max_length and left[length] == right[length]):

            length += 1

        longest_include = max(longest_include, length)

    # times 2 because the current longest is for the half of the array

    longest_include *= 2

    return max(longest_exclude, longest_include)

    

print(longest_subarr([1, 4, 3, 5, 3, 4, 1]))

print(longest_subarr([1, 4, 3, 5, 5, 3, 4, 1]))

print(longest_subarr([1, 3, 2, 2, 1]))

这涵盖了奇数长度子数组[a, b, a]和偶数长度子数组的测试用例[a, b, b, a]。

Answer 2

由于您需要可以镜像的最长序列，因此这里有一个简单的 O(n^2) 方法。

转到每个索引，以它为中心，如果数字相等，则向左和向右扩展，一次一步。否则中断，并移动到下一个索引。

def longest_mirror(my_array): 

    maxLength = 1

  

    start = 0

    length = len(my_array) 

  

    low = 0

    high = 0

  

    # One by one consider every character as center point of mirrored subarray

    for i in range(1, length): 

    # checking for even length subarrays

        low = i - 1

        high = i 

        while low >= 0 and high < length and my_array[low] == my_array[high]: 

            if high - low + 1 > maxLength: 

                start = low 

                maxLength = high - low + 1

            low -= 1

            high += 1

  

        # checking for even length subarrays

        low = i - 1

        high = i + 1

        while low >= 0 and high < length and my_array[low] == my_array[high]: 

            if high - low + 1 > maxLength: 

                start = low 

                maxLength = high - low + 1

            low -= 1

            high += 1

  

    return maxLength