C++程序 找到左右旋转相同的一个数字的最长子序列

C++程序 找到左右旋转相同的一个数字的最长子序列

给定一个数字字符串 S ,任务是找到具有其左旋等于其右旋的最长子序列的最大长度。

例:

输入: S = “100210601”

输出: 4

解释:

子序列“0000”满足必要条件。

子序列“1010”在左旋和右旋时分别生成字符串“0101”和“0101”。旋转相同。因此,“1010”也满足条件。

因此,这种子序列的最大长度为4。

输入: S = “252525”

输出: 6

解释:

子序列“252525”在左旋和右旋时分别生成字符串“525252”和“525252”。旋转相同。因此,“252525”满足要求的条件。

Naive Approach: 解决问题的最简单方法是生成给定字符串的所有可能子序列,并对于每个子序列检查其左和右旋转是否相等。

时间复杂度: O(2 N * N)

辅助空间: O(N)

Efficient Approach: 优化上述方法的主要观察结果是,子序列应该由一个 单个字符 或由 交替出现的两个字符 形成的偶数长度。

说明:

str = “2424”

字符串的左旋 = “4242”

字符串的右旋 = “4242”

正如我们所看到的,由于数字长度为偶数,有两个字符交替出现,因此给定数字的左旋和右旋是相等的。

str = “24242”

字符串的左旋 = “42422”

字符串的右旋 = “22424”

正如我们所看到的,由于数字长度为奇数,有两个字符交替出现,因此给定数字的左旋和右旋不相等。

执行以下步骤来解决问题:

  • 生成所有可能的两位数字。
  • 对于生成的每个两位数字,检查字符串中两个数字是否交替出现。保持递增的计数器以存储该特定组合的交替子序列的长度。
  • 在字符串的整个遍历之后,检查两个数字是否相等。如果为真,则将 计数器 更新为所需答案。如果两个数字相等,则更新 计数器 或如果计数器为奇数或偶数,则更新为 count-1 答案。
  • 对于所有可能的组合重复以上步骤,并打印得到的最大 计数器

下面是上述方法的实现:

// C++ 程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
 
// 查找具有相等左右旋转的最长子序列的函数
int findAltSubSeq(string s)
{
    // 字符串的长度
    int n = s.size(), ans = INT_MIN;
 
    // 遍历所有可能的组合
    // 一个两位数字
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            int cur = 0, f = 0;
 
            // 检查当前组合出现的交替情况
            for (int k = 0; k < n; k++) {
 
                if (f == 0 and s[k] - '0' == i) {
                    f = 1;
 
                    // 增加当前值
                    cur++;
                }
                else if (f == 1 and s[k] - '0' == j) {
                    f = 0;
 
                    // 增加当前值
                    cur++;
                }
            }
 
            // 如果获得了奇数长度的交替序列
            if (i != j and cur % 2 == 1)
 
                // 缩小到偶数长度
                cur--;
 
            // 更新答案以存储最大值
            ans = max(cur, ans);
        }
    }
 
    // 返回答案
    return ans;
}
 
// 主函数
int main()
{
    string s = "100210601";
    cout << findAltSubSeq(s);
 
    return 0;
}  

输出:

4

时间复杂度: O(N),因为我们使用一个循环遍历N次,所以它将花费O(N)的时间
辅助空间: O(1),因为我们不使用任何额外空间。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例