本周是搜索专题，题目或多或少用到了深度优先搜索或者是广度优先搜索的思想。
1，字母大小写全排列：
1.1.题目描述:
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例: 输入: S = "a1b2" 输出: ["a1b2", "a1B2", "A1b2", "A1B2"] 输入: S = "3z4" 输出: ["3z4", "3Z4"] 输入: S = "12345" 输出: ["12345"]
1.2.题解:
1.2.1.思路:
从左往右依次遍历字符，过程中保持 ans 为已遍历过字符的字母大小全排列。
例如，当 S = “abc” 时，考虑字母 “a”, “b”, “c”，初始令 ans = [“”]，依次更新 ans = [“a”, “A”]， ans = [“ab”, “Ab”, “aB”, “AB”]， ans = [“abc”, “Abc”, “aBc”, “ABc”, “abC”, “AbC”, “aBC”, “ABC”]。
1.2.2.算法
如果下一个字符 c 是字母，将当前已遍历过的字符串全排列复制两份，在第一份的每个字符串末尾添加 lowercase(c)，在第二份的每个字符串末尾添加 uppercase(c)。
如果下一个字符 c 是数字，将 c 直接添加到每个字符串的末尾。
1.3.示例代码:
class Solution(object):
def letterCasePermutation(self, S):
ans = [[]]
for char in S:
n = len(ans)
if char.isalpha():
for i in xrange(n):
ans.append(ans[i][:])
ans[i].append(char.lower())
ans[n+i].append(char.upper())
else:
for i in xrange(n):
ans[i].append(char)
return map("".join, ans)
简单来说，我们依次遍历数组中的每一个元素，并且将当前位为字母的位置，大写–>小写，小写–>大写，数字不变，即可。
想要速度上更快的话可以使用异或运算
首先大小写之间差了32，刚好是2的5次方，异或是不进位的加法。大写的二进制码第5位是0，小写的二进制码是1，所以异或32就实现了大小写的转换。
2，岛屿数量
2.1.题目描述:
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000 00100 00011 输出: 3
2.2.题解:
2.2.1.思路:
这道题目在《啊哈！算法》的第四章中有类似的题目，再见炸弹人和宝岛探险两个小节里面都对深度优先和广度优先探索地图进行了详细的介绍。
这里的解法跟书上的思路类似，不过将其封装在了C语言函数里面
我们遍历储存岛屿信息的每一个坐标，如果为陆地的话，就深度优先搜索其周围的陆地，直到没有陆地可遍历为止，并将周围能够到达的陆地都标记一遍，避免重复，每次这样都使岛屿数量+1，最后输出即可。
2.2.2.示例代码:
int direc[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} }; // dfs的路径方向
void dfs(char** grid, int gridSize, int* gridColSize, int i, int j){
if(grid[i][j]!='1') { // 访问过直接返回
return;
}
// 未访问过，则访问，但先置位
grid[i][j] = '2';
// 作 4 个方向的dfs
for(int k=0;k<4;k++) {
int tmpX = i + direc[k][0];
int tmpY = j + direc[k][1];
if(tmpX<0 || tmpX>=gridSize|| tmpY<0|| tmpY>=gridColSize[0]) { // 四个方向改动后边界防护
continue; // 这种写法关键是 边界防护 是 continue 而不是 return
}
dfs(grid, gridSize, gridColSize, tmpX, tmpY);
}
}
// dfs
int numIslands(char** grid, int gridSize, int* gridColSize){
int count=0;
if(gridSize==0){
return 0;
}
for(int i=0;i<gridSize;i++) {
for(int j=0;j<gridColSize[0];j++) {
if(grid[i][j]=='1'){
dfs(grid, gridSize, gridColSize, i, j);
count++;
}
}
}
return count;
}
3，岛屿的最大面积
3.1.题目描述:
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回
6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回
0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
3.2.题解:
3.2.1.思路:
岛屿的最大面积，跟第二题类似，我们只需要在对每一个岛屿进行深度搜索或者广度搜索的时候，记录下其岛屿的面积，同时与最大岛屿面积max进行比较，遍历结束后即可获得岛屿的最大面积，max的初始值为0，因为有传入数组全为0的情况。
3.2.2.示例代码:
//全局变量，统计当前岛屿面积
int count = 0;
//从第一个1开始搜索四周的岛屿
void SEARCH(int **grid , int i, int j, int gridSize, int *gridColSize){
if (i - 1 >=0 && grid[i - 1][j] == 1)
{
count++;
grid[i - 1][j] = 2;
SEARCH(grid,i - 1,j,gridSize,gridColSize);
}
if (j - 1 >= 0 && grid[i][j - 1] == 1)
{
count++;
grid[i][j - 1] = 2;
SEARCH(grid,i,j - 1,gridSize,gridColSize);
}
if (i + 1 < gridSize && grid[i + 1][j] == 1)
{
count++;
grid[i + 1][j] = 2;
SEARCH( grid, i + 1, j, gridSize, gridColSize);
}
if (j + 1 < *gridColSize && grid[i][j + 1] == 1)
{
count++;
grid[i][j + 1] = 2;
SEARCH(grid,i,j + 1,gridSize,gridColSize);
}
}
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
int max = 0;
for (int i = 0; i < gridSize;i++)
{
for ( int j = 0; j < *gridColSize; j++)
{
if (grid[i][j] == 1)
{
count++;
//将陆地位置标记为2，避免重复
grid[i][j] = 2;
SEARCH(grid,i,j,gridSize,gridColSize);
if (count > max)
{
max = count;
}
}
count = 0;
}
}
return max;
}
4，电话号码的字母组合
4.1.题目描述:
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
4.2.题解:
4.2.1.思路:
这道题的解法是用回溯的方式，在循环里面套了递归调用。本来递归就不好理解了，再加上循环的递归，就更难理解了。
我们先不考虑递归，先看看下面这个问题怎么解决。
假设输入是2，只有一个字符，那么应该怎么解呢？
按照题目要求2=“abc”，所以结果应该是[“a”,”b”,”c”]
先不用想着怎么去写递归，只思考下怎么打印出这个结果。
这个太简单了，一个循环就搞定了：
result = List()
for(i=0;i<len("abc");i++) {
tmp = i
result.add(tmp)
}
return result
上面是伪代码，一个循环就搞定了。
如果输入的是23，应该怎么做呢？23的结果是[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]，我们仍然不考虑怎么去写递归，只是考虑怎么把这个结果给弄出来。代码如下：
result = List()
for(i=0;i<len("abc");i++) {
for(j=0;j<len("def");j++)
tmp = i+j
result.add(tmp)
}
return result
也就是说23这样的长度为2的字符串可以用两层循环搞定。
如果输入的是234呢，仍然不要考虑怎么去写递归，而是想怎么把结果打印出来。
result = List()
for(i=0;i<len("abc");i+=1) {
for(j=0;j<len("def");j+=1) {
for(k=0;k<len("ghi");k+=1) {
tmp = i+j+k
result.add(tmp)
}
}
}
return result
这次用了三层循环。
如果输入的是2345，那么代码可以这么写：
result = List()
for(i=0;i<len("abc");i+=1) {
for(j=0;j<len("def");j+=1) {
for(k=0;k<len("ghi");k+=1) {
for(n=0;n<len("jkl");n+=1)
tmp = i+j+k+n
result.add(tmp)
}
}
}
return result
这次是用了四层循环。现在是不是能看出一些门道了？对的。循环的嵌套层数，就是输入的字符串长度。输入的字符串长度是1，循环只有1层。
输入的字符串长度是3，循环就是3层。如果输入的字符串长度是10，那么循环就是10层。
可是输入的字符串长度是不固定的，对应的循环的嵌套层数也是不固定的，那这种情况怎么解决呢？这时候递归就派上用场了。
对于打印”2345″这样的字符串：
第一次递归就是上图中最下面的方格，然后处理完第一个字符2之后，将输入的字符改变成”345″并调用第二个递归函数
第二次递归处理3，将字符串改变成”45″后再次递归
第三次递归处理4，将字符串改变成”5″后继续递归
第四次递归处理5，将字符串改变成””后继续递归
最后发现字符串为空了，将结果放到列表中并返回
上面是从函数调用的角度去看的，而每次调用下一层递归时，都需要将本层的一些处理结果放到一个临时变量中，再传递给下一层，从这个变量层层传递的变化看，就像一棵树一样，这个算法的时间复杂度很高，是O(3^n)这个级别的，空间复杂度是O(n)
4.2.2.示例代码:
class Solution {
//一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
//这里也可以用map，用数组可以更节省点内存
String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
//注意边界条件
if(digits==null || digits.length()==0) {
return new ArrayList<>();
}
iterStr(digits, "", 0);
return res;
}
//最终输出结果的list
List<String> res = new ArrayList<>();
//递归函数
void iterStr(String str, String letter, int index) {
//递归的终止条件，注意这里的终止条件看上去跟动态演示图有些不同，主要是做了点优化
//动态图中是每次截取字符串的一部分，"234"，变成"23"，再变成"3"，最后变成""，这样性能不佳
//而用index记录每次遍历到字符串的位置，这样性能更好
if(index == str.length()) {
res.add(letter);
return;
}
//获取index位置的字符，假设输入的字符是"234"
//第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
//subString每次都会生成新的字符串，而index则是取当前的一个字符，所以效率更高一点
char c = str.charAt(index);
//map_string的下表是从0开始一直到9， c-'0'就可以取到相对的数组下标位置
//比如c=2时候，2-'0'，获取下标为2,letter_map[2]就是"abc"
int pos = c - '0';
String map_string = letter_map[pos];
//遍历字符串，比如第一次得到的是2，页就是遍历"abc"
for(int i=0;i<map_string.length();i++) {
//调用下一层递归，用文字很难描述，请配合动态图理解
iterStr(str, letter+map_string.charAt(i), index+1);
}
}
}
5，最大人工岛
5.1.题目描述:
在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。
进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
示例 1:
输入: [[1, 0], [0, 1]] 输出: 3 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: [[1, 1], [1, 0]] 输出: 4 解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: [[1, 1], [1, 1]] 输出: 4 解释: 没有0可以让我们变成1，面积依然为 4。
说明:
1 <= grid.length = grid[0].length <= 500 <= grid[i][j] <= 1
5.2.题解:
5.2.1.思路:
这道题目是前两道岛屿问题的升级版，多了一个人工岛的选项，我们可以将一个方格的海变成陆地，然后再求所能达到的最大岛屿的面积。
我们首先想到的可能是对于数组里面的每一个0，先暂时将其变为1，然后深度搜索求出连通块的大小，遍历之后求得最大的连通块的面积，也就是最大人工岛的面积。如果数组里面没有0，那么答案就是整个网格的大小，即全部都是陆地。
class Solution {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};
public int largestIsland(int[][] grid) {
int N = grid.length;
int ans = 0;
boolean hasZero = false;
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 0) {
hasZero = true;
grid[r][c] = 1;
ans = Math.max(ans, check(grid, r, c));
grid[r][c] = 0;
}
return hasZero ? ans : N*N;
}
public int check(int[][] grid, int r0, int c0) {
int N = grid.length;
Stack<Integer> stack = new Stack();
Set<Integer> seen = new HashSet();
stack.push(r0 * N + c0);
seen.add(r0 * N + c0);
while (!stack.isEmpty()) {
int code = stack.pop();
int r = code / N, c = code % N;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (!seen.contains(nr * N + nc) && 0 <= nr && nr < N &&
0 <= nc && nc < N && grid[nr][nc] == 1) {
stack.push(nr * N + nc);
seen.add(nr * N + nc);
}
}
}
return seen.size();
}
}
但是在这个解法当中，我们检查了每一个位置的0，并且对他们都进行了深度搜索，这样的做法是很容易超时的，里面有大量的重复计算。
所以我们换一种解法，对于每一个0.我们将它周围的岛屿的面积累加起来，就可以得到当前位置变成1之后的岛屿面积。
不过我们需要考虑海洋被岛屿包围的情况，例如，考虑 grid = [[0,1],[1,1]] 答案是 4 而不是 1 + 3 + 3，因为 0 右边的邻居和底下的邻居属于同一连通块。
我们可以通过记录连通块编号来解决这个问题，不同的连通块编号不同。这样，我们就可以累加不同编号的连通块面积和。
5.2.2.示例代码:
class Solution {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};
int[][] grid;
int N;
public int largestIsland(int[][] grid) {
this.grid = grid;
N = grid.length;
int index = 2;
int[] area = new int[N*N + 2];
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 1)
area[index] = dfs(r, c, index++);
int ans = 0;
for (int x: area) ans = Math.max(ans, x);
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 0) {
Set<Integer> seen = new HashSet();
for (Integer move: neighbors(r, c))
if (grid[move / N][move % N] > 1)
seen.add(grid[move / N][move % N]);
int bns = 1;
for (int i: seen) bns += area[i];
ans = Math.max(ans, bns);
}
return ans;
}
public int dfs(int r, int c, int index) {
int ans = 1;
grid[r][c] = index;
for (Integer move: neighbors(r, c)) {
if (grid[move / N][move % N] == 1) {
grid[move / N][move % N] = index;
ans += dfs(move / N, move % N, index);
}
}
return ans;
}
public List<Integer> neighbors(int r, int c) {
List<Integer> ans = new ArrayList();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < N && 0 <= nc && nc < N)
ans.add(nr * N + nc);
}
return ans;
}
}