每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！
第一题：36. 有效的数独 - 力扣（LeetCode）
题目要求我们进行判断，我们不需要自己填写，所以要一个标志位，来看当前的值是否在行、列、格中出现过，每当这时候可以考虑使用位掩码。
class Solution {
public boolean isValidSudoku(char[][] board) {
int[] line = new int[9];// 行
int[] col = new int[9];// 列
int[] cell = new int[9];// 9宫格
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// 如果当前位置没有数字，不用判断。
if (board[i][j] == '.')
continue;
//使用位掩码来记录数字
int shift = 1 << (board[i][j] - '0');// 确定第几位
int k = (i / 3) * 3 + j / 3;// 9宫格的第几个。
// 如果对应的位置只要有一个被标记过，说明有冲突，直接返回false。
//&与要求两边完全相同才大于0，下面这一步在判断是否有相同数字出现过
if ((col[i] & shift) > 0 || (line[j] & shift) > 0
|| (cell[k] & shift) > 0)
return false;
// 把当前位置所在的行，列以及9宫格都标记为该数字已经存在。
//或|只要某一位是1，则都是1，所以不管原来的col[i]等是否为0，
//反正判断的时候还是判断col[i] & shift，所以下面这样写正确
//建议自己手动模拟一下
col[i] |= shift;
line[j] |= shift;
cell[k] |= shift;
}
}
return true;
}
}第二题：37. 解数独 - 力扣（LeetCode）
class Solution {
//类似于dfs，要找到刚好唯一一组解，可能会涉及到已经放入的值回退的情况
//直接使用空间换时间了，不回退直接判断可不可以放，注意看两层循环那个
//if-for-return的逻辑：如果是'.' 那么能不能放数字，如果放了就继续，否则return false
//再注意看for循环里的逻辑，判断这个数字放进去满足数独不，所以有一个isValidSudoku的判断函数
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(char[][] board){
for (int i = 0; i < 9; i++){ // 遍历行
for (int j = 0; j < 9; j++){ // 遍历列
if (board[i][j] != '.'){ // 跳过原始数字
continue;
}
for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
if (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
//注意这个地方的判断，潜逃了两层true的判断
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
private boolean isValidSudoku(int row, int col, char val, char[][] board){
//分别判断行列格里是否存在相同元素
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
第三题：38. 外观数列 - 力扣（LeetCode）
public class Solution {
// countAndSay 方法用于生成一个特定的字符串序列。
// 序列的第 n 项是通过将第 n-1 项字符串中的连续相同字符进行计数和描述来生成的。
public static String countAndSay(int n) {
// 递归出口：如果 n 为 1，则返回字符串 "1"，这是序列的第一项。
if (n == 1) {
return "1";
}
// 递归调用：如果 n 大于 1，则先递归调用 countAndSay(n - 1) 生成第 n-1 项，
// 然后调用 transfer 方法将第 n-1 项转换为第 n 项。
return transfer(countAndSay(n - 1));
}
// transfer 方法接受一个字符串 s 作为输入，并生成下一个字符串。
// 它通过计数 s 中连续出现的相同字符，并将计数和字符拼接起来形成新的字符串。
public static String transfer(String s) {
StringBuilder sb = new StringBuilder(); // 使用 StringBuilder 来构建最终的字符串。
int count = 1; // 初始化计数器，用于计数连续相同字符的数量。
int length = s.length(); // 获取输入字符串的长度。
int i;
char temp = s.charAt(0); // 初始化临时变量 temp 为字符串的第一个字符。
// 遍历输入字符串 s。
for (i = 1; i <= length; i++) {
// 如果当前字符 temp 与 s.charAt(i) 相同，继续计数。
while (i < length && temp == s.charAt(i)) {
count++; // 连续字符计数加 1。
i++; // 移动到下一个字符。
}
// 如果 i < length，说明找到了不同的字符，更新 temp。
if (i < length) {
temp = s.charAt(i);
}
// 将当前字符的计数和字符本身添加到 StringBuilder 中。
sb.append(count); // 添加计数。
sb.append(s.charAt(i - 1)); // 添加字符本身。
// 重置计数器，为下一个字符的计数做准备。
count = 1;
}
// 返回构建好的字符串。
return sb.toString();
}
}第四题：39. 组合总和 - 力扣（LeetCode）
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//为了避免排列的重复情况出现，所以我们先进行排序
Arrays.sort(candidates);
traversal(0, target, candidates);
return res;
}
private void traversal(int start, int target, int[] candidates){
//把满足条件的提出来
if(target == 0){
res.add(new ArrayList<>(path));
return;
}
for(int i = start; i < candidates.length; i++){
//对于每一个candidate进行遍历，因为我们升序排列了，所以一旦选过了，
//就不会再回去，就避免了排列情况的发生，实际上变为了组合
if(target - candidates[i] >= 0){
path.add(candidates[i]);
traversal(i, target - candidates[i], candidates);
//记得回溯
path.remove(path.size() - 1);
}else{
//注意给一个边界条件，如果不满足了就退出
break;
}
}
}
}第五题：40. 组合总和 II - 力扣（LeetCode）
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // 对数组进行排序
List<List<Integer>> res = new ArrayList<>();
//因为每个候选人数字只能出现一次，所以我们与上一题不同的地方是要多加入一个标记数组
backtrack(candidates, target, 0, new ArrayList<>(), res, new boolean[candidates.length]);
return res;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res, boolean[] used) {
if (target == 0) {
res.add(new ArrayList<>(path)); // 找到一种组合
return;
}
for (int i = start; i < candidates.length; i++) {
// 本质来说，这题有重复元素的排列导致的结果重复的问题，必须去重
// 跳过重复的元素，注意这种去重的方式（避免上一行提到的情况）
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// 如果当前元素大于剩余目标，直接返回
//注意边界条件
if (candidates[i] > target) {
break;
}
// 使用当前元素
if (!used[i]) {
used[i] = true; // 标记为已使用
path.add(candidates[i]); // 添加到路径
backtrack(candidates, target - candidates[i], i + 1, path, res, used); // 递归调用
path.remove(path.size() - 1); // 回溯，移除当前元素
used[i] = false; // 重置为未使用
}
}
}
}
