前言
今天聊聊掌握了不一定能拿到大廠 Offer，但不掌握一定進(jìn)不去大廠的神技「數(shù)據(jù)結(jié)構(gòu)與算法」。
為什么突然提到了數(shù)據(jù)結(jié)構(gòu)與算法呢？這要從一個(gè)朋友的吐槽開始。
我這位朋友一心想進(jìn)大廠，學(xué)歷還不錯(cuò)、能力也不錯(cuò)，但就是拿不到大廠Offer。大家都勸他多刷 LeetCode ，把數(shù)據(jù)結(jié)構(gòu)與算法弄明白。他確實(shí)聽了，半年過去之后，現(xiàn)在基礎(chǔ)知識(shí)還行，一旦涉及圖、排序、遞歸這些高級(jí)一點(diǎn)的知識(shí)就完蛋了。
其實(shí)很多人都有遇到這種情況，算法到底有多重要呢？
數(shù)據(jù)結(jié)構(gòu)與算法是互聯(lián)網(wǎng)大廠的敲門磚,也是開發(fā)者精益求精、持續(xù)提升的內(nèi)功基礎(chǔ)。
面試為什么考算法？
無非是算法最能說明一個(gè)人的綜合實(shí)力。
而大廠考算法一般也會(huì)分兩步，第一步：讓你直接說思路；第二步：讓你實(shí)操寫代碼。
通過這兩步，就可以看出你的編程內(nèi)功是否深厚，除此之外還能多維度考察你的其他能力，比如：邏輯思維清晰與否、debug 能力如何、編碼習(xí)慣怎樣、是否能寫出可維護(hù)的代碼等等......
下面講一講算法的學(xué)習(xí)方法
第一部分：把“爛”代碼優(yōu)化為高效率代碼的方法和路徑，也是關(guān)于代碼開發(fā)與優(yōu)化方法框架的總綱。代碼的目標(biāo)，除了完成任務(wù)，還要求把某項(xiàng)任務(wù)高效率地完成。
第二部分，補(bǔ)充必備的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)。時(shí)間/空間復(fù)雜度的降低，要求對(duì)數(shù)據(jù)有超強(qiáng)的組織方式，這些能力需要你對(duì)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)有極為深刻的理解，只有理解了他們的優(yōu)劣才能靈活選用合適的數(shù)據(jù)結(jié)構(gòu)。
第三部分，這部分是你學(xué)習(xí)的重點(diǎn)，也就是用算法思考問題的邏輯和程序設(shè)計(jì)方法。
第四部分，側(cè)重在 BAT 高頻面試真題詳解。
第五部分，面試現(xiàn)場(chǎng)。很多工程師有個(gè)共性問題，那就是明明有能力，卻說不出來，表現(xiàn)得就像是個(gè)初學(xué)者一樣。
其中，最最最重要的就是刷題了，百煉才能成鋼！！（重要的事兒多說幾遍。）
推薦幾個(gè)做編程題目的網(wǎng)站：
下面給大家分享一些算法題
題目：
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
分析：
根據(jù)題意畫了個(gè)簡(jiǎn)單的圖，首先我們要確定查找開始的位置，因?yàn)樗嵌S的數(shù)組，它的下標(biāo)變化是兩個(gè)方向的，根據(jù)四個(gè)邊界點(diǎn)來分析。
a b
c d
Ａ：向下 增 ，向右 增
Ｂ：向左 減 ，向下 增
Ｃ：向上 減 ，向右 增
Ｄ：向左 減 ，向上 減
可以看出從B 或Ｃ點(diǎn)開始查找剛好可以構(gòu)建一個(gè)二叉查找樹。
二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。
先確定二維數(shù)組的行數(shù)和列數(shù)，把 查找值 與 二叉查找樹的根節(jié)點(diǎn)（Ｂ或者 Ｃ）開始比較，如果相等返回true，小于查找左子樹，大于就查找右子樹。如果遍歷超過數(shù)組邊界，就返回 false。
以C為根節(jié)點(diǎn)查找
public class Solution {
public boolean Find(int [][] array,int target) {
int i = array.length -1;
int m = array[0].length -1;
int j = 0;
while(i>=0 && j<=m){
if(target == array[i][j]){
return true;
}else if(target >array[i][j]){
j++;
}else{
i--;
}
}
return false;
}
}
以B為根節(jié)點(diǎn)查找
public class Solution {
public boolean Find(int [][] array,int target) {
int i = array.length -1;
int j = array[0].length -1;
int n = 0;
while(j>=0 && n<=i){
if(target == array[n][j]){
return true;
}else if(target >array[n][j]){
n++;
}else{
j--;
}
}
return false;
}
}
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。
題目分析
解法一 運(yùn)行時(shí)間：29m 占用內(nèi)存：629k
public int NumberOf1(int n) {
String s=Integer.toBinaryString(n);
char[] c=s.toCharArray();
int j=0;
for(int i=0;i<c.length;i++){
if(c[i]=='1'){
j++;
}
}
return j;
}
}
解析：
public static String toBinaryString(int i)
以二進(jìn)制（基數(shù) 2）無符號(hào)整數(shù)形式返回一個(gè)整數(shù)參數(shù)的字符串表示形式。
①先把整數(shù)轉(zhuǎn)換成二進(jìn)制字符串
②把字符串轉(zhuǎn)換成字符數(shù)組
③遍歷該數(shù)組，判斷每位是否為1，為1 計(jì)數(shù)加1。
④遍歷完成返回1的個(gè)數(shù)
解法二 運(yùn)行時(shí)間：30ms 占用內(nèi)存：629k
public class Solution {
public int NumberOf1(int n) {
int count =0;
while(n!=0){
count++;
n = n&(n-1);
}
return count;
}
}
解析：
如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1。如果我們把這個(gè)整數(shù)減1，那么原來處在整數(shù)最右邊的1就會(huì)變?yōu)?，原來在1后面的所有的0都會(huì)變成1(如果最右邊的1后面還有0的話)。其余所有位將不會(huì)受到影響。
題目：
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。
思路：
壓入元素直接壓入stack1 刪除元素先查看stack2是否為空，非空則彈出；空則將stack1中元素取出，置于stack2中
代碼：
public class StackQueue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node){
stack1.push(node);
}
public int pop(){
if(stack2.empty()){
while(!stack1.empty())
stack2.push(stack1.pop());
}
return stack2.pop();
}
遞歸和迭代的區(qū)別是什么，各有什么優(yōu)缺點(diǎn)？
程序調(diào)用自身稱為遞歸，利用變量的原值推出新值稱為迭代。
遞歸的優(yōu)點(diǎn)大問題轉(zhuǎn)化為小問題，可以減少代碼量，同時(shí)代碼精簡(jiǎn)，可讀性好；
缺點(diǎn)就是遞歸調(diào)用浪費(fèi)了空間，而且遞歸太深容易造成堆棧的溢出。
迭代的好處就是代碼運(yùn)行效率好，因?yàn)闀r(shí)間只因循環(huán)次數(shù)增加而增加，而且沒有額外的空間開銷；
缺點(diǎn)就是代碼不如遞歸簡(jiǎn)潔
找不到學(xué)習(xí)資料怎么辦
有很多小伙伴他們其實(shí)都明白算法的重要性，也有去學(xué)習(xí)的心，可是苦于不知道從何處下手，身邊也沒有可以請(qǐng)教的人。
下面我就介紹一下我整理的學(xué)習(xí)資料。
