36. Valid Sudoku
分析：
判断一个9 * 9的数独的方阵是否有效。
要求1.每一行必须包含1-9而且不能重复。2.每一列包含1-9不能重复。3.每一个的小方阵必须包含1-9且不能重复。
参考https://leetcode.com/problems/valid-sudoku/discuss/15472/Short%2BSimple-Java-using-Strings
使用一种编码
比如4在第五行，那么定义为(4)5。
4在第6列，定义为6(4)。
4在右上角的小方格中，定义为0(4)2。
然后遍历每个元素，将编码之后的字符串存入set中，如果已存在则返回false。
Java语言：
public boolean isValidSudoku(char[][] board) {
Set<String> set = new HashSet<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
String str = "(" + board[i][j] + ")";
if (!set.add(str + i) || !set.add(j + str) || !set.add(i / 3 + str + j / 3)) {
return false;
}
}
}
}
return true;
}
37. Sudoku Solver
分析：
数独求解。
对于每一个空白位置，尝试使用1-9去填充，每尝试一个数字之后继续去检查其他的位置，递归直到所有位置都检查成功为止。
Java：
public class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
public boolean solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board)) {
return true;
} else {
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int row, int col, char c) {
int blockRow = 3 * (row / 3);
int blockCol = 3 * (col / 3);
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) {
return false;
}
if (board[row][i] == c) {
return false;
}
if (board[blockRow + i / 3][blockCol + i % 3] == c) {
return false;
}
}
return true;
}
}
38. Count and Say
分析：
定义一个序列如下
- 1
- 11
- 21
- 1211
- 111221
第二个数是去描述第一个数，1个1，所以是11。
第三个数是去描述第二个数，2个1，所以是21。
第四个数是去描述第三个数，1个2，1个1，所以是1211。
要求第n个数是多少，使用递归，边界是n=1时，返回"1"。
Java：
public class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
StringBuilder sb = new StringBuilder();
//找到n-1的结果
String str = countAndSay(n - 1);
//对n-1的结果进行表示
char c = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == c) {
count++;
} else {
sb.append(count);
sb.append(c);
c = str.charAt(i);
count = 1;
}
}
sb.append(count);
sb.append(c);
return sb.toString();
}
}
39. Combination Sum
分析：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
使用dfs，边界是sum刚好等于target，当index 等于数组大小时或者sum大于target时直接返回节省时间。
Java：
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public Solution() {
this.res = new ArrayList<>();
this.temp = new ArrayList<>();
}
public void dfs(int index, int sum, int target, int[] candidates) {
if (sum == target) {
List<Integer> list = new ArrayList<>();
list.addAll(temp);
res.add(list);
return;
}
if (index == candidates.length || sum > target) {
return;
}
//选
temp.add(candidates[index]);
dfs(index, sum + candidates[index], target, candidates);
temp.remove(temp.size() - 1);
//不选
dfs(index + 1, sum, target, candidates);
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(0, 0, target, candidates);
return res;
}
}
40. Combination Sum II
分析：
和上一道题不同的地方是candidates 中的每个数字在每个组合中只能使用一次，
且解集不能包含重复的组合。
把选的分支稍作修改即可。
将 dfs(index, sum + candidates[index], target, candidates);
改成dfs(index + 1, sum + candidates[index], target, candidates);
加入到res的时候先判断一下是否有重复的组合，没有的话再add进去。
Java：
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public Solution() {
this.res = new ArrayList<>();
this.temp = new ArrayList<>();
}
public void dfs(int index, int sum, int target, int[] candidates) {
if (sum == target) {
List<Integer> list = new ArrayList<>();
list.addAll(temp);
if (!res.contains(list)) {
res.add(list);
}
return;
}
if (index == candidates.length || sum > target) {
return;
}
//选
temp.add(candidates[index]);
dfs(index + 1, sum + candidates[index], target, candidates);
temp.remove(temp.size() - 1);
//不选
dfs(index + 1, sum, target, candidates);
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(0, 0, target, candidates);
return res;
}
}
