刷题指南

参考文档：

1. https://oi-wiki.org/basic/
2. hello-algo

数据结构遍历方式

数组 线性迭代

function traverse(list) {
    for (let i = 0; i < list.length; i++) {
        const element = array[i];
        //
    }
}

链表 递归 迭代

linkedList

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}

function traverse(node) {
    for (let i = 0; i != null; i = i.next) {
        const val = node.val;
        //
    }
}

function traverse(node) {
    // 前序 node.val
    traverse(node.next);
    // node.val
    // 后序
}

二叉树递归遍历

binaryTree

class TreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function traverse(node) {
    // 前序 console.log(node.val)
    traverse(node.left);
    // 中序 console.log(node.val)
    traverse(node.right);
    // 后序 console.log(node.val)
}

dp 数组遍历方式

正向遍历

for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
        nums[i][j];
    }
}

反向遍历

for (let i = len - 1; i >= 0; i--) {
    for (let j = len - 1; j >= 0; j--) {
        nums[i][j];
    }
}

斜向遍历

for (let l = 2; l <= len; l++) {
    for (let i = 0; i <= len - l; i++) {
        let j = l + i - 1;
        nums[i][j];
    }
}

或者

for (let l = 1; l < len; l++) {
    for (let i = 0; i < len - l; i++) {
        let j = l + i;
        nums[i][j];
    }
}

反着遍历

for (let i = len - 2; l >= 0; l--) {
    for (let j = i + 1; j < len; j++) {
        nums[i][j];
    }
}

二分查找

寻找一个数

递归实现

/**
 * @param {number[]} nums - 有序数组
 * @param {number} target - 目标值
 * @return {number} - 目标值的索引，如果未找到则返回 -1
 */
function binarySearch(nums, target) {
    return traverse(nums, target, 0, nums.length - 1);
}

function traverse(nums, target, left, right) {
    if (left > right) {
        return -1;
    }

    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
        return mid;
    } else if (nums[mid] < target) {
        return traverse(nums, target, mid + 1, right);
    } else {
        return traverse(nums, target, left, mid - 1);
    }
}

迭代实现

/**
 * @param {number[]} nums - 有序数组
 * @param {number} target - 目标值
 * @return {number} - 目标值的索引，如果未找到则返回 -1
 */
function binarySearchIterative(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

寻找左侧边界的二分搜索

尽可能移动 right ，结束检测 left 值

/* @param {number[]} nums - 有序数组
 * @param {number} target - 目标值
 * @return {number} - 目标值的左侧边界索引
 */
function leftBoundBinarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        // 先判断 < 情况，否则都移动 right
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 检查 left 是否越界以及 nums[left] 是否为 target
    if (left >= nums.length || nums[left] !== target) {
        return -1; // 如果未找到目标值，则返回 -1
    }

    return left; // 返回左侧边界索引
}

寻找右侧边界的二分搜索

/**
 * @param {number[]} nums - 有序数组
 * @param {number} target - 目标值
 * @return {number} - 目标值的右侧边界索引
 */
function rightBoundBinarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 检查 right 是否越界以及 nums[right] 是否为 target
    if (right < 0 || nums[right] !== target) {
        return -1; // 如果未找到目标值，则返回 -1
    }

    return right; // 返回右侧边界索引
}

回溯算法

算法框架 路径 选择列表 结束条件

const res = [];
function backtrack(路径，选择列表) {
  if(结束条件){
    res.push(路径);
    return ;
  }

  for(选择 of 选择列表) {
    // 1. 做选择
    backtrack(路径，选择列表);
    // 3. 撤销选择
  }
}