常见算法

堆、栈、 队列、 链表、 双指针、随机算法、 二分查找、 排序算法（冒泡、选择、插入、归并、快速）、动态规划、滑动窗口。

洗牌

export function shuffleArray<T>(arr: T[]) {
  for (let i = arr.length - 1; i > 0; --i) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  return arr;
}

function shuffle(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    // 随机选择一个位置，与当前位置交换
    let j = Math.floor(Math.random() * (n - i)) + i;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}
shuffle([1, 2, 3, 4]);

随机算法

export function randomItem<T>(arr: T[]) {
  return arr[Math.floor(Math.random() * arr.length)];
}

双指针

链表是否有环

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
// 示例： 链表结构
const head = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: { val: 4, next: head.next }, // 这里形成环
    },
  },
};

hasCycle(head);

通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

var findLongestWord = function (s, dictionary) {
  let str = "";
  for (let i = 0; i < dictionary.length; i++) {
    let left = 0;
    let right = 0;
    const curDic = dictionary[i];

    // 双指针，左指针指向s的当前字符，右指针指向字典单词的当前字符
    while (left < s.length && right < curDic.length) {
      // 如果当前字符相等，则右指针向右移动一位
      if (s.charAt(left) === curDic.charAt(right)) {
        right++;
      }

      // 如果右指针已经移动到字典单词的末尾，则更新最长字符串
      if (right === curDic.length) {
        if (
          curDic.length > str.length ||
          (curDic.length === str.length && curDic < str)
        ) {
          str = curDic;
        }
      }

      // 左指针向右移动一位，继续匹配下一个字符
      left++;
    }
  }
  return str;
};

滑动窗口

原理： 滑动窗口是一种常用的算法技巧，用于在数组或字符串中查找满足特定条件的子序列。它通过维护一个固定大小的窗口（通常是一个连续的子数组或子串），并动态地移动这个窗口来遍历整个数据结构。

无重复字符的最长子串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) return s.length;
  let left = 0;
  let right = 1;
  let max = 0;
  let sArr = s.split("");
  while (right < s.length) {
    let cur = s.slice(left, right);
    if (cur.indexOf(sArr[right]) > -1) {
      left++;
      continue;
    } else {
      right++;
    }

    if (right - left > max) {
      max = right - left;
    }
  }
  return max;
};

树

树一般采用的解决方式是递归

常见题：

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

** 解法：**

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
      stack.push(s[i]);
    } else if (s[i] === ")") {
      const cur = stack.pop();
      if (cur !== "(") return false;
    } else if (s[i] === "]") {
      const cur = stack.pop();
      if (cur !== "[") return false;
    } else if (s[i] === "}") {
      const cur = stack.pop();
      if (cur !== "{") return false;
    }
  }
  return !stack.length;
};

// 方式二：
var isValid = function (s) {
  let map = new Map([
    ["(", ")"],
    ["[", "]"],
    ["{", "}"],
  ]);
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      stack.push(s[i]);
    } else if (map.get(stack.pop()) !== s[i]) {
      return false;
    }
  }
  return !stack.length;
};

// 方式三：
var isValid = function (s) {
  if (s.length % 2 !== 0) return false;

  let length = s.length / 2;
  while (length--) {
    s = s.replace("{}", "").replace("()", "").replace("[]", "");
  }
  return !s.length;
};

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

• 示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

• 示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

• 示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

** 解法：**

var threeSum = function (nums) {
  if (nums.length < 3) return [];

  let result = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    if (nums[i] > 0) break;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      let cur = nums[i];
      let curLeft = nums[left];
      let curRight = nums[right];
      const curTotal = cur + curLeft + curRight;
      let pre = [cur, curLeft, curRight];
      if (curTotal === 0 && result.indexOf(pre) < 0) {
        result.push([cur, curLeft, curRight]);
        // 跳过左侧重复元素
        while (left < right && nums[left] === nums[left + 1]) left++;
        // 跳过右侧重复元素
        while (left < right && nums[right] === nums[right - 1]) right--;
        // 移动左右指针到下一组不同元素
        left++;
        right--;
      }
      if (curTotal < 0) {
        left++;
      }
      if (curTotal > 0) {
        right--;
      }
    }
  }
  return result;
};

有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

** 解法：**

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
  let result = 0;
  nums.sort((a, b) => a - b);

  for (let k = nums.length - 1; k >= 2; k--) {
    let left = 0;
    let right = k - 1;

    while (left < right) {
      // 如果最小的两条边之和大于最大的边，则可以形成三角形
      if (nums[left] + nums[right] > nums[k]) {
        // 所有left到right-1的索引与right和k都能组成三角形
        result += right - left;
        right--;
      } else {
        left++;
      }
    }
  }

  return result;
};

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

// 处理乘数为零的情况
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
    // 处理乘数为零的情况
    if (num1 === "0" || num2 === "0") return "0";

    // 实现字符串与单个数字的乘法
    function multiplySingleDigit(numStr, digit) {
        if (digit === "0") return "0";
        let result = "";
        let carry = 0;

        for (let i = numStr.length - 1; i >= 0; i--) {
            const digit1 = parseInt(numStr[i]);
            const product = digit1 * parseInt(digit) + carry;
            carry = Math.floor(product / 10);
            result = (product % 10) + result;
        }

        if (carry > 0) {
            result = carry + result;
        }
        return result;
    }

    // 实现两个数字字符串的加法
    function addNumberString(str1, str2) {
        let result = "";
        let carry = 0;
        let i = str1.length - 1;
        let j = str2.length - 1;

        while (i >= 0 || j >= 0 || carry > 0) {
            const digit1 = i >= 0 ? parseInt(str1[i--]) : 0;
            const digit2 = j >= 0 ? parseInt(str2[j--]) : 0;
            const sum = digit1 + digit2 + carry;
            carry = Math.floor(sum / 10);
            result = (sum % 10) + result;
        }

        return result;
    }

    // 确定较短和较长的数字
    const minLengthNum = num1.length > num2.length ? num2 : num1;
    const maxLengthNum = num1.length > num2.length ? num1 : num2;
    const centerArr = [];

    // 生成中间结果（带补零）
    for (let i = minLengthNum.length - 1; i >= 0; i--) {
        const curMin = minLengthNum[i];
        const product = multiplySingleDigit(maxLengthNum, curMin);
        const zeros = "0".repeat(minLengthNum.length - 1 - i);
        centerArr.push(product + zeros);
    }

    // 累加所有中间结果
    let result = "0";
    for (const num of centerArr) {
        result = addNumberString(result, num);
    }

    return result;
};