当前播放: 33 | 面试题:数独问题
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
33 | 面试题:数独问题

33 | 面试题:数独问题

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
全集22979
新人首单 ¥29.9 原价 ¥129
18
登录 后留言

精选留言(15)

  • 预见
    sometimes naive 老师满怀爱意地笑了
    2018-11-15
    34
  • Lcanboom
    老师,可以给下添加了预处理后的代码吗
    2019-05-26
    2
  • 薛25
    老师不用python来写朴素程序是因为运行的太慢了leetcode上通不过吧。。。。

    作者回复: 不是,只是随机选的语言。我记得leetcode上不同需要的时限不一样。

    2018-12-21
    1
    1
  • 堕落天使
    老师,我按照您讲的第二种方式给数独的DFS加速了(遍历一遍数独,先求出每个格子的可选值,然后再根据可选值的数量进行排序,最后再跟据排过序的列表递归遍历),虽然递归调用的次数大大减少了(从4209次减少到了103次)。但是总体的时间却增加了(从我电脑的0ms变成了4ms)。那么这个加速还有必要吗,它的意义又在哪里呢?
    2018-11-29
    1
  • Geek_949848
    老师,这道题代码那么多,建议以后都用python写会更简洁,更方便教学。表示对于您在java和python代码中切换有点晕了。
    2018-11-26
    1
    1
  • 宋晓明
    老师 这节课跟皇后那节有点难以理解,即使看代码也理解不了 看着看着就绕进去了 是否暂时先不看?

    作者回复: 可以先多多练习递归和分治,然后回来再看和写数独和八皇后问题。

    2018-11-17
    1
  • lzh
    C++,预处理+位运算

    class Solution {
    public:
    void solveSudoku(vector<vector<char>>& board) {
    this->initCriteria(board);
    this->fill(board, 0, 0);
    }

    private:
    vector<int> rowCriteria, colCriteria, cellCriteria;
    int size = 9, cellSize = 3;
    bool finish = false;

    void initCriteria(vector<vector<char>>& board)
    {
    int cellNum;
    char numChar;

    this->rowCriteria = vector<int>(this->size, 0);
    this->colCriteria = vector<int>(this->size, 0);
    this->cellCriteria = vector<int>(this->size, 0);

    for (int x = 0; x < this->size; x++)
    {
    for (int y = 0; y < this->size; y++)
    {
    if (board[x][y] != '.')
    {
    numChar = (int)board[x][y] - int('0');
    this->criteriaAdd(x, y, 1 << numChar);
    }
    }
    }
    }

    void fill(vector<vector<char>>& board, int x, int y)
    {
    int tmp, cellNum;

    while (x < this->size)
    {
    while (y < this->size)
    {
    if (board[x][y] == '.')
    {
    for (int i = 1; i <= this->size; i++)
    {
    tmp = 1 << i;
    cellNum = x / this->cellSize * this->cellSize + y / this->cellSize;
    if ((this->rowCriteria[x] & tmp) == 0 &&
    (this->colCriteria[y] & tmp) == 0 &&
    (this->cellCriteria[cellNum] & tmp) == 0)
    {
    board[x][y] = char('0' + i);
    this->criteriaAdd(x, y, tmp);
    this->fill(board, x, y + 1);
    if (this->finish)
    {
    return;
    }
    else
    {
    this->criteriaAdd(x, y, tmp, false);
    }
    }
    }
    board[x][y] = '.';
    return;
    }
    y++;
    }
    y = 0;
    x++;
    }
    this->finish = true;
    }

    void criteriaAdd(int x, int y, int num, bool add = true)
    {
    int cellNum;

    this->rowCriteria[x] = add ? this->rowCriteria[x] + num : this->rowCriteria[x] - num;
    this->colCriteria[y] = add ? this->colCriteria[y] + num : this->colCriteria[y] - num;

    cellNum = x / this->cellSize * this->cellSize + y / this->cellSize;
    this->cellCriteria[cellNum] = add ? this->cellCriteria[cellNum] + num : this->cellCriteria[cellNum] - num;
    }
    };
    2020-01-03
  • Aliliin
    PHP 实现:

    public function solveSudoku(&$board)
      {
        if (!$board) return;
        $this->sudoku($board);
      }
      public function sudoku(&$board)
      {
        for ($i = 0; $i < count($board); $i++) {
          for ($j = 0; $j < count($board[0]); $j++) {
            if ($board[$i][$j] == ".") {
              for ($c = "1"; $c <= "9"; $c++) {
                if ($this->valid($board, $i, $j, $c)) {
                  $board[$i][$j] = (string)$c;
                  if ($this->sudoku($board)) {
                    return true;
                  }
                  $board[$i][$j] = ".";
                }
              }
              return false;
            }
          }
        }
        return true;
      }

      public function valid($board, $row, $col, $c)
      {

        for ($i = 0; $i < 9; $i++) {
          if ($board[$i][$col] != "." && $board[$i][$col] == $c) return false;
          if ($board[$row][$i] != "." && $board[$row][$i] == $c) return false;
          $x = 3 * floor($row / 3) + floor($i / 3);
          $y = 3 * floor($col / 3) + floor($i % 3);
          if ($board[$x][$y] != "." && $board[$x][$y] == $c) return false;
        }
        return true;
      }
    2019-11-19
  • czh
    深度遍历要注意遍历对象的确定,这里遍历的是“抽象层”(只有空位的地方)
    2019-09-27
  • czh
    搜索+剪枝
    2019-09-27
  • czh
    dfs bfs就是一种遍历的暴力解法,要在这个基础上进行优化
    2019-09-27
  • 大橙子
    too young too simple,sometimes naive
    2019-07-24
  • 大俊stan
    老师,您好。我看了您的数独有效解法,在思考一个问题,会不会存在这样一种情况接:一开始第一个格子是让填三个数字的,但最终结果是只有一个数字是正确的那么另外两个错误的数字是如何执行的呢?后来思考到当执行到一步出现错误时,递归会一层一层的返回,把之前填上错误数值一层一层的重新设置成‘.’就 突然间觉得递归真厉害。
    2019-07-21
  • 曾经瘦过
    native方法比较容易想(和N皇后问题一样的思路 就是valid 有点区别),没玩过数独游戏,所以对如何剪枝并不是太理解。同时还产生了一些疑问,我是从事android 开发的,现在这些搜索的算法感觉比较适合 后台使用,对于前端学习这些算法感觉似乎用处并不是特别大,希望老师能帮忙解惑。

    作者回复: 也需要的,mobile上的应用效率和速度尤其重要。所以一定要对自己代码的时间复杂度有深刻理解。

    2018-12-04
  • yann [扬] :曹同学
    public void solveSudoku(char[][] board){
    // public boolean isValidSudoku(char[][] board) {

    貌似和给定的申明不大一样,编译不过去,
    2018-11-30
收起评论
看过的人还看
数据结构与算法之美

王争  前Google工程师

80讲 | 85881 人已学习

新人首单 ¥29.9 原价 ¥129
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 44820 人已学习

新人首单 ¥19.9 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

109讲 | 45580 人已学习

新人首单 ¥69.9 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

44讲 | 46470 人已学习

新人首单 ¥19.9 原价 ¥99