Welcome👋

Appearance

算法手撕 ​

基础题 ​

大数相加 ​

js
const addStrings = function (num1, num2) {
  const maxLen = Math.max(num1.length, num2.length);
  num1 = num1.padStart(maxLen, '0');
  num2 = num2.padStart(maxLen, '0');
  let carry = 0;
  const res = [];
  for (let i = 0; i < maxLen; i++) {
    let tempNum = parseInt(num1[i]) + parseInt(num2[i]) + carry;
    if (tempNum >= 10) {
      carry = 1;
    } else {
      carry = 0;
    }
    res.unshift(tempNum % 10);
  }
  if (carry === 1) res.unshift('1');
  return res.join('');
};

const res = addStrings('1234567123', '345678234567');
console.log(res);

大数相乘 ​

js
let multiply = function (num1, num2) {
    if (isNaN(num1) || isNaN(num2)) return '';
    if (num1 === '0' || num2 === '0') return '0';

    let l1 = num1.length,
        l2 = num2.length;

    let result = [];

    for (let i = l1 -1; i >= 0; i--) {
        for (let j = l2 - 1; j >= 0; j--) {
            let index1 = i + j;
            let index2 = i + j + 1;

            let product = num1[i] * num2[j] + (result[index2] || 0);
            result[index2] = product % 10;
            result[index1] = Math.floor(product / 10) + (result[index1] || 0);
        }
    }
    return result.join('').replace(/^0+/, '');
}
console.log(multiply('123', '234')) //28782

只出现一次的数字 ​

js
function findUniqueNumbers(arr) {
    const count = {}; // 用于存储每个数字的出现次数

    // 统计每个数字的出现次数
    for (const num of arr) {
        count[num] = (count[num] || 0) + 1;
    }

    // 筛选出只出现一次的数字
    const uniqueNumbers = Object.keys(count).filter(num => count[num] === 1).map(Number);

    return uniqueNumbers; // 返回只出现一次的数字
}

const input = [1, 2, 3, 5, 2, 1];
const output = findUniqueNumbers(input);
console.log(output); // [3, 5]

字符串异位词 ​

字符串异位词：字符组成相同但排列不同的字符串。

方法一：

  • 将两个字符串排序。
  • 比较排序后的字符串是否相等。
js
function isAnagram(str1, str2) {
    const sortedStr1 = str1.split('').sort().join('');
    const sortedStr2 = str2.split('').sort().join('');
    return sortedStr1 === sortedStr2;
}

// 示例
console.log(isAnagram('listen', 'silent')); // 输出: true

方法二：

  • 使用一个对象或数组来计数每个字符的出现次数。
  • 比较两个计数对象是否相等。
js
function isAnagram(str1, str2) {
    if (str1.length !== str2.length) return false;

    const count = {};

    for (const char of str1) {
        count[char] = (count[char] || 0) + 1;
    }

    for (const char of str2) {
        if (!count[char]) return false;
        count[char]--;
    }

    return true;
}

// 示例
console.log(isAnagram('listen', 'silent')); // 输出: true

添加千分位分隔符 ​

js
function thousandSeparator(n) {
  // 处理负号
  const isNegative = n < 0;
  const strNum = Math.abs(n).toString();
  
  // 分割整数部分和小数部分
  const parts = strNum.split('.');
  let integerPart = parts[0];
  const decimalPart = parts[1] ? '.' + parts[1] : '';

  // 反转字符串以便从后面开始添加千分位
  let result = '';
  let count = 0;

  for (let i = integerPart.length - 1; i >= 0; i--) {
    result = integerPart[i] + result;
    count++;

    // 每三位添加一个分隔符
    if (count % 3 === 0 && i > 0) {
      result = '.' + result;
    }
  }

  // 返回最终格式化的结果
  return (isNegative ? '-' : '') + result + decimalPart;
}

// 示例用法
console.log(thousandSeparator(1234567));        // "1.234.567"
console.log(thousandSeparator(-1234567.89));    // "-1.234.567.89"
console.log(thousandSeparator(12345.678));      // "12.345.678"
console.log(thousandSeparator(0));               // "0"

字符串转数组 ​

可以直接：

js
const str = '[11, 22, [ 13, [24], 11], 23]';
const array = JSON.parse(str);
console.log(array);
js
function parseArray(str) {
  const stack = [];
  let current = [];
  let num = '';
  let inArray = false;

  for (const char of str) {
    if (char === '[') {
      // 开始新的数组
      if (inArray) {
        stack.push(current);
      }
      current = [];
      inArray = true;
    } else if (char === ']') {
      // 结束当前数组
      if (num) {
        current.push(Number(num));
        num = '';
      }
      if (stack.length > 0) {
        const parent = stack.pop();
        parent.push(current);
        current = parent;
      }
      inArray = false;
    } else if (char === ',') {
      // 分隔符，处理数字
      if (num) {
        current.push(Number(num));
        num = '';
      }
    } else if (char.trim()) {
      // 处理数字
      num += char;
    }
  }

  // 处理最后的数字
  if (num) {
    current.push(Number(num));
  }

  return current;
}
const str = '[11, 22, [ 13, [24], 11], 23]';
const result = parseArray(str);
console.log(result);

排序 ​

插入排序 ​

每次将一个待排序的记录按照关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

js
function insertSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < nums[i - 1]) {
      let temp = nums[i];
      let j;
      for (j = i - 1; j >= 0 && nums[j] >= temp; j--) {
        nums[j + 1] = nums[j];
      }
      nums[j + 1] = temp;
    }
  }
  return nums;
}

const nums = [13, 38, 49, 27, 3];
const sortedNums = insertSort(nums);
console.log(sortedNums);
  • 空间复杂度：O(1)
  • 时间复杂度：
    • 最好：O(n) 数组本身就是有序的
    • 最坏：O(n2) 数组是逆序的
    • 平均：O(n2)
  • 稳定性：稳定

希尔排序 ​

思想：先追求表中元素部分有序，再逐渐逼近全局有序。

基于插入排序，当处理的数组本身就有序的时候，插入排序的时间复杂度最低。

希尔元素基于的思想就是数组本身基本有序。

TIP

先将待排序表分割成子表，对各个子表分别进行插入排序。再缩小增量 d（每次缩小一半），重复上述过程，直到 d = 1 为止。

js
function shellSort(nums) {
  const n = nums.length;
  for (let gap = Math.floor(n / 2); gap >= 1; gap = Math.floor(gap / 2)) {
    // 对每个间隔为 gap 的子序列进行插入排序
    for (let i = gap; i < n; i++) {
      if (nums[i] < nums[i - gap]) {
        let temp = nums[i];
        let j;
        for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
          nums[j + gap] = nums[j];
        }
        nums[j + gap] = temp;
      }
    }
  }
  return nums;
}
const nums = [13, 38, 49, 27, 3];
const sortedNums = shellSort(nums);
console.log(sortedNums);
  • 空间复杂度：O(1)
  • 时间复杂度：
    • 最坏：O(n2)
  • 稳定性：不稳定
  • 适用性：仅适用于顺序表，不适用于链表

冒泡排序 ​

如果想要最终得到一个升序的序列，冒泡排序的思想就是让最小的不断向前冒，或者让最大的不断向后冒。

js
function bubbleSort(nums) {
  const n = nums.length;
  for (let i = 0; i < n - 1; i++) {
    // 从后向前
    for (let j = n - 1; j > i; j--) {
      if (nums[j - 1] > nums[j]) {
        let temp = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = temp;
      }
    }
  }
  return nums;
}

const nums = [13, 38, 49, 27, 3];
const sortedNums = bubbleSort(nums);
console.log(sortedNums);

这里有一个优化的思路：如果一趟冒泡中没有进行交换，就代表当前数组是有序的了，就可以提前结束函数。

  • 空间复杂度：O(1)
  • 时间复杂度：
    • 最好：O(n) 数组本身就是有序的
    • 最坏：O(n2) 数组是逆序的
    • 平均：O(n2)
  • 稳定性：稳定

快速排序 ​

11.5   快速排序 - Hello 算法

快速排序的步骤和思路：

  1. 选择基准元素： • 从数组中选择一个元素作为基准元素（pivot）。通常选择第一个元素、最后一个元素或者随机选择。

  2. 分区操作： • 将数组重新排序，使得比基准元素小的元素都排在基准元素前面，比基准元素大的元素都排在基准元素后面。在分区过程结束后，基准元素处于最终位置。

  3. 递归排序： • 递归地对基准元素左边的子数组和右边的子数组进行快速排序。递归的结束条件是子数组的长度为1或0，此时数组已经有序。

js
/* 元素交换 */
function swap(nums, i, j) {
  let tmp = nums[i];
  nums[i] = nums[j];
  nums[j] = tmp;
}
// 快速排序
function quickSort(nums, low, high) {
  // 将 pivot 放在应该在的地方，将一个较长数组的排序问题简化为两个较短数组的排序问题。
  function getPosition(nums, low, high) {
    let pivot = nums[low];
    while (low < high) {
      while (low < high && nums[high] > pivot) { // 从右向左找首个小于基准数的元素
        high--;
      }
      while (low < high && nums[low] < pivot) { // 从左向右找首个大于基准数的元素
        low++;
      }
      swap(nums, low, high); // 交换这两个元素
    }
    return low; // 返回最新的基准数的索引
  }

  if (low >= high) return; // 递归结束的条件为子数组的长度为 1
  let pivotPosition = getPosition(nums, low, high);

  quickSort(nums, low, pivotPosition - 1);
  quickSort(nums, pivotPosition + 1, high);
}

let nums = [0, 3, 2, 8, 1, -5];
quickSort(nums, 0, nums.length - 1);
console.log(nums);
  • 时间复杂度：
    • 最好：O(nlogn) 每次选择的都是序列的中位数。
    • 最坏：O(n2) 每次选择的都是序列的最值。
    • 平均：O(nlogn) 。
  • 稳定性：不稳定。

堆排序 ​

堆排序是一种基于比较的排序算法，它利用堆这种数据结构来实现排序。堆是一种完全二叉树，可以分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值。

堆排序的步骤：

  1. 构建最大堆：将无序数组构建成最大堆。
  2. 排序：
    • 将堆顶元素（最大元素）与最后一个元素交换。
    • 然后减少堆的大小并重新调整堆，以保持最大堆的性质。
    • 重复上述步骤，直到堆的大小为 1。
javascript
function heapSort(array) {
    const n = array.length;

    // 构建最大堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(array, n, i);
    }

    // 一个一个提取元素
    for (let i = n - 1; i > 0; i--) {
        // 将当前根节点（最大值）与最后一个元素交换
        [array[0], array[i]] = [array[i], array[0]];
        
        // 重新调整堆
        heapify(array, i, 0);
    }

    return array;
}

// 堆调整函数
function heapify(array, n, i) {
    let largest = i; // 初始化最大值为根节点
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点

    // 如果左子节点比根节点大
    if (left < n && array[left] > array[largest]) {
        largest = left;
    }

    // 如果右子节点比当前最大值大
    if (right < n && array[right] > array[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点
    if (largest !== i) {
        [array[i], array[largest]] = [array[largest], array[i]]; // 交换

        // 递归调整影响的子树
        heapify(array, n, largest);
    }
}

// 示例用法
const arr = [3, 5, 1, 10, 2, 7];
console.log(heapSort(arr)); // 输出: [1, 2, 3, 5, 7, 10]

  1. 时间复杂度：

    • 构建最大堆：O(n)，因为堆的构建只需对每个非叶子节点执行一次 heapify，而每次 heapify 的时间复杂度为 O(log n)。
    • 排序：O(n log n)，因为每次提取最大值后都需要重新调整堆。

  2. 空间复杂度：O(1)，堆排序是原地排序，不需要额外的存储空间。

  3. 稳定性：堆排序是不稳定的。由于在排序过程中元素可能被移动到不同的位置，所以可能会改变相同元素的相对顺序。

堆排序的优点在于它的时间复杂度是 O(n log n)，并且不需要额外的空间，但由于它的不稳定性和较高的常数因子，实际应用中不如快速排序和归并排序常见。

合并区间 ​

可以通过以下步骤在 JavaScript 中实现 LeetCode 第 56 题“合并区间”：

  1. 排序区间：首先根据每个区间的起始值进行排序。
  2. 合并区间：遍历排序后的区间，检查当前区间是否与上一个区间重叠，如果重叠，则合并。
js
function merge(intervals) {
    if (intervals.length === 0) return [];

    // 按照起始值排序
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const lastMerged = merged[merged.length - 1];

        // 检查是否重叠
        if (current[0] <= lastMerged[1]) {
            // 合并
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // 不重叠，直接添加
            merged.push(current);
        }
    }

    return merged;
}

console.log(
  merge([
    [3, 6],
    [-3, -1],
    [-2, 1],
  ])
);

双指针 ​

删除有序数组中的重复项 ​

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

js
function removeDup(nums) {
  if (nums.length === 0) return 0;
  // 双指针
  let i = 0,
    j = 1;
  while (j < nums.length) {
    if (nums[i] !== nums[j]) {
      nums[i + 1] = nums[j];
      i++;
    }
    j++;
  }
  return i + 1;
}
console.log(removeDup([1, 2, 2, 2, 3, 6]));

打印所有回文子串 ​

中心扩展法：

js
function palindrome(s) {
  const res = new Set();

  for (let i = 0; i < s.length; i++) {
    let left = i - 1;
    let right = i + 1;
    while (left >= 0 && right <= s.length && s[left] === s[right]) {
      res.add(s.slice(left, right + 1));
      left--;
      right++;
    }
  }
  return res;
}

console.log(palindrome('abacdfdcaba')); //  {'aba', 'dfd', 'cdfdc', 'acdfdca', 'bacdfdcab', …}

在字符串前添加前缀使其变为回文串 ​

js
function shortestPalindrome(s) {
  const reversed = s.split('').reverse().join('');
  const combined = s + '#' + reversed; // 使用特殊字符避免重叠
  const lps = computeLPSArray(combined); // 计算LPS数组

  const prefixLength = lps[lps.length - 1]; // 获取最长回文后缀长度
  const suffixToAdd = reversed.slice(0, s.length - prefixLength); // 获取需要添加的后缀

  return suffixToAdd + s; // 返回添加后的结果
}

// 计算LPS数组（部分匹配表）
function computeLPSArray(str) {
  const lps = Array(str.length).fill(0);
  let len = 0; // 长度
  let i = 1;

  while (i < str.length) {
    if (str[i] === str[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1]; // 回溯
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

// 示例
const result = shortestPalindrome('acecaaa');
console.log(result); // 输出: "aaacecaaa"

字符串压缩 ​

js
var compressString = function(S) {
    if (S.length < 2) {
        return S
    }
    let res = ''
    let i = 0
    while (i < S.length) {
        let j = i + 1
        let num = 1
        while (j < S.length) {
            if (S[i] === S[j]) {
                j++
                num++
            } else {
                break
            }
        }
        res += `${S[i]}${num}`
        i += j - i
    }
    return S.length > res.length ? res : S
};

压缩字符串展开 ​

js
var decompressString = function(S) {
    let res = '';
    let i = 0;

    while (i < S.length) {
        let char = S[i];
        i++;

        // 提取数字部分，可能是多位数字
        let num = '';
        while (i < S.length && !isNaN(S[i])) {
            num += S[i];
            i++;
        }

        // 将字符重复 num 次
        res += char.repeat(parseInt(num));
    }

    return res;
};

// 示例用法：
console.log(decompressString("a2b3c1"));  // 输出: aabbbc

合并两个有序数组 ​

js
function mergeSortedArrays(arr1, arr2) {
    let merged = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            merged.push(arr1[i]);
            i++;
        } else {
            merged.push(arr2[j]);
            j++;
        }
    }

    // 将剩余的元素添加到结果中
    while (i < arr1.length) {
        merged.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        merged.push(arr2[j]);
        j++;
    }

    return merged;
}

// 示例
const arr1 = [1, 3, 5];
const arr2 = [2, 4, 6];
const result = mergeSortedArrays(arr1, arr2);
console.log(result); // 输出: [1, 2, 3, 4, 5, 6]

三数之和 ​

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

思路：

  1. 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
  2. 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
  3. 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
  4. 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
  5. 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
  6. 时间复杂度：O(n^2 )，n 为数组长度
js
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

接雨水 ​

暴力解法：

js
var trap = function(height) {
    let res = 0;
    // 按照列进行计算
    for(let i = 1; i < height.length - 1; i++){
        const leftMax = Math.max(...height.slice(0,i));
        const rightMax = Math.max(...height.slice(i + 1, height.length));
        let h = Math.min(leftMax, rightMax) - height[i];
        if(h > 0) res += h;
    }
    return res;
};

优化：

js
var trap = function(height) {
    // 以空间换时间，提前建立两个数组保存[0,i]的最大值和[i,len]右侧最大值
    const len = height.length;
    const maxLeft = new Array(len).fill(0);
    maxLeft[0] = height[0];
    for(let i = 1; i < len; i++){
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
    }
    const maxRight = new Array(len).fill(0);
    maxRight[len - 1] = height[len - 1];
    for(let i = len - 2; i >= 0; i--){
        maxRight[i] = Math.max(maxRight[i + 1], height[i]);
    }
    let sum = 0;
    for(let i = 1; i < len; i++){
        let h = Math.min(maxLeft[i], maxRight[i]) - height[i];
        if(h > 0) sum += h;
    }
    return sum;
};

无重复字符最长字串 ​

复杂度较高的方法：

js
var lengthOfLongestSubstring = function(s) {
    if(!s) return 0;
    const res = [];
    for(let i = 0; i < s.length; i++){
        let hashSet = new Set();
        let j;
        for(j = i; j < s.length; j++){
            if(hashSet.has(s[j])){
                break;
            }
            hashSet.add(s[j]);
        }
        res.push(s.slice(i, j));
    }
    return Math.max(...res.map(item=>item.length));
};
js
var lengthOfLongestSubstring = function(s) {
    if(!s) return 0;
    // 双指针 滑动窗口 右边界不断变化
    // 有重复字母时，调整左边界
    // 从而保证窗口内字母都是唯一的
    const charMap = new Map();
    let longestLen = 1;
    let start = 0;
    for(let end = 0; end < s.length; end++){
        const char = s[end];

        if(charMap.has(char)){
            start = Math.max(charMap.get(char) + 1, start); 
        }
        charMap.set(char, end);
        longestLen = Math.max(longestLen, end - start + 1);
    }
    return longestLen;
};

删除最短子数组使剩余数组有序 ​

js
var findLengthOfShortestSubarray = function(arr) {
    let n = arr.length, j = n - 1;

    // 找到右边界 j，确保 arr[j-1] <= arr[j]
    while (j > 0 && arr[j - 1] <= arr[j]) {
        j--;
    }
    
    // 如果数组已经有序
    if (j === 0) {
        return 0;
    }

    let res = j; // 最短子数组的初始长度
    for (let i = 0; i < n; i++) {
        // 找到 j，使得 arr[j] >= arr[i]
        while (j < n && arr[j] < arr[i]) {
            j++;
        }
        // 更新最短子数组长度
        res = Math.min(res, j - i - 1);

        // 如果下一个元素比当前元素小，说明不需要再检查
        if (i + 1 < n && arr[i] > arr[i + 1]) {
            break;
        }
    }
    
    return res;
};

// 示例用法
console.log(findLengthOfShortestSubarray([2, 6, 4, 8, 10, 9, 15])); // 输出: 5
console.log(findLengthOfShortestSubarray([1, 2, 3, 4]));            // 输出: 0

字符串中所有字母异位词 ​

js
var findAnagrams = function (s, p) {
  // 滑动窗口
  if (p.length > s.length) return [];
  const map = new Map();
  let res = [];
  // 初始化 map
  for (let item of p) {
    map.set(item, (map.get(item) || 0) - 1);
  }
  // 左指针对应的 map 减，右指针对应的 map 加
  // 初始化右指针的位置，相应地改变 map
  let r = 0;
  for (; r < p.length; r++) {
    if (map.has(s[r])) {
      map.set(s[r], map.get(s[r]) + 1);
    }
  }
  console.log(map);
  // 同时移动左右指针
  for (let l = 0; r <= s.length; l++, r++) {
    if ([...map.values()].every((v) => v === 0)) {
      res.push(l);
    }
    if (map.has(s[l])) {
      map.set(s[l], map.get(s[l]) - 1);
    }
    if (map.has(s[r])) {
      map.set(s[r], map.get(s[r]) + 1);
    }
  }
  return res;
};

二分 ​

二分查找 ​

js
var search = function (nums, target) {
    // 有序数组
    let right = nums.length - 1;
    let left = 0;

    while(right >= left){
        let mid = Math.ceil((right+left)/2);
        if(nums[mid] === target) return mid;
        if(nums[mid] > target){
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        // console.log(left, right);
    }
    return -1;
};

二维数组的二分查找 ​

js
function searchIn2DArray(array, X) {
    // 遍历每一行
    for (let i = 0; i < array.length; i++) {
        const row = array[i];
        const left = 0;
        const right = row.length - 1;

        // 使用二分查找
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (row[mid] === X) {
                return [i, mid]; // 找到目标值，返回下标
            } else if (row[mid] < X) {
                left = mid + 1; // 在右半部分继续查找
            } else {
                right = mid - 1; // 在左半部分继续查找
            }
        }
    }

    return [-1, -1]; // 如果未找到，返回 [-1, -1]
}

// 示例用法
const array = [[1, 3, 5, 6], [7, 8, 9], [10, 14]];
console.log(searchIn2DArray(array, 9)); // 输出: [1, 2]
console.log(searchIn2DArray(array, 11)); // 输出: [-1, -1]

二叉树 ​

和为目标值的路径 ​

js

var pathSum = function (root, target) {
  let res = [];
  const backtrack = (root, path, sum) => {
    if (root == null) return null;
    path.push(root.val);
    // 路径中加入当前节点的值
    sum += root.val;
    // 到了叶子节点 并且 整个路径的值的和 和target相等，则推入结果集中
    if (root.left == null && root.right == null && target == sum)
      res.push(path.slice());
    // 递归的去左右子树当中查找路径
    backtrack(root.left, path, sum);
    backtrack(root.right, path, sum);
    sum -= root.val;
    path.pop();
  };
  backtrack(root, [], 0);
  return res;
};

前序遍历 - 递归 ​

js
// 树节点的定义
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 前序遍历递归实现
function dfsPreorder(root) {
  if (!root) return; // 如果根节点为空，则直接返回

  console.log(root.val); // 访问当前节点的值
  dfsPreorder(root.left); // 递归遍历左子树
  dfsPreorder(root.right); // 递归遍历右子树
}

// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log("DFS 前序遍历结果：");
dfsPreorder(root);

二进制二叉树 ​

js
function calculateDecimal(node, currentNumber = "") {
    if (!node) return 0; // 如果节点为空，返回0

    // 更新当前的二进制数
    currentNumber += node.value.toString();

    // 如果是叶子节点，将二进制数转换为十进制数
    if (!node.left && !node.right) {
        return parseInt(currentNumber, 2);
    }

    // 继续遍历左右子树
    return calculateDecimal(node.left, currentNumber) + calculateDecimal(node.right, currentNumber);
}

// 计算整棵树所有叶子节点值的和
let totalDecimal = calculateDecimal(root);
console.log(totalDecimal); // 输出计算得到的十进制数

层序遍历 - 队列 ​

js
// 层序遍历实现
function bfsLevelOrder(root) {
  if (!root) return; // 如果根节点为空，则直接返回

  const queue = [root]; // 使用队列来存储每一层的节点

  while (queue.length > 0) {
    const node = queue.shift(); // 出队列
    console.log(node.val); // 访问当前节点的值

    if (node.left) {
      queue.push(node.left); // 左子节点入队列
    }
    if (node.right) {
      queue.push(node.right); // 右子节点入队列
    }
  }
}

// 示例用法（使用前面定义的树结构）
console.log("BFS 层序遍历结果：");
bfsLevelOrder(root);

二叉树最大层宽 ​

js
function maxWidthOfBinaryTree(root) {
    if (!root) return 0;

    let maxWidth = 0;
    const queue = [{ node: root, index: 0 }]; // 保存节点和其在层中的索引

    while (queue.length > 0) {
        const length = queue.length;
        const startIndex  = queue[0].index; // 当前层的起始索引
        let lastIndex = startIndex; // 当前层的结束索引

        for (let i = 0; i < length; i++) {
            const { node, index } = queue.shift();
            lastIndex = index; // 更新结束索引

            if (node.left) {
                queue.push({ node: node.left, index: 2 * index }); // 左子节点
            }
            if (node.right) {
                queue.push({ node: node.right, index: 2 * index + 1 }); // 右子节点
            }
        }

        // 当前层的宽度是结束索引减去起始索引加一
        maxWidth = Math.max(maxWidth, lastIndex - startIndex + 1);
    }

    return maxWidth;
}

// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

console.log(maxWidthOfBinaryTree(root)); // 输出最大宽度

二叉树的最近公共祖先 ​

js
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) {
    return root; // 当前节点是公共祖先
  }
  return left ? left : right; // 返回非空的子节点
}

// 示例用法
const root = new TreeNode(3);
const node5 = new TreeNode(5);
const node1 = new TreeNode(1);
root.left = node5;
root.right = node1;
const node6 = new TreeNode(6);
const node2 = new TreeNode(2);
node5.left = node6;
node5.right = node2;
const node0 = new TreeNode(0);
const node8 = new TreeNode(8);
node1.left = node0;
node1.right = node8;

const lca = lowestCommonAncestor(root, node5, node1);
console.log(lca.value); // 输出 3

BST 实现二叉搜索树 ​

js
class TreeNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

    // 插入一个新的 key
    insert(key) {
        const newNode = new TreeNode(key);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this._insertNode(this.root, newNode);
        }
    }

    _insertNode(node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this._insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this._insertNode(node.right, newNode);
            }
        }
    }

    // 搜索一个 key
    search(key) {
        return this._searchNode(this.root, key);
    }

    _searchNode(node, key) {
        if (node === null) return false;
        if (key < node.key) return this._searchNode(node.left, key);
        if (key > node.key) return this._searchNode(node.right, key);
        return true; // key === node.key
    }

    // 删除一个 key
    delete(key) {
        this.root = this._deleteNode(this.root, key);
    }

    _deleteNode(node, key) {
        if (node === null) return null;

        if (key < node.key) {
            node.left = this._deleteNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = this._deleteNode(node.right, key);
            return node;
        } else {
            // key === node.key
            // 节点无子节点或只有一个子节点
            if (node.left === null) return node.right;
            if (node.right === null) return node.left;

            // 节点有两个子节点，找到右子树的最小节点
            const minNode = this._findMinNode(node.right);
            node.key = minNode.key;
            node.right = this._deleteNode(node.right, minNode.key);
            return node;
        }
    }

    _findMinNode(node) {
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    }

    // 中序遍历
    inorder() {
        this._inorderNode(this.root);
        console.log('');
    }

    _inorderNode(node) {
        if (node !== null) {
            this._inorderNode(node.left);
            process.stdout.write(`${node.key} `);
            this._inorderNode(node.right);
        }
    }
}

// 使用示例
const bst = new BST();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);

console.log("Inorder traversal of the BST:");
bst.inorder();

console.log("Search for key 40:");
console.log(bst.search(40) ? "Found" : "Not Found");

console.log("Delete key 20:");
bst.delete(20);
bst.inorder();

console.log("Delete key 30:");
bst.delete(30);
bst.inorder();

console.log("Delete key 50:");
bst.delete(50);
bst.inorder();

实现前缀树 ​

js
class TrieNode {
    constructor() {
        this.children = {}; // 存储子节点
        this.isEndOfWord = false; // 标记这个节点是否是一个单词的结束
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // 插入一个单词到前缀树
    insert(word) {
        let currentNode = this.root;
        for (let i = 0; i < word.length; i++) {
            const char = word[i];
            if (!currentNode.children[char]) {
                currentNode.children[char] = new TrieNode();
            }
            currentNode = currentNode.children[char];
        }
        currentNode.isEndOfWord = true;
    }

    // 检查单词是否在前缀树中
    search(word) {
        let currentNode = this.root;
        for (let i = 0; i < word.length; i++) {
            const char = word[i];
            if (!currentNode.children[char]) {
                return false;
            }
            currentNode = currentNode.children[char];
        }
        return currentNode.isEndOfWord;
    }

    // 检查是否有任何单词以给定前缀开始
    startsWith(prefix) {
        let currentNode = this.root;
        for (let i = 0; i < prefix.length; i++) {
            const char = prefix[i];
            if (!currentNode.children[char]) {
                return false;
            }
            currentNode = currentNode.children[char];
        }
        return true;
    }
}

链表 ​

反转链表 ​

js
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}
 
let temp = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode)));
js
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}
 
let head = new ListNode(1, new ListNode(2, new ListNode(3)));
 
 
let reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;  // 如果链表只有一个元素或者是空链表，我们直接返回
    }
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
 
reverseList(head);

k 个一组反转链表 ​

js
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseKGroup(head, k) {
    let count = 0;
    let current = head;

    // 计算链表长度
    while (current && count < k) {
        current = current.next;
        count++;
    }

    // 如果长度不足 k，则不反转
    if (count < k) return head;

    // 反转 k 个节点
    let prev = null;
    current = head;
    for (let i = 0; i < k; i++) {
        const nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    // 递归反转剩下的部分
    if (current) {
        head.next = reverseKGroup(current, k);
    }

    // 返回新的头节点
    return prev;
}

// 示例使用
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const k = 2;
const newHead = reverseKGroup(head, k);

链表判断环 ​

遍历链表中的每个节点，并将保存到set，如果下次遇到了遍历过的节点，说明链表中存在环，此时的节点为入环节点。时间复杂度O(n) 空间复杂度O(n)

js
function hasCycle(head) {
    const visited = new Set();
    while (head !== null) {
        if (visited.has(head)) {
            return true;
        } else {
            visited.add(head);
            head = head.next;
        }
    }
    return false;
}

一个走两步，一个走一步，如果链表中有环，必会相遇。

js
function hasCycle(head) {
    let one=head;
    let two=head;
    while(two!=null&&two.next!=null){
        one=one.next;
        two=two.next.next;
        if(one===two){
            return true;
        }
    }
    return false;
}

倒数第 k 个节点 ​

js
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function getKthFromEnd(head, k) {
    let fast = head;
    let slow = head;

    // 移动 fast 指针 k 步
    for (let i = 0; i < k; i++) {
        if (fast) {
            fast = fast.next;
        } else {
            return null; // 如果 k 超过链表长度
        }
    }

    // 同时移动 fast 和 slow
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow; // slow 指向倒数第 k 个节点
}

// 示例用法
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const k = 2;
const result = getKthFromEnd(head, k);
console.log(result ? result.val : null); // 输出: 4

链表相加 ​

要实现两个链表的相加，通常情况下我们会将链表视为数字的逆序表示。即链表的每个节点表示一个数字的位，最低位在链表头部。相加的思路与竖式加法相似。

  1. 创建一个新的链表来存储结果。
  2. 使用一个指针遍历两个链表，同时维护一个进位（carry）。
  3. 对每一位进行相加，将结果的个位存入新链表，并更新进位。
  4. 遍历结束后，检查是否还有进位需要添加。
js
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function addTwoNumbers(l1, l2) {
    let dummyHead = new ListNode(0); // 创建一个虚拟头节点
    let current = dummyHead; // 指向结果链表的当前节点
    let carry = 0; // 进位初始化为 0

    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0; // l1 当前节点的值
        const val2 = l2 ? l2.val : 0; // l2 当前节点的值

        // 计算当前位的和
        const sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10); // 更新进位
        current.next = new ListNode(sum % 10); // 创建新节点并连接到结果链表

        // 移动到下一个节点
        current = current.next;
        if (l1) l1 = l1.next; // 移动 l1
        if (l2) l2 = l2.next; // 移动 l2
    }

    return dummyHead.next; // 返回结果链表（去掉虚拟头节点）
}

// 示例用法
const l1 = new ListNode(2, new ListNode(4, new ListNode(3))); // 342
const l2 = new ListNode(5, new ListNode(6, new ListNode(4))); // 465
const result = addTwoNumbers(l1, l2); // 807

// 打印结果链表
let current = result;
while (current) {
    console.log(current.val); // 输出: 7 -> 0 -> 8
    current = current.next;
}

栈 ​

括号匹配 ​

js
// 括号匹配算法
function isValid(str){
    let strArr = str.split(''),
        left = [];// 空栈
    for(let i=0;i<strArr.length;i++){
        if(strArr[i] == '(' || strArr[i] == '[' || strArr[i] == '{'){
            left.push(strArr[i]) //左括号入栈
        }else{
            if(strArr[i] == ')' && left.pop() != '('){
                return false //结束循环
            }
            if(strArr[i] == ']' && left.pop() != '['){
                return false 
            }
            if(strArr[i] == '}' && left.pop() != '{'){
                return false
            }
        }
    }
    return left.length == 0
}

let test = '{9()32358}'
console.log(isValid(test))

最少删除多少个字符使括号匹配 ​

js
function minDeletionsToMatchBrackets(s) {
  let stack = [];
  let deletions = 0;

  for (let char of s) {
    if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      if (stack.length > 0) {
        stack.pop(); // 找到匹配的左括号
      } else {
        deletions++; // 右括号没有匹配，计数删除
      }
    }
  }

  // 剩下的左括号也需要删除
  deletions += stack.length;

  return deletions;
}

// 示例
console.log(minDeletionsToMatchBrackets('(()))(((')); // 输出 4

实现计算器 ​

思路：

  1. 输入解析：将输入的字符串表达式分解为一个个独立的 token，包括数字、运算符、括号等。
    1. 遍历输入字符串。
    2. 遇到数字的时候累积成为一个完整的值。
    3. 遇到运算符或括号时将其单独存储。
    4. 跳过无用的字符，如空格。
  2. 转换为可计算的结构，如逆波兰表达式（后缀表达式）。
  3. 基于逆波兰表达式执行计算。
js
function calculate(expression) {
  // 定义运算符优先级
  const priority = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
  };
  // 判断是否为数字
  function isNumber(char) {
    return /\d/.test(char);
  }

  // 将中缀表达式转换为后缀表达式
  function infixToPostfix(expression) {
    const output = []; // 输出队列
    const operators = []; // 运算符栈
    let number = ''; // 累积数字

    for (let char of expression) {
      if (char === ' ') continue;

      if (isNumber(char)) {
        number += char;
      } else {
        if (number) {
          output.push(parseInt(number));
          number = '';
        }
        if (char === '(') {
          operators.push(char); // 左括号直接入栈
        } else if (char === ')') {
          // 右括号，弹出运算符直到遇到左括号
          while (operators.length && operators[operators.length - 1] !== '(') {
            output.push(operators.pop());
          }
          operators.pop(); // 弹出左括号
        } else if (priority[char]) {
          // 处理运算符，弹出优先级大于等于当前运算符的所有运算符
          while (
            operators.length &&
            priority[operators[operators.length - 1]] >= priority[char]
          ) {
            output.push(operators.pop());
          }
          operators.push(char); // 当前运算符
        }
      }
    }

    // 处理最后的数字
    if (number) output.push(parseInt(number));
    // 弹出剩余所有运算符
    while (operators.length) output.push(operators.pop());
    console.log(output);
    return output;
  }

  // 计算后缀表达式
  function calPostFix(postfix) {
    const stack = [];
    for (let token of postfix) {
      if (typeof token === 'number') {
        stack.push(token);
      } else {
        const right = stack.pop();
        const left = stack.pop();
        let result;
        if (token === '+') {
          result = left + right;
        } else if (token === '-') {
          result = left - right;
        } else if (token === '*') {
          result = left * right;
        } else if (token === '/') {
          result = Math.floor(left / right);
        }
        stack.push(result);
      }
    }
    console.log(stack);
    return stack.pop();
  }
  const postfix = infixToPostfix(expression);
  return calPostFix(postfix);
}

// 示例用法
const expression = '3 + 5 * (2 - 8 / 4)';
const result = calculate(expression);
console.log(result);

动态规划 ​

最小编辑距离 ​

给定两个字符串 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作数。 你可以对字符串执行以下三种操作之一：

  1. 插入一个字符。
  2. 删除一个字符。
  3. 替换一个字符。
bash
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (替换 'h' 为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

定义状态：dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需要的最少操作数。

状态转移公式，分两种情况讨论：

  1. 当字符相等：word1[i-1] === word2[j-1]，无需额外操作，继承前一个状态
dp[i][j]=dp[i−1]dp[j−1]
  1. 当字符不相等（word1[i-1] != word2[j-1]）：需要选择替换、删除或插入之一，取最小值加 1：
dp[i][j]=min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1

边界条件：

  • 当 i = 0（word1 为空时）：需要插入所有 word2 的字符，dp[0][j] = j。
  • 当 j = 0（word2 为空时）：需要删除所有 word1 的字符，dp[i][0] = i。
js
var minDistance = function(word1, word2) {
    const len1 = word1.length;
    const len2 = word2.length;
    const dp = Array.from(Array(len1 + 1), () => Array(len2 + 1))
    dp[0][0] = 0

    for (let i = 1; i <= len1; i++) dp[i][0] = dp[i - 1][0] + 1

    for (let i = 1; i <= len2; i++) dp[0][i] = dp[0][i - 1] + 1

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1]
            else
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j-1]) + 1
        }
    }

    return dp[len1][len2]
};

跳跃游戏4 ​

给定一个整数数组 nums 和一个整数 k，你从数组的第一个下标开始，目标是到达最后一个下标。每次跳跃时，你可以向前跳到 i + 1, i + 2, ..., i + k 中的任意一个下标。你需要找到到达最后一个下标时的路径得分最大值。

路径得分的定义是：你跳跃经过的所有下标 nums[i] 的值的总和。

  1. 定义状态：dp[i] 表示从起点到达下标 i 的最大得分。
  2. 状态转移方程：到达下标 i 时，我们可以从 i-1, i-2, ..., i-k 中的任意一个位置跳过来，因此：
dp[i]=max(dp[j])+nums[i](j∈[i−k,i−1])

即：从范围 [i-k, i-1] 内的最大 dp[j] 加上 nums[i]。

  1. 优化思路：直接遍历 [i-k, i-1] 求最大值的时间复杂度是 O(k)，整体复杂度为$$ O(n \cdot k)$$为优化时间复杂度，我们使用单调队列维护滑动窗口内的最大值。

单调队列的核心逻辑:

  • 队列中存储的是数组下标，且保证队列中的 dp 值单调递减。
  • 每次计算 dp[i] 时，队首元素就是窗口 [i-k, i-1] 中的最大值的下标。
  • 为保持窗口大小，当队首元素超出窗口范围时，移出队首。
  • 当加入新的元素时，为保持单调性，移除队列中所有比当前 dp[i] 小的元素。
js
function maxResult(nums: number[], k: number): number {
  const dp: number[] = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  const queue: number[] = [0];
  for (let i = 1; i < nums.length; i++) {
      // 排除区间之外的点
    while(queue.length && queue[0] < Math.max(i - k, 0)) queue.shift();
    dp[i] = dp[queue[0]] + nums[i];
        // 维护队列单调性
    while(queue.length && dp[queue[queue.length - 1]] < dp[i]) queue.pop();
    queue.push(i);
  }
  return dp[nums.length - 1];
};

最大连续子数组和 ​

js
function contMax(array) {
	if (array.length == 0)
		return 0
	var sum = array[0] //保存每组的和
	var maxSum = array[0] //连续子数组最大和
	for (var i = 1; i < array.length; i++) {
		sum = Math.max(sum + array[i], array[i]);
		maxSum = Math.max(sum, maxSum)
	}
	return maxSum
}

console.log(contMax([1, -3, 9, 10, -2, 3, -6, 5])) //20

打家劫舍 ​

在这个问题中，给定一个数组，表示每个房屋中的金额，不能抢劫相邻的房屋，目标是最大化抢劫的金额。

js
function rob(nums) {
    const n = nums.length;
    if (n === 0) return 0; // 如果没有房屋，返回 0
    if (n === 1) return nums[0]; // 只有一个房屋，返回该房屋的金额

    let dp = new Array(n); // 创建一个动态规划数组
    dp[0] = nums[0]; // 第一个房屋的最大金额就是其金额
    dp[1] = Math.max(nums[0], nums[1]); // 前两个房屋的最大金额是两个中较大的

    for (let i = 2; i < n; i++) {
        // dp[i] 为第 i 个房屋的最大金额
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[n - 1]; // 返回最后一个房屋的最大金额
}

// 示例用法
const houses = [2, 7, 9, 3, 1];
const maxAmount = rob(houses);
console.log(maxAmount); // 输出 12

分割等和子集 ​

[[分割数组为和相等的两个子集]]

ts
function canPartition(nums: number[]): boolean {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);

    if (totalSum % 2 !== 0) return false;

    const target = totalSum / 2;

    const dp = Array(target + 1).fill(false);
    dp[0] = true;
    
    for(let num of nums) {
        for(let j = target; j>=num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

零钱兑换 ​

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

  • 输入：coins = [1, 2, 5], amount = 11
  • 输出：3
  • 解释：11 = 5 + 5 + 1

解答：

  1. 定义状态：dp[i] 表示组成金额 i 所需的最少硬币数。

  2. 状态转移方程：对于每一种硬币 coin： • 如果我们选择了 coin，则：

dp[i]=min(dp[i],dp[i−coin]+1)

即：当前金额 i 的最优解是之前的最优解和选择当前硬币后的最优解的较小值。

  1. 初始化 • dp[0] = 0：组成金额 0 需要 0 枚硬币。 • dp[i] = Infinity（默认值）：表示初始时金额 i 无法被组成。
  2. 返回结果 • 如果 dp[amount] === Infinity，说明无法组成金额，返回 -1。 • 否则返回 dp[amount]，即所需的最少硬币数。
js
function coinChange(coins: number[], amount: number): number {
    if (amount === 0) return 0;
    if (coins.length === 0) return -1;

    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};

回溯 ​

回溯模板：

js
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

全排列 ​

js
function permute(nums){
    let res = []; // 保存结果
    let path = []; //当前所在位置的路径
    let used = [];//记录当前这条路径下第 i 位的数字是否被使用过
    backTracking(nums, [])
    return res;
    function backTracking(nums: number[], used){
        // 结束递归的条件
        if(path.length === nums.length){
            res.push(Array.from(path));
            return;
        }
        for(let i = 0; i < nums.length; i++){
            if(used[i]){
                continue;
            }
            path.push(nums[i]);
            used[i] = true;
            backTracking(nums, used);
            path.pop();
            used[i] = false;

        }
    }
}
console.log(permute([1,2,3]));

生成所有有效的括号组合 ​

js
function generateParentheses(n) {
  const result = []; 

  // 回溯函数
  function backtrack(current, open, close) {
    // 如果当前组合的长度等于 n*2，说明生成了一个有效组合
    if (current.length === n * 2) {
      result.push(current); // 将有效组合加入结果数组
      return;
    }
    // 如果当前开放的括号数量小于 n，继续添加左括号
    if (open < n) {
      backtrack(current + '(', open + 1, close); // 递归调用，增加左括号
    }
    // 如果当前关闭的括号数量小于开放的数量，继续添加右括号
    if (close < open) {
      backtrack(current + ')', open, close + 1); // 递归调用，增加右括号
    }
  }

  // 初始化回溯，当前组合为空，开放和关闭括号数量为 0
  backtrack('', 0, 0);
  return result; // 返回所有有效的括号组合
}

const output = generateParentheses(2);
console.log(output); // [ '()()', '(())' ]

分割有效 ip ​

js
function isValid(segment) {
  // 检查是否是有效的 IP 段
  if (segment.length === 0 || segment.length > 3) return false;
  if (segment[0] === '0' && segment.length > 1) return false; // 前导零
  return Number(segment) >= 0 && Number(segment) <= 255;
}

function backtrack(start, path, result, s) {
  // 如果已经分割了 4 段，并且到达字符串末尾
  if (path.length === 4 && start === s.length) {
    result.push(path.join('.'));
    return;
  }
  
  // 生成每一段 IP
  for (let i = 1; i <= 3; i++) {
    const segment = s.substring(start, start + i);
    if (start + i <= s.length && isValid(segment)) {
      path.push(segment); // 添加当前段
      backtrack(start + i, path, result, s); // 继续分割
      path.pop(); // 回溯
    }
  }
}

function restoreIpAddresses(s) {
  const result = [];
  backtrack(0, [], result, s);
  return result;
}

// 示例用法
console.log(restoreIpAddresses("25525511135")); // 输出: ["255.255.11.135", "255.255.111.35"]

贪心 ​

跳跃游戏 ​

js
function canJump(nums) {
  let maxReachable = 0; // 记录当前能到达的最远位置

  for (let i = 0; i < nums.length; i++) {
    // 如果当前位置超过了最远可达位置，返回 false
    if (i > maxReachable) {
      return false;
    }

    // 更新最远可达位置
    maxReachable = Math.max(maxReachable, i + nums[i]);

    // 如果已经可以到达最后一个位置，返回 true
    if (maxReachable >= nums.length - 1) {
      return true;
    }
  }

  return false; // 如果循环结束，说明不能到达最后一个位置
}

// 示例用法
console.log(canJump([2, 3, 1, 1, 4])); // 输出: true
console.log(canJump([3, 2, 1, 0, 4])); // 输出: false
  1. 最大可达位置：使用 maxReachable 变量记录当前能到达的最远位置。
  2. 遍历数组：循环遍历数组的每个位置，如果当前位置超过了 maxReachable，则返回 false，说明无法到达该位置。
  3. 更新最远位置：在每个位置更新 maxReachable，即当前位置加上能跳跃的最大步数。
  4. 判断终点：如果 maxReachable 达到或超过数组的最后一个位置，返回 true。

这种贪心算法的时间复杂度为 O(n)，空间复杂度为 O(1)，适用于处理跳跃游戏问题。

和为 k 的 fib 的最少数目 ​

要找到和为 ( k ) 的斐波那契数字的最少数量，可以使用贪心算法。斐波那契数列的性质使得我们可以从最大的斐波那契数开始，逐步减去，直到达到 ( k )。以下是一个示例实现：

javascript
function fibonacciNumbers(n) {
    const fibs = [1, 2]; // 从1和2开始，因为我们用的是非零正整数
    let a = 1, b = 2;
    while (b <= n) {
        const next = a + b;
        fibs.push(next);
        a = b;
        b = next;
    }
    return fibs;
}

function minFibonacciNumbers(k) {
    const fibs = fibonacciNumbers(k);
    let count = 0;

    for (let i = fibs.length - 1; i >= 0; i--) {
        while (k >= fibs[i]) {
            k -= fibs[i];
            count++;
        }
        if (k === 0) break;
    }

    return count;
}

const k = 7; // 你可以替换成任意想要的值
console.log(minFibonacciNumbers(k));

这个代码段首先生成所有小于或等于 ( k ) 的斐波那契数，然后从最大的斐波那契数开始，尽可能多地减去这些数，直到 ( k ) 减至 0，最后返回所需的数目。你可以替换 k 的值来计算不同的和。

买卖股票1 ​

要实现“买卖股票的最佳时机 I”的问题，通常需要找到在给定的价格数组中，能够获得的最大利润。可以通过遍历价格数组来解决这个问题，计算在每个时刻卖出的利润。

题目描述:

给定一个数组 prices，其中 prices[i] 是第 i 天的股票价格。你只能进行一次买入和一次卖出，返回可以获得的最大利润。如果无法获利，返回 0。

javascript
function maxProfit(prices) {
    let minPrice = Infinity; // 初始化最低价格为无穷大
    let maxProfit = 0; // 初始化最大利润为 0

    for (let price of prices) {
        if (price < minPrice) {
            minPrice = price; // 更新最低价格
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice; // 更新最大利润
        }
    }

    return maxProfit;
}

// 示例用法
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // 输出: 5 (在第 2 天买入， 第 5 天卖出)

  1. 初始化:

    • minPrice 用于存储当前最低价格，初始设为无穷大。
    • maxProfit 用于存储当前最大利润，初始设为 0。

  2. 遍历价格:

    • 对于每一天的价格，检查是否小于当前 minPrice，如果是，则更新 minPrice。
    • 否则，计算当前价格与 minPrice 之间的利润，并更新 maxProfit。

  3. 返回结果:

    • 最终返回 maxProfit，表示可以获得的最大利润。

买卖股票2 ​

js
function maxProfit(prices) {
    let totalProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        // 如果今天的价格比昨天的价格高，进行交易
        if (prices[i] > prices[i - 1]) {
            totalProfit += prices[i] - prices[i - 1]; // 累加利润
        }
    }

    return totalProfit;
}

// 示例用法
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // 输出: 7 (买入 1 卖出 5, 买入 3 卖出 6)

图 ​

js
function hasCycle(graph) {
  const visited = new Set();
  const stack = new Set();

  function dfs(node) {
    if (stack.has(node)) {
      return true; // 检测到循环
    }
    if (visited.has(node)) {
      return false; // 已访问过，不再检查
    }

    visited.add(node);
    stack.add(node);

    for (const neighbor of graph[node] || []) {
      if (dfs(neighbor)) {
        return true;
      }
    }

    stack.delete(node); // 回溯
    return false;
  }

  for (const node in graph) {
    if (dfs(node)) {
      return true; // 找到循环
    }
  }

  return false; // 没有循环
}

// 示例图：A -> B, B -> C, C -> A
const graph = {
  A: ['B'],
  B: ['C'],
  C: ['A']
};

console.log(hasCycle(graph)); // 输出: true
  • 图的表示：图用一个对象表示，键是节点，值是一个数组，表示与该节点相连的邻居。
  • 访问记录：
    • visited 集合记录已经访问的节点，以避免重复访问。
    • stack 集合用于跟踪当前 DFS 路径上的节点，以检测循环。
  • 深度优先搜索：对于每个节点，检查其邻居。如果邻居在当前路径（stack）中，说明存在循环。
  • 回溯：在完成对某个节点及其邻居的 DFS 后，从 stack 中删除该节点，以便在检查其他路径时不干扰。