笔试强训之每日一题(七)

x33g5p2x  于2022-02-07 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(236)

笔试强训之每日一题(七)

判断是否互为字符重排

题目链接

题目描述

给定两个字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。

示例 1

输入: s1 = “abc”, s2 = "bca"
输出: true

示例 2

输入: s1 = “abc”, s2 = "bad"
输出: false

题目思路

当两个字符串的字符一样时,利用哈希的思想,将s1中对应字符在哈希表中对应位置++,将将s1中对应字符在哈希表中对应位置–,如果最后哈希表中的数组都为0,则确定其中一个字符串的字符重新排列后,能变成另一个字符串。否则不能

题目代码

  1. class Solution {
  2. public:
  3. bool CheckPermutation(string s1, string s2)
  4. {
  5. int arr1[128] = {0};
  6. if(s1.size()!=s2.size())
  7. {
  8. return false;
  9. }
  10. for(int i = 0;i<s1.size();i++)
  11. {
  12. arr1[s1[i]]++;
  13. arr1[s2[i]]--;
  14. }
  15. for(int i = 0;i < 128;i++)
  16. {
  17. if(arr1[i]!=0)
  18. {
  19. return false;
  20. }
  21. }
  22. return true;
  23. }
  24. };

回文排列

题目链接

题目描述

给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。

示例1

输入:"tactcoa"
输出:true(排列有"tacocat"、“atcocta”,等等)

题目思路

当字符串当中有两个或两个以上的奇数次字符时,则该字符串的重新排列不会是回文串,反之则该字符串的重新排列会是回文串,我们同样利用哈希的思想来解决,先统计字符的次数,然后看次数是奇数的有几个,如果有两个或两个以上,则不会是回文串,反之,则会是回文串。

题目代码

  1. class Solution {
  2. public:
  3. bool canPermutePalindrome(string s) {
  4. //哈希
  5. if(s.size() == 0)
  6. {
  7. return false;
  8. }
  9. int arr[128] = {0};
  10. for(int i = 0;i<s.size();i++)
  11. {
  12. arr[s[i]]++;//统计次数
  13. }
  14. int count = 0;
  15. for(int i = 0;i<128;i++)
  16. {
  17. if((arr[i]%2) == 1)//次数是奇数
  18. {
  19. count++;
  20. }
  21. }
  22. return count < 2;
  23. }
  24. };

相关文章