前言
本系列筆記主要記錄筆者刷《程序員面試金典》算法的一些想法與經(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)：通過使用平臺的默認字符集解碼指定的 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)：將此字符串與指定對象進行比較脚乡，忽略大小寫蜒滩。
獲取功能的方法:
-
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()：使用平臺的默認字符集將該String編碼轉(zhuǎn)換為新的字節(jié)數(shù)組。String replaceAll(String regex, String replacement)：成功則返回替換的字符串捡需，失敗則返回原始字符串。其中regex為匹配此字符串的正則表達式；replacement為用來替換每個匹配項的字符串战得。-
String replace(CharSequence target, CharSequencere placement)：將與target匹配的字符串使用replacement字符串替換。CharSequence是一個接口庸推，也是一種引用類型常侦。作為參數(shù)類型浇冰，可以把String對象傳遞到方法中。
分割功能的方法:
-
String[] split(String regex)：將此字符串按照給定的regex（規(guī)則）拆分為字符串數(shù)組聋亡。split方法的參數(shù)其實是一個“正則表達式”肘习，如果按照英文句點“.”進行切分，必須寫"\."坡倔。
將基本數(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 可以對字符串的字符先進行排序
Arrays.sort(int[] a, int fromIndex, int toIndex)：對數(shù)組部分排序臣樱，也就是對數(shù)組a的下標從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ù)組進行排序
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當數(shù)組大小小于32時逛裤，采用二分插入排序算法；當大于32時猴抹，采用基于塊-區(qū)run的歸并排序带族。所以TimSort是一種二分插入排序和歸并排序的變種算法。對對象進行排序蟀给，沒有采用快速排序蝙砌，是因為快速排序是不穩(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碼姑宽，再進行比較。但不能區(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為匹配此字符串的正則表達式拢切；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%纳寂；
- 該方法的特點是不用開辟額外空間主穗；
- 上乘做法，因為字符串尾部有額外的緩沖毙芜，可以直接修改忽媒，不必擔心會覆蓋寫原有數(shù)據(jù)；
- 如果題目沒有顯示描述“有足夠空間”腋粥，可以先遍歷空格數(shù)量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)一個字符，如果當前位置是1烛卧，表示有字符了佛纫，那么加上當前字符就是2個妓局，我們把它變?yōu)?。如果當前位置沒有字符呈宇，我們就把當前位置變?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)){
//如果是長度相同字符串有额，那就比較下一個般又，如果長度不一樣，那就從該字符開始進行比較巍佑。
return first.substring(i + 1).equals(second.substring(len1 == len2 ? i + 1 : i));
}
}
return true;
}
- 執(zhí)行時間：53.77%倒源；內(nèi)存消耗：17.11%；
- 找到第一個不同處后句狼，對后面字符串進行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;//邊界條件胳螟，相當于word1的刪除操作
}
for (int i = 0; i <= length2; i++) {
dp[0][i] = i;//邊界條件，相當于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ù)學水平要求較高逢防；
- 不使用額外內(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 標記數(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++){
//沒有被標記
if( !isZero[i][j] ){
//處理0情況并標記
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 使用兩個標記變量法（優(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ù)下標在第一行與第一列置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ù)空間存儲若干變量忙芒；
- 用矩陣的第一行和第一列代替方法一中的兩個標記數(shù)組示弓，以達到 O(1) 的額外空間。但這樣會導(dǎo)致原數(shù)組的第一行和第一列被修改呵萨，無法記錄它們是否原本包含 0奏属。因此我們需要額外使用兩個標記變量分別記錄第一行和第一列是否原本包含 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ù)空間存儲若干變量齿兔；
- 只使用一個標記變量記錄第一列是否原本存在 0。這樣础米，第一列的第一個元素即可以標記第一行是否出現(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%事扭；
