學(xué)代碼，從最簡單的開始

相關(guān)資料：
《數(shù)據(jù)結(jié)構(gòu)與算法之美》
《劍指Offer》

代碼規(guī)范

1. 代碼命名規(guī)范

2. 代碼書寫規(guī)范

1. 合并判斷條件，減少 if 語句

if (sortType == SortType.descend)

優(yōu)化為

if (num > data[i] && sortType == SortType.descend)

總結(jié)思路

1. 謹(jǐn)慎處理邊界問題（空數(shù)組等）

2. 從變化中設(shè)計不變的量

• 題目 283 移動零：后移 0 → 前移非 0
• 題目 566 重塑矩陣：index 表示重構(gòu)矩陣前后的第 index 個元素

3. 類比經(jīng)典算法

• 題目 03 數(shù)組中重復(fù)的數(shù)字：n 個元素，取值范圍為 0~n-1 → 類 Hash 尋找元素沖突
• 題目 04 二維數(shù)組中的查找：行和列均遞增 → 類二分法縮小查找范圍

數(shù)據(jù)結(jié)構(gòu)與算法之美

1. 數(shù)組

題目 1：大小固定的有序數(shù)組，支持動態(tài)增刪改

• 錯誤 1：插入函數(shù)搜索插入位置時 index 初值為 -1，未考慮空數(shù)組的情況，導(dǎo)致數(shù)組越界

// 考慮空數(shù)組，因此 index 設(shè)為 0
if (count == 0) {
    index = 0;
}

• 錯誤 2：降序數(shù)組只有元素 7 時，插入 4 的index值為 0，反而插入到了 7 前面，未考慮數(shù)組元素比較結(jié)束，插入數(shù)組末尾的情況

// 考慮插入數(shù)組末尾的情況
if (i == count) {
    index = count;
}

查找成功后沒有 break 循環(huán)，導(dǎo)致此判斷條件失效

• 總結(jié)：未考慮插入首位和末位的特殊情況（即邊界）**

題目 2：支持動態(tài)擴容的無序數(shù)組，按索引增刪改查

1. 無參構(gòu)造函數(shù)調(diào)用有參構(gòu)造函數(shù)
2. 數(shù)組已滿則擴容，不足1/4則縮容為1/2，擴容和縮容調(diào)用同一函數(shù)

題目 3：兩個有序數(shù)組合并為一個有序數(shù)組

• 錯誤：數(shù)組中有 count 個元素，但最后一個元素的位置是 count-1

劍指Offer

題目 03：數(shù)組中重復(fù)的數(shù)字

在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0~n-1 的范圍內(nèi)

• 思路1（×）：HashSet的add方法，元素重復(fù)則返回false

• 思路2（√）：將值為 i 的元素調(diào)整到第 i 個位置上進行求解（類Hash）

時間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)

• 注意事項：

1. 某處缺少返回值
2. 先初始化類，才能在main函數(shù)中調(diào)用

題目 04：二維數(shù)組中的查找

行和列均遞增

• 思路：選取數(shù)組中右上角的數(shù)字，縮小查找區(qū)間（類似二分法取中值）

時間復(fù)雜度 O(M + N)，空間復(fù)雜度 O(1)

1. if 該數(shù)字=要查找的數(shù)字，查找過程結(jié)束
2. else if 該數(shù)字>要查找的數(shù)字，剔除這個數(shù)字所在的列
3. else if 該數(shù)字<要查找的數(shù)字，剔除這個數(shù)字所在的行

• 注意事項：

1. 空數(shù)組求長度越界
2. 判斷空數(shù)組的條件寫在一起

if (matrix == null || matrix.length == 0 || matrix[0].length == 0)

LeetCode

1. 數(shù)組與矩陣

題目 283：移動零

將數(shù)組 nums 中的 0 移動至數(shù)組末尾

• 思路：遍歷數(shù)組，跳過 0 元素，即前移非 0 元素，最后根據(jù) index 位置在末尾補 0（移動 0 至末尾 → 移動非 0 至前面）

時間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)

題目 566：重塑矩陣

將 m×n 的矩陣 nums 重構(gòu)為 r×c 的矩陣 reshapedNums

• 思路：重構(gòu)過程中行遍歷的元素位置不變，將 index 設(shè)為原數(shù)組 nums 行遍歷的第 index 個元素（index < m×n），則重構(gòu)后其依然為第 index 個元素

1. 2×2 → 1×4：reshapedNums[i][j] = nums[index / 2][index % 2]
2. 1×6 → 2×3：reshapedNums[i][j] = nums[index / 6][index % 1]
3. m×n → r×c：reshapedNums[i][j] = nums[index / n][index % n]

時間復(fù)雜度 O(r * c)，空間復(fù)雜度 O(r * c)