前言

提起數(shù)據(jù)結(jié)構(gòu)與算法，大家可能第一時(shí)間想到的就是藍(lán)橋杯這種算法競(jìng)賽，并不會(huì)太過(guò)于在意它在面試中的占比。因?yàn)樵谌舾赡昵?，你去面試這種互聯(lián)網(wǎng)公司或者大的IT公司，面試官并不會(huì)過(guò)于考察你的算法能力，甚至說(shuō)你會(huì)簡(jiǎn)單的寫(xiě)一些框架，搭一些數(shù)據(jù)庫(kù)，就能找到一份不錯(cuò)的工作

但是直至今日，大家會(huì)發(fā)現(xiàn)面試的門(mén)檻越來(lái)越高，甚至來(lái)說(shuō)去到一些大公司去面試算法與數(shù)據(jù)結(jié)構(gòu)的題目已經(jīng)成為必問(wèn)了，算法的在面試的占比已經(jīng)越來(lái)越高，在此我整理了一下近幾年面試中問(wèn)的比較頻繁的算法題，大家感興趣的可以看看，看自己能答出來(lái)多少。

尋找數(shù)組的中心索引

數(shù)組中某一個(gè)下標(biāo)，左右兩邊的元素之后相等，該下標(biāo)即為中心索引
思路：先統(tǒng)計(jì)出整個(gè)數(shù)組的總和，然后從第一個(gè)元素開(kāi)始疊加
總和遞減當(dāng)前元素，疊加遞增當(dāng)前元素，知道兩個(gè)值相等

刪除排序數(shù)組中的重復(fù)項(xiàng)

一個(gè)有序數(shù)組 nums ，原地刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素只出現(xiàn)一次 ，返回刪除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

雙指針?biāo)惴ǎ?/h3>

數(shù)組完成排序后，我們可以放置兩個(gè)指針 i 和 j，其中 i 是慢指針，而 j 是快指針。只要nums[i]=nums[j]，我們就增加 j 以跳過(guò)重復(fù)項(xiàng)。
當(dāng)遇到 nums[j] ！= nums[i]時(shí)，跳過(guò)重復(fù)項(xiàng)的運(yùn)行已經(jīng)結(jié)束，必須把nums[j]）的值復(fù)制到 nums[i +1]。然后遞增 i，接著將再次重復(fù)相同的過(guò)程，直到 j 到達(dá)數(shù)組的末尾為止。

x的平方根

在不使用 sqrt(x) 函數(shù)的情況下，得到 x的平方根的整數(shù)部分

解法一：二分查找

x的平方根肯定在0到x之間，使用二分查找定位該數(shù)字，該數(shù)字的平方一定是最接近x的，m平方值如果大于x、則往左邊找，如果小于等于x則往右邊找
找到0和X的最中間的數(shù)m，
如果m * m > x，則m取x/2到x的中間數(shù)字，直到m * m < x，m則為平方根的整數(shù)部分如果m * m <= x，則取0到x/2的中間值，知道兩邊的界限重合，找到最大的整數(shù)，則為x平方根的整數(shù)部分
時(shí)間復(fù)雜度：O(logN)

解法二：牛頓迭代

假設(shè)平方根是 i ，則 i 和 x/i 必然都是x的因子，而 x/i 必然等于 i ，推導(dǎo)出 i + x / i = 2 * i，得出 i = (i +x / i) / 2
由此得出解法，i 可以任選一個(gè)值，只要上述公式成立，i 必然就是x的平方根，如果不成立， (i + x / i) /2得出的值進(jìn)行遞歸，直至得出正確解

三個(gè)數(shù)的最大乘積

一個(gè)整型數(shù)組 nums ，在數(shù)組中找出由三個(gè)數(shù)字組成的最大乘積，并輸出這個(gè)乘積。
乘積不會(huì)越界
如果數(shù)組中全是非負(fù)數(shù)，則排序后最大的三個(gè)數(shù)相乘即為最大乘積；如果全是非正數(shù)，則最大的三個(gè)數(shù)相乘同樣也為最大乘積。
如果數(shù)組中有正數(shù)有負(fù)數(shù)，則最大乘積既可能是三個(gè)最大正數(shù)的乘積，也可能是兩個(gè)最小負(fù)數(shù)（即絕對(duì)值最大）與最大正數(shù)的乘積。
分別求出三個(gè)最大正數(shù)的乘積，以及兩個(gè)最小負(fù)數(shù)與最大正數(shù)的乘積，二者之間的最大值即為所求答案。

解法一：排序

解法二：線(xiàn)性?huà)呙?/h3>

兩數(shù)之和

給定一個(gè)升序排列的整數(shù)數(shù)組 numbers ，從數(shù)組中找出兩個(gè)數(shù)滿(mǎn)足相加之和等于目標(biāo)數(shù) target 。
假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，而且不可以重復(fù)使用相同的元素。
返回兩數(shù)的下標(biāo)值，以數(shù)組形式返回
暴力解法

時(shí)間復(fù)雜度：O(N的平方)
空間復(fù)雜度：O(1)
哈希表：將數(shù)組的值作為key存入map，target - num作為key

解法一：二分查找

先固定一個(gè)值(從下標(biāo)0開(kāi)始)，再用二分查找查另外一個(gè)值，找不到則固定值向右移動(dòng)，繼續(xù)二分查找

時(shí)間復(fù)雜度：O(N * logN)
空間復(fù)雜度：O(1)

解法二：雙指針

左指針指向數(shù)組head，右指針指向數(shù)組tail，head+tail > target 則tail 左移，否則head右移

時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)

斐波那契數(shù)列

求取斐波那契數(shù)列第N位的值。
斐波那契數(shù)列：每一位的值等于他前兩位數(shù)字之和。前兩位固定 0，1,1,2,3,5,8。。。。

解法一：暴力遞歸

解法二：去重遞歸

遞歸得出具體數(shù)值之后、存儲(chǔ)到一個(gè)集合(下標(biāo)與數(shù)列下標(biāo)一致)，后面遞歸之前先到該集合查詢(xún)一次，如果查到則無(wú)需遞歸、直接取值。查不到再進(jìn)行遞歸計(jì)算

解法三：雙指針迭代

基于去重遞歸優(yōu)化，集合沒(méi)有必要保存每一個(gè)下標(biāo)值，只需保存前兩位即可，向后遍歷，得出N的值

環(huán)形鏈表

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)該節(jié)點(diǎn)，則鏈表中存在環(huán)如果鏈表中存在環(huán)，則返回 true 。 否則，返回 false 。

解法一：哈希表

解法二：雙指針

排列硬幣

總共有 n 枚硬幣，將它們擺成一個(gè)階梯形狀，第 k 行就必須正好有 k 枚硬幣。
給定一個(gè)數(shù)字 n，找出可形成完整階梯行的總行數(shù)。
n 是一個(gè)非負(fù)整數(shù)，并且在32位有符號(hào)整型的范圍內(nèi)

解法一：迭代

從第一行開(kāi)始排列，排完一列、計(jì)算剩余硬幣數(shù)，排第二列，直至剩余硬幣數(shù)小于或等于行數(shù)

解法二：二分查找

假設(shè)能排 n 行，計(jì)算 n 行需要多少硬幣數(shù)，如果大于 n，則排 n/2行，再計(jì)算硬幣數(shù)和 n 的大小關(guān)系

解法三：牛頓迭代

使用牛頓迭代求平方根，(x + n/x)/2
假設(shè)能排 x 行 則 1 + 2 + 3 + ...+ x = n，即 x(x+1)/2 = n 推導(dǎo)出 x = 2n - x

合并兩個(gè)有序數(shù)組

兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組。
初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。假設(shè) nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來(lái)自 nums2 的元素。

解法一：合并后排序

時(shí)間復(fù)雜度 : O((n+m)log(n+m))。
空間復(fù)雜度 : O(1)。

解法二：雙指針 從前往后

將兩個(gè)數(shù)組按順序進(jìn)行比較，放入新的數(shù)組

時(shí)間復(fù)雜度 : O(n + m)。
空間復(fù)雜度 : O(m)。

解法三：雙指針優(yōu)化

從后往前

時(shí)間復(fù)雜度 : O(n + m)。
空間復(fù)雜度 : O(1)。

子數(shù)組最大平均數(shù)

給一個(gè)整數(shù)數(shù)組，找出平均數(shù)最大且長(zhǎng)度為 k 的下標(biāo)連續(xù)的子數(shù)組，并輸出該最大平均數(shù)。
滑動(dòng)窗口：

窗口移動(dòng)時(shí)，窗口內(nèi)的和等于sum加上新加進(jìn)來(lái)的值，減去出去的值

更多的算法筆記個(gè)刷題思路大家可以關(guān)注公眾號(hào)：前程有光，免費(fèi)獲取完整版