摘要:为了不让字符串越界,特别在循环里面再次添加了条件函数判断一个字符是否是字母或者十进制数字,若为字母和数字则返回真,否则返回否函数把字符转换成小写字母,非字母字符不做出处理。我一时半会是搞不定了,但如果是哈希的话,还是可以接受这种思路
向大家推荐一下我们的社区:万人千题
同时向大家推荐一下我们社区几位大佬的主页
英雄哥
磊哥
解题者大佬
思路:只有当字符个数奇数个的情况最多有一个时,才会形成回文字符串
</>复制代码
class Solution {public: bool canPermutePalindrome(string s) { int res = 0; unordered_map<char, int> map; for(auto &c : s) { map[c]++; } for(auto &c : map) { if(c.second&1) res++; } return res <= 1; }};
思路:在左指针比右指针小的前提下,比较左右指针所指的值是否相等,同时在比较的时候使用isalnum()和tolower()函数。为了不让字符串越界,特别在循环里面再次添加了left
isalnum()函数:判断一个字符是否是字母或者十进制数字,若为字母和数字则返回真,否则返回否
tolower()函数:把字符转换成小写字母,非字母字符不做出处理。
方法一:双指针
</>复制代码
class Solution {public: bool isPalindrome(string s) { //双指针 int left = 0, right = s.size()-1; while(left < right) { while(left < right && !isalnum(s[left])) { ++left; } while(left < right && !isalnum(s[right])) { --right; } if(tolower(s[left]) != tolower(s[right])) { return false; } ++left; --right; } return true; }};
方法二:使用库函数
思路:新建一个字符串与字符串一相等,使用reverse函数反转字符,与之比较
</>复制代码
class Solution {public: bool isPalindrome(string s) { string str1; for(char &i : s) { if(isalnum(i)) { str1 += tolower(i); } } string str2=str1; reverse(str1.begin(), str1.end()); return str1 == str2; }};
思路:使用上词学到的哈希映射来解决问题,然后利用
if判断条件(map[c - ‘A’] & 1) 是否为 0
来判断该字母个数达到偶数,若为偶数,则res+2
</>复制代码
class Solution {public: int longestPalindrome(string s) { int res = 0; unordered_map<char, int>map; for(char &c : s) { map[c - "A"]++; if((map[c - "A"] & 1) == 0) { res += 2; } } return res == s.size() ? res : res+1; }};
思路:左右双指针,比较左右指针所指的值,直到左右指针交叉重合
</>复制代码
class Solution {public: bool validPalindrome(string s) { int left = 0, right = s.size()-1; while(left<right && s[left] == s[right]) { ++left; --right; } return Palindrom(s, left+1, right) || Palindrom(s, left, right-1); } bool Palindrom(const string& s, int left, int right) { while(left < right && s[left] == s[right]) { ++left; --right; } return left >= right; }};
与第五题相同
思路:主要是题目有点绕,删除的是回文子序列,不是子字符串
所以一共有三种情况:
空字符返回0,回文返回1,否则一次全部删a,一次全部删b,返回2
</>复制代码
class Solution {public: int removePalindromeSub(string s) { if(s.size() == 0) return 0; for(int left=0, right=s.size()-1; left<right; left++, right--) { if(s[left] != s[right]) { return 2; } } return 1; }};
思路:就是将字符串正序和逆序转换为base进制的数,然后比较两个数取模后是否相等,如果相等,表示两个字符串相等。
KMP我一时半会是搞不定了,但如果是哈希的话,还是可以接受这种思路
</>复制代码
class Solution {public: string shortestPalindrome(string s) { int n = s.size(); int base = 131, mod = 1000000007; int left = 0, right = 0, mul = 1; int best = -1; for (int i = 0; i < n; ++i) { left = ((long long)left * base + s[i]) % mod; right = (right + (long long)mul * s[i]) % mod; if (left == right) { best = i; } mul = (long long)mul * base % mod; } string add = (best == n - 1 ? "" : s.substr(best + 1, n)); reverse(add.begin(), add.end()); return add + s; }};
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123494.html
摘要:三结对编程排位赛四个人为一组,由队长带队刷题,每周根据这周四个人的刷题总数进行队伍间排名。万人千题结对编程排位赛如果想参加的第二期的同学,可以先联系作者加群,看看第一期的同袍是如何奋斗的。 ...
阅读 923·2021-11-16 11:45
阅读 2130·2021-10-09 09:44
阅读 1346·2019-08-30 14:03
阅读 1132·2019-08-26 18:28
阅读 3332·2019-08-26 13:50
阅读 1719·2019-08-23 18:38
阅读 3455·2019-08-23 18:22
阅读 3595·2019-08-23 15:27