解题步骤

知识导图

[p8] 数据结构与算法学习路径 - 图1

数据结构

  • 1.理解常见数据结构的特点，以及他们在不同场景下使用的优缺点
  • 2.理解数组、字符串的存储原理，并熟练应用他们解决问题
  • 3.理解二叉树、栈、队列、哈希表的基本结构和特点，并可以应用它解决问题
  • 4.了解图、堆的基本结构和使用场景

线性表

线性表，n个数据元素的有限序列。

  1. 线性表
  2.   |
  3.   |--顺序表（数组）.优：便于定位.缺: 操作元素， 对其他元素影响较大
  4.   |--链表list
  5.        |
  6.        |--静态链表， 没有指针， 借助数组。
  7.        |--单链，节点（数据域+指针域（指向下一个节点， 尾节点指向null））
  8.        |--循环链表， 尾节点指向第一个节点
  9.        |--双向链表， 节点（指针域（正）+数据域+指针域（反））
  • 前序
  • 后继

方法：

  • 创建/销毁
  • 是否空
  • 清空
  • 统计长度
  • 获取指定元素
  • 定位
  • 前序/后继
  • 插入/删除
  • 遍历

私有：

  • 指针
  • 容量
  • 长度

算法

  • 1.可计算一个算法的时间复杂度和空间复杂度，可估计业务逻辑代码的耗时和内存消耗
  • 2.至少理解五种排序算法的实现原理、应用场景、优缺点，可快速说出时间、空间复杂度
  • 3.了解递归和循环的优缺点、应用场景、并可在开发中熟练应用
  • 4.可应用回溯算法、贪心算法、分治算法、动态规划等解决复杂问题
  • 5.前端处理海量数据的算法方案

  • 回溯

    - 深度优先搜索
- 正则表达式匹配
- 编译原理中的语法分析
- 数独、~~八皇后~~、0-1 背包、图的着色、旅行商问题、全排列<br />

  • 哈希算法

  • 字符串匹配算法

五大经典算法对比

模型：贪心、回溯、动态规划可抽象成多阶段决策最优解模型，分治算法不可以。
重复子问题：分治分割成子问题， 不存在重复子问题。动态规划存在大量重复子问题。
局部最有解。贪心算法可以解决一部分动态规划，满足，最有子结构、无后效性、贪心选择性（通过局部最有选择， 产生全局最优选择）

在线机试网站

leedtcode

牛客网

华为成都、
注意运行环境， 输入输出

JavaScript(v8 6.0.0) (推荐)

while (line = readline()) {
    var lines = line.split(' ');
    var a = parseInt(lines[0]);
    var b = parseInt(lines[1]);
    print(a + b);
}

JavaScript(Node 12.18.2)

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    const tokens = line.split(' ');
    console.log(parseInt(tokens[0]) + parseInt(tokens[1]));
});

例如：

// 题目描述
// 输入一个整数，将这个整数以字符串的形式逆序输出
// 程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
// 输入描述:
// 输入一个int整数
// 输出描述:
// 将这个整数以字符串的形式逆序输出
// 示例1
// 输入
// 1516000
// 输出
// 0006151

// v8
while (line = readline()) {
    var lines = line.split(' ');
    let res = []
    while (lines > 0) {
        res.push(lines % 10);
        lines = Math.floor(lines / 10);
    }
    print(res.join(''));
}

// node
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    const tokens = line.split(' '); // input: 1516000  ouput: [ '1516000' ]
    let num = parseInt(tokens[0])
    let res = [];
    while (num > 0) {
        res.push(num % 10);
        num = Math.floor(num / 10)
    }
    console.log(res.join(''));
});

趋势

  • 算法模型正在取代数学模型

参考：
算法4 https://algs4.cs.princeton.edu/home/
算法4-斯坦福