算法与数据结构

目标

主要的数据结构，常用的算法，一些题。

Trie 树 跳表（redis）

大纲

数据结构

链表、栈、队列 hash 树 -- 树打平、反过来、前序、后序、中序 图

为什么说算法和数据结构很重要？

有人说时间复杂度/空间复杂度？八股文？

1. 算法和数据结构，是计算机的基本逻辑的提现(体系化);
2. 作为基础，一定是你的成长的天花板。

• 算法、数据结构 -- 阻碍你构建知识体系的第一关。
• 设计模式。
• 编译原理、计算机组成原理。

前端真的没有算法么？

virtual dom diff算法； react fiber 各种各样的链表(环状);

算法是很有魅力的东西

羊了个羊

1. 生成N个图案 * (m-n,m+n)
2. N*个图案，随机打散，叠加 * 3的倍数；玉米、玉米、玉米、线团等等
3. 随机按照画布上的格子，堆上去就行了。

热身，写一个算法随机一个数组

在V8引擎中，数组长度 > 10 ? 快排 : 插入

算法的概念

时间复杂度

一个算法的时间复杂度，就是在程序运行需要的时间中，把算法的重复执行次数，拿了出来

主观感觉

• 没有循环 = O(1)
• 一层循环 = O(n)
• 二分 = lgn

实际上的原则

• 只关注循环最多的代码
• 加法法则：总复杂度 = 量级最大那段
• 乘法法则：嵌套代码的复杂度 = 嵌套内外的复杂度乘积

数据结构

数组

• 我们先抛开js

• 数组是一种线性表结构，他用一组连续的内存空间，来存储一组具有相同类型的数据。 0x0001

• 随机访问时，根据下标访问的时间复杂度是O(1)

• 但是如果插入一个数据进去

• JS 的数组

  • 快数组
    • [1,2,3,4,5,6]
  • 慢数组
    • [ 1 , "hello" , {key:"val"} , true]

链表

0x0003 -> 0x3501 -> 0x3508 1 -> 2 -> 3

1. 首先没有连续的地址空间
2. 方便我进行插入和删除

这里主要说明链表反转的两个方法：

1. 插入法，首先给head添加一个前继节点dummy，然后取head的下一个节点塞到dummy的后面，循环就完事了

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    const dummy = new ListNode(-1, head)
    let next = head?.next
    while (next) {
        let cur = dummy.next
        head.next = next.next
        dummy.next = next
        next.next = cur // 这里注意不是head
        next = head.next
    }
    return dummy.next
};

2. 直接交替，因为反转以后头部变成了null，所以直接设置prev为null，拿到cur和next，然后让链表裂开，每次取旧的头塞到新的当头就行了。而这里的prev实际上是每次循环新链表的尾巴，而cur是每次循环旧链表的头部。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let prev = null
    let cur = head
    while (cur) { 
        const next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
};

算法类型

各种排序 二分(分治)、贪心、动规、回溯 分治算法，在排序中应用是十分广泛的。

• 分解：将问题分解成一系列子问题；
• 条件：递归分解了以后，一定有一个最小的时候，怎么直接求解。
• 合并：将子问题合并

原问题，分解了以后，每个子问题要相互独立

典型题目：

快排、归并、求平方根

贪心

需要转换思路。每次都给局部最优解，但是能保证，算法结束的时候，结果一定是全局最优的。

找钱、背包问题、装豆子。

// leetcode 跳跃游戏

动规

将小问题记录下来，逐步推导结果 dp[n] = f(dp[n-1])

爬楼梯、斐波那契数列

回溯

DFS ，大部分情况下，就是广义搜索，解决问题

• 组件问题:N个数，按照一定的规则，找出 K 个数
• 切割问题：一个字符串，有多少种切割的方案
• 棋盘问题：八皇后，数独；
• 排列问题：n个数按照一定的规则（比如求多个数的和），有多少种排列方案

滑动窗口

用来解决满足一定条的连续区间性质的问题

js精度问题

介绍

• JavaScript使用IEEE 754标准来表示浮点数，在IEEE 754双精度浮点数（64位）中，只有53位用于表示整数部分，这限制了可以精确表示的整数的大小。
• 超过这个范围的整数可能无法精确表示，导致精度损失。
• JS浮点数精度的缺失实际上是因为浮点数的小数部分无法用二进制很精准的转换出来，而以近似值来进行运算的话，肯定就存在精度的问题

大数相加

function bigNumberAdd(a, b) {
    let num1 = a.split('');
    let num2 = b.split('');
    let result = '';
    // 下一个十进制的位置
    let carry = 0;

    // 这里之所以后面有||carry就是解决 最后一次while循环中carry为1的情况
    while (num1.length || num2.length || carry) {
        let val1 = num1.pop() || '0';
        let val2 = num2.pop() || '0';
        let sum = parseInt(val1) + parseInt(val2) + carry;
        carry = Math.floor(sum / 10);
        result = (sum % 10) + result;
    }

    return result.replace(/^0+/, ''); // 移除结果前导0
}

// 使用示例
let sum = bigNumberAdd('312431243241341341341341', '2131231231231421431535');
console.log(sum); // 输出相加结果

浮点数计算

function floatOperation(num1, num2, operator) {
    // 将数字转换为字符串，并且移除尾随零
    const strNum1 = num1.toString().replace(/[0]+$/, '');
    const strNum2 = num2.toString().replace(/[0]+$/, '');

    // 计算小数点后的位数
    const decimal1 = strNum1.split('.')[1] ? strNum1.split('.')[1].length : 0;
    const decimal2 = strNum2.split('.')[1] ? strNum2.split('.')[1].length : 0;
    const decimal = Math.max(decimal1, decimal2);

    // 对数字进行放大或缩小到整数区间
    const scale = 10 ** decimal;
    const int1 = Math.round(num1 * scale);
    const int2 = Math.round(num2 * scale);

    if ((operator === '/' || operator === '%') && num2 === 0) {
        throw new Error('除数不能为0');
    }

    // 执行运算
    let result;
    switch (operator) {
        case '+':
            result = int1 + int2;
            break;
        case '-':
            result = int1 - int2;
            break;
        case '*':
            result = int1 * int2;
            break;
        case '/':
            result = int1 / int2;
            break;
        case '%':
            result = int1 % int2;
            break;
    }

    // 将结果缩小回正确的小数位
    return result / scale;
}

// 使用示例
console.log(floatOperation(0.1, 0.2, '+')); // 0.3
console.log(floatOperation(5.34, 1.12, '-')); // 4.22
console.log(floatOperation(2.7, 100, '/')); // 0.0027
console.log(floatOperation(4.567, 0.001, '*')); // 4.567
console.log(floatOperation(10.5, 3, '%')); // 1.5