LeetCode刷题总结
1. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1
输入: s = "anagram", t = "nagaram"
输出: true示例 2
输入: s = "anagram", t = "nagaram"
输出: true说明
你可以假设字符串只包含小写字母。
进阶
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
我的思路与解答（6ms）：
class Solution {
public boolean isAnagram(String s, String t) {
// 先判断字符串长度是否相等，如果不相等则直接返回false
if(s.length() != t.length()){
return false;
}
// 将字符串转为char类型数组，并排序
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
Arrays.sort(sc);
Arrays.sort(tc);
// 排序后从第一个char开始对比，若有不同则直接返回false
for(int i = 0; i < sc.length; i++){
if(sc[i] != tc[i]){
return false;
}
}
// 默认返回true
return true;
}
}
别人的解答（4ms）：
class Solution {
public boolean isAnagram(String s, String t) {
// 定义一个int类型数组，长度为26即26个字母，用于记录 s中出现的次数 - t中出现的次数
int []chars = new int[26];
// 先记录s中每个字母出现次数
for(char c : s.toCharArray()){
chars[c-'a']++;
}
// 再将t中每个字母出现的次数扣除
for(char c: t.toCharArray()){
chars[c-'a']--;
}
// 如果这个字母的记录值为0，则s和t中出现的次数一样，反之次数不一样，也就是两个字符串不是有效的字母异位词
for(int i : chars){
if( i != 0){
return false;
}
}
return true;
}
}
小结：
我的办法是利用了Arrays.sort()方法，思路比较简单，相同的字符串排序后肯定所有字符的顺序一定是一样的，所以只需排序后对比各个字符，性能较差。
而别人的解答，思路较为不同，是统计各个字符出现的次数，进行对比，没有用到Arrays.sort()方法，性能较好一些。
2. 验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明
本题中，我们将空字符串定义为有效的回文串。
示例 1
输入: "A man, a plan, a canal: Panama"
输出: true示例 2
输入: "race a car"
输出: false
我的思路与解答（218 ms）：
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sb = new StringBuffer(s);
// 利用StringBuffer将不是字母或者数字的字符删除，并将大写字母转换为小写字母
for(int i = 0; i < sb.length(); i++){
if(sb.charAt(i) >= '0' && sb.charAt(i) <= '9'){
continue;
}
if(sb.charAt(i) >= 'A' && sb.charAt(i) <= 'Z'){
// 小写字母unicode码比大写的大32
sb.setCharAt(i, (char)(sb.charAt(i) + 32));
continue;
}
if(sb.charAt(i) < 'a' || sb.charAt(i) > 'z'){
sb.delete(i, i+1);
i--;
}
}
char[] sc = sb.toString().toCharArray();
// 从第一个与最后一个进行循环对比
for(int i = 0; i < sc.length/2; i++){
if(sc[i] != sc[sc.length - i -1]){
return false;
}
}
return true;
}
}
别人的解答（3ms）：
class Solution {
public boolean isPalindrome(String s) {
// 若字符串为空或者内容为空则直接返回true
if(s == null || s.length() == 0) return true;
// 声明两个int类型的变量用来标记第一个字母和最后一个字母
int start = 0;
int end = s.length() - 1;
// 判断字母是否是数字或者字母，如果不是则指向下一个字符，并将大写字母转换为小写字母
while(start < end) {
char c = ' ';
while(start < end) {
c = s.charAt(start);
if(c >= 'a' && c <= 'z') {
break;
} else if(c >= '0' && c <= '9') {
break;
} else if(c >= 'A' && c <= 'Z') {
c = (char) (c - 'A' + 'a');
break;
} else {
start++;
}
}
char b = ' ';
while(start < end) {
b = s.charAt(end);
if(b >= 'a' && b <= 'z') {
break;
} else if(b >= '0' && b <= '9') {
break;
} else if(b >= 'A' && b <= 'Z') {
b = (char) (b - 'A' + 'a');
break;
} else {
end--;
}
}
// 进行对比
if(start < end) {
if(c != b) {
return false;
}
start++;
end--;
}
}
return true;
}
}
小结：
我的办法是利用了StringBuffer，将不是数字与字母的删除，并将大写字母转换为小写字母，再进行对比。
而别人的解答，用了两个变量来标记要对比的两个字母的位置，所以少了删除的操作，并且没有用到StringBuffer，性能比我的解答大大提高。
3. 总结
从这两题来看，我的算法知识还比较差，特别是第二题，花费了较多的性能去做了没必要的操作，要学会灵活使用变量来标记位置，不过整体思路还算清晰，需要继续努力。
4. 最后
欢迎来看我的博客 RoNnx的博客
