c++回文数使用vector
时间: 2023-10-23 17:42:46 浏览: 61
#include <iostream>
#include <vector>
using namespace std;
bool isPalindrome(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
if (nums[left] != nums[right]) {
return false;
}
left++;
right--;
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
if (isPalindrome(nums)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
相关问题
c++ 最长回文子串
在 C++ 中找到最长回文子串可以使用动态规划或者中心扩展算法。下面是两种方法的示例代码。
方法一:动态规划
```cpp
#include <iostream>
#include <vector>
std::string longestPalindrome(std::string s) {
int n = s.length();
std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
int start = 0, maxLen = 1;
// 初始化长度为1和2的回文子串
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = true;
start = i;
maxLen = 2;
}
}
// 计算长度大于2的回文子串
for (int len = 3; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
maxLen = len;
}
}
}
return s.substr(start, maxLen);
}
int main() {
std::string s = "babad";
std::cout << longestPalindrome(s) << std::endl;
return 0;
}
```
方法二:中心扩展算法
```cpp
#include <iostream>
std::string expandAroundCenter(std::string s, int left, int right) {
int n = s.length();
while (left >= 0 && right < n && s[left] == s[right]) {
--left;
++right;
}
return s.substr(left + 1, right - left - 1);
}
std::string longestPalindrome(std::string s) {
int start = 0, maxLen = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
std::string s1 = expandAroundCenter(s, i, i);
std::string s2 = expandAroundCenter(s, i, i + 1);
int len1 = s1.length(), len2 = s2.length();
if (len1 > maxLen) {
start = i - len1 / 2;
maxLen = len1;
}
if (len2 > maxLen) {
start = i - len2 / 2 + 1;
maxLen = len2;
}
}
return s.substr(start, maxLen);
}
int main() {
std::string s = "babad";
std::cout << longestPalindrome(s) << std::endl;
return 0;
}
```
这两种方法分别使用了动态规划和中心扩展算法来找到最长回文子串。你可以根据实际情况选择其中一种方法来解决问题。这些示例代码可以在输入字符串 "babad" 的情况下找到最长回文子串。你可以根据需要修改输入字符串来测试代码。
判断回文链表 c++
判断回文链表是一个常见的问题,可以通过以下步骤来实现:
1. 遍历链表,将链表的值存储在一个数组中。
2. 使用双指针法,一个指针从数组的开头开始,另一个指针从数组的末尾开始,逐个比较两个指针指向的值是否相等。
3. 如果两个指针指向的值不相等,则链表不是回文链表;如果两个指针相遇,则链表是回文链表。
下面是C++的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isPalindrome(ListNode* head) {
vector<int> vals;
ListNode* curr = head;
while (curr != NULL) {
vals.push_back(curr->val);
curr = curr->next;
}
int left = 0;
int right = vals.size() - 1;
while (left < right) {
if (vals[left] != vals[right]) {
return false;
}
left++;
right--;
}
return true;
}
int main() {
// 构造一个回文链表:1->2->3->2->1
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(1);
bool result = isPalindrome(head);
cout << "Is the linked list a palindrome? " << (result ? "Yes" : "No") << endl;
return 0;
}
```