前言

本文隶属于专栏《LeetCode 刷题汇总》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢!

本专栏目录结构请见LeetCode 刷题汇总

正文

幕布

在这里插入图片描述

幕布链接

36. 有效的数独

题解

Short+Simple Java using Strings

set,j/3+b+i/3,左j右i

import scala.collection.mutable.Set
object Solution {
    def isValidSudoku(board: Array[Array[Char]]): Boolean = {
        val set = Set[String]()
        for(i <- 0 to 8; j <- 0 to 8 if(board(i)(j) != '.')){
            val b = "(" + board(i)(j) + ")"
            if(!set.add(b + i) || !set.add(j + b) || !set.add(i / 3 + b + j / 3)) return false
        }
        true
    }
}

37. 解数独

题解

官方题解

行列boolean二维数组,块 boolean 3 维数组,回溯,appear

public class Solution {
    //(i,j)=true表示数字j+1在第i+1行是否出现,同一行不可重复
    private boolean[][] rows = new boolean[9][9];
    //(i,j)=true表示数字j+1在第i+1列是否出现,同一列不可重复
    private boolean[][] cols = new boolean[9][9];
    //(i,j,k)=true表示数字k+1在第i+1横块第j+1竖块是否出现,同一3*3块内不可重复
    private boolean[][][] blocks = new boolean[3][3][9];
    //表示当前解法是否有效
    private boolean valid = false;
    //用来存储空白格位置的列表,列表里面每个元素表示空白格坐标组成的一维数组,方便递归
    private List<int[]> spaces = new ArrayList<int[]>();

    /**
     * 解数独
     *
     * @param board 数独
     */
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                //判断是否是空白格
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    appear(i, j, board[i][j] - '1', true);
                }
            }
        }
        //此时已经知道哪些行列块哪些数字都已经出现,开始解决数独中的空白格
        backtracking(board, 0);
    }

    /**
     * 回溯解决数独中的空白格
     *
     * @param board 数独
     * @param pos   空白格数组索引
     */
    private void backtracking(char[][] board, int pos) {
        //终止条件,pos == spaces.length 说明此时空白格都已经解决了,结果必然有效
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        //获取当前空白格坐标
        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        //从1到9一个个判断,并且需要满足当前还未求得解
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            //如果当前行当前列当前块都不存在该数字
            if (!rows[i][digit] && !cols[j][digit] && !blocks[i / 3][j / 3][digit]) {
                //我们先让这个数字出现
                appear(i, j, digit, true);
                board[i][j] = (char) (digit + '1');
                //接着进行回溯
                backtracking(board, pos + 1);
                //回溯最后一定要记得恢复
                appear(i, j, digit, false);
            }
        }
    }

    /**
     * 表示坐标为 (i,j) 时数字 digit+1 是否已经出现
     *
     * @param i     第i+1行
     * @param j     第j+1列
     * @param digit 数字digit+1
     * @param flag  是否出现,默认已经出现
     */
    private void appear(int i, int j, int digit, boolean flag) {
        rows[i][digit] = cols[j][digit] = blocks[i / 3][j / 3][digit] = flag;
    }
}

38. 外观数列

题解

官方题解

递归+sb

class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        String str = countAndSay(n - 1);
        char cur = str.charAt(0);
        int count = 0;
        StringBuilder sb = new StringBuilder(str.length());
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != cur) {
                sb.append(count).append(cur);
                cur = str.charAt(i);
                count = 0;
            }
            count++;
        }
        sb.append(count).append(cur);
        return sb.toString();
    }
}

39. 组合总和

题解

官方题解

回溯

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) {
        if (remain > 0) {
            for (int i = start; i < nums.length; i++) {
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i);
                tempList.remove(tempList.size() - 1);
            }
        } else if (remain == 0) {
            list.add(new ArrayList<>(tempList));
        }
    }
}

40. 组合总和 II

题解

官方题解

回溯+continue

class Solution {
    public List<List<Integer>> combinationSum2(int[] cand, int target) {
        Arrays.sort(cand);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs(cand, 0, target, path, res);
        return res;
    }
    void dfs(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList(path));
            return ;
        }
        if (target < 0) return;
        for (int i = cur; i < cand.length; i++){
            if (i > cur && cand[i] == cand[i-1]) continue;
            path.add(path.size(), cand[i]);
            dfs(cand, i+1, target - cand[i], path, res);
            path.remove(path.size()-1);
        }
    }
}
上一篇 下一篇