目录

岛屿的最大面积

电话号码的字母组合 

二进制手表 

组合总数 

活字印刷

岛屿的最大面积

题目链接：leetcode-695.岛屿的最大面积

示例 

输入：grid = [[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

题目分析 

由题意知，在这个二维数组中，有很多陆地，因此维护一个最大面积，一个临时面积，一个标记数组。遍历二维数组的每一个位置，当遇到陆地且该陆地未被标记过时，就进行搜索，搜索的方式为，从该陆地开始，遍历其上下左右，再遍历每个位置的上下左右，直至遇到边界或海洋或该陆地已被标记过为止。 

class Solution {int ret;int tmpArea;public int maxAreaOfIsland(int[][] grid) {if (grid == null || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int[][] book = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1 && book[i][j] == 0) {tmpArea = 0;dfs(grid, book, i, j);ret = Math.max(ret, tmpArea);}}}return ret;}private void dfs(int[][] grid, int[][] book, int row, int col) {if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {return ;}if (book[row][col] == 1) {return ;}book[row][col] = 1;tmpArea++;dfs(grid, book, row + 1, col);dfs(grid, book, row - 1, col);dfs(grid, book, row, col + 1);dfs(grid, book, row, col - 1);}
}

电话号码的字母组合 

题目链接：leetcode-17.电话号码的字母组合

示例 

输入：digits = "23"

输出： ["ad","ae","af","bd","be","bf","cd","ce","cf"]

题目分析

根据题意，每个数字表示几个字符，因此，定义一个字符串数组来记录每个数字所代表的几个字符

String[] mapString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

 维护一个深度和当前的可能的字母组合，当输入的数字长度等于深度时，就将当前的字母组合加入到结果集中，结束该路径并继续向上回溯；根据深度找到当前的数字，再根据这个数字得到该数字所代表的字符，依次遍历每一种可能，直至所有字符遍历结束。

class Solution {String[] mapString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List ret = new ArrayList<>();public List letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return new ArrayList<>();}StringBuilder curStr  = new StringBuilder("");dfs(digits, curStr, 0);return ret;}private void dfs(String digits, StringBuilder curStr, int curDepth) {if (curDepth == digits.length()) {ret.add(curStr.toString());return ;}int curIndex = digits.charAt(curDepth) - '0';String curMap = mapString[curIndex];for (int i = 0; i < curMap.length(); i++) {dfs(digits, curStr.append(curMap.charAt(i)), curDepth + 1);curStr.deleteCharAt(curStr.length() - 1);}}
}

二进制手表 

题目链接：leetcode-401.二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

 例如

输入：turnedOn = 1

输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

题目分析：

表示时的有1，2，4，8，表示分的有1，2，4，8，16，32，分别定义两个数组用来存储时的可能数字和分的可能数字。由于题目中要求小时0~11，分钟0~59，因此表示时的灯最多亮三个，表示分的灯最多亮5个，因此给定的数字需在0~8之间。依次从每一个时和分进行深度优先搜索，当分钟和大于59或小时和大于11就返回，当深度达到给定的数字时，拼接时和分将其加入到结果集中。

class Solution {int[] hours = {1, 2, 4, 8};int[] minutes = {1, 2, 4, 8, 16, 32};List ret = new ArrayList<>(); public List readBinaryWatch(int turnedOn) {if (turnedOn < 0 || turnedOn >= 9) {return new ArrayList<>();}dfs(turnedOn, 0, 0, 0, 0, 0);return ret;}private void dfs(int turnedOn, int hour, int min, int i, int j, int curDepth) {if (min > 59 || hour > 11) {return ;}if (curDepth == turnedOn) {StringBuilder cur = new StringBuilder();cur.append(hour);if (min < 10) {cur.append(":0" + min);} else {cur.append(":" + min);}ret.add(cur.toString());return ;}for (; i < hours.length; i++) {hour += hours[i];dfs(turnedOn, hour, min, i + 1, j, curDepth + 1);hour -= hours[i];}for (; j < minutes.length; j++) {min += minutes[j];dfs(turnedOn, hour, min, i, j + 1, curDepth + 1);min -= minutes[j];}}
}

组合总数 

题目链接：leetcode-39.组合总数

示例

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]

题目分析：

由于同一个数字可以无限制重复被选取，因此每次从上一个位置开始搜索，边界值的设定：当目前的累加值大于给定的值就返回，当累加值等于给定的值就将其加入结果集中。

class Solution {List> ret = new ArrayList<>();List curRet = new ArrayList<>();int curSum;public List> combinationSum(int[] candidates, int target) {dfs(candidates, target, 0);return ret;}private void dfs(int[] candidates, int target, int pre) {if (curSum > target) {return ;}if (curSum == target) {ret.add(new ArrayList<>(curRet));return ;}for (int i = pre; i < candidates.length; i++) {if (candidates[i] > target) {continue;}curSum += candidates[i];curRet.add(candidates[i]);dfs(candidates, target, i);curSum -= curRet.get(curRet.size() - 1);curRet.remove(curRet.size() - 1);}}
}

活字印刷

题目链接：leetcode-1079.活字印刷

示例

输入："AAB"

输出：8 

题目分析：

 按照题意tiles中每一个位置的字符在组合中只能出现一次，所以可以用一个标记辅助当去组合新的组合时，可以与tiles中的每一个位置组合，但是如果当前位置已经在当前组合中出现过，则跳过 虽然此题中每一个位置的字符在组合中只能出现一次，但是tiles中可能有相同的字符，所以需要考虑重复的组合，使用HashSet可以实现去重

class Solution {public int numTilePossibilities(String tiles) {Set ret = new HashSet<>();List usedIndex = new ArrayList<>();for (int i = 0; i < tiles.length(); i++) {usedIndex.add(0);}StringBuilder curStr = new StringBuilder("");dfs(tiles, curStr, usedIndex, ret);return ret.size();}private void dfs(String tiles, StringBuilder curStr, List usedIndex, Set ret) {if (curStr.length() != 0) {ret.add(curStr.toString());}for (int i = 0; i < tiles.length(); i++) {if (usedIndex.get(i) == 1) {continue;}usedIndex.set(i, 1);dfs(tiles, curStr.append(tiles.charAt(i)), usedIndex, ret);usedIndex.set(i, 0);curStr.deleteCharAt(curStr.length() - 1);}}
}