二分
# 二分
二分的思想到现在我都还没掌握过，之前备战蓝桥杯的时候有突击过，但是现在来看完全没记到脑子🧠里面
所以这次就整理一下，然后在js中实现一下这个算法，当然语言只是语法上有差别而已，要真正懂得他的思想才是最重要的
先给一个例题：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4。
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1。
首先你想一下不用二分会怎么做这道题目？（前提这个数组是要是按照顺序来的）
明显就用一个循环不就好了，但是这是从头开始遍历的，那我们换个思路从中间开始这样会不会就折半的寻找的复杂度呢？不管你信不信二分法就是比普通循环高效一点
那我们从中间开始这个出发点来思考一下我们的二分法，一般我们会用到一个指针的方法来实现，动态指针
就是中间有一个中间数你可以定在头尾两个数的中间值，然后从中间出发比大小，然后如果中间数比目标值小
一个简单的
nums = [-1,0,3,5,9,12], target = 9
1. 首和尾之和 取平均值mid -1 + 12 / 2 = 5
2. 比较：target > mid 是小于target所以 mid应该要在在[mid 9, 10]这边对不对，也就是mid要往右边一位（反之亦然呗）
3. 当然有些时候需要考虑mid是要往右边一步还是就在此地
那我们赶紧结束这一题吧
function binarySearch(nums, target) {
let left = 0
let right = nums.length - 1
while (left <= right) { // 注意这个写法：区间有效条件
let mid = Math.floor((left + right) / 2) // 取中间的那个下标，向下取整
if (nums[mid] > target) {
// 中间这个数大了，目标在左边
right = mid - 1
} else if (nums[mid] < target) {
// 中间这个数小了，目标在右边
left = mid + 1
} else {
// 找到了，直接 return
return mid
}
}
// 没找到，返回 -1
return -1
}
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9)) // 4
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 2)) // -1
再来2题加深一下
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
输入: (nums = [1, 3, 5, 6]), (target = 2);
输出: 1;
function searchInsert (nums, target) {
let left = 0, right = nums.length
let result = 0
while(left <= right){
let mid = Math.floor((left + right) / 2)
if(nums[mid] > target){
right = mid - 1
}else if (nums[mid] < target){
left = mid + 1
}else{
return mid
}
}
return left
}
console.log(searchInsert([1, 3, 5, 6],7))
给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 Math.pow(x, 0.5) 或者 x ** 0.5。
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
输入：x = 4
输出：2
function mySqrt (x) {
let left = 0
let right = x
while(left <= right) {
let mid = Math.floor((left + right) / 2)
if(mid * mid === x) {
return mid
} else if(mid * mid < x) {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
# 栈和队列（前端视角）
诶其实我是觉得在前端上面没太多必要是学这个数据结构的东西的，但是有时候使用的话又很能解决一些问题和对性能等有帮助那么我就简单来学一下吧~~
基础原理：搞清楚栈和队列是什么
- 栈 Stack：先进后出（LIFO）
就像堆书本，最后放上去的，最先拿走。
- 队列 Queue：先进先出（FIFO）
就像排队买奶茶，先排队的人，先拿奶茶。
JS中的实现（基础 + 手写封装）
栈 Stack 👉 JS 原生支持的数组就可以
let stack = []
stack.push(1) // 入栈
satck.push(2)
console.log(stack.pop()) // 出栈，输出 2
console.log(stack[stack.length - 1]) // 栈顶
栈的封装（手写一个类）
class Stack{
constructor() {
this.stack = []
}
push(item){
this.stack.push(item)
}
pop() {
return this.stack.pop()
}
peek() {
return this.stack[this.satck.length - 1]
}
isEmpty() {
return this.stack.length === 0
}
}
图解：
底部 [ 1, 2, 3 ] 顶部
push(4) → [1, 2, 3, 4]
pop() → [1, 2, 3]
在前端的应用场景
| 场景 | 说明 |
|---|---|
| 括号匹配 | 你写的例题就是 |
| 浏览器的历史记录 | 后退、前进就是栈 |
| 页面路径导航 | Vue Router 的历史模式，路径回退也是栈 |
| 撤销、恢复功能 | 编辑器里的撤销功能，栈保存操作记录 |
| DFS（深度优先搜索） | 手写递归 or 改写成栈 |
来个例题看一下
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
输入：s = "{[]}"
输出：true
输入：s = "([)]"
输出：false
function isValid (s) {
let stack = []
let brackets = {
'(': ')',
'{': '}',
'[': ']'
}
for(let i = 0; i < s.length; i++) {
// 左括号进栈
if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
stack.push(s[i])
} else {
// 出栈的值对应的括号与当前括号不匹配，一定是无效的括号
if(brackets[stack.pop()] != s[i]) {
return false
}
}
}
return stack.length == 0 // 看是否栈空
}
module.exports = isValid
队列 Queue 👉 JS 数组也可以，但 shift 性能差
let queue = []
queue.push(1) // 入队
queue.push(2)
console.log(queue.shift()) // 出队，输出 1
console.log(queue[0]) // 队头
队列的封装（手写一个类）
class Queue {
constructor() {
this.queue = []
}
enqueue(item) {
this.queue.push(item)
}
dequeue() {
return this.queue.shift()
}
peek() {
return this.queue[0]
}
isEmpty() {
return this.queue.length === 0
}
}
如果你需要更高性能的队列，最好用链表或双端队列。
图解：
头部 [ 1, 2, 3 ] 尾部
enqueue(4) → [1, 2, 3, 4]
dequeue() → [2, 3, 4]
前端常用场景
| 场景 | 说明 |
|---|---|
| 消息队列 | 事件循环、任务调度 |
| BFS（广度优先搜索） | 最短路径、层序遍历 |
| 节流控制 | 控制请求队列 |
| 动画排队 | 页面多个动画顺序执行 |
来个例题：
# 双指针
双指针（Two Pointers）是一种遍历数组的技巧，使用两个]指针在数据结构（通常是数组或字符串）上进行扫描，以提高效率。
| 场景 | 描述 | 举例题目 |
|---|---|---|
| 对撞指针 | 一头一尾往中间靠 | 反转字符串、判断回文 |
| 快慢指针 | 一快一慢移动 | 删除重复元素、检测环 |
| 滑动窗口 | 区间变化计算 | 最小覆盖子串、最长子数组 |
对撞指针的例题：反转字符串
思路：一个指针从左向右，一个从右向左，逐步逼近
function reverseString(s) {
let left = 0 , right = s.length -1
while(left < right) {
[s[left], s[right]] = [s[right], s[left]]
left++
right--
}
}
快慢指针
思路：两个指针维护一个区间，动态调整窗口
right：快指针，向右滑动窗口，不断尝试加入新字符
left：慢指针，一旦发现重复，就往前推进，排除掉重复字符
// 无重复字符的最长子串
function lengthOfLongestSubstring(s) {
let map = new Map() //存储字符最后一次出现的位置
let left = 0 //慢指针，滑动窗口的左边界
let maxLen = 0 //记录最大长度
for(let right = 0; right < s.length; right++) {
const ch = s[right] //当前要处理的字符
//如果 map 中存在 ch，并且它的位置 >= 当前窗口起点
}
}
# 哈希表Map
# 动态规划
# 数组api
# 字符串api
# 字符串匹配
# 树
js实现二叉树的定义和基本操作
定义二叉树节点
**树（Tree）**是一种非线性数据结构，每个节点包含一个值和若干子节点。
**二叉树（Binary Tree）**是树的一种特殊形式：
- 每个节点最多有两个子节点（左子节点
left和右子节点right）。
在 JS 里没有原生的“树”类型，需要自己用 对象 + 指针引用 去构建。
class TreeNode {
constructor(value) {
this.value = value; // 节点值
this.left = null; // 左子树
this.right = null; // 右子树
}
}
二叉树的构建原理
- 通常从一个
root根节点开始。 - 通过不断给
left和right赋值，递归形成树形结构。 - 在插入时，常见两种规则：
- 普通二叉树：自由插入，位置由逻辑控制。
- 二叉搜索树（BST）：左子树 < 根节点 < 右子树。\
遍历原理
树的核心操作就是遍历，常见三种深度优先遍历（DFS）：
- 前序遍历（根 → 左 → 右）
- 中序遍历（左 → 根 → 右）
- 后序遍历（左 → 右 → 根）
以及一种广度优先遍历（BFS，层序遍历）。 它们的本质是：
- DFS → 递归栈/手动栈 实现。
- BFS → 队列 实现。
插入一个二叉搜索树的过程：
- 从
root开始比较值大小。 - 小于根节点则往左走，大于则往右走。
- 直到找到空位，插入新节点。
遍历时：
- 递归函数本质是调用栈模拟一条路径走到头，再回溯。
- BFS 使用队列保证逐层访问。
构建二叉搜索树（BST）
class BinarySearchTree {
constructor() {
this.root = null;
}
// 插入节点
insert(value) {
const newNode = new TreeNode(value);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (value < current.value) {
// 插入左子树
if (!current.left) {
current.left = newNode;
break;
}
current = current.left;
} else {
// 插入右子树
if (!current.right) {
current.right = newNode;
break;
}
current = current.right;
}
}
}
// 查找节点
search(value) {
let current = this.root;
while (current) {
if (current.value === value) return true;
current = value < current.value ? current.left : current.right;
}
return false;
}
// 前序遍历
preorder(node = this.root) {
if (!node) return;
console.log(node.value);
this.preorder(node.left);
this.preorder(node.right);
}
// 中序遍历
inorder(node = this.root) {
if (!node) return;
this.inorder(node.left);
console.log(node.value);
this.inorder(node.right);
}
// 后序遍历
postorder(node = this.root) {
if (!node) return;
this.postorder(node.left);
this.postorder(node.right);
console.log(node.value);
}
}
使用示例
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
console.log("查找 7:", bst.search(7)); // true
console.log("查找 12:", bst.search(12)); // false
console.log("前序遍历:");
bst.preorder(); // 10, 5, 3, 7, 15
console.log("中序遍历:");
bst.inorder(); // 3, 5, 7, 10, 15 （升序）
console.log("后序遍历:");
bst.postorder(); // 3, 7, 5, 15, 10
# 手写题：
# 浅/深拷贝
浅拷贝 (Shallow Copy)
只复制对象的第一层属性。
如果属性是引用类型（对象 / 数组），拷贝的只是引用地址。
常见方法:
Object.assign({}, obj){ ...obj }（展开运算符）
function shallowCopy(obj){
if (typeof obj !== 'object' || obj === null) return obj
let newObj = Array.isArray(obj) ? [] : {}
for(let key in obj){
if(obj.hasOwnProperty(key)) {
newObj[key] = obj[key]
}
}
return newObj
}
深拷贝
递归复制每一层属性。
引用类型会重新创建，不共享内存地址。
简单写法：JSON
let deep = JSON.parse(JSON.stringify(obj))
有缺点：
手写深拷贝（递归版）
递归思想
每次遇到对象或数组时，继续调用 deepCopy，直到遇到基本类型才返回。
function deepCopy(obj, map = new WeakMap()){
if (typeof obj !== 'object' || obj === null) return obj
// 解决循环引用
// 如果 map 已经保存过这个对象，说明出现了循环引用，直接返回之前的拷贝结果
if(map.has(obj)) return map.get(obj)
// 创建新对象，判断是数组还是普通对象
let newObj = Array.isArray(obj) ? [] : {}
// 把当前对象和新对象的对应关系存入 WeakMap
// 这样如果再次遇到 obj，就可以直接拿出来用，避免无限递归
map.set(obj, newObj)
// 遍历对象的属性（只拷贝自有属性，不拷贝原型链上的）
for(let key in obj){
if(obj.hasOwnProperty(key)){ // 避免拷贝原型链上的属性。
// 递归拷贝子属性
newObj[key] = deepCopy(obj[key], map)
}
}
return newObj
}
为什么要用 WeakMap？
解决 循环引用 问题，比如：
let obj = {} obj.self = obj deepCopy(obj) // 没有 WeakMap 会无限递归WeakMap 的 key 必须是对象，且是弱引用，不会阻止垃圾回收，避免内存泄漏。
调用示例
let obj = {
name: 'mmx',
info: { age: 20, hobby: ['code', 'music'] }
}
let shallow = shallowCopy(obj)
let deep = deepCopy(obj)
obj.info.age = 99
obj.info.hobby.push('game')
console.log('浅拷贝:', shallow.info.age) // 99 （被影响）
console.log('深拷贝:', deep.info.age) // 20 （不受影响）
# 防抖/节流
防抖
时间触发后一段时间再执行，等待期间再次触发要重新计算
常用于搜索框搜索、窗口resize、按钮点击防止重复提交
function debounce(fn ,delay){
let timer = null
return function (...args) {
if(timer) clearTimeout(timer)
timer = setTimerout(()=>{
fn.apply(this,args)
}, delay)
}
}
//
function search(value) {
console.log('请求接口：', value)
}
const debounceSearch = debounce(search, 500)
// 连续输入，只会在停止 500ms 后执行一次
debounceSearch('a')
debounceSearch('ab')
debounceSearch('abc')
// => 只会打印一次 "请求接口：abc"
节流
规定一段时间内只执行一次。即使多次触发，也在时间间隔内只会执行一次。
常用场景：滚动加载、鼠标移动、窗口 resize。
// 时间戳版立即执行
function throttle(fn, delay) {
let last = 0
return function (...args) {
const now = Date.now()
if(now - last > delay) {
fn.apply(this.args)
last = now
}
}
}
//定时器版（延迟执行）
function throttle(fn, delay){
let timer = null
return function (...args){
if(!timer){
timer = setTimerout(()=>{
fn.apply(this, args)
timer = null
},delay)
}
}
}
//调用示例
function handleScroll() {
console.log('滚动事件', Date.now())
}
const throttleScroll = throttle(handleScroll, 1000)
// 即使疯狂滚动，也每隔 1s 执行一次
window.addEventListener('scroll', throttleScroll)
# new
手搓一个new
function myNew(Con, ...args) {
// 1. 空对象且隐式原型指向 Con.prototype
const obj = Object.create(Con.prototype)
// 2. 绑定 this 并执行构造函数
const res = Con.apply(obj, args)
// 3. 若构造函数显式返回对象，则返回该对象，否则返回第一步创建的对象
return (res !== null && (typeof res === 'object' || typeof res === 'function')) ? res : obj
}
追问 1：为什么用 Object.create 而不用字面量 {}？
字面量默认指向 Object.prototype，而我们要把新对象的 __proto__ 精确地指向构造函数的 prototype 属性，才能保证 instanceof 语义与原生 new 一致。
追问 2：第三步的判断条件为什么把 function 也考虑进去？
在 ES 规范里，构造函数如果返回一个函数（例如返回一个箭头函数或类），这个函数同样会覆盖默认的 this，所以要把 function 类型也纳入判断；null 特殊处理是因为 typeof null === 'object'，但 null 不是有效对象，需排除。
追问 3：你的实现与原生 new 还有什么关键差异？
- 原生
new在引擎层面是原子操作，中间不会插入其他脚本；而手搓版本在Con.apply时若抛出异常，无法自动清理已创建的临时对象——原生引擎会回滚。
# 手搓一个apply
手搓 Function.prototype.apply ——不依赖原生 apply/call
// ======================手搓apply=================================
//fn.apply(context, [args])
Function.prototype.myApply = function (context, args) {
// this 指向调用 myApply 的函数
if (typeof this !== 'function') {
throw new TypeError('myApply must be called on a function')
}
// 处理 context（可能是 null/undefined，要指向全局对象）
context = context || globalThis // 浏览器是 window，Node.js 是 global
// 给 context 添加一个临时属性 fn，指向当前函数（this）
const fnSymbol = Symbol('fn') // 避免覆盖原有属性
context[fnSymbol] = this
// 执行函数，展开参数数组
let result
if (Array.isArray(args)) {
result = context[fnSymbol](...args)
} else if (args === undefined || args === null) {
result = context[fnSymbol]() // 没有参数时直接调用
} else {
throw new TypeError('CreateListFromArrayLike called on non-object') // 跟原生一致
}
// 删除临时属性
delete context[fnSymbol]
// 返回执行结果
return result
}
# 手搓bind
Function.prototype.myBind = function (Context, ...args){
if(typeof this !== "function"){
throw new TypeError("")
}
const self = this // 保存原函数
function boundFunction(...newArgs) {
// 如果作为构造函数调用new
if(this instanceof boundFunction) {
return new self(...args, ...newArgs)
}
// 普通函数调用
return self.apply(context, [...args, ...newArgs])
}
// 继承原型
boundFunction.prototype = Object.create(self.prototype)
return boundFunction
}