C++ 中可重新排列形成回文子数组的计数


给定一个整数元素数组,任务是计算可以从给定数组中形成的子数组的数量,使得其元素可以形成一个有效的回文。回文是从开头到结尾排列方式相同的序列。

输入 − int arr[] = { 3, 3, 1, 4, 2, 1, 5}

输出 − 可重新排列形成回文的子数组数量为 − 9

解释 − 元素可以排列成回文的有效子数组为 {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1, 2, 1} 和 {1, 3, 1}。因此,总数为 9。

输入 − int arr[] = { 2, 5, 5, 2, 1}

输出 − 可重新排列形成回文的子数组数量为 − 8

解释 − 元素可以排列成回文的有效子数组为 {2}, {5}, {5}, {2}, {1}, {5, 2, 5}, {2, 5, 2}, {2, 5, 5, 2}。因此,总数为 8。

下面程序中使用的方案如下

  • 输入一个整数元素数组,并计算数组的大小,并将数据传递给函数以进行进一步处理。

  • 声明一个临时变量 count 来存储回文子数组。

  • 从 0 到数组大小开始 FOR 循环

  • 在循环内部,声明一个 long long 类型的变量并将其设置为 1LL << arr[j],并将 temp 设置为 temp ^ val

  • 在布尔变量内部调用一个函数,该函数将返回 true 或 false。

  • 检查 IF temp 为 0LL 或 ch 为 True,则将 count 加 1

  • 返回 count

  • 打印结果。

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
bool check(long long temp){
   return !(temp & (temp - 1LL));
}
int palindromes_rearrange(int arr[], int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      long long temp = 0LL;
      for (int j = i; j < size; j++){
         long long val = 1LL << arr[j];
         temp = temp ^ val;
         bool ch = check(temp);
         if (temp == 0LL || ch){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 3, 1, 4, 2, 1, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub-arrays whose elements can be re-arranged to form palindromes are:
"<<palindromes_rearrange(arr, size);
   return 0;
}

输出

如果我们运行以上代码,它将生成以下输出:

Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9

更新于: 2020-12-02

224 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告