LeetCode

动态规划解法

确定状态

最后一步

无论机器人用多少种方式到达右下角，最后的一步只能是向下或者向右

右下角的坐标为

那么它的上一步一定是在 或

子问题

如果有种方式走到 ，有 种方式走到，那么走到的方式为种

为什么可以是种

满足加法需要保证两点:

• 无重复，机器人不坑能从的位置走到的位置，不会有重复路线

• 无遗漏，机器人只能从其他两个位置走到最终位置，在没有其他的方式

所以问题就可以转化为有多少种方式走到或的位置，并求两者之和

子问题缩小了元问题的规模，可以忽略最右边一列，或最下面一列，这也是子问题的作用

状态

最终可以确定状态： f[i][j]为机器人有多少种方式走到右下角(i,j)

转移方程

初始条件和边界情况

• 初始条件： f[0][0]=1机器人只有一种方式到左上角，也就是不动

• 边界条件： 第一行和第一列只有一种走法，一直向右或一直向下,因为第一行没有上面的格子，不能从上面走到下面，第一列没有左边的格子，不能从左边走到右边，所以f[0->i][0]=1 f[0][0->j]=1，其他的格子都可以使用状态转移方程

计算顺序

• f[0][0]=1

• 计算第0行： f[0][0],f[0][1],…,f[0][j-1]

• 计算第1行： f[1][0],f[1][1],…,f[1][j-1]

• 计算第i-1行： f[i-1][0],f[i-1][1],…,f[i-1][j-1]

计算顺序并是不里所当然，或是为了循环方便，如下图所示:

B格子在计算i-1行时刚刚算过，A格子在上面一步计算i-2行时计算过，所以可以计算出f[i-1][j-2]为最终返回结果

1
2
3
4
5
6
7
8
9
10
11
12
13

var uniquePaths = function (m, n) {
    var i, j, arr = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i === 0 || j === 0) {
                Array.isArray(arr[i]) ? arr[i][j] = 1 : arr[i] = [1]
            } else {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
    }
    return arr[i - 1][j - 1];
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

终端窗口字体大小

ctrl + shift + = 放大终端窗口字体

ctrl + - 缩小终端窗口字体

命令格式

parameter 参数
options 选项
[] 表示可选

1

command [-options] [parameter]

查阅命令帮助信息

• 显示command 命令的帮助信息

1

command --help

• 查询command命令的使用手册 man是manual手册的意思，包含命令的详细信息

1

man command

显示内容较多时可以使用操作键

自动补全

打出文件/目录/命令之后，按下tab键

• 如果没有歧义（包含输入字母有唯一的对应），系统会自动补全

• 如果有多个包含当前输入字母的 文件/目录/命令，再次按下tab键会自动提示

曾经使用过的命令

按 上/下 光标键可以在曾经使用过的命令之间切换

如果想退出按ctrl+c

快捷方式

LeetCode

动态规划详解

动态规划

注意

• 边界情况amount===0时返回0，0元需要0枚硬币

• stack[i - coins[j]] stack[i] 需要判断为undefined的情况，因为JavaScript中Math.min(undefined)===NaN需要特殊处理，用Infinity占位，在使用Math.min(1,Infinity) 可以取得最小值

• 返回时需要判断不能匹配的情况，如果当前位置为Infinity表示不能匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

var coinChange = function (coins, amount) {
    // 边界情况
    if (amount === 0) return 0;
    // 初始化
    var stack = [0],
        n = coins.length,
        i, j, a, b;
    for (i = 1; i <= amount; i++) {
        //f[i] = min{f(i-coins[0]),f(i-coins[1]),...,f(i-coins[j])}
        for (j = 0; j < n; j++) {
            a = stack[i - coins[j]] === undefined ? Infinity : stack[i - coins[j]];
            b = stack[i] === undefined ? Infinity : stack[i];
            stack[i] = Math.min(a, b)
        }
    }
    if (stack[i - 1] === Infinity) {
        return -1;
    }
    return stack[i - 1]
};

另一种优雅的边界处理方式

• 默认stack[i] = Infinity 避免了上面判断 stack[i] === undefined的情况

• i >= coins[j] 时才会比较，如果硬币的面额比需要凑出的总金额还要大，显然不需要比较，从而避免上面stack[i - coins[j]] === undefined的情况

• stack[i - coins[j]] !== Infinity 表示如果上一步的结果是Infinity,也就是上一步没有办法凑出指定面额，那下一步也凑不出指定面额，在Javascript中虽然可以不写这一步，只会增加依次赋值操作，但在其他语言中如 C++,如果不加判断Integer.MAX_VALUE+1可能会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function coinChange(coins, amount) {
    if (amount === 0) return 0;
    var stack = [0],
        n = coins.length,
        i, j;
    for (i = 1; i <= amount; ++i) {
        stack[i] = Infinity;
        for (j = 0; j < n; j++) {
            if (i >= coins[j] && stack[i - coins[j]] !== Infinity) {
                stack[i] = Math.min(stack[i - coins[j]] + 1, stack[i])
            }
        }
    }
    if (stack[i - 1] === Infinity) {
        return -1;
    }
    return stack[i - 1];
}

复杂度分析

• 时间复杂度：，其中 是金额， 是面额数。我们一共需要计算 个状态， 为题目所给的总金额。对于每个状态，每次需要枚举 n个面额来转移状态，所以一共需要 的时间复杂度。

• 空间复杂度： 数组长度等于金额的大小

什么样的问题可以使用动态规划

• 计数

  • 到达一个位置有多少中走法
  • 有多少种方式选出 k 个数使其和使 sum

• 求最大值最小值

  • 从左下角到右下角路径的最大数字和
  • 最长上升子序列长度

• 存在性 博弈性

  • 取石子游戏，先手是否必胜
  • 能不能选出 k 个数使其和是 sum

问题描述

一起提动态规划，可能最先想到的就是硬币问题，这也是动态规划的最常见问题。

你有三种硬币，面值分别为 2 元，5 元，7 元，每种硬币数量足够多。买一本书须要 27 元，如何使用最少的硬币组合正好可以付清 27 元

从直觉上我们可能会这样尝试：

• 因为要最够少的硬币，那就尽量选择大的面额

• 拿 3 个 7 元硬币，还剩 6 元，发现如果使用 5 元硬币不能凑够 6 元，所以选择用 3 个两元硬币

• 我想到的结果是 2 元，2 元，2 元，7 元，7 元，7 元 6 枚硬币

• 但正确的结果是 5 元，5 元，5 元，5 元，7 元 5 枚硬币

问题所在

我们通过直觉的分析，并不是正确的思路，因为不能通过数学的方式证明。

下面来学习一下动态规划，通常动态规划有四个组成部分

确定状态

① 状态是动态规划中最重要的概念

② 常见的，动态规划解题时会创建一个数组，数组的每个元素f[i]或者f[i][j]代表什么,类似数学中的

③ 确定状态时关键的两个概念

  1） 最后一步

  以题目为例，随算我们不知道最少的方式是什么，但它肯定是由 这么多硬币加一起组成的，这些硬币加在一起的面值是 27

  其中一定会有一枚最后取到的硬币

  除去这枚硬币，前面的硬币面值是

  这其中有两个非常重要的关键点：

    a. 不关心前面 枚硬币如何拼出 的面值，可能有 1 种方法，也可能有 100 种，虽然现在不知道（最后一枚硬币面值）,(最少使用的硬币数量)，但可以肯定的是我们用了枚硬币，拼出了 的面值。

    b. 为什么前面一定是枚硬币，而不能更少？ 因为我们假设的是最优策略，如果前面可以用少于枚硬币，组成 的面值，那么加上最后一枚硬币，总硬币的数量还是小于,与最初假设的最优策略 枚硬币相违背。换句话说，对于拼出的面值，需要使用 枚硬币，这仍然是一个最优策略。

  2） 子问题

  通过上面的分析问题变成，拼出的面值，最少需要多少硬币

  原问题是拼出的面值，最少需要多少硬币

  可以发现问题本身没有变化，但是规模更小，这就是子问题的意义

  为了简化定义，设定状态 最少用多少硬币拼出

回顾一下如何抽象出状态的：我们先考虑最后一步，提取出除了最后一步之后的子问题，发现子问题和原问题，都是求最少硬币数量，原问题求的是拼除的最少硬币数量，子问题是拼出的最少硬币数量。所以我们用 表示最少硬币数量的结果，用 表示需要求解的面值。

  到目前为止，我们还是不知道最后那个的硬币是多少，但它只可能是 2，5，或者 7，所以：

  如果 ,则 最后一枚硬币为 2

  如果 ,则 最后一枚硬币为 5

  如果 ,则 最后一枚硬币为 7

  所以需要的最少硬币数，就是上面三种情况中的最小值

递归求解

通过上面的分析，找到了最小硬币数量的表示方法

从硬币总额的角度思考：

a. 如果求解总额>=7,最后一个硬币，可以是 2，5，7

b. 如果求解总额>=5,最后一个硬币，可以是 2，5

c. 如果求解总额>=2,最后一个硬币，可以是 2

b. 边界情况总额是 0， 结果返回 0，0 元需要 0 枚硬币

1
2
3
4
5
6
7
8
9
10
11
12

function fn(x) {
  if (x === 0) return 0;
  var res = Infinity;
  if (x >= 7) {
    res = Math.min(fn(x - 2) + 1, fn(x - 5) + 1, fn(x - 7) + 1);
  } else if (x >= 5) {
    res = Math.min(fn(x - 2) + 1, fn(x - 5) + 1);
  } else if (x >= 2) {
    res = fn(x - 2) + 1;
  }
  return res;
}

从最后一枚硬币角度考虑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function fn(x) {
  if (x === 0) return 0;
  var res = Infinity;
  //最后一枚硬币是7
  if (x >= 7) {
    res = Math.min(fn(x - 7) + 1, res);
  }
  if (x >= 5) {
    res = Math.min(fn(x - 5) + 1, res);
  }
  if (x >= 2) {
    res = Math.min(fn(x - 2) + 1, res);
  }
  return res;
}

存在的问题：递归做了大量的重复计算，指数级的时间复杂度，所以需要通过将已经计算的结果保存下来，并改变计算顺序，这就是动态规划的状态转移方程

转移方程

转移方程通常在分析子问题的时候已经分析清楚，对于任意 X

但是想避免使用递归还需要下面的两个分析过程

初始条件和边界情况

• 如果,,小于 0 怎么办

• 用正无穷来表示不能拼出某个值

• 初始条件，用转移方程算不出来的需要定义，,所以需要定义边界情况。

计算顺序

计算顺序的分析是解决避免递归问题的根本原因。

递归是从大到小计算的在计算 时， 都不知道，要只有执行到,才能得到第一个计算结果，且直接过程中没有保存执行结果，导致每一个结果都需要重复计算。可以通过缓存计算结果优化递归。

所以我们可以从小到大计算从而避免递归，动态规划计算顺序的核心思路就是下一次计算时所用的值，在上一步已经计算过且被缓存

初始条件

依次计算

当计算到 时， 都已经计算过，且能拿到计算结果。

动态规划求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function fn(x) {
  if (x === 0) return 0;
  var stack = [0],
    i = 1;
  for (; i <= x; ++i) {
    stack[i] = Math.min(
      (stack[i - 2] === undefined ? Infinity : stack[i - 2]) + 1,
      (stack[i - 5] === undefined ? Infinity : stack[i - 5]) + 1,
      (stack[i - 7] === undefined ? Infinity : stack[i - 7]) + 1
    );
  }
  if (stack[i - 1] === Infinity) {
    return -1;
  }
  return stack[i - 1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function fn(x) {
  if (x === 0) return 0;
  var stack = [0],
    i = 1;
  for (; i <= x; ++i) {
    // 如果硬币面额数量不确定，其实就是循环两两比较
    stack[i] = Math.min(
      stack[i - 2] === undefined ? Infinity : stack[i - 2] + 1,
      stack[i] === undefined ? Infinity : stack[i]
    );
    stack[i] = Math.min(
      stack[i - 5] === undefined ? Infinity : stack[i - 5] + 1,
      stack[i] === undefined ? Infinity : stack[i]
    );
    stack[i] = Math.min(
      stack[i - 7] === undefined ? Infinity : stack[i - 7] + 1,
      stack[i] === undefined ? Infinity : stack[i]
    );
  }
  if (stack[i - 1] === Infinity) {
    return -1;
  }
  return stack[i - 1];
}

相关题目详解

最值型动态规划

零钱兑换

乘积最大子数组

求和型动态规划

不同路径

n 个骰子的点数

存在型动态规划

跳跃游戏

LeetCode

暴力解法

暴力法的思路很直观，遍历字符串 SS，对于 SS 中的每个字符，遍历一次字符串 JJ，如果其和 JJ 中的某一个字符相同，则是宝石。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var numJewelsInStones = function (J, S) {
    var result = 0,
        i = 0,
        j = 0,
        jlen = J.length,
        slen = S.length;
    for (; i < slen; i++) {
        var s = S[i];
        for (j = 0; j < jlen; j++) {
            if (J[j] === s) {
                result++;
            }
        }
    }
    return result;
};

复杂度分析

• 时间复杂度： , 为字符串的长度，为字符串 的长度

• 空间复杂度：

使用map结构

遍历字符串 JJ，使用哈希集合存储其中的字符，然后遍历字符串 SS，对于其中的每个字符，如果其在哈希集合中，则是宝石。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var numJewelsInStones = function (J, S) {
    var map = {},
        result = 0,
        i = 0,
        j = 0,
        jlen = J.length,
        slen = S.length;
    for (;i<jlen;i++){
        map[J[i]] = J[i];
    }
    for(;j<slen;j++){
        if(S[j]===map[S[j]]){
            result++;
        }
    }
    return result;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var numJewelsInStones = function (J, S) {
    var map = new Map(),
        result = 0,
        i = 0,
        j = 0,
        jlen = J.length,
        slen = S.length;
    for (;i<jlen;i++){
        map.set(J[i],J[i]);
    }
    for(;j<slen;j++){
        if(map.get(S[j])){
            result++;
        }
    }
    return result;
};

复杂度分析

• 时间复杂度： , 为字符串的长度，为字符串 的长度

• 空间复杂度：

1. 复制图层

2. 打开色阶

3. 调整色阶使文字颜色更深

4. 打开色彩范围

5. 调整颜色容差，增加笔迹的选择范围，点击吸管，点击页面空白部分，点击确认，载入选区

6. 删除底色，如果没有效果，查看是否因为右侧图层没有把备份图层，取消勾选

7. 反转选区

8. 填充颜色

• Google 浏览器搜索报错，但是可以使用翻译等功能，但不能搜索。

原因

• chrome将你输入的字符转换成google搜索指令时出错所致。新版chrome为增强安全性，对非https的地址会报如上错误。

• 也可能是运营商网络原因

解决办法

删除原来的goole搜索引擎，手动输入一个新的即可。

• 进入设置

• 进入管理搜索引擎

• 点击添加

• 填入下面几项

搜索引擎： Goolge 或任意名字

关键字： www.google.com.hk

网址格式： https://www.google.com.hk/search?q=%s&{google:RLZ}{google:originalQueryForSuggestion}{google:assistedQueryStats}{google:searchFieldtrialParameter}{google:iOSSearchLanguage}{google:searchClient}{google:sourceId}{google:instantExtendedEnabledParameter}{google:contextualSearchVersion}ie={inputEncoding}

• 保存并选设为默认选项

LeetCode

解法一

• 因为是从查找最后一个单词，考虑从后向前匹配

• 因为有以一个或多个空字符串结尾的情况，所以如果先遇到空字符串则跳过，从遇到的第一个字符串开始基数，再次遇到空格则返回结果

• 注意边界的处理，如果字符串为空，返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var lengthOfLastWord = function (s) {
    // 边界处理
    if (s === '') return 0
    var i = s.length - 1;
    var res = 0;
    for (; i >= 0; i--) {
        if (s[i] === ' ' && res !== 0) {
            return res;
        }
        else if(s[i] !== ' '){
            res++;
        }
        //跳过空字符串的情况
    }
    return res;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

方法二

1
2
3
4

var lengthOfLastWord = function(s) {
    if(s==='') return 0
    return s.trim().split(' ').pop().length;
};

ls命令

linux 下文件和目录的特点

• Linux 文件或目录名称最长可以有256个字符
• 以.开头的文件为隐藏文件
• .代表当前目录
• ..代表上一级目录

ls 命令常用选项

1

ls -lh

ls 通配符

1

ls [abc].txt

cd

相对路径和绝对路径

• 相对路经：在输入路径时，最前面的不是/或者～，表示相对当前目录所在位置的目录位置

• 绝对路径：在输入路径时，最前面是/或者～，表示从根目录/家目录开始的目录位置

pwd

其功能是显示当前所在工作目录的全路径。主要用在当不确定当前所在位置时，通过pwd来查看当前目录的绝对路径。

-L --logical 显示当前的路径，有连接文件时，直接显示连接文件的路径，(不加参数时默认此方式).
-p --physical，显示当前的路径，有连接文件时，不使用连接路径，直接显示连接文件所指向的文件，参考示例2。 当包含多层连接文件时，显示连接文件最终指向的文件.

创建和删除

创建文件touch

创建文件或修改文件时间

• 如果文件不存在，可以创建一个空白文件

• 如果文件存在，可以修改文件的修改日期

创建目录mkdir

1

mkdir -p a/b/c

新建目录名称不能与当前目录中已有的目录或文件重复

删除命令rm

删除文件或目录，不能恢复

1

rm -rf workspace

修改文件权限

修改文件|目录的拥有者

1

chown 用户名 文件名|目录名

递归修改文件|目录的组

1

chown 用户名 文件名|目录名

常见数字组合有（u表示用户／g表示组／o表示其他）：

• 777 ===> u=rwx,g=rwx,o=rwx
• 755 ===> u=rwx,g=rx,o=rx
• 644 ===> u=rw,g=r,o=r

基本概念

• 用户 是 Linux 系统工作中重要的一环，用户管理包括 用户 与 组 管理

• 在 Linux 系统中，不论是由本机或是远程登录系统，每个系统都必须拥有一个账号，并且对于不同的系统资源拥有不同的使用权限

• 在 Linux 中，可以指定 每一个用户 针对 不同的文件或者目录 的 不同权限对 文件／目录 的权限包括：

组

• 为了方便用户管理，提出了 组 的概念，如下图所示

• 在实际应用中，可以预先针对 组 设置好权限，然后 将不同的用户添加到对应的组中，从而不用依次为每一个用户设置权限

ls -l 扩展

• ls -l 可以查看文件夹下文件的详细信息，从左到右依次是：

  • 权限，第 1 个字符如果是 d 表示目录

  • 硬链接数，通俗地讲，就是有多少种方式，可以访问到当前目录／文件

    文件硬链接数为1，只能通过一种绝对路径访问

    文件夹的硬连接数取决于子文件夹的数量，可以在当前文件夹通过 .方法，也可以在子文件夹通过 .. 访问

  • 拥有者，家目录下 文件／目录 的拥有者通常都是当前用户

  • 组，在 Linux 中，很多时候，会出现组名和用户名相同的情况

  • 大小

  • 创建/修改时间

  • 名称

chmod

chmod 可以修改 用户／组 对 文件／目录 的权限

1

chmod +/-rwx 文件名|目录名

以上方式会一次性修改 拥有者 / 组 权限

读权限控制目录是否可以被访问

取消文件的可读可写权限

1

chmod -rw xxx.md

增加文件的可读权限

1

chmod +r xxx.md

在添加文件的可执行权限后,文件名变为绿色

1

chmod +x test.js

对目录的权限操作

• 可读权限控制目录是否可以被访问

• 可读权限控制目录中是否可以创建文件

• 可读可写都需要可执行权限,且如果没有可执行权限目录不能被访问

超级用户

• Linux 系统中的 root 账号通常 用于系统的维护和管理，对操作系统的所有资源 具有所有访问权限

• 在大多数版本的 Linux 中，都不推荐 直接使用 root 账号登录系统

• 在 Linux 安装的过程中，系统会自动创建一个用户账号，而这个默认的用户就称为“标准用户”

sudo

• su 是 substitute user 的缩写，表示 使用另一个用户的身份

• sudo 命令用来以其他身份来执行命令，预设的身份为 root

• 用户使用 sudo 时，必须先输入密码，之后有 5 分钟的有效期限，超过期限则必须重新输入密码

若其未经授权的用户企图使用 sudo，则会发出警告邮件给管理员

组管理

创建组 / 删除组 的终端命令都需要通过 sudo 执行

组信息保存在 /etc/group 文件中

/etc 目录是专门用来保存 系统配置信息 的目录

在实际应用中，可以预先针对 组 设置好权限，然后 将不同的用户添加到对应的组中，从而不用依次为每一个用户设置权限

• 新建文件夹dev

1

mkdir zhen

• 新建组zhengrp

1

sudo groupadd zhengrp

• 把zhen目录的组修改为zhengrp

1

sudo chgrp -R zhengrp zhen