(1)Valid Anagram
解题思路：
使用一个数组，首先遍历S相应位置加1，然后遍历T，判断此时如果相应位置为零返回FALSE，否则就减一。T遍历完毕后返回true.
代码如下：
public class Solution {
public boolean isAnagram(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
int[] alphabet = new int[26];
for (int i = 0; i < s.length(); i++) {
alphabet[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
if (alphabet[t.charAt(i) - 'a'] == 0) {
return false;
}
alphabet[t.charAt(i) - 'a']--;
}
return true;
}
}
（2）Longest Palindrome
解题思路:
- 这里是要求出最长回文子串的长度，而不是求出最长回文子串
- 当字符串中字符出现次数为偶数时，必然可以加入最长回文子串
- 当字符串中字符出现次数为奇数时，分情况讨论：
- 如果出现次数为大于1的奇数n，则可以加入n-1个对应字符到最长回文子串
- 最终的最长回文子串，最中间还可以加入一个单一字符
- 上面两条合并起来，即可以直接将出现最大奇数次数的字符都加入最长回文子串
- 即if（出现奇数次数的字符数==0），return s.length()
- if(出现奇数次数的字符数!=0),return s.length()- 出现奇数次数的字符数+1
解法一：使用Hashset，偶次数出现的字符可以直接消掉，奇数次出现的字符可以消掉偶数个，剩余一个。如果最终set集合不为空，证明有剩余单个字符只能再加入回文串中一个。代码如下：
public class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashSet<Character> set = new HashSet<Character>();
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (set.contains(s.charAt(i))) {
set.remove(s.charAt(i));
count++;
} else {
set.add(s.charAt(i));
}
}
if (!set.isEmpty()) {
return count*2 + 1;
} else {
return count*2;
}
}
}
注意其中set.contains(),set.add(),set.isEmpty(),s.charAt(i)[取字符]的用法。
解法二：使用一个数组记录下每个字符出现的次数。如果为偶次数，直接加入字符串；如果是不为1的奇数次n，加入字符串中n-1的长度；同时记录只出现一次的字符个数。最后判断如果只出现一次的字符个数不为0，返回结果为字符串长度加一；如果为0 ，返回字符串长度即可。代码如下：
public class Solution {
public int longestPalindrome(String s) {
int[] charStatArray = new int[52];
int oneTimeOddCount = 0;
int evenCount = 0;
for (char ch: s.toCharArray()) {
if (ch >= 97) {
charStatArray[26 + ch - 'a']++;
}
else {
charStatArray[ch - 'A']++;
}
}
for (int cnt: charStatArray) {
if (cnt != 0) {
if (cnt % 2 == 0) {
evenCount += cnt;
} else {
if (cnt == 1) {
oneTimeOddCount++;
}
else {
evenCount += cnt - 1;
oneTimeOddCount++;
}
}
}
}
return oneTimeOddCount > 0 ? 1 + evenCount : evenCount;
}
}
注意：String.toCharArray()作用是将字符串转化为字符数组
(3)Intersection of Two Arrays II
解题思路一：对nums1使用HashMap,(nums[i],i) i里面存的是该字符出现的次数。依次判断nums2中的字符是否出现在nums1,如果出现且当前存在的次数大于0，就将该字符存入结果list中，并将map中的次数减1。最后以数组形式返回list中的结果即可。
代码如下：
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums1.length; i++) {
if (map.containsKey(nums1[i])) {
map.put(nums1[i], map.get(nums1[i]) + 1);
} else {
map.put(nums1[i], 1);
}
}
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums2.length; i++) {
if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
list.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
解题思路二：
1）对数组nums1进行排序；
2）对数组nums2进行排序；
3）遍历数组nums1和nums2中元素，并比较对应的元素，
- 若相等，则将其保存到输出结果中，并变化两个数组对应的索引
- 不等，则变化较小元素对应的索引即可。
代码如下：
public int[] intersect(int[] nums1, int[] nums2){
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList result = new ArrayList();
for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ){
if (nums1[i] == nums2[j]){
result.add(nums1[i]);
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++){
res[i] = (int) result.get(i);
}
return res;
}