小白的算法課-方法論
為什麼要重視算法
面試畢竟歷程- 其實這是個偽命題，如果為了面試，大家去背一下特定的幾個算法答案就好了
- 提高邏輯思維，理解能力
- 提高代碼質量
為什麼說算法是程序員最應該學習的技能，沒有之一
為什麼這麼說呢？可以思考一下
學框架其實就是學怎麼更好的用人家封裝好的api
看源碼，就是看人家怎麼實現的這個組件，學習人家的設計思維。
但真的是這樣嗎？但其實大多數情況都是為了應付面試，然後實際學習場景大家都是看看別人的博客，看看講解視頻，然後隨便扒扒源碼
綜上所述其實，無論學習新框架還是看源碼，更多的考驗的是記憶力，與略微的理解能力
思考一下，為什麼面試都要考算法？
其實我們都在逃避，相比於算法，其他的能力確實相對於來說比較容易掌握
- 程序員更重要的就是邏輯能力，服務端更甚
-
優秀的軟件工程師必須具備過硬的代碼開發能力，而這就體現在你對數據結構、算法思維、代碼效率優化等知識的儲備上，並直接反應在你工作中解決實際問題的好壞上。
能力分佈表
| 邏輯能力 | 理解能力 | 記憶力 | |
|---|---|---|---|
| 算法 | 60% | 30% | 10% |
| 新框架，新知識 | 10% | 20% | 70% |
| 源碼探索 | 20% | 30% | 50% |
為什麼說算法會提高代碼質量
舉個簡單的例子
在海量數據中查詢指定數據，粗笨的方法就是循環便利一邊找到對應的就好了，
如何用算法來解決？
- 有序存儲
- 二分查找
收益：數據量小的時候可能沒什麼明顯收益，但假如我們數據量達到了1000w，兩種查找方法的效率可能就是1000萬次和24次的區別了（log2 10000000 = 23.25）
代碼質量如何一步步提高
- 暴力解法
- 在沒有任何時間、空間約束下，完成代碼任務的開發。
- 剔除無效操作處理
- 將代碼中的無效計算、無效存儲剔除，降低時間或空間複雜度。
- 時空轉換
- 設計合理數據結構，完成時間複雜度向空間複雜度的轉移。
- 邏輯歸納
- 利用邏輯關係，完成時間複雜度和空間複雜度的降低
eg1：
假設有任意多張面額為 2 元、3 元、7 元的貨幣，現要用它們湊出 100 元，求總共有多少種可能性
暴力解法
public void s1_1() { int count = 0; for (int i = 0; i <= (100 / 7); i++) { for (int j = 0; j <= (100 / 3); j++) { for (int k = 0; k <= (100 / 2); k++) { if (i * 7 + j * 3 + k * 2 == 100) { count += 1; } } } } System.out.println(count); }
3 層的 for 循環。從結構上來看，顯然的 O( n³ ) 的時間複雜度。思考一下會發現，最內層的 for 是多餘的剔除無效操作處理
public void s1_2() { int count = 0; for (int i = 0; i <= (100 / 7); i++) { for (int j = 0; j <= (100 / 3); j++) { if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) { count += 1; } } } System.out.println(count); }
eg2:
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那 兩個 整數，並返回它們的數組下標。
暴力解法
public int[] s2_1(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; }
時空轉換
public int[] s2_2(int[] nums, int target) { Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { if (hashtable.containsKey(target - nums[i])) { return new int[]{hashtable.get(target - nums[i]), i}; } hashtable.put(nums[i], i); } return new int[0]; }
