下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 50 | 面试题:零钱兑换
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
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 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享

精选留言(6)

  • 2019-02-25
    老师, 能不能把所有可能的组合输出来, 而不是仅仅输出一个3, 想了下代码好像比较麻烦

    作者回复: 需要用回溯的办法!

    1
  • 2019-12-03
    PHP 的两种解法
     public $min = PHP_INT_MAX;

        /**
         * dfs 解法
         */
        function coinChange1($coins, $amount)
        {
            if (empty($coins)) return -1;
            if ($amount == 0) return 0;
            sort($coins);
            if ($amount < $coins[0]) return -1;
            $sum = 0;
            $this->dfs($coins, $amount, $sum, count($coins) - 1);
            return $this->min === PHP_INT_MAX ? -1 : $this->min;
        }

        function dfs($coins, $amount, $sum, $index)
        {
            if ($index < 0 || ($sum + $amount / $coins[$index] >= $this->min)) return;
            if ($amount == 0) {
                $this->min = min($this->min, $sum);
                return;
            }
            for ($i = $index; $i >= 0; --$i) {
                if ($amount < $coins[$i]) continue;
                $this->dfs($coins, $amount - $coins[$i], $sum + 1, $i);
            }
        }

        /**
         * 动态规划
         */
        function coinChange($coins, $amount)
        {
            $dp = array_fill(1, $amount + 1, $amount + 1);
            $dp[0] = 0;
            for ($i = 1; $i <= $amount; $i++) {
    // for ($j = 0; $j < count($coins); $j++) {
    // if ($coins[$j] <= $i) {
    // $dp[$i] = min($dp[$i], $dp[$i - $coins[$j]] + 1);
    // }
    // }
                foreach ($coins as $coin) {
                    if ($coin <= $i) {
                        $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
                    }
                }
            }
            return $dp[$amount] > $amount ? -1 : $dp[$amount];
        }
    展开
  • 2019-09-28
    1.复杂度O(x*n)
    2.dp的两种题型:序列“选择”最优问题 序列“排列”(可重复)最优
  • 2019-06-03
    这个题目是要求出最长子序列的长度,所以二分查找法适用,如果要求出内容,是用动态规划。
  • 2019-03-04
    当amount = 2147483647时,视频中的代码是有问题的,很遗憾LeetCode并没有这样的TestCase

    作者回复: 可以帮忙改进下代码。

    1
  • 2019-02-07
    如果不是返回上升序列的size,第二种方式数组维护上升元素是有问题的吧