算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持刷算法题吧。
遇事不决，可问春风，春风不语，即是本心。
我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。
目录
1.有效的数独
2.解数独
3.外观数列
4.组合总数
5.组合总数II
1.有效的数独
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/valid-sudoku/
思路：9*9的数独，要求每行的数字1-9只能出现一次，每列的数字1-9只能出现一次，每个3*3宫格内数字1-9只能出现一次，那么需要开辟三个标记数组用于记录每行、每列、每个3*3宫格内数字1-9出现的次数，若出现次数大于1，则无效，反之有效。
Java版：
class Solution {
public boolean isValidSudoku(char[][] board) {
// 第i行对应的元素j的数目
int [][] row = new int [9][9] ;
// 第i列对应的元素j的数目
int [][] column = new int [9][9] ;
// 当前宫内的第i行第j列元素k的数目
int [][][] square = new int [3][3][9] ;
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
if(board[i][j] != '.'){
int element = board[i][j] - '0' - 1 ;
row[i][element] ++ ;
column[j][element] ++ ;
square[i/3][j/3][element] ++ ;
if(row[i][element] > 1 || column[j][element] > 1 || square[i/3][j/3][element] > 1){
return false ;
}
}
}
}
return true ;
}
}2.解数独
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/sudoku-solver/
思路：同样是需要用三个数字去标记元素在相应的行、列、宫内是否出现，在list集合存储i行与j列上的非数字元素下表，遍历数字1-9搜索所有的非数字下表，填充满足要求的数字。
Java版：
class Solution {
boolean valid = false ;
List<int []> list = new ArrayList<>() ;
public void solveSudoku(char[][] board) {
// dfs搜索加标记的思想
// 先进行标记，若相应的行、列、宫内出现了数字用数组标记为true，反之标记为false
// 对于标记为false的，可以传入值进去
int n = board.length, m = board[0].length ;
boolean [][] row = new boolean[n][m] ;
boolean [][] column = new boolean[n][m] ;
boolean [][][] matrix = new boolean[n/3][m/3][9] ;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(board[i][j] != '.'){
int element = board[i][j] - '0' - 1 ;
row[i][element] = true ;
column[j][element] = true ;
matrix[i/3][j/3][element] = true ;
}else{
list.add(new int []{i,j}) ;
}
}
}
dfs(board, 0, row, column, matrix) ;
}
public void dfs(char [][] board, int k, boolean [][] row, boolean [][] column, boolean [][][] matrix){
if(k==list.size()){
// valid = true ;
return ;
}
int i = list.get(k)[0], j = list.get(k)[1] ;
for(int digit=0; digit<9 && !valid; digit++){
if(!row[i][digit] && !column[j][digit] && !matrix[i/3][j/3][digit]){
board[i][j] = (char)(digit + 1 + '0');
row[i][digit] = column[j][digit] = matrix[i/3][j/3][digit] = true ;
dfs(board, k+1, row, column, matrix) ;
// 回溯
row[i][digit] = column[j][digit] = matrix[i/3][j/3][digit] = false ;
}
}
}
}3.外观数列
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/count-and-say/description/
思路：外观数列是一种有效数列，由1开始，通过n-1次转换成第n项，每次转换通过统计每个元素的数目，第一个元素相同元素的数目，第二个元素是相同的元素值，通过字符串拼接的思想将数字组合成为外观数列。
class Solution {
public String countAndSay(int n) {
String res = "1" ;
for(int i=2; i<=n; i++){
// 每次根据当前的数字生成下一个数字
int left = 0, right = 0 ;
StringBuilder sb = new StringBuilder("") ;
// 一次外观数列
while(right < res.length()){
// 一次相同数字
while(right <res.length() && res.charAt(left) == res.charAt(right)){
right ++ ;
}
sb.append(String.valueOf(right-left)).append(res.charAt(left) ) ;
left = right ;
}
res = sb.toString() ;
}
return res ;
}
}4.组合总数
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/combination-sum/description/
思路：随机选择元素中的数字组合成目标数字，数字可以重复选择，但是要保证每次从初始化位置选择，不允许初始化位置之前的元素，不然是认为重复的选择，所以需要用k标志当前初始化选择的位置。
Java版：
class Solution {
List<Integer> tmp = new ArrayList<>() ;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>() ;
dfs(res, candidates, target, 0) ;
return res ;
}
public void dfs(List<List<Integer>> res, int [] candidates, int target, int k){
if(target == 0){
res.add(new ArrayList<>(tmp)) ;
return ;
}
if(target < 0){
return ;
}
// 每次从第i个开始选,不允许选择第i个之前的
for(int i=k; i<candidates.length; i++){
tmp.add(candidates[i]) ;
dfs(res, candidates, target - candidates[i], i) ;
tmp.remove(tmp.size()-1) ;
}
}
}5.组合总数II
题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/combination-sum-ii/
思路：这道题相比较上一道，除了需要考虑每次的搜索位置标记，还要保证搜索到后面的去重问题，所以需要先排序，在搜索过程中遇到重复的组合跳过。
Java版：
class Solution {
List<Integer> tmp = new ArrayList<>() ;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>() ;
Arrays.sort(candidates) ;
dfs(res, candidates, 0, target) ;
return res ;
}
public void dfs(List<List<Integer>> res, int [] candidates, int k, int target){
if(target == 0){
res.add(new ArrayList<>(tmp)) ;
return ;
}
if(target < 0){
return ;
}
for(int i=k; i<candidates.length; i++){
// 避免选到重复的组合
if(i-1 >=k && candidates[i] == candidates[i-1]){
continue ;
}
tmp.add(candidates[i]) ;
dfs(res, candidates, i+1, target - candidates[i]) ;
tmp.remove(tmp.size() - 1) ;
}
}
}
