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
广告