LeetCode 36~40

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

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

幕布链接

Short+Simple Java using Strings

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
    }
}

官方题解

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 spaces = new ArrayList();

    
    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);
    }

    
    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);
            }
        }
    }

    
    private void appear(int i, int j, int digit, boolean flag) {
        rows[i][digit] = cols[j][digit] = blocks[i / 3][j / 3][digit] = flag;
    }
}

官方题解

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();
    }
}

官方题解

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

    private void backtrack(List> list, List 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));
        }
    }
}

官方题解

class Solution {
    public List> combinationSum2(int[] cand, int target) {
        Arrays.sort(cand);
        List> res = new ArrayList>();
        List path = new ArrayList();
        dfs(cand, 0, target, path, res);
        return res;
    }
    void dfs(int[] cand, int cur, int target, List path, List> 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);
        }
    }
}