链表与数组相关算法总结

1. 删除链表中的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var removeElements = function (head, val) {
  let dummy = new ListNode(0, head);
  let cur = dummy;

  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }

  return dummy.next;
};

2.反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var reverseList = function (head) {
  if (!head) return null;

  let end = head;
  while (end.next) end = end.next;

  function reverse(node) {
    if (node.next === null) {
      return node;
    } else {
      return (reverse(node.next).next = node);
    }
  }

  reverse(head).next = null;
  return end;
};

3. 数组去重（双指针法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var removeDuplicates = function (nums) {
  let slow = 1;
  let fast = 1;

  while (fast !== nums.length) {
    if (nums[slow - 1] !== nums[fast]) {
      nums[slow++] = nums[fast];
    } else {
      fast++;
    }
  }

  return slow;
};

4. 移除数组中的某个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeElement = function (nums, val) {
  let slow = 0;
  let fast = 0;

  while (fast !== nums.length) {
    if (nums[fast] === val) {
      fast++;
    } else {
      nums[slow] = nums[fast];
      fast++;
      slow++;
    }
  }

  return slow;
};

5. 算法写作原则

写好的代码

  • 不要写“恶心”的代码。
  • 当你需要某个功能函数时，如果已有现成实现（AI 或第三方库），就不要重复造轮子。
  • 做开发的目标是 最终产出可维护、可用的代码。

写算法前要想清楚

  1. 明确起止条件
  2. 明确答案的表现形式（数组、链表、数值等）
  3. 从语义上保证代码正确
  4. 能够自己推导出逻辑，而不是依赖抄答案

数组抽象思路

如果问题可以抽象为“答案数组”：

  • 考虑常规的数组操作（插入、删除、覆盖、移动等）
  • 思考如何根据输入计算出答案

保证代码正确性

除了常规情况，还要考虑：

  • 边界值
  • 极端值

确保算法在各种场景下都能正确运行。

算法复杂度选择

  • 数据规模较小 → 可以用暴力算法
  • 数据规模较大 → 必须考虑优化

暴力枚举的思路

  • 枚举就是函数映射： f(x) = y
  • 定义域 (X)： 所有可能的输入（枚举单元）
  • 映射规则 (f)： 输入如何映射到结果
  • 值域 / 解空间 (Y)： 所有可能的答案

目标： 在解空间中找到最符合题目要求的解。

写算法题的时候是用数学归纳法很好用，并且可以分类讨论，不重不漏，奇偶分类之类的很好用

算法要能被数学证明是正确的

很多事情都是没有正确的方法 导致学的非常痛苦 没有提升

任何涉及到数字的比较 JS 都会把他转换为数字类型 比如 undefined 和数字，undefined 转换为数字是 NaN NaN 和任何数字做表达式运算的结果都是 false

JS [].sort 是按照字典顺序 而非数字大小顺序 比如 [1,-2,2,10].sort() => [-2,1,10,2]

题目要保证某些东西互不相同 那么最好的办法就是把他们做成 map 的 key 去重

JS 字符串是不可变的 无法改变里面的值 s=”string” s[1]=”d” s 依然是”string”

React/框架：每种框架都是一种编程范式，比如 react 是声明式编程，区别于命令式编程

声明式编程：只是描述这里有一个东西是什么样子的，不用关心具体实现

命令式编程：其实就是声明式编程具体的实现，书写每一步要做什么

声明式编程更利于大项目的开发 因为不用关心详细的细节

写小 demo 脚本可以使用命令式编程更好

react 生态丰富 基本上每一个你需要的东西 都可以有现成的第三方工具使用

react 完全可以跨平台开发 [react Native] 学习方式参考资料 AI react 官方文档和教程

react 是一个用于构建网页和原生产品的交互界面的库

库是解决特定类型问题的工具，往往产品的开发除了库还要别的东西集合
框架是集合了开发项目所需的所有的库

React 的主要作用是专注于视图层和组件化

视图层：页面中元素管理的代码 View

组件化：设定相应的逻辑就可以批量生产组件，多次重复的调用

虚拟 DOM：React 封装的一层 JS 对象，是 React.createElement 函数调用返回的结果，然后以树的形式组织起来的，里面节点就是 react 元素

所去别的 fiber tree 就是树形链表的形式，又做了一层封装 为了快速的找到 diff 和协调 找到需要提交的 dom 更改 ，给到 commit 阶段

只有真实的 DOM 才会是页面上展示的结果，虚拟 DOM 其实就是为了控制真实的 DOM 可以提高页面的更新效率 为了保证浏览器的性能，短时间内大量多次的重绘有效率问题

但是呢，任何的技术方案都有自己的优缺点，主要还是看适合项目与否

React 开发环境设置： 不用构建工具,codesandbox,vite,cra,next.js

不用构建工具 你要导入两个 script 标签，一个是虚拟 DOM 做出真正的 fiber, 还有一个是和真实 DOM 打交道 commit 阶段,还有一个 babel 从在线地址中导入代码 defer

useEffect / useLayoutEffect 使用方式一模一样，只是生命周期发生的时间点不一样，这两个函数都是在提交阶段生效，在生成真实 DOM 之后，会执行 useLayoutEffect 中注册的回调函数，然后浏览器绘制页面，之后执行 useEffect 中注册的回调函数，注册是在虚拟 DOM 的时候就被注册

之后再次渲染，若依赖数组中有变化，会在 diff 算法之后

先执行 useLayoutEffect 的 return 函数 然后执行 useLayoutEffect 的回调函数

然后在浏览器重新绘制页面之后执行 useEffect 的 return 函数 然后执行 useEffect 的回调函数 [看到真实的结果]

组件生命周期：组件实例从创建到销毁的过程 函数组件实例的生命周期

分别从整体的视角和从组件的视角来查看 react 是如何工作

mount 挂载：组件的第一次执行/渲染

mount 过程: 执行函数组件代码，计算 JSX 生成新虚拟 DOM -> 生成真实 DOM -> useLayoutEffec 过程 -> 浏览器渲染绘制页面 (Repainr/Reflow) -> useEffect 过程

update 更新：组件第 n 次执行/渲染

update 过程： 重新执行函数组件代码，计算 JSX 生成新虚拟 DOM -> Diff & 真实 DOM 更新 -> useLayout 过程 -> 浏览器渲染绘制页面 (Repainr/Reflow) -> useEffect 过程

unmount 卸载：组件从页面上移除

unmount 过程: 标记需要移除的虚拟 DOM -> 移除真实 DOM -> useLayoutEffect -> 浏览器渲染绘制页面 -> useEffect -> 清理并释放虚拟 DOM 等相关数据内存