新网站建设ppt,沈阳seo排名优化教程,网站开发设计培训价格,wordpress 手机版 导航题1#xff1a;判定是否互为字符重排
给定两个由小写字母组成的字符串 s1 和 s2#xff0c;请编写一个程序#xff0c;确定其中一个字符串的字符重新排列后#xff0c;能否变成另一个字符串。 输入: s1 abc, s2 bca 输出: true 输入: s1 判定是否互为字符重排
给定两个由小写字母组成的字符串 s1 和 s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。 输入: s1 abc, s2 bca 输出: true 输入: s1 abb, s2 aab 输出: false 解题思路
1.遍历s1构建哈希表记录s1中出现的字符且该字符出现的个数
2. 遍历s2在哈希表中查找s2中的字符是否在s1中出现过
若找到同时哈希表对应的值大于1map[s2[i]]--
若找到同时哈希表对应的值小于1说明当前这个字符在s2中出现的次数比s1中出现的多返回false
若找不到map.find(s2[i])map.end()说明当前字符在s1中没有出现过返回false
源代码如下
class Solution {
public:bool CheckPermutation(string s1, string s2) {unordered_mapchar,int map;if(s1.size()!s2.size()) return false;for(int i0;is1.size();i){map[s1[i]]1;//用哈希表保存s1字符中每个字符出现的次数}for(int i0;is2.size();i){//遍历s2找哈希表中是否存在s2字符串中的每个字符且出现次数是否相同if(map.find(s2[i])map.end()||map[s2[i]]1){return false;}map[s2[i]]--;}return true;}
};
题2回文排列
给定一个字符串编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。 输入tactcoa 输出true排列有tacocat、atcocta等等 输入aa 输出true(aa本身就是回文串) 解题思路 判断回文重排也就是说判断将字符串重排后是否能够组成回文串。
这里我们定义一个sum变量当前字符第一次出现则sum1
当前字符第二次出现则sum-1
将所有字符遍历完后要组成回文串
那么该字符串里每个字符出现的个数要么都是两次例如abbasum11-1-10
要么只有一个字符出现一次其余字符都必须出现两次例如tacocatsum1111-1-1-11
所以跟题1类似我们需要判断字符出现的个数从而判断是否是回文重排 源代码如下
class Solution {
public:bool canPermutePalindrome(string s) {unordered_mapchar,int map;//建立哈希表来保存字符出现的次数int sum0;//起始总和为0for(int i0;is.size();i){//在哈希表中找不到说明是第一次出现则sum1//找到后发现值为-1说明前面已经有该字符两两配对过了所以也就是新的一轮了则sum1if(map.find(s[i])map.end()||map[s[i]]-1){map[s[i]]1;//先给哈希表赋值summap[s[i]];//sum加上当前的值}//剩下的情况就是当前字符出现过一次那么出现第二次时就从sum中-1else{map[s[i]]-1;summap[s[i]];}}//只有sum1/sum0 才能是回文重排return sum1||sum0;}
};
