LeetCode刷題總結(jié)
1. 有效的字母異位詞
給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的一個(gè)字母異位詞嗜傅。
示例 1
輸入: s = "anagram", t = "nagaram"
輸出: true示例 2
輸入: s = "anagram", t = "nagaram"
輸出: true說(shuō)明
你可以假設(shè)字符串只包含小寫(xiě)字母。
進(jìn)階
如果輸入字符串包含 unicode 字符怎么辦憔儿？你能否調(diào)整你的解法來(lái)應(yīng)對(duì)這種情況医清？
我的思路與解答（6ms）：
class Solution {
public boolean isAnagram(String s, String t) {
// 先判斷字符串長(zhǎng)度是否相等，如果不相等則直接返回false
if(s.length() != t.length()){
return false;
}
// 將字符串轉(zhuǎn)為char類(lèi)型數(shù)組铺罢，并排序
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
Arrays.sort(sc);
Arrays.sort(tc);
// 排序后從第一個(gè)char開(kāi)始對(duì)比艇挨，若有不同則直接返回false
for(int i = 0; i < sc.length; i++){
if(sc[i] != tc[i]){
return false;
}
}
// 默認(rèn)返回true
return true;
}
}
別人的解答（4ms）：
class Solution {
public boolean isAnagram(String s, String t) {
// 定義一個(gè)int類(lèi)型數(shù)組，長(zhǎng)度為26即26個(gè)字母韭赘，用于記錄 s中出現(xiàn)的次數(shù) - t中出現(xiàn)的次數(shù)
int []chars = new int[26];
// 先記錄s中每個(gè)字母出現(xiàn)次數(shù)
for(char c : s.toCharArray()){
chars[c-'a']++;
}
// 再將t中每個(gè)字母出現(xiàn)的次數(shù)扣除
for(char c: t.toCharArray()){
chars[c-'a']--;
}
// 如果這個(gè)字母的記錄值為0缩滨，則s和t中出現(xiàn)的次數(shù)一樣，反之次數(shù)不一樣，也就是兩個(gè)字符串不是有效的字母異位詞
for(int i : chars){
if( i != 0){
return false;
}
}
return true;
}
}
小結(jié)：
我的辦法是利用了Arrays.sort()方法脉漏，思路比較簡(jiǎn)單苞冯，相同的字符串排序后肯定所有字符的順序一定是一樣的，所以只需排序后對(duì)比各個(gè)字符侧巨，性能較差舅锄。
而別人的解答，思路較為不同刃泡，是統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)巧娱，進(jìn)行對(duì)比，沒(méi)有用到Arrays.sort()方法烘贴，性能較好一些。
2. 驗(yàn)證回文字符串
給定一個(gè)字符串撮胧，驗(yàn)證它是否是回文串桨踪，只考慮字母和數(shù)字字符，可以忽略字母的大小寫(xiě)芹啥。
說(shuō)明
本題中锻离，我們將空字符串定義為有效的回文串。
示例 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將不是字母或者數(shù)字的字符刪除墓怀，并將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母
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'){
// 小寫(xiě)字母unicode碼比大寫(xiě)的大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();
// 從第一個(gè)與最后一個(gè)進(jìn)行循環(huán)對(duì)比
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) {
// 若字符串為空或者內(nèi)容為空則直接返回true
if(s == null || s.length() == 0) return true;
// 聲明兩個(gè)int類(lèi)型的變量用來(lái)標(biāo)記第一個(gè)字母和最后一個(gè)字母
int start = 0;
int end = s.length() - 1;
// 判斷字母是否是數(shù)字或者字母汽纠，如果不是則指向下一個(gè)字符，并將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母
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--;
}
}
// 進(jìn)行對(duì)比
if(start < end) {
if(c != b) {
return false;
}
start++;
end--;
}
}
return true;
}
}
小結(jié)：
我的辦法是利用了StringBuffer傀履，將不是數(shù)字與字母的刪除虱朵，并將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母，再進(jìn)行對(duì)比钓账。
而別人的解答碴犬，用了兩個(gè)變量來(lái)標(biāo)記要對(duì)比的兩個(gè)字母的位置，所以少了刪除的操作梆暮，并且沒(méi)有用到StringBuffer服协，性能比我的解答大大提高。
3. 總結(jié)
從這兩題來(lái)看啦粹，我的算法知識(shí)還比較差偿荷，特別是第二題，花費(fèi)了較多的性能去做了沒(méi)必要的操作唠椭，要學(xué)會(huì)靈活使用變量來(lái)標(biāo)記位置跳纳，不過(guò)整體思路還算清晰，需要繼續(xù)努力泪蔫。
4. 最后
歡迎來(lái)看我的博客 RoNnx的博客
