Github： https://github.com/MyGitBooks/niubility-algorithm
本文檔是作者小傅哥通過從leetcode 劍指offer 編程之美 等資料中收集算法題目并加以邏輯分析和編碼搞定題目，最終編寫資料到本文檔中，為大家提供在算法領域的幫助。如果本文能為您提供幫助，請給予支持(加入、點贊、分享)！
一、前言
在這之前我基本沒怎么關注過leetcode，還是最近有人經常說面試刷題，算法刷到谷歌上班去了。我才開始了解下，仔細一看原來雖然沒關注過，但是類似的題還是做過的并且還買過一本《編程之美》的書。
在 中每個算法題都有編號；1 2 3 ... 1566，而且還在增加。你我都是新人，既然沒了解過那就從第一題開始吧，嘗試從算法中吸取一些創新的思路。否則為什么那么多公司面試招聘都會去考下算法！谷歌``````字節跳動``````騰訊``````阿里``````等等
對于這個算法題來說我還是蠻喜歡的，因為我是屬于那種很偏科的男人，通常數學：140分，英語：40分(當年)。好！理由找好了，開始刷個題。聽說數學好的男人都不簡單！ 所以我打算接下來定期的做一些算法題，同時將我的思路進行整理，寫成筆記分享給新人，一起從算法中成長。
二、時間復雜度
時間復雜度可以說是算法的基礎，如果不在乎時間復雜度，那么沒有 for循環解決不了問題！而我們一般所說的時間復雜度以及耗時排列包括；O(1)<>O(logn)<>O(n)<>O(nlogn)<>O(n^2)<>O(n^3)<>O(2^n)<>O(n!)<>O(n^n)等。那么一段代碼的耗時主要由各個行為塊的執行次數相加并去掉最小影響系數而得出的，接下來先看下這種東西是如何計算出來的。
1. O(n)
代碼塊
int n = 10;
for (int i = 0; i n; i++) {
System.out.println(i);
}
| 序號 | 代碼塊 | 耗時 |
|---|
| 1 | int n = 10 | 1 |
| 2 | int i = 0 | 1 |
| 3 | i <> | n + 1 |
| 4 | i++ | n |
| 5 | System.out.println(i) | n |
最終耗時：
sum = 1 + 1 + n + 1+ n + n
= 3n+3
= n (忽略低階梯)
從公式和象限圖中可以看到，當我們的公式3n+3，隨著 n 的數值越來越大的時候，常數3就可以忽略低階梯不記了。所以在這段代碼中的時間復雜度就是；O(n)
所謂低階項，簡單地說就是當n非常大時，這個項相對于另外一個項很小，可以忽略，比如n相對于n^2,n就是低階項
2. O(logn)
代碼塊
int sum = 1, n = 10;
while (sum n) {
sum = sum * 2;
}
最終耗時：
這回我們只看執行次數最多的，很明顯這是一個 2 * 2 * 2 ··· n，大于 n 跳出循環。
那么我們使用函數；2^x = n，x = logn，就可以表示出整體的時間復雜度為 O(logn)
好！結合這兩個例子，相信你對時間復雜度已經有所理解，后面的算法題中就可以知道自己的算法是否好壞。
三、算法題：兩數之和
https:///problems/two-sum/submissions/
給定一個整數數組 nums和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
java
class Solution {
public int[] twoSum(int[] nums, int target) {
// todo
}
}
四、解題
這是leetcode的第一題，難度簡單，其實如果要是使用兩層for循環嵌套，確實不太難。但是如果想打敗99%的選手還是需要斟酌斟酌算法。
思路1，雙層循環
先不考慮時間復雜度的話，最直接的就是雙層for循環，用每一個數和數組中其他數做家和比對，如下；
可以看到這樣的時間復雜度是；n*(n-1) ··· 4*3、4*2、4*1，也就是O(n^2)，有點像九九乘法表的結構。
代碼：
public int[] twoSum(int[] nums, int target) {
int[] idxs = new int[2];
for (int i = 0; i nums.length; i++) {
for (int j = i + 1; j nums.length; j++) {
if (nums[i] + nums[j] == target) {
idxs[0] = i;
idxs[1] = j;
}
}
}
return idxs;
}
耗時：
- 對于這樣的算法雖然能解決問題，但是并不能滿足我們的需求，畢竟這個級別的時間復雜度下實在是太慢了。
思路2，單層循環
為了把這樣一個雙層循環簡化為單層，我們最能直接想到的就事放到 Map 這樣的數據結構中，方便我們存取比對。那么這樣的一個計算過程如下圖；
- 這個過程的核心內容是將原來的兩數之和改成差值計算，并將每次的差與 Map 中元素進行比對。如果差值正好存在 Map 中，那么直接取出。否則將數存入到 Map 中，繼續執行。
- 這個過程就可以將原來的雙層循環改為單層，時間復雜度也到了 O(n) 級別。
代碼：
public static int[] twoSum(int[] nums, int target) {
MapInteger, Integer> hashMap = new HashMapInteger, Integer>(nums.length);
for (int i = 0; i nums.length; i++) {
if (hashMap.containsKey(target - nums[i])) {
return new int[]{hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[]{-1, -1};
}
耗時：
- 可以看到當我們使用 Map 結構的時候，整個執行執行用時已經有了很大的改善。但是你有考慮過
containsKey與 get是否為 null 相比哪個快嗎？ - 這個算法已經很良好了，但是這個對 key 值的比對還是很耗時的，需要反復的對 map 進行操作，那么我們還需要再優化一下。
思路3，Bit結構
如果說想把我們上面使用 Map 結構的地方優化掉，我們可以考慮下 Map 數據是如何存放的，他有一種算法是自身擴容 2^n - 1 & 元素，求地址。之后按照地址在進行存放數據。那么我們可以把這部分算法拿出來，我們自己設計一個數組結構，將元素進行與運算存放到我們自己定義的數組中。如下圖；
- 左側是我們假定的入參
int[] nums，32是我們設定的值，這個值的設定需要滿足存放大小夠用，否則地址會混亂。 - 接下來我們使用 32 - 1，也就是二進制
011111與每一個數組中的值進行與運算，求存放地址。 - 當算好地址后，將元素存放在數組中，設置值。這個值就是我們的元素本身位置了，但是需要
+1，因為默認數組是0，如果不加1，就看不到位置了。最終使用的時候，可以再將位置結果 -1。
代碼：
public static int[] towSum(int[] nums, int target) {
int volume = 2048;
int bitMode = volume - 1;
int[] t = new int[volume];
for (int i = 0; i nums.length; i++) {
int c = (target - nums[i]) & bitMode;
if (t[c] != 0) return new int[]{t[c] - 1, i};
t[nums[i] & bitMode] = i + 1;
}
return new int[]{-1, -1};
}
- 這個2048是我們試出來的，主要根據leetcode中的單測用例決定。
耗時：
- 出現0毫秒耗時，100%擊敗，這個不一定每次都這樣，可能你試的時候不一樣。得益于數據結構的優化使得這個算法的耗時很少。
五、總結
- 野路子搞算法，沒有看過算法導論、也沒有套用模板，但如果需要后續的不斷的加深自己的知識點，也是需要學習的。目前在我看來這些更像是數學題，主要可以提升對同一件事情的多種處理方式，同時也增加個人的編程能力。
- 算法的學習也不太應該套用各種理論，當然每個人看法不一樣，我允許你的觀點，也要接受我的想法。
- 在各個大廠面試過程中，都有；算法、源碼、項目、技術棧以及個人的一些優點，如果你能在前兩個點上給面試官很好的印象，那么你就放心的要工資吧。
- 從這篇文章開始，我會陸續做一做算法題，提升自己的功夫底子，也分析給小白。歡迎小白跟隨！Git地址：https://github.com/MyGitBooks/niubility-algorithm
