首页 > 代码库 > Continue To DO！

Continue To DO！

2024-08-26 14:08:42   265人阅读

(1)Valid Anagram

技术分享

解题思路：

使用一个数组，首先遍历S相应位置加1，然后遍历T，判断此时如果相应位置为零返回FALSE，否则就减一。T遍历完毕后返回true.

代码如下：

技术分享 
 1 public class Solution {
 2     public boolean isAnagram(String s, String t) {
 3         if (s == null || t == null || s.length() != t.length()) {
 4             return false;
 5         }
 6         int[] alphabet = new int[26];
 7         for (int i = 0; i < s.length(); i++) {
 8             alphabet[s.charAt(i) - ‘a‘]++;
 9         }
10         for (int i = 0; i < t.length(); i++) {
11             if (alphabet[t.charAt(i) - ‘a‘] == 0) {
12                 return false;
13             }
14             alphabet[t.charAt(i) - ‘a‘]--;
15         }
16         return true;
17     }
18 }
View Code

（2）Longest Palindrome

技术分享

解题思路:

  • 这里是要求出最长回文子串的长度，而不是求出最长回文子串
  • 当字符串中字符出现次数为偶数时，必然可以加入最长回文子串
  • 当字符串中字符出现次数为奇数时，分情况讨论：
  • 如果出现次数为大于1的奇数n，则可以加入n-1个对应字符到最长回文子串
  • 最终的最长回文子串，最中间还可以加入一个单一字符
  • 上面两条合并起来，即可以直接将出现最大奇数次数的字符都加入最长回文子串
  • 即if（出现奇数次数的字符数==0），return s.length()
  • if(出现奇数次数的字符数!=0),return s.length()- 出现奇数次数的字符数+1

解法一：使用Hashset，偶次数出现的字符可以直接消掉，奇数次出现的字符可以消掉偶数个，剩余一个。如果最终set集合不为空，证明有剩余单个字符只能再加入回文串中一个。代码如下：

技术分享 
 1 public class Solution {
 2     public int longestPalindrome(String s) {
 3         if (s == null || s.length() == 0) {
 4             return 0;
 5         }
 6         HashSet<Character> set = new HashSet<Character>();
 7         int count = 0;
 8         for (int i = 0; i < s.length(); i++) {
 9             if (set.contains(s.charAt(i))) {
10                 set.remove(s.charAt(i));
11                 count++;
12             } else {
13             set.add(s.charAt(i));
14             }
15         }
16         if (!set.isEmpty()) {
17             return count*2 + 1;
18         } else {
19             return count*2;
20         }
21         
22     }
23 }
View Code

注意其中set.contains(),set.add(),set.isEmpty(),s.charAt(i)[取字符]的用法。

解法二：使用一个数组记录下每个字符出现的次数。如果为偶次数，直接加入字符串；如果是不为1的奇数次n，加入字符串中n-1的长度；同时记录只出现一次的字符个数。最后判断如果只出现一次的字符个数不为0，返回结果为字符串长度加一；如果为0 ，返回字符串长度即可。代码如下：

技术分享 
 1 public class Solution {
 2     public int longestPalindrome(String s) {
 3         int[] charStatArray = new int[52];
 4         int oneTimeOddCount = 0;
 5         int evenCount = 0;
 6     
 7         for (char ch: s.toCharArray()) {
 8             if (ch >= 97) {
 9                 charStatArray[26 + ch - ‘a‘]++;
10             }
11             else {
12                 charStatArray[ch - ‘A‘]++;
13             }
14         }
15     
16         for (int cnt: charStatArray) {
17             if (cnt != 0) {
18                 if (cnt % 2 == 0) {
19                     evenCount += cnt;
20                 } else {
21                     if (cnt == 1) {
22                         oneTimeOddCount++;
23                     }
24                     else {
25                         evenCount += cnt - 1;
26                         oneTimeOddCount++;
27                     }
28                 }
29             }
30         }
31     
32         return oneTimeOddCount > 0 ? 1 + evenCount : evenCount;
33     }
34 }
View Code

（3）

Continue To DO！


联系
我们