引言
現(xiàn)在互聯(lián)網(wǎng)的招工流程，算法題是必不可少的，對(duì)于像我這種沒(méi)搞過(guò)ACM的吃瓜群眾，好在有l(wèi)eetcode，拯救我于水火。于是乎，斷斷續(xù)續(xù)，刷了一些題，其中一些題還是值得細(xì)細(xì)品味的，現(xiàn)把一些問(wèn)題整理一下，有些解法是我自己寫的，也有些解法是參考了discuss中的答案，當(dāng)做是秋招的一個(gè)小小總結(jié)。由于水平有限，代碼寫得并不好，選的題目也只能用于入門，希望大家見(jiàn)諒。
暴力破解
暴力破解，據(jù)我個(gè)人理解，就是遍歷整棵搜索樹(shù)，沒(méi)有刪繁就簡(jiǎn)，緊是單單的搜索和匹配。
1、基本暴力破解：對(duì)于最基本的暴力破解，就是取出所有的可能，和題目中的條件相比較，直到找到符合題意的答案。
舉例：雞兔同籠問(wèn)題，已知x個(gè)頭，y只腳，問(wèn)兔和雞的個(gè)數(shù)。
解法：從0~x個(gè)枚舉雞（或兔）的只數(shù)，計(jì)算腳的個(gè)數(shù)是否為y。
2、DFS：深度優(yōu)先搜索。從原始狀態(tài)出發(fā)，選擇任一狀態(tài)，沿這個(gè)狀態(tài)一直走到?jīng)]有下一個(gè)狀態(tài)為止，這時(shí)候進(jìn)行回溯，到當(dāng)前狀態(tài)的上一個(gè)狀態(tài)，選擇另一個(gè)狀態(tài)進(jìn)行遍歷。DFS在代碼實(shí)現(xiàn)上常使用遞歸方法來(lái)實(shí)現(xiàn)。
舉例1：Leetcode 129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
解法：最直觀的思路，就是找到所有路徑，記錄路徑上所有的值，并且求和，代碼如下：
class Solution {
public:
int ret = 0;
int sumNumbers(TreeNode* root) {
if(root == nullptr) return ret;
getSum(root,root->val);
return ret;
}
//遞歸調(diào)用
void getSum(TreeNode* root,int preval){
if(root->left==nullptr&&root->right==nullptr){
ret+=preval;
return;
}
if(root->left)getSum(root->left,preval*10+root->left->val);
if(root->right)getSum(root->right,preval*10+root->right->val);
return;
}
};
除此之外，DFS還可常用于尋找所有可達(dá)狀態(tài)：
舉例二：Leetcode200. Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
思路：在這個(gè)題目中，認(rèn)為所有為1（上下左右）組成的是一個(gè)島，求給出數(shù)組中島的個(gè)數(shù)。主要的思想就是從任一個(gè)為值1的點(diǎn)開(kāi)始，將所有能達(dá)到的點(diǎn)都標(biāo)記為已訪問(wèn)，如果所有可達(dá)的點(diǎn)都為已訪問(wèn)或0，說(shuō)明這個(gè)島中所有的數(shù)據(jù)已經(jīng)被搜索完畢，則可以去找下一個(gè)島。最后可以得到島的個(gè)數(shù)。在下面的代碼中，已訪問(wèn)的點(diǎn)標(biāo)記為0,如果相鄰的點(diǎn)的值為1，說(shuō)明可擴(kuò)展，則進(jìn)行擴(kuò)展。
解法：
class Solution {
public:
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int m,n,ret = 0;
int numIslands(vector<vector<char>>& grid) {
if(grid.empty())return 0;
m = grid.size(),n = grid[0].size();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){
dfs(i,j,grid);
++ret;
}
}
}
return ret;
}
void dfs(int s,int t,vector<vector<char>>& grid) {
//如果已經(jīng)訪問(wèn)過(guò)或超界，則不需要再擴(kuò)展
if(s<0||s>=m||t<0||t>=n||grid[s][t]=='0'){
return;
}
//標(biāo)記為已經(jīng)訪問(wèn)過(guò)
grid[s][t]='0';
//向下一個(gè)狀態(tài)擴(kuò)展，進(jìn)行遞歸訪問(wèn)
for(int i=0;i<4;i++){
dfs(s+dir[i][0],t+dir[i][1],grid);
}
return;
}
};
3.BFS：廣度優(yōu)先搜索，是和DFS相對(duì)的一種方法，從初始狀態(tài)開(kāi)始，用“輻射狀”的形式遍歷其余所有狀態(tài)。對(duì)于狀態(tài)的遍歷，BFS和DFS能使用的場(chǎng)景有很多有很多相似之處，例如上面的Leetcode129，就也有BFS解法。
BFS一般使用隊(duì)列實(shí)現(xiàn)：將初始狀態(tài)放到隊(duì)列中，當(dāng)出隊(duì)的時(shí)候，將出隊(duì)狀態(tài)的所有未訪問(wèn)過(guò)的后續(xù)狀態(tài)放到隊(duì)列中進(jìn)行后續(xù)訪問(wèn)。BFS的一個(gè)典型應(yīng)用是用于（最短）路徑的尋找，從初始狀態(tài)到目標(biāo)狀態(tài)，因?yàn)锽FS可以保證每次遍歷的時(shí)候從初始狀態(tài)到當(dāng)前隊(duì)列中的狀態(tài)的步數(shù)是相同的；另一個(gè)典型應(yīng)用是對(duì)于某種“分層”的場(chǎng)合，對(duì)于某一狀態(tài)，其后續(xù)的所有狀態(tài)具有相同的性質(zhì)。
舉例1：LeetCode 490，但這個(gè)題是付費(fèi)的，我只看過(guò)解法，并沒(méi)有做過(guò)，迷宮類的題是BFS最經(jīng)典的應(yīng)用。題目和解法可以參考我一直比較崇拜的一個(gè)博主的博客：https://www.cnblogs.com/grandyang/p/6381458.html
** 舉例2：LeetCode 542. 01 Matrix**
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2:
Input:
0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
解法：此題即是“分層”場(chǎng)景的一個(gè)典型應(yīng)用”、對(duì)于每一個(gè)0，其周圍的非0點(diǎn)的狀態(tài)相同：周圍最近的0距離為1；再以這些1為中心，擴(kuò)散出去的第二層具有相同的性質(zhì)。
class Solution {
public:
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
#define pii pair<int,int>
#define mp make_pair
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if(m==0)return matrix;
int n = matrix[0].size();
queue<pii> q;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0){
q.push(mp(i,j));
}else{
matrix[i][j]=INT_MAX;
}
}
}
while(!q.empty()){
pii tmp = q.front();
q.pop();
for(int k=0;k<4;k++){
int a = tmp.first+dir[k][0],b = tmp.second+dir[k][1];
if(a<0||a>=m||b<0||b>=n)continue;
if(matrix[a][b]<=matrix[tmp.first][tmp.second]) continue;
matrix[a][b]=min(matrix[a][b],matrix[tmp.first][tmp.second]+1);
q.push({a,b});
}
}
return matrix;
}
};
舉例3：102. Binary Tree Level Order Traversal
BFS另一個(gè)典型應(yīng)用就是用于樹(shù)或圖的層次遍歷，這個(gè)比較基本，此處不再贅述。
4、Permutation：即全排列，可以獲取1~n的全排列
在C++中，可以使用STL里面的接口來(lái)實(shí)現(xiàn)，例如求一個(gè)數(shù)組的全排列：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
ret.push_back(nums);
while(next_permutation(nums.begin(),nums.end())){
ret.push_back(nums);
}
return ret;
}
};
這個(gè)函數(shù)在使用之前要注意，需要將數(shù)組排序，這樣才能檢測(cè)出來(lái)當(dāng)前的排列是否生成過(guò)。
除此之外，permutation也可以用來(lái)求子集（m中選k個(gè)），即使用m的全排列的前k個(gè)。
permutation的復(fù)雜度為O(n!)，一般只有數(shù)據(jù)量較小的時(shí)候可以使用。
