51. 岛屿数量（图论/200）

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
假设：
m == grid.length；
n == grid[i].length；
1 <= m, n <= 300；
grid[i][j] 的值为 ‘0’ 或 ‘1’。

【分析】
解法1：深度优先搜索（DFS）
循环每个元素，遇到“1”则增加岛屿数，同时调用深度优先搜索方法，递归地根据当前元素是否为“1”将当前元素十字路线上的元素都置“0”，使每个岛屿块最终只剩一个“1”。
解法2：广度优先搜索（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution{
	//深度优先搜索
	public int NumIslands1(char[][] grid){
		if(grid==null || grid.Length==0) return 0;
		
		int numIslands=0;
		int rows=grid.Length;
		int cols=grid[0].Length;
		
		for(int i=0;i<rows;i++){
			for(int j=0;j<cols;j++){
				if(grid[i][j]=='1'){
					numIslands++;
					DFS(grid,i,j,rows,cols);
				}
			}
		}
		return numIslands;
	}
	
	private void DFS(char[][] grid, int i, int j, int rows, int cols){
		if(i<0 || i>=rows || j<0 || j>=cols || grid[i][j]!='1'){//中断递归
			return;
		}
		
		grid[i][j]='0';
		
		//顺序为“下、上、右、左”，不是固定顺序
		DFS(grid,i+1,j,rows,cols);
		DFS(grid,i-1,j,rows,cols);
		DFS(grid,i,j+1,rows,cols);
		DFS(grid,i,j-1,rows,cols);
	}
}

55. 全排列（回溯/46）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
假设：
1 <= nums.length <= 6；
-10 <= nums[i] <= 10；
nums 中的所有整数 互不相同。
示例：输入：nums = [1,2,3]；输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

【分析】
解法：回溯法（递归）
时间复杂度O(n*n!)
递推：函数不断调用自身，将问题分解为更小的子问题。
回溯：当递归达到基本情况（即不能再分解的子问题）时，逐层返回结果。
回溯算法通常基于递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution{
	public IList<IList<int>> Permute(int[] nums){
		IList<IList<int>> resAll=new List<IList<int>>();
		//Q:为什么只有第一个IList转为List：
		//A:将外层的IList接口转为具体实现的List，这个实例化过程是正确的。
		//不能写成IList<IList<int>> res = new List<List<int>>();
		//因为res所声明的变量类型IList<IList<int>> 要求存储的是 IList<int> 类型的对象，而 List<List<int>> 无法满足这个要求。
		//IList<IList<int>> 是声明类型，表示可以存储 IList<int> 类型对象的集合。
		//new List<IList<int>>() 是具体的实现，表示创建一个可以存储 IList<int> 类型对象的 List。
		//这种写法符合接口和实现类的关系，同时也符合泛型的类型安全要求。
		
		IList<int> resOne=new List<int>();//用于记录其中一组排列
		Trackback(nums,resAll,resOne);
		return res;
	}
	
	public void Trackback(int[] nums, IList<IList<int>> resAll, IList<int> resOne){
		//Q:为什么声明res时具体实现为List<IList<int>>类型后，Trackback接收的类型还是IList<IList<int>>？
		//A:接口的多态性
		//使用接口类型作为参数可以让方法更加通用。Trackback 方法不需要知道 res 的具体实现是什么，只需要知道它是一个实现了 IList<IList<int>> 接口的对象即可。这意味着你可以传递任何实现了 IList<IList<int>> 的对象，而不仅仅是 List<IList<int>>。
		//在Permute方法中传给Trackback的res是List<IList<int>>，其它地方可能调用Trackback可以使用IList<IList<int>>，参数类型可以使用接口。
		
		if(resOne.Count==nums.Length){//跳出一次递归（循环）
			resAll.Add(new List<resOne>);
			return;
		}
		
		for(int i=0;i<nums.Length;i++){
			if(!resOne.Contains(nums[i])){
				resOne.Add(nums[i]);
			}else{
				continue;
			}
			Trackback(nums,resAll,resOne);
			resOne.RemoveAt(resOne.Count-1);//回撤
		}
	}
}