算法 | 第1章 數(shù)組與字符串相關(guān)《程序員面試金典》

前言

本系列筆記主要記錄筆者刷《程序員面試金典》算法的一些想法與經(jīng)驗總結(jié)，按專題分類，主要由兩部分構(gòu)成：經(jīng)驗值點和經(jīng)典題目。其中重點放在經(jīng)典題目上；

0. *經(jīng)驗總結(jié)

0.1 程序員面試金典 P76

  • 數(shù)組問題與字符串問題往往是相通的；
  • 散列表是一種通過將鍵（key）映射為值（value）從而實現(xiàn)快速查找的數(shù)據(jù)結(jié)構(gòu)；
  • 可變長度數(shù)組ArrayList插入N個元素總計用時為O(N)，平均每次插入操作用時O(1)；
  • 拼接n個長度為x字符串，直接使用String的+用時O( n2)；而StringBuilder可以避免此問題，它會創(chuàng)建一個足以容納所有字符串的可變長度數(shù)組；
  • Java的字符串是不可變長度的，如果要改變長度，可以轉(zhuǎn)成數(shù)組或使用StringBuilder；
  • 一般而言字符串的處理離不開集合，尤其是Map類型的集合；

0.2 ACSII碼總結(jié)

ACSII編碼 常用字符
48 0
57 9
65 A
90 Z
97 a
122 z

0.3 String的一些易忘的API

完整API請參考：個人總結(jié)的Java常用API手冊匯總

構(gòu)造方法:

  • String(byte[] bytes, int offset, int length)：通過使用平臺的默認(rèn)字符集解碼指定的 byte 子數(shù)組，構(gòu)造一個新的 String。//把字節(jié)數(shù)組的一部分轉(zhuǎn)換為字符串。

  • String(char[] value, int offset, int count)：分配一個新的 String，它包含取自字符數(shù)組參數(shù)一個子數(shù)組的字符。//把字符數(shù)組的一部分轉(zhuǎn)換為字符串。

    把字節(jié)/字符數(shù)組的一部分轉(zhuǎn)換為字符串 offset:數(shù)組的開始索引 length:轉(zhuǎn)換的字節(jié)個數(shù) count:轉(zhuǎn)換的字符個數(shù)

判斷功能的方法:

  • boolean equalsIgnoreCase(String anotherString)：將此字符串與指定對象進(jìn)行比較，忽略大小寫。

獲取功能的方法:

  • String concat(String str)：將指定的字符串連接到該字符串的末尾。
  • char charAt(int index)：返回指定索引處的char值。
  • int indexOf(String str)：返回指定子字符串第一次出現(xiàn)在該字符串內(nèi)的索引。
  • String substring(int beginIndex)：返回一個子字符串，從beginIndex開始截取字符串到字符串結(jié)尾。
  • String substring(int beginIndex, int endIndex)：返回一個子字符串，從beginIndex到endIndex截取字符串。含beginIndex，不含endIndex。

轉(zhuǎn)換功能的方法:

  • char[] toCharArray()：將此字符串轉(zhuǎn)換為新的字符數(shù)組。

  • byte[] getBytes()：使用平臺的默認(rèn)字符集將該String編碼轉(zhuǎn)換為新的字節(jié)數(shù)組。

  • String replaceAll(String regex, String replacement)：成功則返回替換的字符串，失敗則返回原始字符串。其中regex為匹配此字符串的正則表達(dá)式；replacement為用來替換每個匹配項的字符串。

  • String replace(CharSequence target, CharSequencere placement)：將與target匹配的字符串使用replacement字符串替換。

    CharSequence是一個接口，也是一種引用類型。作為參數(shù)類型，可以把String對象傳遞到方法中。

分割功能的方法:

  • String[] split(String regex)：將此字符串按照給定的regex（規(guī)則）拆分為字符串?dāng)?shù)組。

    split方法的參數(shù)其實是一個“正則表達(dá)式”，如果按照英文句點“.”進(jìn)行切分，必須寫"\."。

將基本數(shù)據(jù)型態(tài)轉(zhuǎn)換成String的static方法：

  • String.valueOf(Object o) : 將 Object 變量 o 轉(zhuǎn)換成字符串，等于 obj.toString()。

    Object可以是： char、char[]、double、float等。

  • String.valueOf(char[] data, int offset, int count) : 將 char 數(shù)組 data 中 由 data[offset] 開始取 count 個元素 轉(zhuǎn)換成字符串。

將String轉(zhuǎn)換成基本數(shù)據(jù)型態(tài)的方法（Character除外）：

  • static Object parseObject(String s)：將字符串參數(shù)轉(zhuǎn)換為對應(yīng)的byte基本類型。

    Object可以是： byte、short、int、long、float、double、boolean等。

0.4 可以對字符串的字符先進(jìn)行排序

  • Arrays.sort(int[] a, int fromIndex, int toIndex)：對數(shù)組部分排序，也就是對數(shù)組a的下標(biāo)從fromIndex到toIndex-1的元素排序；如果要從大到小需要實現(xiàn)Comparator接口；

  • Arrays.sort(obj)：可以對obj對象排序；

    obj對象一般是數(shù)組，包括各種數(shù)組；

0.5 使用Map來統(tǒng)計每個字符出現(xiàn)次數(shù)（記住即可）

private Map<Character, Integer> getMap(String str) {
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = str.toCharArray();
    for (char aChar : chars) {
        map.put(aChar, map.getOrDefault(aChar, 0) + 1);
    }
    return map;
}

0.6 遍歷Map的四種方式

主要就兩種方法：

  • 第一種是通過keySet()方法獲得key，再通過map.get(key)方法，得到值；
  • 第二種是先用entrySet()方法轉(zhuǎn)為Set類型，其中set的每一個元素值就是map的一個鍵值對，即Map.Entry<K,V>；
//方法一：普通的foreach循環(huán)，使用keySet()方法，遍歷key
for(Integer key : map.keySet()){
    System.out.println("key = " + key);
    System.out.println("Value = " + map.get(key));
}

//方法二：把所有的鍵值對裝入迭代器中，然后遍歷迭代器
Iterator<Map.Entry<Integer,String>> it = map.entrySet().iterator();
    while(it.hasNext()){
        Map.Entry<Integer,String> entry=it.next();
        System.out.println("key = "+entry.getKey());
        System.out.println("Value = "+entry.getValue());
}

//方法三：分別得到key和value
for(Integer obj : map.keySet()){
    System.out.println("key = " + obj);
}
for(String obj : map.values()){
    System.out.println("value = " + obj);
}

//方法四，entrySet()方法
Set<Map.Entry<Integer,String>> entries=map.entrySet();
for (Map.Entry entry:entries){
    System.out.println("key = " + entry.getKey());
    System.out.println("value = " + entry.getValue());
}

0.7 獲取字符串字符的兩種方式

  • 遍歷字符串時char[] c = S.toCharArray()的索引效率更高；
  • 通過s.charAt(i)方法索引多了方法棧和越界檢查的消耗；


1. 判斷字符是否唯一 [easy]

判斷字符是否唯一

1.1 考慮點

  • 字符是否為26個英文字母；
    • 如果是，可以先判斷如果字符長度>26, 直接返回False；
  • 是否為ASCII字符集；
    • 如果是ASCII，考慮邊界檢查，判斷是否超過ASCII字符集范圍（0~128，擴展為255）；
    • 如果是unicode，沒有字符范圍，需要擴大存儲空間，可以先排序再判斷；
  • 是否允許修改字符串；
    • 如果允許，可以先在O(nlog(n))的時間復(fù)雜度內(nèi)對字符串排序，然后線性檢查有無相鄰字符完全相同；
  • 大小寫算不算相同；

1.2 解法

1.2.1 使用HashMap統(tǒng)計字符次數(shù)

public boolean isUnique(String astr) {
    Map<Character, Integer> map = new HashMap<>();
    for(int i = 0; i < astr.length(); i++ ){
        if(map.containsKey(astr.charAt(i))){
            return false;
        }
        map.put(astr.charAt(i), i);
    }
    return true;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：69.76%；

1.2.2 利用boolean數(shù)組（優(yōu)）

  • 需要知道需要判斷的字符范圍；
public boolean isUnique(String astr) {
    if( astr.length() > 128 ){
        return true;
    }
    boolean[] arr = new boolean[128];
    for (int i = 0; i < astr.length(); i++) {
        int c = (int)astr.charAt(i);
        if ( arr[c] ){
            return false;
        }
        arr[c] = true;
    }
    return true;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：69.76%；
  • 時間復(fù)雜度：O(n)；或者O(1)，因為for循環(huán)迭代不會超過128次；
  • 空間復(fù)雜度：O(1)

1.2.3 位運算符（優(yōu)）

public boolean isUnique(String astr) {
    int mark = 0;
    for (int i = 0; i < astr.length() ; i++) {
        //移動距離
       int move = (int)astr.charAt(i) - 'a';
       if ((mark & (1<< move) )!=0){
           return false;
       }else {
           mark |=(1<<move);
       }
    }
    return true;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：63.69%；
  • 時間復(fù)雜度：O(n)
  • 空間復(fù)雜度：O(1)

1.2.4 雙循環(huán)

  • 雙循環(huán)開銷O(n2)，不推薦；
public boolean isUnique(String astr) {
    if( astr == null || "".equals(astr)){
        return true;
    }
    int left = 0;
    int rigth = astr.length();
    for(int i = 0; i < astr.length(); i++){
        for(int j = i+1; j < astr.length(); j++){
            if(astr.charAt(i) == astr.charAt(j)){
                return false;
            }
        }
    }
    return true;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：65.16%；
  • 時間復(fù)雜度：O(n2)
  • 空間復(fù)雜度：O(1)


2. 判定是否互為字符重排 [easy]

判定是否互為字符重排

2.1 考慮點

  • 詢問面試官是否可以更改s1和s2的值；
  • 問清楚變位詞是否區(qū)分大小寫（如Dog和dog）；
  • 是否考慮空白字符；

2.2 解法

2.2.1 先排序后比較

public boolean CheckPermutation(String s1, String s2) {
    // 將字符串轉(zhuǎn)換成字符數(shù)組
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();
    // 對字符數(shù)組進(jìn)行排序
    Arrays.sort(c1);
    Arrays.sort(c2);
    // 再將字符數(shù)組轉(zhuǎn)換成字符串，比較是否相等
    return new String(c1).equals(new String(c2));
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：35.67%；
  • JDK中Arrays.sort排序：JDK7以后，對應(yīng)基本變量數(shù)組采用變異的快速排序方法DualPivotQuicksort，對于對象數(shù)組比較由原來的mergeSort改為ComparableTimSort方法，TimSort當(dāng)數(shù)組大小小于32時，采用二分插入排序算法；當(dāng)大于32時，采用基于塊-區(qū)run的歸并排序。所以TimSort是一種二分插入排序和歸并排序的變種算法。對對象進(jìn)行排序，沒有采用快速排序，是因為快速排序是不穩(wěn)定的，而Timsort是穩(wěn)定的。與其他合并排序一樣，Timesrot是穩(wěn)定的排序算法，最壞時間復(fù)雜度是O(nlogn)。在最壞情況下，Timsort算法需要的臨時空間是n/2，在最好情況下，它只需要一個很小的臨時存儲空間；
  • 方法不算最優(yōu)，但勝在清晰、簡單易懂，不失為一種上佳之選；

2.2.2 HashMap計數(shù)（優(yōu)）

public boolean CheckPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    char[] s1Chars = s1.toCharArray();
    Map<Character, Integer> s1Map = getMap(s1);
    Map<Character, Integer> s2Map = getMap(s2);
    for (char s1Char : s1Chars) {
        if (!s2Map.containsKey(s1Char) || s2Map.get(s1Char) != s1Map.get(s1Char)) {
            return false;
        }
    }
    return true;
}
// 統(tǒng)計指定字符串str中各字符的出現(xiàn)次數(shù)，并以Map的形式返回
private Map<Character, Integer> getMap(String str) {
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = str.toCharArray();
    for (char aChar : chars) {
        map.put(aChar, map.getOrDefault(aChar, 0) + 1);
    }
    return map;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：62.49%；
  • 時間復(fù)雜度：O(n)；
  • 空間復(fù)雜度：O(1)；

2.2.3 桶計數(shù)法

用數(shù)組來統(tǒng)計每個字符的出現(xiàn)次數(shù)；

public boolean CheckPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    int[] c1 = count(s1);
    int[] c2 = count(s2);
    for (int i = 0; i < c1.length; i++) {
        if (c1[i] != c2[i]) {
            return false;
        }
    }
    return true;
}
private int[] count(String str) {
    int[] c = new int[26];
    char[] chars = str.toCharArray();
    for (char aChar : chars) {
        c[aChar - 'a']++;
    }
    return c;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：30.77%；
  • 時間復(fù)雜度：O(n)；
  • 空間復(fù)雜度：O(1)；

2.2.4 一個偷巧的方法

public boolean CheckPermutation(String s1, String s2) {
    int sum1 = 0;
    int sum2 = 0;
    if(s1.length() != s2.length()) {
        return false;
    }
    for(int i = 0; i < s1.length(); i++){
        sum1 += s1.charAt(i);
        sum2 += s2.charAt(i);
    }
    return (sum1 == sum2); 
}
  • 不推薦
  • 時間復(fù)雜度：O(n)；
  • 空間復(fù)雜度：O(1)；
  • 一個騙測試用例的方法，先累加字符串各個字符的ASCII碼，再進(jìn)行比較。但不能區(qū)分“bbb" 和“abc”；
  • 但通過ASCII的解題思路還是值得思考一番的；

3. URL化 [easy]

URL化

3.1 考慮點

  • Java的String是不可變的，可以先思考給出的字符串是否“夠長”，如果夠長，從后面開始處理可能不會覆蓋原有數(shù)據(jù)；

3.2 解法

3.2.1 一行流法：使用String類的API

public String replaceSpaces(String S, int length) {
    return S.substring(0, length).replaceAll(" ", "%20");
}
  • 執(zhí)行時間：12.07%；內(nèi)存消耗：30.13%；
  • String substring(int beginIndex, int endIndex)：返回一個子字符串，從beginIndex到endIndex截取字符串。含beginIndex，不含endIndex。
  • String replaceAll(String regex, String replacement)：成功則返回替換的字符串，失敗則返回原始字符串。其中regex為匹配此字符串的正則表達(dá)式；replacement為用來替換每個匹配項的字符串。

3.2.2 可變長度字符串StringBuilder

public String replaceSpaces(String S, int length) {
    if(S ==  null || length < 0){
        return null;
    }
    char[] c = S.toCharArray();
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < c.length; i++){
        if( c[i] == ' ' && length == 0){
            return sb.toString();
        }
        if(c[i] == ' '){
            sb.append("%20");
        } else {
            sb.append(c[i]);
        }
        length--;
    }
    return sb.toString();
}
  • 執(zhí)行時間：46.27%；內(nèi)存消耗：8.08%；

3.2.3 倒序計算（優(yōu)）

public String replaceSpaces(String S, int length) {
    //先把字符串轉(zhuǎn)化為字符數(shù)組
    char[] chars = S.toCharArray();
    int index = chars.length - 1;
    for (int i = length - 1; i >= 0; i--) {
        //如果遇到空格就把他轉(zhuǎn)化為"%20"
        if (chars[i] == ' ') {
            chars[index--] = '0';
            chars[index--] = '2';
            chars[index--] = '%';
        } else {
            chars[index--] = chars[i];
        }
    }
    return new String(chars, index + 1, chars.length - index - 1);
}
  • 執(zhí)行時間：99.70%；內(nèi)存消耗：51.01%；
  • 該方法的特點是不用開辟額外空間；
  • 上乘做法，因為字符串尾部有額外的緩沖，可以直接修改，不必?fù)?dān)心會覆蓋寫原有數(shù)據(jù)；
  • 如果題目沒有顯示描述“有足夠空間”，可以先遍歷空格數(shù)量n，再對字符串進(jìn)行3n擴展以獲得足夠空間；

4. 回文排列 [easy]

回文排列
  • 回文串：從正、反兩個方向讀都一致的字符串；
  • 即：偶數(shù)長度的字符串所有字符必須出現(xiàn)偶數(shù)次；奇數(shù)長度的字符串必須只有一個字符出現(xiàn)奇數(shù)次；

4.1 考慮點

  • 思考的地方在字符串字符出現(xiàn)次數(shù)的奇偶關(guān)系；
  • 不能構(gòu)造出所有可能排列后比較判斷，因為時間復(fù)雜度是階乘級別的；

4.2 解法

4.2.1 散列表統(tǒng)計法

public boolean canPermutePalindrome(String s) {
    if(s == null){
        return false;
    }
    Map<Character, Integer> map = getMap(s);
    int single = 0;
    for( Map.Entry<Character, Integer> entry : map.entrySet()){
        if( entry.getValue() % 2 == 1){
            single++;
        }
    }
    if((s.length() % 2 == 0) && (single == 0)){
        return true;
    }
    if((s.length() % 2 == 1) && (single == 1)){
        return true;
    }
    return false;
}
// 統(tǒng)計指定字符串str中各字符的出現(xiàn)次數(shù)，并以Map的形式返回
private Map<Character, Integer> getMap(String str) {
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = str.toCharArray();
    for (char aChar : chars) {
        map.put(aChar, map.getOrDefault(aChar, 0) + 1);
    }
    return map;
}
  • 執(zhí)行時間：45.13%；內(nèi)存消耗：51.07%；
  • 時間復(fù)雜度：O(n)；

4.2.2 利用HashSet的唯一性原理（優(yōu)）

public boolean canPermutePalindrome(String s) {
    Set<Character> set = new HashSet<>();
    for (char ch : s.toCharArray()) {
        //set的add方法如果返回false，表示已經(jīng)有了，就刪除
        if (!set.add(ch)) {
            set.remove(ch);
        }
    }
    return set.size() <= 1;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：78.48%；

HashSet的規(guī)則：

  • 新添加到HashSet集合的元素都會與集合中已有的元素一一比較；
  • 首先比較哈希值（每個元素都會調(diào)用hashCode()產(chǎn)生一個哈希值）；
    • 如果新添加的元素與集合中已有的元素的哈希值都不同，新添加的元素存入集合；
    • 如果新添加的元素與集合中已有的某個元素哈希值相同，此時還需要調(diào)用equals()方法比較；
      • 如果equals()方法返回true，說明新添加的元素與集合中已有的某個元素的屬性值相同，那么新添加的元素不存入集合；
      • 如果equals()方法返回false，說明新添加的元素與集合中已有的元素的屬性值都不同,，那么新添加的元素存入集合；

set.size() <= 1：

  • 最后判斷set的長度是否小于等于1，如果等于1說明只有一個字符的個數(shù)是奇數(shù)，其他的都是偶數(shù)。如果等于0說明每個字符都是偶數(shù)，否則不可能構(gòu)成回文字符串；

4.2.3 count計數(shù)法（優(yōu)）

public boolean canPermutePalindrome(String s) {
    int[] map = new int[128];
    int count = 0;
    for (char ch : s.toCharArray()) {
        if ((map[ch]++ & 1) == 1) {
            count--;
        } else {
            count++;
        }
    }
    return count <= 1;
}

  • 執(zhí)行時間：100.00%；內(nèi)存消耗：76.73%；

  • 結(jié)果其實與字符的奇偶性無關(guān)，遇到不同count++，遇到相同count--，如果滿足回文，count的結(jié)果只有可能是0或1；

  • 有點類似于HashSet的唯一性；

4.2.4 位運算（優(yōu)）

public boolean canPermutePalindrome(String s) {
    long highBitmap = 0;
    long lowBitmap = 0;
    for (char ch : s.toCharArray()) {
        if (ch >= 64) {
            highBitmap ^= 1L << ch - 64;
        } else {
            lowBitmap ^= 1L << ch;
        }
    }
    return Long.bitCount(highBitmap) + Long.bitCount(lowBitmap) <= 1;
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：75.90%；
  • 在位運算中有類似奇偶性質(zhì)；
  • 在128位的字符中，如果是用int類型，需要4位，但如果使用long類型，只需要兩位就行了。一個記錄0-63，一個記錄64-127。每一位對應(yīng)一個字符，如果當(dāng)前位置是1，表示有字符了，那么加上當(dāng)前字符就是2個，我們把它變?yōu)?。如果當(dāng)前位置沒有字符，我們就把當(dāng)前位置變?yōu)?，表示有一個字符。最后在判斷這兩個long類型中1的個數(shù)，如果大于1個就不能構(gòu)成回文排列。


5. 一次編輯 [medium]

一次編輯

5.1 考慮點

  • 對于操作“一次”的題目，可以分為找到前和找到后兩種方向處理；

5.2 解法

5.2.1 count計數(shù)找不同法

public boolean oneEditAway(String first, String second) {
    if( first == null && second == null){
        return true;
    }
    if( first == null ){
        return false;
    }
    if( second == null ){
        return false;
    }
    if(first.length() == second.length()){
    //判斷替換
        int count = 0;
        for(int i = 0; i < first.length(); i++){
            if( first.charAt(i) != second.charAt(i) ){
                count++;
            }
        }
        return count <= 1;
    } else {
        //判斷增刪
        //替換找最長
        String longger;
        String shortter;
        if( first.length() > second.length() ){
            longger = first;
            shortter = second;
        } else {
            longger = second;
            shortter = first;
        }
        if(longger.length() == 1 && shortter.length() == 0){
            return true;
        }
        //用count記錄不同次數(shù)
        int count = 0;
        int j = 0;
        for( int i = 0; i < shortter.length() ; i++, j++){
            if( longger.charAt(j) != shortter.charAt(i) ){
                count++;
                i--;
            }
            if( count > 1){
                return false;
            }
        }
        //判斷長字符串最后一個字符是否不同
        if( j  == longger.length() - 1){
            count++;
            if( count > 1){
                return false;
            }
        }
        return j == longger.length()-1 || j == longger.length();
    }
}
  • 執(zhí)行時間：53.77%；內(nèi)存消耗：26.60%；
  • 其中“替換找最長”簡寫成：if(second.length()>first.length) return oneEditAway(second, first)；
  • 時間復(fù)雜度：O(min(n,m))，n和m分別為兩個字符串的長度；

5.2.2 剩余字符串比較法（優(yōu)）

public boolean oneEditAway(String first, String second) {
    if (first == null || second == null) return false;
    int len1 = first.length();
    int len2 = second.length();
    if (Math.abs(len1 - len2) > 1) return false;
    // 保持第一個比第二個長
    if (len2 > len1) return oneEditAway(second, first);

    for (int i = 0; i < len2; i++){
        if (first.charAt(i) != second.charAt(i)){
            //如果是長度相同字符串，那就比較下一個，如果長度不一樣，那就從該字符開始進(jìn)行比較。
            return first.substring(i + 1).equals(second.substring(len1 == len2 ? i + 1 : i));
        }
    }
    return true;
}
  • 執(zhí)行時間：53.77%；內(nèi)存消耗：17.11%；
  • 找到第一個不同處后，對后面字符串進(jìn)行equals判斷即可；
  • 思考點：對于只需要找出“一次”的題目，可以分為找到前和找到后兩種方向處理；

5.2.3 動態(tài)規(guī)劃

public boolean oneEditAway(String word1, String word2) {
    int length1 = word1.length();
    int length2 = word2.length();
    int dp[][] = new int[length1 + 1][length2 + 1];
    for (int i = 0; i <= length1; i++) {
        dp[i][0] = i;//邊界條件，相當(dāng)于word1的刪除操作
    }
    for (int i = 0; i <= length2; i++) {
        dp[0][i] = i;//邊界條件，相當(dāng)于word1的添加操作
    }
    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= length2; j++) {//下面是上面分析的遞推公式
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[length1][length2] <= 1;
}
  • 執(zhí)行時間：10.57%；內(nèi)存消耗：20.57%；
  • 殺雞用牛刀，不推薦；


6. 字符串壓縮 [easy]

在這里插入圖片描述

6.1 考慮點

  • 如果先檢查原字符串與壓縮后字符串長度，在沒有很多字符重復(fù)下可以避免構(gòu)造不會被使用的字符串，代價是需要增加近乎重復(fù)的代碼；

6.2 解法

6.2.1 逐一遍歷法（優(yōu)）

public String compressString(String S) {
    if( S == null || "".equals(S)){
        return S;
    }
    char[] chs = S.toCharArray();
    char cache = chs[0];
    StringBuilder sb = new StringBuilder();
    sb.append(chs[0]);
    int count = 0;
    for(int i = 0; i < S.length(); i++){
        if( cache != chs[i] ){
            sb.append(count);
            sb.append(chs[i]);
            cache = chs[i];
            count = 1;
        } else {
            count++;
        }
        if( i == S.length() -1 ){
            sb.append(count);
        }
    }
    String result = sb.toString();
    return result.length() < S.length() ? result : S;
}
  • 執(zhí)行時間：76.02%；內(nèi)存消耗：50.21%；
  • 時間復(fù)雜度：O(n)，其中 n 為字符串的長度，即遍歷一次字符串的復(fù)雜度；
  • 空間復(fù)雜度：O(1)，只需要常數(shù)空間（不包括存儲答案 ans 的空間）存儲變量；


7. 旋轉(zhuǎn)矩陣 [medium]

旋轉(zhuǎn)矩陣

7.1 考慮點

  • 詢問面試官是否可以開辟額外空間，如果可以，可以使用第一種輔助數(shù)組的解法；如果不能，只能原地旋轉(zhuǎn)或翻轉(zhuǎn)法；
  • 任何算法都需要O(n2)時間復(fù)雜度；

7.2 解法

7.2.1 使用輔助數(shù)組逐層復(fù)制法（優(yōu)）

public void rotate(int[][] matrix) {
    int line = matrix.length;
    int row = matrix[0].length;
    if(line == 0){
        return;
    }
    int[][] result = new int[row][line];
    for( int i = 0; i < line; i++){
        for( int j = 0; j < row; j++){
            result[j][line-1-i] = matrix[i][j];
        }
    }
    for(int i = 0; i < row; i++){
        for( int j = 0; j < line; j++){
            matrix[i][j] = result[i][j];
        }
    }
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：30.87%；
  • 時間復(fù)雜度：O(n2)；
  • 需要使用額外空間；

7.2.2 原地旋轉(zhuǎn)法

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < (n + 1) / 2; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = temp;
        }
    }
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：61.77%；
  • 時間復(fù)雜度：O(N2)，其中 N 是 matrix 的邊長。我們需要枚舉的子矩陣大小 O(?n/2?×?(n+1)/2?)=O(N2)。
  • 空間復(fù)雜度：O(1)。為原地旋轉(zhuǎn)。
  • 對數(shù)學(xué)水平要求較高；
  • 不使用額外內(nèi)存空間；

7.2.3 翻轉(zhuǎn)法（優(yōu)）

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 水平翻轉(zhuǎn)
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < n; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];
            matrix[n - i - 1][j] = temp;
        }
    }
    // 主對角線翻轉(zhuǎn)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：50.10%；
  • 時間復(fù)雜度：O(N2)，其中 N 是 matrix 的邊長。對于每一次翻轉(zhuǎn)操作，我們都需要枚舉矩陣中一半的元素。
  • 空間復(fù)雜度：O(1)。為原地翻轉(zhuǎn)得到的原地旋轉(zhuǎn)。
  • 不使用額外內(nèi)存空間；


8. 零矩陣 [medium]

零矩陣

8.1 考慮點

  • 對空間復(fù)雜度的思考，需要注意陷阱，發(fā)現(xiàn)0直接將整行整列置0最后全是0；

8.2 解法

8.2.1 標(biāo)記數(shù)組法

public void setZeroes(int[][] matrix) {
    int line = matrix.length;
    int row = matrix[0].length;
    if(line == 0){
        return;
    }
    boolean[][] isZero = new boolean[line][row];
    for(int i = 0; i < line; i++){
        for(int j =0; j < row; j++){
            //沒有被標(biāo)記
            if( !isZero[i][j] ){
                //處理0情況并標(biāo)記
                if(matrix[i][j] == 0){
                    for(int k = 0; k < row; k++){
                        if(matrix[i][k] != 0){
                            matrix[i][k] = 0;
                            isZero[i][k] = true;
                        }
                    }
                    for(int k = 0; k < line; k++){
                        if(matrix[k][j] != 0 ){
                            matrix[k][j] = 0;
                            isZero[k][j] = true;
                        }
                    }
                }
                
            }
        }
    }
}
  • 執(zhí)行時間：98.04%；內(nèi)存消耗：58.15%；
  • 時間復(fù)雜度：O(mn)O(mn)，其中 mm 是矩陣的行數(shù)，nn 是矩陣的列數(shù)。我們至多只需要遍歷該矩陣兩次；
  • 空間復(fù)雜度：O(mn)，其中 m 是矩陣的行數(shù)，n 是矩陣的列數(shù)。新創(chuàng)建了個mn的二維數(shù)組；

8.2.2 使用兩個標(biāo)記變量法（優(yōu)）

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean flagCol0 = false, flagRow0 = false;
    //檢查第一列是否有0
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            flagCol0 = true;
        }
    }
    //檢查第二列是否有0
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            flagRow0 = true;
        }
    }
    //檢查其他元素是否有0，有0則根據(jù)下標(biāo)在第一行與第一列置0
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    //根據(jù)第一行與第一列的值置空
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    //置空第一列
    if (flagCol0) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
    //置空第一行
    if (flagRow0) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
}
  • 執(zhí)行時間：98.04%；內(nèi)存消耗：69.77%；
  • 時間復(fù)雜度：O(mn)：其中 m 是矩陣的行數(shù)，n 是矩陣的列數(shù)。我們至多只需要遍歷該矩陣兩次；
  • 空間復(fù)雜度：O(1)：我們只需要常數(shù)空間存儲若干變量；
  • 用矩陣的第一行和第一列代替方法一中的兩個標(biāo)記數(shù)組，以達(dá)到 O(1) 的額外空間。但這樣會導(dǎo)致原數(shù)組的第一行和第一列被修改，無法記錄它們是否原本包含 0。因此我們需要額外使用兩個標(biāo)記變量分別記錄第一行和第一列是否原本包含 0。

8.2.3 一次遍歷法

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean flagCol0 = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            flagCol0 = true;
        }
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
        if (flagCol0) {
            matrix[i][0] = 0;
        }
    }
}
  • 執(zhí)行時間：98.04%；內(nèi)存消耗：26.56%；
  • 時間復(fù)雜度：O(mn)，其中 m 是矩陣的行數(shù)，n 是矩陣的列數(shù)。我們至多只需要遍歷該矩陣兩次；
  • 空間復(fù)雜度：O(1)。我們只需要常數(shù)空間存儲若干變量；
  • 只使用一個標(biāo)記變量記錄第一列是否原本存在 0。這樣，第一列的第一個元素即可以標(biāo)記第一行是否出現(xiàn) 0。但為了防止每一列的第一個元素被提前更新，我們需要從最后一行開始，倒序地處理矩陣元素。


9. 字符串輪轉(zhuǎn) [easy]

字符串輪轉(zhuǎn)

9.1 考慮點

  • 詢問面試官是否為一次旋轉(zhuǎn)還是多次旋轉(zhuǎn)；
    • 如果是一次，先排序后判斷和使用Map統(tǒng)計數(shù)量的方法是不符合要求的；
    • 如果是多次，尋找父段法是不行的；

9.2 解法

9.2.1 先排序后比較法

public boolean isFlipedString(String s1, String s2) {
    if(s1.length() != s2.length()){
        return false;
    }
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();
    int[] count = new int[128];
    for( int i = 0; i < s1.length(); i++){
        count[c1[i]]++;
        count[c2[i]]--;
    }
    for( int i = 0; i < 128; i++){
        if(count[i] != 0){
            return false;
        }
    }
    return true;
}
  • 執(zhí)行時間：24.35%；內(nèi)存消耗：33.25%；

9.2.2 尋找父段法（優(yōu)）

public boolean isFlipedString(String s1, String s2) {
        if(s1.length() != s2.length()) {
        return false;
    }
    String s = s2 + s2;
    return s.contains(s1);
}
  • 執(zhí)行時間：100.00%；內(nèi)存消耗：59.46%；

最后

\color{blue}{\rm\small{新人制作，如有錯誤，歡迎指出，感激不盡！}}

\color{blue}{\rm\small{歡迎關(guān)注我，并與我交流！}}

\color{blue}{\rm\small{如需轉(zhuǎn)載，請標(biāo)注出處！}}

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容