四月八日

O11.旋转数字最小数字

2020-10-15

LeetCode

二分查找

通过上图直观的分析出旋转数字的一些特点

最右边的值只能小于等于最左边的值
如果一个值比最右边的值小，那么最小值一定在这个值左边或是这个值本身
如果最左边的值比其中一个值大，那么最小值一定在这个值右边

 var minArray = function (numbers) {
  var left = 0,
      right = numbers.length - 1,
      mid = Math.floor(right / 2);
  while (left < right) {
      if (numbers[mid] < numbers[right]) {
          right = mid;
      } else if (numbers[mid] === numbers[right]) {
          right--;
      } else if (numbers[mid] > numbers[right]) {
          left = mid + 1;
      }
      mid = Math.floor((left + right) / 2)
  }
  return numbers[left];
};

什么左边的值比其中一个值大的时候，这个值不能是最小值

因为我们先处理了右半区的比较，会使得最右边值先到达最小值

复杂度分析

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

46.全排列

2020-10-15

算法 / 关联题目

LeetCode

回溯法

function permute(nums) {
  const res = [];
  const  set = new Set();
  function dfs(set){
      if(set.size===nums.length){
          res.push([...set]);
      }
      for(let k of nums){
          if(set.has(k)){
              continue;
          }
          set.add(k);
          dfs(set);
          set.delete(k)
      }
  }
  dfs(set);
  return res;
};

位置交换

回溯法在进入下一次递归时，并没有标注循环位置，所以nums中的元素每一个都要通过Set集合判断一次

如果不使用Set数据结构，时间复杂度更高

位置交换，是通过在一次循环把第一个元素更换为其他剩余元素，在第一个元素固定下来后，后面的元素进行全排列

function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
function permute(nums) {
    const res = [];
    function dfs(n) {
        if (n === nums.length - 1) {
            res.push([...nums]);
        }
        for (let i = n; i < nums.length; i++) {
            swap(nums, i, n)
            dfs(n + 1);
            swap(nums, i, n)
        }
    }
    dfs(0);
    return res;
};

位置交换稍微调整

发现在最后只有一个元素的时候，还是进行了递归

所以提前判断剩余数组是否满足递归条件，如果只剩下一个元素就结束递归

使用一下es6数组元素交换的方法

function permute(nums) {
  const res = [];
  function dfs(n) {
      for (let i = n; i < nums.length; i++) {
          [nums[i], nums[n]] = [nums[n], nums[i]];
          if (n + 1 > nums.length - 1) {
              res.push([...nums]);
              continue;
          }
          dfs(n + 1);
          [nums[i], nums[n]] = [nums[n], nums[i]];
      }
  }
  dfs(0);
  return res;
};

复杂度分析

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

图

2020-10-15

算法 / 数据结构

图的相关术语

图是网络结构的抽象模型。是一组由边连接的节点（或顶点）

任何二元关系都可以用图来表示。

数学上表示为 , 表示一组顶点，表示一组边，连接中的顶点

有向图无向图

图可以是无向的（边没有方向）或是有向的（有向图）。第一张图是无向图，下面这张是有向图

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。例如，C 和D 是强连通的，而A 和B 不是强连通的。

图还可以是未加权的（目前为止我们看到的图都是未加权的）或是加权的。如下图所示，加权图的边被赋予了权值。

应用

搜索图中的一个特定顶点或搜索一条特定边
寻找图中的一条路径（从一个顶点到另一个顶点
寻找两个顶点之间的最短路径，以及环检测。

图的表示

邻接矩阵

每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。

如果索引为i 的节点和索引为 j 的节点相邻，则 array[i][j] === 1，否则array[i][j] === 0，如下图所示。

由于不是强连通图（每两个节点间都存在路径），所以数组中有大量的0

给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。

邻接矩阵表示法不够好的另一个理由是，图中顶点的数量可能会改变，修改二维数组不够灵活。

邻接表

邻接表由图中每个顶点的相邻顶点列表所组成。

存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。

对大多数问题来说都是更好的选择

但要找出顶点 v 和 w 是否相邻，使用邻接矩阵会比较快

关联矩阵

关联矩阵中，矩阵的行表示顶点，列表示边。如下图所示，

使用二维数组来表示两者之间的连通性，如果顶点 v 是边 e 的入射点，则 array[v][e] === 1

否则，array[v][e] === 0

关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存。

创建Graph 类

类的结构

图是否有向，默认无无向图 ①
使用一个数组来储存顶点的名字 ②
使用一个字典来储存邻接表，字典将会使用顶点的名字作为键，邻接顶点列表作为值 ③

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // ①
    this.vertices = []; // ②
    this.adjList = new Map(); // ③
  }
}

插入顶点方法

如果顶点不存 ④ 在顶点列表中添加节点 ⑤
在邻接表中为该顶点创建空数组 ⑥

addVertex(v) {
  if (!this.vertices.has(v)) { // ④
    this.vertices.push(v); // ⑤ 
    this.adjList.add(v, []); // ⑥
  }
}

建立链接方法

如果建立链接的两个点不在顶点列表中，要先填入顶点列表
将 w 加入到 v 的邻接表中，表示添加了一条自顶点 v 到顶点 w 的边
无向图需要添加一条自 w 到 v 的边

addEdge(v, w) {
  if (!this.adjList.has(v)) {
    this.addVertex(v);
  }
  if (!this.adjList.has(w)) {
    this.addVertex(w);
  }
  this.adjList.get(v).push(w);
  if (!this.isDirected) {
    this.adjList.get(w).push(v);
  }
}

请注意我们只是往数组里新增元素，因为数组已经在行 ⑥ 被初始化了

取值

一个返回顶点列表，另一个返回邻接表

getVertices() {
  return this.vertices;
}
getAdjList() {
  return this.adjList;
}

测试

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // {1}
    this.vertices = []; // {2}
    this.adjList = new Map(); // {3}
  }
  addVertex(v) {
    if (!this.vertices.includes(v)) { // {5}
      this.vertices.push(v); // {6}
      this.adjList.set(v, []); // {7}
    }
  }
  addEdge(v, w) {
    if (!this.adjList.has(v)) {
      this.addVertex(v);
    }
    if (!this.adjList.has(w)) {
      this.addVertex(w);
    }
    this.adjList.get(v).push(w);
    if (!this.isDirected) {
      this.adjList.get(w).push(v);
    }
  }
  getVertices() {
    return this.vertices;
  }
  getAdjList() {
    return this.adjList;
  }
  toString() {
    let s = '';
    for (let i = 0; i < this.vertices.length; i++) { // {15}
      s += `${this.vertices[i]} -> `;
      const neighbors = this.adjList.get(this.vertices[i]); // {16}
      for (let j = 0; j < neighbors.length; j++) { // {17}
        s += `${neighbors[j]} `;
      }
      s += '\n'; // {18}
    }
    return s;
  }
}
const graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']; // {12}
for (let i = 0; i < myVertices.length; i++) { // {13}
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B'); // {14}

graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());

图的遍历

有两种算法可以对图进行遍历：广度优先搜索（breadth-first search，BFS） 和 深度优先搜索（depth-first search，DFS）

图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环，等等。

图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。

完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。

为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。

广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构，如下表所示。

算法	数据结构	描述
深度优先搜索	栈	将顶点存入栈，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
广度优先搜索	队列	将顶点存入队列，最先入队列的顶点先被探索

广度优先遍历

队列结构是广度优先遍历的精髓

从起点节点开始相邻的节点会被添加到队列中

因为队列有先进先出的性质，所以相邻的节点在遍历队列的时候会先被拿到，从而是实现了广度优先遍历

下一个关键点是如何知道节点没有被重复访问，解决办法是给访问过的节点打一个标记，如果下次访问相同的节点就跳过

WHITE: 表示没有被访问过 GARY: 访问过但是没有遍历子节点 BALCK: 节点和子结点都被访问过

// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  for (var i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if(color[v] === 'WHITE'){
        color[v] = "GARY"
        queue.push(v);
      }
    }
    color[v] = "BLACK"
    console.log(node);
  }
}
breadthFirstSearch(graph,myVertices[0])

使用广度优先寻找最短路径

因为使用了广度优先，所以会先访问距离为1的节点，然后是距离为2的节点，路径长的那一条线路，因为同一个节点被访问过，所以不会被记录，从而记录的都是每个节点到起点的最短路径

// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  // 距离
  const distance = {};
  // 回溯节点 标识上一个节点是什么
  const predecessors = {}
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  // 初始化默认距离，和回溯节点
  for(let i = 0; i < vertices.length; i++){
    distance[vertices[i]] = 0;
    predecessors[vertices[i]] = null
  }

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if (color[v] === 'WHITE') {
        // 上级节点的最短路进
        distance[v] = distance[node] + 1;
        // 指定当前节点的上级节点
        predecessors[v] = node;
        color[v] = "GARY"
        queue.push(v);
      }
    }
  }
  console.log(
    distance,
    predecessors
  )
}
breadthFirstSearch(graph, myVertices[0])

通过生成的前溯表以及所有的节点我们可以生成每个节点到头节点的最短路径

// 遍历每一个节点
for (let v of myVertices) {
  const path = [];
  // 如果当前节点不是头节点，就存入上一个节点
  for (let w = v; w !== null; w = shortestPathA.predecessors[w]) {
    path.push(w);
  }
  let s = path.pop();
  //反向拼接每一个节点
  while (path.length) {
    s += '-' + path.pop()
  }
  console.log(s);
}

深度优先遍历

因为深度优先需要把一条路径遍历到底，所以拿到的节点需要继续遍子结点

所以深度优先的精髓就是栈的结构，拿到的子结点加入栈中，由于栈先进先出可以继续访问下层的子结点

const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  // 栈结构
  const stack = [];
  stack.unshift(vertices[0]);
  // 如果栈不为空就继续遍历
  while (stack.length) {
    const v = stack.shift();
    // 如果没有访问过就访问子结点
    if (color[v] === "WHITE") {
      color[v] = 'GARY';
      // 获取到子结点 放入栈中
      const nabor = adjList.get(v);
      for (let vn of nabor.reverse()) {
        stack.unshift(vn);
      }
    }
  }
}
fn(graph)

这种写法可以实现遍历，但是不方便统计某个节点的子结点是否全部遍历，也就是置成BLACK

另一个关键点，函数递归调用也可以调用栈，保存每个函数的调用帧, 所以深度优先也常用递归来解决

const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  depthFirstSearch(vertices[0], adjList, color);
}
const depthFirstSearch = function (v, adjList, color) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
  console.log(v);

    color[v] = 'GARY'
    for (let vn of nabor) {
      depthFirstSearch(vn, adjList, color);
    }
    // 子结点遍历完成之后标记为黑色
    color[v] === 'BLACK'
  }
}
fn(graph)

加入节点信息

在遍历图的时候加入更多的节点信息

1.每个节点的发现时间，到达某个节点经历的步数
2.每个节点的访问时间，某个节点所有子结点都被访问过的步数
3.节点的前溯节点表

const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
    find[v] = ++(time.t);
    color[v] = 'GARY'
    for (let vn of nabor) {
      back[vn] = v;
      depthFirstSearch(vn, adjList, color, find, visit, back, time);
    }
    color[v] === 'BLACK'
    visit[v] = ++(time.t);
  }
}
const fn = function (graph,) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  const find = {};// 发现时间
  const visit = {};// 访问时间
  const back = {};// 回溯时间
  const time = { t: 0 }//用于计时
  for (let v of vertices) {
    color[v] = "WHITE";
    //初始化
    find[v] = 0;
    visit[v] = 0;
    back[v] = null;
  }
  depthFirstSearch(vertices[0], adjList, color, find, visit, back, time);
  return {
    find, visit, back, time
  }
}
fn(graph)

通过深度优先搜索拓扑排序

有些任务需要按顺序执行，而且不同的任务会公用一些子任务，编排这些有序任务被成为拓扑排序

这些任务形成了有向无环图，通过上面一节添加的节点信息，生成这些任务的执行顺序

首先生成图

graph = new Graph(true); // 有向图
myVertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');

添加节点信息

const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
      const nabor = adjList.get(v);
      if (color[v] === 'WHITE') {
        find[v] = ++(time.t);
        color[v] = 'GARY'
        for (let vn of nabor) {
          back[vn] = v;
          depthFirstSearch(vn, adjList, color, find, visit, back, time);
        }
        color[v] === 'BLACK'
        visit[v] = ++(time.t);
      }
    }
    const fn = function (graph,) {
      const vertices = graph.getVertices();
      const adjList = graph.getAdjList();
      const color = {};
      const find = {};// 发现时间
      const visit = {};// 访问时间
      const back = {};// 回溯时间
      const time = { t: 0 }//用于计时
      for (let v of vertices) {
        color[v] = "WHITE";
        //初始化
        find[v] = 0;
        visit[v] = 0;
        back[v] = null;
      }
      // 因为有向图，每个节点不一定能到达其他节点
      for(let v of vertices){
        depthFirstSearch(v, adjList, color, find, visit, back, time);
      }
      return {
        find, visit, back, time
      }
    }
    fn(graph)

通过节点信息经行拓扑排序,按照访问时间从大到小

1	Object.entries(visit).sort((it, it2) => it2[1] - it1[1])

152.乘积最大子数组

2020-10-14

算法 / 关联题目

LeetCode

动态规划

确定状态

最后一步

只考虑最后一步，为，很好理解，就是最后一个元素，稍稍复杂一点

因为本题不是求和，较小的值在下一次计算后（加上一个数或减去一个数）仍然是较小的值，但是乘法收到正负符号的影响，一个负数乘以另一个负数，可以是一个正数，所以这个应该考虑正负的情况

子问题

由上面的分析，原问题为数组子数组城际的最大值，除去最后一步之后子问题为子数组的乘积最大值

所以用来表示子数组乘积最大值

转移方程

根据确定状态的分析，为上一步的最大值，考虑到正负符号的影响，应该同时保存最大值和最小值，因为最小值乘以可能变为最大值

初始条件和边界情况

初始化

用于记录最大值

计算顺序

， ，

 var maxProduct = function (nums) {
    var n = nums.length,
        // 初始化第一个
        // 考虑到f[1]依赖f[0]的结果至少要初始化一组数据
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        if (f[i - 1][0] == 0) {
            f[i] = [nums[i], nums[i]]
        } else {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        }
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};

优化

删除无用的代码

1
2
3

if (f[i - 1][0] == 0) {
    f[i] = [nums[i], nums[i]]
}

最初考虑到num[i+1]===0的情况，会将f[i+1]最小值，最大值都变为0，会使后面的循环计算都为0，但无需有这种担心，因为Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]); 最大值最小值的计算都有nums[i]的比较，并不会使后面的运算一直为0

这里还需要考虑为什么需要用nums[i]，对于数组[-2,-3,0,2-2]

循环	值
初始化	f[0] = [-2,-2]，最大值最小值都为第一个数
1	f[1] = [6,-3]，有最小值并不是乘积得出的情况，而是元素本身就是最小值
2	f[2] = [0,0]，遇到零的情况
3	f[3] = [2,0]，最大值为元素本身，并不是乘积
4	f[4] = [0,-4]

var maxProduct = function (nums) {
    var n = nums.length,
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};

优化数储存，可以发现我们每次存下来的最大值最小值，只会用在下一次的计算中，所以并不需要额外的空间把每一个结果保存下来，只需要三个变量

变量	作用
max	临时储存上一次的最大值
min	临时储存上一次的最小值
res	保存最终结果的最大值

var maxProduct = function (nums) {
    var n = nums.length,
        max = nums[0],
        min = nums[0],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        var _min = Math.min(min * nums[i], max * nums[i], nums[i]);
        var _max = Math.max(min * nums[i], max * nums[i], nums[i]);
        // 防止相互影响
        min = _min;
        max = _max;
        if (max > res) res = max;
    }
    return res
};

通过判断是否负数，交换两个元素

初始化时min=1,max=1,巧妙的从下表为0的位置遍历

var maxProduct = function (nums) {
    var n = nums.length,
        max = 1,
        min = 1,
        res=-Infinity;
    for (var i=0; i < n; i++) {
        if(nums[i]< 0){
            var temp = max;
            max = min;
            min = temp;
        }
        var min = Math.min(min* nums[i], nums[i]);
        var max = Math.max(max*nums[i], nums[i]);
        if (max > res) res = max;
    }
    return res
};

复杂度分析

时间复杂度：程序一次循环遍历了，故渐进时间复杂度为。
空间复杂度：优化后只使用常数个临时变量作为辅助空间，与无关，故渐进空间复杂度为

linux 架构

2020-10-13

Linux / 基础命令

内核5大核心功能
操作系统用于管理计算机资源，cpu资源，外围设备，内存

程序在调用文件的读写时，需要调用内核的功能，也叫做内核模式
用户在写自己的逻辑的时候，就是用户模式

Process mannagement (进程管理) linux多任务系统，进程管理用于调度cpu
Memory management 用于内存分配
File systems 读写文件，终端输入输出，保存文件，linux树状结构也是有文件系统维护
Device drivers 如何与硬件对接
Network 对上提供socket, ssh http 都是应用层协议

字典树

2020-10-13

算法 / 常见算法与数学

树的种类

二叉树，索引树，红黑树，btree,B+tree,字典树，哈夫曼

结构特点

一定会有一个根节点root
每一个元素都被称为node
除了root节点，其余的节点都会被分成n个互不相交的集合
最末尾的节点，叫做叶子节点，其他节点叫子节点
深度：从根节点到叶子节点的最多的个数
度：和深度的概念不同，分为出度（有多少个节点指向其他节点），和入度（有多少节点指向自己）

字典树

Trie Tree 又称为单词查找树，哈希树的变种，常用于统计，查找搜索引擎中用于分词，词频统计（DF/IDF）,自动补全等机制。

查找效率高：其核心思想是利用公共前缀来减少查询时间。

对于英文可以按常规字典树进行处理，因为英文只有二十六个字母，最多有26层

但是对于中文不能直接使用，因为不同的文字过多，同一层级的分支过多

字典树的实现

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.end = Symbol('end');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        root[this.end] = true;
    }
    //查找是否存在某个单词
    find(str) {
        let root = this.root;
        for (let s of str) {
            if (root[s] === undefined) {
                return false;
            }
            root = root[s];
        }
        // 可以查到字符串中的每个字符，且最后一个字母是一个结束符
        return !!root[this.end]
    }
}

对于如何可以查找出现次数最多的单词，只需要为节点增加更多的信息

把上面基础示例中的结束标识符，修改一下，把值改为单词的出现次数，通过递归找到出现次数最多的单词

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.$ = Symbol('$');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        if (!root[this.$]) root[this.$] = 0;
        root[this.$]++

    }
    findMost() {
        let root = this.root;
        //用于记录出现次数最多的单词
        let mostWord = [];
        let max = 0;

        const find = (word, root) => {
            if (root[this.$] && root[this.$] == max) {
                mostWord.push(word);
            }
            if (root[this.$] && root[this.$] > max) {
                max = root[this.$];
                mostWord = [word];
            }
            for (let s in root) {
                find(word + s, root[s]);
            }
        }
        find('', root);

        return {
            max,
            mostWord
        }
    }
}

通过字典树做自动提示

如果其中一个节点没有匹配到，返回null

如果最后一个节点之后还有子树，递归子树找出所有匹配字符串

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.$ = Symbol('$');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        // 不需要关心是否有多个
        root[this.$] = true;
    }
    auto(str) {
        const autonode = [];
        let root = this.root;

        if (!str) return autonode;
        for (let s of str) {
            console.log(s);
            if (root[s] === undefined) {
                return autonode;
            }
            root = root[s];
        }
        const each = (word, root) => {
            if (root[this.$]) autonode.push(word)
            for (let s in root) {
                each(word + s, root[s]);
            }
        }
        each(str + '', root)
        return autonode;
    }
}

55.跳跃游戏

2020-10-12

算法 / 关联题目

LeetCode

动态规划详解

确定状态

最后一步

考虑青如果能跳到最后一个位置,

那必须满足这样的关系：

如果是从位置上跳过来，必须能先跳到位置
位置上表示的步数大小必须大于或等于从到最后位置,即

子问题

把能否跳到位置的问题，转化位能否跳到位置的问题

且问题规模缩小

状态

最终可以确定状态：表示能否到最后位置

转移方程

通过最后一步的分析, 位置必须能到达，且位置的步数与位置的和必须大于等于最后位置的索引 ,所以有
如何找到是通过循环 ,只要可以找到一个满足的条件，那么
最终转移方程为

**注意:**为什么不能只找最近的进行判断？因为能否到达受之前所有能到达位置的影响，而且最近的可到达位置，并不一定能到最终位置，例如 [3,0,0,5,0,0,1,0,1]

初始条件和边界情况

位置0为true

运算顺序

设表示青蛙不能跳到石头
初始化 f[0]==true
计算 f[1],f[2]....,f[n-1]
返回结果为 f[n-1]

var canJump = function (nums) {
    var f = [true],
        n = nums.length;
    for (var j = 1; j < n; j++) {
        f[j] = false;
        for (var i = 0; i < j; i++) {
            if (f[i] && i + nums[i] >= j) {
                f[j] = true;
                break;
            }
        }
    }
    return f[n - 1];
};

复杂度分析

时间复杂度：,每次需要重复遍历已经遍历过的元素所以，
空间复杂度：

远程管理命令

2020-10-12

Linux / 基础命令

关机 / 重启

序号	命令	对应英文	作用
01	shutdown 选项时间	shutdown	关机/重新启动

shutdown 命令可以安全关闭或者重新启动系统

选项	含义
-r	重新启动

提示:
不指定选项和参数 ,默认表示 1 分钟之后关闭电脑
远程维护服务器时,最好不要关闭系统,而应该重新启动系统

重新启动操作系统,其中 now 表示现在

1	$ shutdown -r now

立刻关机,其中 now 表示现在

1	$ shutdown now

系统在今天的 20:25 会关机

1	$ shutdown 20:25

系统再过十分钟后自动关机

1	$ shutdown +10

取消之前指定的关机计划

1	$ shutdown -c

查看或配置网卡信息

序号	命令	对应英文	作用
01	ifconfig	configure a network interface	查看 / 配置计算机当前的网卡配置信息
02	ping ip 地址	ping	检测到目标 ip 地址的连接是否正常

网卡

网卡是一个专门负责网络通讯的硬件设备
IP 地址是设置在网卡上的地址信息

们可以把电脑比作电话 , 网卡相当于 SIM 卡 , IP 地址相当于电话号码

IP 地址

每台联网的电脑上都有 IP 地址 , 是保证电脑之间正常通讯的重要设置

注意:每台电脑的 IP 地址不能相同,否则会出现 IP 地址冲突,并且没有办法正常通讯
提示:有关 IP 地址的详细内容,在就业班会详细讲解!

ifconfig

ifconfig 可以查看/配置计算机当前的网卡配置信息

需要现安装net-tools软件

查看网卡配置信息

1	$ ifconfig

查看网卡对应的 IP 地址

1	$ ifconfig \| grep inet

提示:一台计算机中有可能会有一个物理网卡和多个虚拟网卡 ,在 Linux 中物理网卡的名字通常以 ensXX 表示

127.0.0.1 被称为本地回环 / 环回地址 ,一般用来测试本机网卡是否正常

ping

检测到目标主机是否连接正常

1	$ ping IP 地址

检测本地网卡工作正常

1	$ ping 127.0.0.1

ping 一般用于检测当前计算机到目标计算机之间的网络是否通畅 ,数值越大,速度越慢

ping 的工作原理与潜水艇的声纳相似,ping 这个命令就是取自声纳的声音
网络管理员之间也常将 ping 用作动词 —— ping 一下计算机 X ,看他是否开着

原理:网络上的机器都有唯一确定的 IP 地址 ,我们给目标 IP 地址发送一个数据包,对方就要返回一个数据包,根据返回的数据包以及时间,我们可以确
定目标主机的存在

提示:在 Linux 中,想要终止一个终端程序的执行,绝大多数都可以使用 CTRL + C

远程登录和复制文件

序号	命令	对应英文	作用
01	ssh 用户名@ip	secure shell	关机／重新启动
02	scp 用户名@ip:文件名或路径用户名@ip:文件名或路径	secure copy	远程复制文件

ssh 基础

在 Linux 中 SSH 是非常常用的工具，通过 SSH 客户端我们可以连接到运行了 SSH 服务器的远程机器上

SSH 客户端是一种使用 Secure Shell（SSH）协议连接到远程计算机的软件程序
SSH 是目前较可靠，专为远程登录会话和其他网络服务提供安全性的协议
- 利用 SSH 协议可以有效防止远程管理过程中的信息泄露
- 通过 SSH 协议可以对所有传输的数据进行加密，也能够防止 DNS 欺骗和 IP 欺骗
SSH 的另一项优点是传输的数据可以是经过压缩的，所以可以加快传输的速度

域名和端口号

域名

由一串用点分隔的名字组成，例如：www.iftrue.me
是 IP 地址的别名，方便用户记忆

端口号

IP 地址：通过 IP 地址找到网络上的计算机
端口号：通过端口号可以找到计算机上运行的应用程序
- SSH 服务器的默认端口号是 22，如果是默认端口号，在连接的时候，可以省略常
常见服务端口号列表：

序号	服务	端口号
01	SSH 服务器	22
02	Web 服务器	80
03	HTTPS	443
04	FTP 服务器	21

SSH 客户端的简单使用

如果没有安装先通过sudo apt install openssh-server安装ssh

1	ssh [-p port] user@remote

user 是在远程机器上的用户名，如果不指定的话默认为当前用户
remote 是远程机器的地址，可以是 IP／域名，或者是后面会提到的别名
port 是 SSH Server 监听的端口，如果不指定，就为默认值 22

使用 exit 退出当前用户的登录

ssh 这个终端命令只能在 Linux 或者 UNIX 系统下使用,如果在 Windows 系统中，可以安装 PuTTY 或XShell 客户端软件即可
在工作中，SSH 服务器的端口号很有可能不是 22，如果遇到这种情况就需要使用 -p 选项，指定正确的端口号，否则无法正常连接到服务器

scp

scp 就是 secure copy，是一个在 Linux 下用来进行远程拷贝文件的命令
它的地址格式与 ssh 基本相同，需要注意的是，在指定端口时用的是大写的 -P 而不是小写的

常见操作

把本地当前目录下的 01.py 文件复制到远程家目录下的 Desktop/01.py
注意：: 后面的路径如果不是绝对路径，则以用户的家目录作为参照路径

1	scp -P port 01.py user@remote:Desktop/01.py

加上 -r 选项可以传送文件夹,把当前目录下的 demo 文件夹复制到远程家目录下的 Desktop

1	scp -r demo user@remote:Desktop

把远程家目录下的 Desktop 复制到当前目录下的 demo 文件夹

1	scp -r user@remote:Desktop demo

复制windows下面的文件到远程服务器

选项	含义
-r	若给出的源文件是目录文件，则 scp 将递归复制该目录下的所有子目录和文件，目标文件必须为一个目录名
-P	若远程 SSH服务器的端口不是 22，需要使用大写字母 -P 选项指定端口

注意：
scp 这个终端命令只能在 Linux 或者 UNIX 系统下使用
如果在 Windows 系统中，可以安装 PuTTY，使用 pscp 命令行工具或者安装 FileZilla 使用 FTP 进行文件传输

免密码登录

提示：有关 SSH 配置信息都保存在用户家目录下的 .ssh 目录下

配置公钥

执行 ssh-keygen 即可生成 SSH 钥匙，一路回车即可
上传公钥到服务器

执行 ssh-copy-id -p port user@remote，可以让远程服务器记住我们的公钥

非对称加密算法

使用公钥加密的数据，需要使用私钥解密

使用私钥加密的数据，需要使用公钥解密

配置别名

每次都输入 ssh -p port user@remote，时间久了会觉得很麻烦，特别是当 user , remote 和 port 都得输入

在 ~/.ssh/config 里面追加以下内容：

Host 别名
  HostName ip地址
  User 用户名
  Port 22

保存之后，即可用 ssh mac 实现远程登录了， scp 同样可以使用

重定向和管道

2020-10-12

Linux / 基础命令

echo (有重复的意思)

echo 会在终端中显示参数指定的文字,通常会和重定向联合使用

重定向 > 和 >>

Linux 允许将命令执行结果重定向到一个文件
将本应显示在终端上的内容输出/追加到指定文件中

其中

> 表示输出,会覆盖文件原有的内容
>> 表示追加,会将内容追加到已有文件的末尾

注意: 通过touch创建的文件只能是空文件,但是配合echo使用,可以在创建文件的时候添加内容

管道 |

Linux 允许将一个命令的输出可以通过管道做为另一个命令的输入
可以理解现实生活中的管子,管子的一头塞东西进去,另一头取出来,这里 | 的左右分为两端,左端塞东西(写),右端取东西(读)
常用的管道命令有:
- more :分屏显示内容
- grep :在命令执行结果的基础上查询指定的文本

文件内容命令

2020-10-12

Linux / 基础命令

查看文件内容

序号	命令	对应英文	作用
01	cat 文件名	concatenate	查看文件内容、创建文件、文件合并、追加文件内容等功能
02	more 文件名	more	分屏显示文件内容
03	grep 搜索文本文件名	grep	搜索文本文件内容

内容较多时more命令会分页显示，cat命令会一次性显示

操作键	功能
空格键	显示手册页的下一屏
Enter 键	一次滚动手册页的一行
b	回滚一屏
f	前滚一屏
q	退出
/word	搜索 word 字符串

cat

cat 命令可以用来查看文件内容、创建文件、文件合并、追加文件内容等功能
cat 会一次显示所有的内容,适合查看内容较少的文本文件

选项	含义
-b	对非空输出行编号
-n	对输出的所有行编号

Linux 中还有一个 nl 的命令和 cat -b 的效果等价

grep

Linux 系统中 grep 命令是一种强大的文本搜索工具
grep 允许对文本文件进行模式查找,所谓模式查找,又被称为正则表达式

选项	含义
-n	显示匹配行及行号
-v	显示不包含匹配文本的所有行(相当于求反)
-i	忽略大小写

参数	含义
^a	行首,搜寻以 a 开头的行
ke$	行尾,搜寻以 ke 结束的行

vim使用方法

安装

1	sudo apt install vim

基本上 vi/vim 共分为三种模式，分别是命令模式（Command mode），输入模式（Insert mode）和底线命令模式（Last line mode）。这三种模式的作用分别是：

命令模式

用户刚刚启动 vi/vim，便进入了命令模式。

此状态下敲击键盘动作会被Vim识别为命令，而非输入字符。比如我们此时按下i，并不会输入一个字符，i被当作了一个命令。

以下是常用的几个命令：

i 切换到输入模式，以输入字符。
x 删除当前光标所在处的字符。
: 切换到底线命令模式，以在最底一行输入命令。

若想要编辑文本：启动Vim，进入了命令模式，按下i，切换到输入模式。

命令模式只有一些最基本的命令，因此仍要依靠底线命令模式输入更多命令。

输入模式

在命令模式下按下i就进入了输入模式。

在输入模式中，可以使用以下按键：

字符按键以及Shift组合，输入字符
ENTER，回车键，换行
BACK SPACE，退格键，删除光标前一个字符
DEL，删除键，删除光标后一个字符
方向键，在文本中移动光标
HOME/END，移动光标到行首/行尾
Page Up/Page Down，上/下翻页
Insert，切换光标为输入/替换模式，光标将变成竖线/下划线
ESC，退出输入模式，切换到命令模式
底线命令模式

在命令模式下按下:（英文冒号）就进入了底线命令模式。

底线命令模式可以输入单个或多个字符的命令，可用的命令非常多。

在底线命令模式中，基本的命令有（已经省略了冒号）：

q 退出程序
w 保存文件

按ESC键可随时退出底线命令模式。

二分查找

回溯法

位置交换

位置交换稍微调整

图的相关术语

相关概念

有向图 无向图

应用

图的表示

邻接矩阵

邻接表

关联矩阵

创建Graph 类

类的结构

插入顶点方法

建立链接方法

取值

测试

图的遍历

广度优先遍历

使用广度优先寻找最短路径

深度优先遍历

加入节点信息

通过深度优先搜索拓扑排序

动态规划

确定状态

转移方程

初始条件和边界情况

计算顺序

优化

树的种类

结构特点

字典树

字典树的实现

确定状态

最后一步

子问题

状态

转移方程

初始条件和边界情况

运算顺序

关机 / 重启

查看或配置网卡信息

ifconfig

ping

远程登录和复制文件

ssh 基础

域名 和 端口号

SSH 客户端的简单使用

scp

免密码登录

配置别名

echo (有重复的意思)

重定向 > 和 >>

管道 |

查看文件内容

cat

grep

vim使用方法

有向图无向图

域名和端口号