給自己的目標(biāo)：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題
在做題的過程中記錄下解題的思路或者重要的代碼碎片以便后來翻閱。
項(xiàng)目源碼：github上的Leetcode
36. Valid Sudoku
題目：給出九個(gè)字符串，每個(gè)字符串有數(shù)字和 '.'組成畜份，'.'表示要填寫的數(shù)字，判斷這九個(gè)字符串能否組成一個(gè)有效的數(shù)獨(dú)淘正。
有效數(shù)獨(dú)：每個(gè)單元摆马，每行臼闻，每列都必須有1-9組成，不能重復(fù)囤采。不一定要求有解述呐。
不要傻乎乎的循環(huán)去求每行每列和每個(gè)單元是否存在重復(fù)數(shù)字，可以給每個(gè)數(shù)字進(jìn)行位置標(biāo)記蕉毯，再利用set看是否有重復(fù)乓搬。
'4' in row 7 is encoded as "(4)7".
'4' in column 7 is encoded as "7(4)".
'4' in the top-right block is encoded as "0(4)2".
public class Solution {
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] != '.') {
String b = "(" + board[i][j] + ")";
if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i / 3 + b + j / 3))
return false;
}
}
}
return true;
}
}
37. Sudoku Solver
題目：給出一個(gè)有效的數(shù)獨(dú)表思犁，求空缺值。假設(shè)必定有解进肯。
使用回溯來求解激蹲，每個(gè)空格可以填1-9的值，每填入一個(gè)值去判斷數(shù)獨(dú)表是否是有效的數(shù)獨(dú)表江掩，若有效填寫下一個(gè)無效則循環(huán)0-9,循環(huán)結(jié)束后沒有找到值則回到上一個(gè)学辱。
public class Solution {
public void solveSudoku(char[][] board) {
sudoku(board, 0,0);
}
public boolean sudoku(char[][] board, int i, int j) {
if (j >= 9) {
return sudoku(board, i + 1, 0);
}
if (i >= 9) {
return true;
}
char c = board[i][j];
if (c != '.') {
return sudoku(board, i, j + 1);
} else {
for (int k = 1; k <= 9; k++) {
char cc = (char) (k + '0');
board[i][j] = cc;
if (isValidSudoku(i, j, board)) {
if (sudoku(board, i, j + 1)) {
return true;
}
}
board[i][j] = '.';
}
}
return false;
}
public boolean isValidSudoku(int i, int j, char[][] board) {
for (int k = 0; k < 9; k++) {
if (k != j && board[i][k] == board[i][j])
return false;
}
for (int k = 0; k < 9; k++) {
if (k != i && board[k][j] == board[i][j])
return false;
}
for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {
for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) {
if ((row != i || col != j) && board[row][col] == board[i][j])
return false;
}
}
return true;
}
}
38. Count and Say
題目：n=1時(shí)輸出字符串1；n=2時(shí)环形，數(shù)上次字符串中的數(shù)值個(gè)數(shù)策泣，因?yàn)樯洗巫址?個(gè)1抬吟，所以輸出11萨咕；n=3時(shí)火本，由于上次字符是11危队，有2個(gè)1，所以輸出21交掏；n=4時(shí)，由于上次字符串是21刃鳄，有1個(gè)2和1個(gè)1盅弛，所以輸出1211。依次類推叔锐，寫個(gè)countAndSay(n)函數(shù)返回字符串挪鹏。
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
這道題理解了題意就是一道簡(jiǎn)單題愉烙，代碼如下：
public class Solution {
public String countAndSay(int n) {
String result = "1";
if (n <= 1) {
return result;
}
for (int i = 1; i < n; i++) {
StringBuilder res = new StringBuilder();
int count = 1;
char c = result.charAt(0);
for (int j = 1; j < result.length(); j++) {
if (c == result.charAt(j)) {
count++;
} else {
res.append(count).append(c);
count = 1;
c = result.charAt(j);
}
}
res.append(count).append(c);
result = res.toString();
}
return result;
}
}
39. Combination Sum
題目：給出一組數(shù)字和一個(gè)目標(biāo)數(shù)讨盒，數(shù)組內(nèi)部的數(shù)字不重復(fù)步责，但可以多次使用返顺。求數(shù)組里面和為目標(biāo)數(shù)的組合。要求組合不能重復(fù)蔓肯。
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
遞歸求解遂鹊。
1）當(dāng)目標(biāo)值與當(dāng)前所選擇的值相等時(shí)，將組合加入列表時(shí)蔗包。
2）當(dāng)目標(biāo)值大于所選擇的值時(shí)秉扑，將值加入組合并將目標(biāo)值減去選擇值進(jìn)入下一輪遞歸。
3）當(dāng)目標(biāo)值小于所選擇的值调限，跳過當(dāng)前值误澳。
public class Solution {
List<List<Integer>> cs = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
sum(candidates, target, new ArrayList<>(), 0);
return cs;
}
public void sum(int[] candidates, int target, List<Integer> list, int index) {
for (int i = index; i < candidates.length; i++) {
List<Integer> temp = new ArrayList<>(list);
if (target == candidates[i]) {
temp.add(candidates[i]);
cs.add(temp);
continue;
} else if (candidates[i] > target) {
sum(candidates, target, temp, i + 1);
break;
} else if (target > candidates[i]) {
temp.add(candidates[i]);
sum(candidates, target - candidates[i], temp, i);
}
}
}
}
40. Combination Sum II
題目：給出一組數(shù)字和一個(gè)目標(biāo)數(shù)秦躯，數(shù)組內(nèi)部的數(shù)字有重復(fù)忆谓，且只能使用一次。求數(shù)組里面和為目標(biāo)數(shù)的組合陪毡。要求組合不能重復(fù)
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
我使用的方法是使用map來去重和記錄數(shù)字重復(fù)的個(gè)數(shù)，雖然也能AC但map的尋址拖慢了整個(gè)運(yùn)行速度勾扭。最優(yōu)的解法是先對(duì)數(shù)組進(jìn)行排序，當(dāng)遇到重復(fù)的數(shù)字時(shí)跳過重復(fù)的步驟妙色。
/**
* 有待優(yōu)化的代碼
*/
public class Solution {
List<List<Integer>> cs = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < candidates.length; i++) {
map.put(candidates[i], map.getOrDefault(candidates[i], 0) + 1);
}
sum(target, new ArrayList<>(), map);
return cs;
}
public void sum(int target, List<Integer> list, Map<Integer, Integer> map) {
Set<Integer> keys = map.keySet();
Map<Integer, Integer> tempMap = new HashMap<>(map);
for (int key : keys) {
List<Integer> temp = new ArrayList<>(list);
int value = tempMap.get(key);
if (target == key) {
temp.add(key);
cs.add(temp);
tempMap.remove(key);
continue;
} else if (key > target) {
tempMap.remove(key);
sum(target, temp, tempMap);
break;
} else if (target > key) {
temp.add(key);
if (value > 1) {
tempMap.put(key, tempMap.get(key) - 1);
} else {
tempMap.remove(key);
}
sum(target - key, temp, tempMap);
tempMap.remove(key);
}
}
}
}
