题目描述
给定一个正整数数组 a
,任务是计算循环对的数量。循环对是指在进行循环移位操作后,数组中的两个元素能够相等。循环移位操作是将某些数字从数字的末尾移到开头,并将其他数字按顺序向后移动一个位置。
例如,对于数组 a = [13, 5604, 31, 2, 13, 4560, 546, 654, 456]
,输出应为 5
,因为有 5 对循环对,它们在进行循环移位操作后相等。
a[0] = 13
和a[2] = 31
是循环对(i=0
,j=2
)。a[0] = 13
和a[4] = 13
是循环对(i=0
,j=4
)。a[2] = 31
和a[4] = 13
是循环对(i=2
,j=4
)。a[1] = 5604
和a[5] = 4560
是循环对(i=1
,j=5
)。a[6] = 546
和a[7] = 654
是循环对(i=6
,j=7
)。
需要注意以下几点:
- a[6] = 546
和 a[8] = 456
不是循环对,因为 546 只能与其循环移位后的数字 465 和 654 形成循环对。
- a[5] = 4560
和 a[8] = 456
不是循环对,因为它们的位数不同。
代码
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// 检查两个数字是否是循环对
bool isCyclicPair(int src, int target) {
// 将两个数字转换为字符串
string str1 = to_string(src);
string str2 = to_string(target);
unordered_map<char, int> hw, ht;
for (auto c: str1) ht[c]++;
for (auto c: str2) hw[c]++;
// 检查两个字符串的长度是否相等
if (str1.length() != str2.length() || ht != hw) {
return false;
}
// 通过循环移动比较两个字符串
int len = str1.length();
for (int i = 0; i < len; i++) {
// 将第一个字符串的最后一个字符移到开头
char temp = str1[len - 1];
// str1.erase(len - 1, 1);
str1.pop_back();
str1.insert(0, 1, temp);
// 检查两个字符串是否相等
if (str1 == str2) {
return true;
}
}
return false;
}
int main() {
vector<int> nums = {13, 5604, 31, 2, 13, 4560, 546, 654, 4561};
int res = 0;
for (int i = 0; i < nums.size() - 1; i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (isCyclicPair(nums[i], nums[j])) res++;
else continue;
}
}
cout << "The numbers are cyclic pairs = " << res << endl;
return 0;
}