引言
現(xiàn)在互聯(lián)網(wǎng)的招工流程，算法題是必不可少的，對于像我這種沒搞過ACM的吃瓜群眾宇姚，好在有l(wèi)eetcode匈庭，拯救我于水火。于是乎浑劳，斷斷續(xù)續(xù)阱持，刷了一些題，其中一些題還是值得細(xì)細(xì)品味的魔熏，現(xiàn)把一些問題整理一下衷咽，有些解法是我自己寫的，也有些解法是參考了discuss中的答案蒜绽，當(dāng)做是秋招的一個(gè)小小總結(jié)镶骗。由于水平有限，代碼寫得并不好躲雅，選的題目也只能用于入門鼎姊，希望大家見諒。
暴力破解
暴力破解相赁，據(jù)我個(gè)人理解相寇，就是遍歷整棵搜索樹，沒有刪繁就簡钮科，緊是單單的搜索和匹配唤衫。
1、基本暴力破解：對于最基本的暴力破解绵脯，就是取出所有的可能佳励，和題目中的條件相比較，直到找到符合題意的答案蛆挫。
舉例：雞兔同籠問題赃承，已知x個(gè)頭，y只腳璃吧，問兔和雞的個(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)上常使用遞歸方法來實(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)開始，將所有能達(dá)到的點(diǎn)都標(biāo)記為已訪問阳距，如果所有可達(dá)的點(diǎn)都為已訪問或0塔粒，說明這個(gè)島中所有的數(shù)據(jù)已經(jīng)被搜索完畢，則可以去找下一個(gè)島筐摘。最后可以得到島的個(gè)數(shù)卒茬。在下面的代碼中，已訪問的點(diǎn)標(biāo)記為0,如果相鄰的點(diǎn)的值為1蓄拣，說明可擴(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)訪問過或超界球恤，則不需要再擴(kuò)展
if(s<0||s>=m||t<0||t>=n||grid[s][t]=='0'){
return;
}
//標(biāo)記為已經(jīng)訪問過
grid[s][t]='0';
//向下一個(gè)狀態(tài)擴(kuò)展，進(jìn)行遞歸訪問
for(int i=0;i<4;i++){
dfs(s+dir[i][0],t+dir[i][1],grid);
}
return;
}
};
3.BFS：廣度優(yōu)先搜索荸镊，是和DFS相對的一種方法咽斧，從初始狀態(tài)開始，用“輻射狀”的形式遍歷其余所有狀態(tài)躬存。對于狀態(tài)的遍歷张惹，BFS和DFS能使用的場景有很多有很多相似之處，例如上面的Leetcode129岭洲，就也有BFS解法宛逗。
BFS一般使用隊(duì)列實(shí)現(xiàn)：將初始狀態(tài)放到隊(duì)列中，當(dāng)出隊(duì)的時(shí)候盾剩，將出隊(duì)狀態(tài)的所有未訪問過的后續(xù)狀態(tài)放到隊(duì)列中進(jìn)行后續(xù)訪問雷激。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)用是對于某種“分層”的場合，對于某一狀態(tài)驻粟，其后續(xù)的所有狀態(tài)具有相同的性質(zhì)根悼。
舉例1：LeetCode 490，但這個(gè)題是付費(fèi)的，我只看過解法挤巡，并沒有做過剩彬，迷宮類的題是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.
解法：此題即是“分層”場景的一個(gè)典型應(yīng)用”矿卑、對于每一個(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)用就是用于樹或圖的層次遍歷，這個(gè)比較基本徘意，此處不再贅述苔悦。
4、Permutation：即全排列椎咧，可以獲取1~n的全排列
在C++中玖详，可以使用STL里面的接口來實(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ù)組排序蟋座，這樣才能檢測出來當(dāng)前的排列是否生成過。
除此之外脚牍，permutation也可以用來求子集（m中選k個(gè)）向臀，即使用m的全排列的前k個(gè)。
permutation的復(fù)雜度為O(n!)诸狭，一般只有數(shù)據(jù)量較小的時(shí)候可以使用券膀。
