四月八日

拷贝和移动命令

2020-10-12

序号	命令	对应英文	作用
01	tree [ 目录名 ]	tree	以树状图列出文件目录结构
02	cp 源文件目标文件	copy	复制文件或者目录
03	mv 源文件目标文件	move	移动文件或者目录/文件或者目录重命名

tree

tree 命令可以以树状图列出文件目录结构

选项	含义
-d	只显示目录

cp

cp 命令的功能是将给出的文件或目录复制到另一个文件或目录中,相当于 DOS 下的 copy 命令

选项	含义
-f	已经存在的目标文件直接覆盖不会提示
-i	覆盖文件前提示 n/y
-r	若给出的源文件是目录文件,则 cp 将递归复制该目录下的所有子目录和文件,目标文件必须为一个目录名

如果文件名相同可以不指定目标文件名，只写目标路径

mv

mv 命令可以用来移动文件或目录 ,也可以给文件或目录重命名

选项	含义
-i	覆盖文件前提示

在同目录下移动实现修改文件的名字,为了防止覆盖可以加上 -i参数

142.形链表2

2020-10-10

算法 / 关联题目

LeetCode

暴力解法哈希表

保存每一个节点判断

var detectCycle = function(head) {
   var map = new Map();
   var cur = head;
    while(cur!==null){
        if(map.get(cur)===cur){
            return cur;
        }
        map.set(cur,cur);
        cur = cur.next;
    }
    return null;
};

复杂度分析

时间复杂度：
空间复杂度：

双指针

快慢指针同时移动，第一次相遇后，定义新指针为头节点，新指针和慢指针同时移动，再次相遇时的节点为入环节点

通过数学演变来确认双指针的正确性,如下图

设慢指针的移动速度为，快指针的移动速度为,用来表示走过的步数
那么慢指针走到相遇点的时候走过,快指针走过了
可以得到
所以从相遇点到入环点的步数和从头节点到入环的步数是相同的

var detectCycle = function(head) {
    var fast = head;
    var slow = head;
    var res = head;
    while(fast!==null && fast.next!==null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow===fast){
            while(res!==fast){
                res = res.next;
                fast = fast.next;
            }
            return res;
        }
    }
    return null;
};

复杂度分析

时间复杂度：
空间复杂度：

344.反转字符串

2020-10-09

算法 / 关联题目

LeetCode

注意

原生API

1
2
3

var reverseString = function(){
    return s.reverse();
}

循环

从前向后两两交换字母位置,n为数组s的长度，那么只需要n/2次就可以调换所有的顺序

var reverseString = function (s) {
    var len = s.length,
        middle = Math.ceil(s.length / 2),
        i = 0;
    for (; i < middle; i++) {
        var temp = s[i];
        s[i] = s[len - i - 1];
        s[len - i - 1] = temp;
    }
    return s;
};

双指针

与循环方法相似，需要left,right两个指针，分别向中间移动，当两个指针相等时，交换完成

var reverseString = function (s) {
    var left = 0,
        right = s.length - 1;
    while (left <= right) {
        var temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
    return s;
}

复杂度分析

时间复杂度：只需要遍历次。
空间复杂度：不需要额外空间

141.环形链表

2020-10-09

算法 / 关联题目

LeetCode

暴力解法哈希表

把每一个遇到的节点都保存下来

如果当前节点为null表示没有环，返回false
如果在map中当前节点存在则表示有环，否则存下当前节点

var hasCycle = function (head) {
    var map = new Map();
    while(head!==null){
        if(map.get(head)===head){
            return true;
        }
        map.set(head,head);
        head = head.next;
    }
    return false;
};

复杂度分析

时间复杂度：，其中是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度：，其中是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

快慢指针

「Floyd 判圈算法」(又称龟兔赛跑算法)。

var hasCycle = function (head) {
    var fast = head;
    var slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

var hasCycle = function (head) {
    if (head===null || head.next===null) return false;
    var fast = head.next;
    var slow = head;
    while (fast!==slow) {
        if (fast===null || fast.next===null) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

复杂度分析

时间复杂度：,当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动轮。
空间复杂度：，我们只使用了两个指针的额外空间。

62.不同路径

2020-10-08

算法 / 关联题目

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]为最终返回结果

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

复杂度分析

时间复杂度：
空间复杂度：

终端控制

2020-10-07

Linux / 基础命令

终端窗口字体大小

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

ctrl + - 缩小终端窗口字体

命令格式

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

1	command [-options] [parameter]

查阅命令帮助信息

显示command 命令的帮助信息

1	command --help

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

1	man command

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

操作键	功能
空格键	显示手册下一屏
Enter键	一次滚动手册的一行
b键	回滚一屏
f键	前滚一屏
q键	退出

自动补全

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

如果没有歧义（包含输入字母有唯一的对应），系统会自动补全
如果有多个包含当前输入字母的文件/目录/命令，再次按下tab键会自动提示

曾经使用过的命令

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

如果想退出按ctrl+c

快捷方式

按键	作用
ctrl+c	结束正在运行的程序 ping,telent 等
ctrl+d	结束输入或退出shell
ctrl+s	暂停屏幕输出
ctrl+q	恢复屏幕输出
ctrl+l	清屏等同于 clear
ctrl+a/ctrl+e	快速移动光标到行首/行尾

332.零钱兑换

2020-10-02

算法 / 关联题目

LeetCode

动态规划详解

动态规划

注意

边界情况amount===0时返回0，0元需要0枚硬币
stack[i - coins[j]] stack[i] 需要判断为undefined的情况，因为JavaScript中Math.min(undefined)===NaN需要特殊处理，用Infinity占位，在使用Math.min(1,Infinity) 可以取得最小值
返回时需要判断不能匹配的情况，如果当前位置为Infinity表示不能匹配

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可能会溢出

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个面额来转移状态，所以一共需要的时间复杂度。
空间复杂度：数组长度等于金额的大小

动态规划

2020-10-02

算法 / 常见算法与数学

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

计数
- 到达一个位置有多少中走法
- 有多少种方式选出 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]代表什么,类似数学中的

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

&ensp;&ensp;1）最后一步

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

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

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

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

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

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

&ensp;&ensp;2）子问题

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

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

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

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

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

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

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

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

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

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

递归求解

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

从硬币总额的角度思考：

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

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

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

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

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

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

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 怎么办
用正无穷来表示不能拼出某个值

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

计算顺序

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

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

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

初始条件

依次计算 $，，$

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

F(i)	最小硬币数量
F(0)	0 //金额为 0 不能由硬币组成
F(1)	1 //
F(2)	1 //
F(3)	2 //
F(4)	2 //
…	…
F(27)	3 //

动态规划求解

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

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

771.宝石与石头

2020-10-02

LeetCode

暴力解法

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

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，对于其中的每个字符，如果其在哈希集合中，则是宝石。

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

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