前端的你需要掌握的一些算法，不来看看？

0210

掌握一些算法对我们开发中解决一些问题会有很大的帮助，今天跟大家分享一些常见的算法题。

如果发现有误的地方，欢迎老铁们指正哈

一、排序算法

1. 冒泡排序

描述： 冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并且交换它们的位置，直到整个列表排序完成。

function bubbleSort(arr) {
  const n = arr.length;
  // 外层循环控制排序的轮数
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // 用于标记本轮是否有元素交换位置，如果没有，则表示已经有序，可以提前结束排序
    // 内层循环遍历未排序部分，进行相邻元素的比较和交换
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    // 如果本轮没有元素交换位置，表示已经有序，提前结束排序
    if (!swapped) {
      break;
    }
  }
  return arr;
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function bubbleSort(arr) {
  const n = arr.length;







  // 外层循环控制排序的轮数
  for (let i = 0; i < n - 1; i++) {

    let swapped = false; // 用于标记本轮是否有元素交换位置，如果没有，则表示已经有序，可以提前结束排序






    // 内层循环遍历未排序部分，进行相邻元素的比较和交换
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }



    // 如果本轮没有元素交换位置，表示已经有序，提前结束排序
    if (!swapped) {
      break;
    }


  }








  return arr;

}







// 示例

const arr = [64, 34, 25, 12, 22, 11, 90];

console.log(bubbleSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function bubbleSort(arr) {
  const n = arr.length;







  // 外层循环控制排序的轮数
  for (let i = 0; i < n - 1; i++) {

    let swapped = false; // 用于标记本轮是否有元素交换位置，如果没有，则表示已经有序，可以提前结束排序






    // 内层循环遍历未排序部分，进行相邻元素的比较和交换
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }



    // 如果本轮没有元素交换位置，表示已经有序，提前结束排序
    if (!swapped) {
      break;
    }


  }








  return arr;

}







// 示例

const arr = [64, 34, 25, 12, 22, 11, 90];

console.log(bubbleSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 外层循环控制排序的轮数，需要进行n-1轮排序，其中n是数组的长度。
  2. 内层循环遍历未排序部分，进行相邻元素的比较，如果当前元素大于下一个元素，则交换它们的位置。
  3. 在每一轮排序结束后，如果本轮没有元素交换位置，表示已经有序，可以提前结束排序。

复杂度分析：

  • 时间复杂度：最坏情况下，需要进行n-1轮排序，每轮排序需要遍历n-i-1个元素，所以总的比较次数为(1 + 2 + … + n-1) = n * (n-1) / 2，时间复杂度为O(n^2)。
  • 空间复杂度：O(1)。

2. 选择排序

描述： 选择排序的核心思想是通过在未排序部分找到最小（或最大）元素，然后将其放到已排序部分的末尾。

function selectionSort(arr) {
  const n = arr.length;
  // 外层循环控制已排序部分的末尾索引
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i; // 假设当前已排序部分的第一个元素为最小值
    // 内层循环遍历未排序部分，找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 将找到的最小值与当前已排序部分的末尾元素交换位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function selectionSort(arr) {
  const n = arr.length;







  // 外层循环控制已排序部分的末尾索引
  for (let i = 0; i < n - 1; i++) {

    let minIndex = i; // 假设当前已排序部分的第一个元素为最小值






    // 内层循环遍历未排序部分，找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }






    // 将找到的最小值与当前已排序部分的末尾元素交换位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }







  return arr;
}









// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function selectionSort(arr) {
  const n = arr.length;







  // 外层循环控制已排序部分的末尾索引
  for (let i = 0; i < n - 1; i++) {

    let minIndex = i; // 假设当前已排序部分的第一个元素为最小值






    // 内层循环遍历未排序部分，找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }






    // 将找到的最小值与当前已排序部分的末尾元素交换位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }







  return arr;
}









// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 外层循环控制已排序部分的末尾索引，需要进行n-1轮排序，其中n是数组的长度。
  2. 内层循环遍历未排序部分，找到最小值的索引。
  3. 将找到的最小值与当前已排序部分的末尾元素交换位置，将最小值放到已排序部分的末尾。

复杂度分析：

  • 时间复杂度：选择排序需要进行n-1轮排序，每轮排序需要遍历n-i个元素来找到最小值，所以总的比较次数为(1 + 2 + … + n-1) = n * (n-1) / 2，时间复杂度为O(n^2)。
  • 空间复杂度：O(1)。

3. 插入排序

描述： 插入排序的核心思想是将未排序部分的元素逐个插入到已排序部分的合适位置。，从而实现排序。

function insertionSort(arr) {
  const n = arr.length;
  // 外层循环控制未排序部分的起始索引
  for (let i = 1; i < n; i++) {
    const current = arr[i]; // 当前要插入的元素
    let j = i - 1; // 已排序部分的末尾索引
    // 内层循环将当前元素插入到已排序部分的合适位置
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 向后移动大于当前元素的元素
      j--;
    }
    arr[j + 1] = current; // 将当前元素插入到合适位置
  }
  return arr;
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function insertionSort(arr) {
  const n = arr.length;







  // 外层循环控制未排序部分的起始索引
  for (let i = 1; i < n; i++) {
    const current = arr[i]; // 当前要插入的元素
    let j = i - 1; // 已排序部分的末尾索引






    // 内层循环将当前元素插入到已排序部分的合适位置
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 向后移动大于当前元素的元素
      j--;
    }






    arr[j + 1] = current; // 将当前元素插入到合适位置
  }







  return arr;
}


// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function insertionSort(arr) {
  const n = arr.length;







  // 外层循环控制未排序部分的起始索引
  for (let i = 1; i < n; i++) {
    const current = arr[i]; // 当前要插入的元素
    let j = i - 1; // 已排序部分的末尾索引






    // 内层循环将当前元素插入到已排序部分的合适位置
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 向后移动大于当前元素的元素
      j--;
    }






    arr[j + 1] = current; // 将当前元素插入到合适位置
  }







  return arr;
}


// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 外层循环控制未排序部分的起始索引，需要进行n-1轮排序，其中n是数组的长度。
  2. 将当前要插入的元素保存在变量current中，内层循环遍历已排序部分，将大于current的元素向后移动，为current腾出插入的位置。
  3. 将current插入到已排序部分的合适位置。

复杂度分析：

  • 时间复杂度：最坏情况下，需要进行n-1轮排序，每轮排序最多需要比较i次（i为当前要插入的元素在已排序部分的位置），所以总的比较次数为(1 + 2 + … + n-1) = n * (n-1) / 2，时间复杂度为O(n^2)。
  • 空间复杂度：O(1)。

4. 希尔排序

描述： 希尔排序（Shell Sort）是插入排序的一种改进版本，它通过将原始数组分割成多个较小的子数组来实现排序。对这些子数组分别进行插入排序，然后逐步缩小子数组的规模，直至整个数组有序。

function shellSort(arr) {
  const n = arr.length;
  let gap = Math.floor(n / 2); // 初始的间隔值
  while (gap > 0) {
    // 对每个子数组进行插入排序
    for (let i = gap; i < n; i++) {
      const current = arr[i]; // 当前要插入的元素
      let j = i;
      // 插入排序的逻辑
      while (j >= gap && arr[j - gap] > current) {
        arr[j] = arr[j - gap]; // 向后移动元素
        j -= gap;
      }
      arr[j] = current; // 插入元素到合适位置
    }
    gap = Math.floor(gap / 2); // 缩小间隔值
  }
  return arr;
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(shellSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function shellSort(arr) {
  const n = arr.length;



  let gap = Math.floor(n / 2); // 初始的间隔值



  while (gap > 0) {
    // 对每个子数组进行插入排序
    for (let i = gap; i < n; i++) {
      const current = arr[i]; // 当前要插入的元素
      let j = i;




      // 插入排序的逻辑
      while (j >= gap && arr[j - gap] > current) {
        arr[j] = arr[j - gap]; // 向后移动元素
        j -= gap;
      }



      arr[j] = current; // 插入元素到合适位置
    }


    gap = Math.floor(gap / 2); // 缩小间隔值
  }








  return arr;

}







// 示例

const arr = [64, 34, 25, 12, 22, 11, 90];

console.log(shellSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function shellSort(arr) {
  const n = arr.length;



  let gap = Math.floor(n / 2); // 初始的间隔值



  while (gap > 0) {
    // 对每个子数组进行插入排序
    for (let i = gap; i < n; i++) {
      const current = arr[i]; // 当前要插入的元素
      let j = i;




      // 插入排序的逻辑
      while (j >= gap && arr[j - gap] > current) {
        arr[j] = arr[j - gap]; // 向后移动元素
        j -= gap;
      }



      arr[j] = current; // 插入元素到合适位置
    }


    gap = Math.floor(gap / 2); // 缩小间隔值
  }








  return arr;

}







// 示例

const arr = [64, 34, 25, 12, 22, 11, 90];

console.log(shellSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 首先，确定初始的间隔值gap，一般取数组长度的一半。然后，不断缩小gap的值，直到gap为1。
  2. 在每一轮排序中，使用插入排序对每个子数组进行排序。插入排序的逻辑和上面的插入排序一样，只是将步长从1改为gap。
  3. 每次排序后，将gap减小为原来的一半，继续排序，直到最后gap为1，此时整个数组已经基本有序，再进行最后一次插入排序。

复杂度分析：

  • 平均时间复杂度：希尔排序的时间复杂度取决于初始的间隔值gap的选择。不同的间隔序列会导致不同的时间复杂度，通常情况下希尔排序的时间复杂度为O(n^1.3)。
  • 空间复杂度：O(1)。

5. 快速排序

描述： 快速排序（Quick Sort）使用分治法来将一个数组分成两个子数组，然后递归地对子数组进行排序，最终将整个数组排序。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回
  }
  const pivot = arr[0]; // 选择基准值为数组的第一个元素
  const left = []; // 用于存放比基准值小的元素
  const right = []; // 用于存放比基准值大的元素
  // 将数组中的元素分别放入左右子数组
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 递归对左右子数组进行排序，并将结果合并
  return quickSort(left).concat(pivot, quickSort(right));
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function quickSort(arr) {
  if (arr.length <= 1) {

    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回

  }







  const pivot = arr[0]; // 选择基准值为数组的第一个元素
  const left = []; // 用于存放比基准值小的元素
  const right = []; // 用于存放比基准值大的元素


  // 将数组中的元素分别放入左右子数组
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }

  }







  // 递归对左右子数组进行排序，并将结果合并
  return quickSort(left).concat(pivot, quickSort(right));
}





// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function quickSort(arr) {
  if (arr.length <= 1) {

    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回

  }







  const pivot = arr[0]; // 选择基准值为数组的第一个元素
  const left = []; // 用于存放比基准值小的元素
  const right = []; // 用于存放比基准值大的元素


  // 将数组中的元素分别放入左右子数组
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }

  }







  // 递归对左右子数组进行排序，并将结果合并
  return quickSort(left).concat(pivot, quickSort(right));
}





// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 首先，选择一个基准值pivot，通常选择数组的第一个元素。然后，将数组中比pivot小的元素放入左子数组left，比pivot大的元素放入右子数组right。
  2. 递归对左右子数组进行排序，并将结果合并。这里用到了concat方法将left、pivot和right连接成一个新的数组。

复杂度分析：

  • 平均时间复杂度：快速排序的平均时间复杂度为O(nlogn)。
  • 最坏时间复杂度：最坏情况下，快速排序的时间复杂度为O(n^2)，例如当数组已经有序时。
  • 空间复杂度：O(logn)。

6. 归并排序

描述： 归并排序（Merge Sort）也是使用分治法实现的，将一个数组分成两个子数组，然后递归地对子数组进行排序，最后将排序后的子数组合并成一个有序数组。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回
  }
  // 将数组一分为二
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  // 递归对左右子数组进行排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  // 合并排序后的子数组
  return merge(sortedLeft, sortedRight);
}
function merge(leftArr, rightArr) {
  const mergedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  // 将两个子数组合并成一个有序数组
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      mergedArr.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      mergedArr.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }
  // 将剩余未合并的元素添加到合并数组中
  return mergedArr.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}
// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function mergeSort(arr) {
  if (arr.length <= 1) {

    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回

  }







  // 将数组一分为二
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);




  // 递归对左右子数组进行排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);





  // 合并排序后的子数组
  return merge(sortedLeft, sortedRight);
}






function merge(leftArr, rightArr) {
  const mergedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;





  // 将两个子数组合并成一个有序数组
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      mergedArr.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      mergedArr.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }



  // 将剩余未合并的元素添加到合并数组中
  return mergedArr.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}



// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
function mergeSort(arr) {
  if (arr.length <= 1) {

    return arr; // 基线条件：如果数组长度为1或者为空，则直接返回

  }







  // 将数组一分为二
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);




  // 递归对左右子数组进行排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);





  // 合并排序后的子数组
  return merge(sortedLeft, sortedRight);
}






function merge(leftArr, rightArr) {
  const mergedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;





  // 将两个子数组合并成一个有序数组
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      mergedArr.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      mergedArr.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }



  // 将剩余未合并的元素添加到合并数组中
  return mergedArr.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}



// 示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

解析：

  1. 将原始数组一分为二，分别得到左子数组left和右子数组right。
  2. 递归对左右子数组进行排序，得到排序后的子数组sortedLeft和sortedRight。
  3. 最后，将排序后的子数组sortedLeft和sortedRight合并为一个有序数组，合并的过程通过merge函数实现。

复杂度分析：

  • 时间复杂度：归并排序的时间复杂度为O(nlogn)。
  • 空间复杂度：归并排序使用了额外的空间来存储临时数组，空间复杂度为O(n)。

二、回文字符串

描述： 判断一个字符串是否是回文字符串（正反读都相同）。

function isPalindrome(str) {
  // 将字符串转换为小写，并去除非字母和数字的字符
  const formattedStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');
  // 使用双指针法判断回文字符串
  let left = 0; // 左指针从字符串开头开始
  let right = formattedStr.length - 1; // 右指针从字符串末尾开始
  // 当左指针小于右指针时，执行判断操作
  while (left < right) {
    // 如果左右指针指向的字符不相等，则说明不是回文字符串
    if (formattedStr[left] !== formattedStr[right]) {
      return false;
    }
    // 移动左指针向右移动一步
    left++;
    // 移动右指针向左移动一步
    right--;
  }
  // 循环结束后，没有发现不相等的字符，说明是回文字符串
  return true;
}
const str1 = "A man, a plan, a canal, Panama!";
const str2 = "race a car";
console.log(isPalindrome(str1)); // 输出: true
console.log(isPalindrome(str2)); // 输出: false
function isPalindrome(str) {
  // 将字符串转换为小写，并去除非字母和数字的字符
  const formattedStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');



  // 使用双指针法判断回文字符串
  let left = 0; // 左指针从字符串开头开始
  let right = formattedStr.length - 1; // 右指针从字符串末尾开始






  // 当左指针小于右指针时，执行判断操作
  while (left < right) {
    // 如果左右指针指向的字符不相等，则说明不是回文字符串
    if (formattedStr[left] !== formattedStr[right]) {
      return false;
    }



    // 移动左指针向右移动一步
    left++;
    // 移动右指针向左移动一步
    right--;
  }






  // 循环结束后，没有发现不相等的字符，说明是回文字符串
  return true;
}







const str1 = "A man, a plan, a canal, Panama!";
const str2 = "race a car";


console.log(isPalindrome(str1)); // 输出: true
console.log(isPalindrome(str2)); // 输出: false
function isPalindrome(str) {
  // 将字符串转换为小写，并去除非字母和数字的字符
  const formattedStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');



  // 使用双指针法判断回文字符串
  let left = 0; // 左指针从字符串开头开始
  let right = formattedStr.length - 1; // 右指针从字符串末尾开始






  // 当左指针小于右指针时，执行判断操作
  while (left < right) {
    // 如果左右指针指向的字符不相等，则说明不是回文字符串
    if (formattedStr[left] !== formattedStr[right]) {
      return false;
    }



    // 移动左指针向右移动一步
    left++;
    // 移动右指针向左移动一步
    right--;
  }






  // 循环结束后，没有发现不相等的字符，说明是回文字符串
  return true;
}







const str1 = "A man, a plan, a canal, Panama!";
const str2 = "race a car";


console.log(isPalindrome(str1)); // 输出: true
console.log(isPalindrome(str2)); // 输出: false
  1. 将输入字符串转换为小写，并去除非字母和数字的字符，以便处理不区分大小写和忽略非字母数字的回文判断。
  2. 使用双指针法，一个指向字符串开头，一个指向字符串末尾，不断比较左右指针指向的字符是否相等，直到左指针大于等于右指针为止。
  3. 如果发现不相等的字符，则返回false，否则返回true，表示字符串是回文字符串。

三、有效的括号

描述： 给定一个字符串，判断其中的括号是否匹配有效。

function isValid(s) {
  const stack = []; // 使用栈来辅助判断括号是否匹配
  // 遍历字符串的每个字符
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    // 如果是左括号，则将其入栈
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      // 如果是右括号，判断栈顶元素是否和当前右括号匹配
      const top = stack.pop();
      if (
        (char === ')' && top !== '(') ||
        (char === ']' && top !== '[') ||
        (char === '}' && top !== '{')
      ) {
        return false;
      }
    }
  }
  // 遍历完字符串后，如果栈不为空，说明有未匹配的左括号，返回false
  return stack.length === 0;
}
console.log(isValid("()")); // 输出: true
console.log(isValid("()[]{}")); // 输出: true
console.log(isValid("(]")); // 输出: false
console.log(isValid("([)]")); // 输出: false
function isValid(s) {
  const stack = []; // 使用栈来辅助判断括号是否匹配




  // 遍历字符串的每个字符
  for (let i = 0; i < s.length; i++) {
    const char = s[i];






    // 如果是左括号，则将其入栈
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      // 如果是右括号，判断栈顶元素是否和当前右括号匹配
      const top = stack.pop();
      if (
        (char === ')' && top !== '(') ||
        (char === ']' && top !== '[') ||
        (char === '}' && top !== '{')
      ) {
        return false;
      }
    }
  }





  // 遍历完字符串后，如果栈不为空，说明有未匹配的左括号，返回false
  return stack.length === 0;
}



console.log(isValid("()")); // 输出: true
console.log(isValid("()[]{}")); // 输出: true
console.log(isValid("(]")); // 输出: false
console.log(isValid("([)]")); // 输出: false
function isValid(s) {
  const stack = []; // 使用栈来辅助判断括号是否匹配




  // 遍历字符串的每个字符
  for (let i = 0; i < s.length; i++) {
    const char = s[i];






    // 如果是左括号，则将其入栈
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      // 如果是右括号，判断栈顶元素是否和当前右括号匹配
      const top = stack.pop();
      if (
        (char === ')' && top !== '(') ||
        (char === ']' && top !== '[') ||
        (char === '}' && top !== '{')
      ) {
        return false;
      }
    }
  }





  // 遍历完字符串后，如果栈不为空，说明有未匹配的左括号，返回false
  return stack.length === 0;
}



console.log(isValid("()")); // 输出: true
console.log(isValid("()[]{}")); // 输出: true
console.log(isValid("(]")); // 输出: false
console.log(isValid("([)]")); // 输出: false

解析：

  1. 使用栈来辅助判断括号是否匹配有效。
  2. 遍历字符串的每个字符，如果是左括号，则将其入栈。
  3. 如果是右括号，从栈顶取出一个元素，判断栈顶元素是否和当前右括号匹配，如果不匹配，则说明括号无效，返回false。
  4. 遍历完字符串后，如果栈不为空，说明有未匹配的左括号，返回false，否则返回true。

四、斐波那契数列

描述： 斐波那契数列是一系列数字，其中每个数字是前两个数字之和。编写一个函数，返回斐波那契数列的第n项。

function fibonacci(n) {
  // 斐波那契数列的前两项是0和1
  if (n === 0) return 0;
  if (n === 1) return 1;
  // 初始化前两项的值
  let prevPrev = 0;
  let prev = 1;
  let current;
  // 计算第n项的值
  for (let i = 2; i <= n; i++) {
    // 当前项等于前两项的和
    current = prevPrev + prev;
    // 更新前两项的值，准备下一次循环
    prevPrev = prev;
    prev = current;
  }
  return current;
}
const n = 7;
console.log(fibonacci(n)); // 输出: 13
function fibonacci(n) {
  // 斐波那契数列的前两项是0和1
  if (n === 0) return 0;
  if (n === 1) return 1;





  // 初始化前两项的值
  let prevPrev = 0;
  let prev = 1;
  let current;




  // 计算第n项的值
  for (let i = 2; i <= n; i++) {
    // 当前项等于前两项的和
    current = prevPrev + prev;



    // 更新前两项的值，准备下一次循环
    prevPrev = prev;
    prev = current;
  }


  return current;
}






const n = 7;
console.log(fibonacci(n)); // 输出: 13
function fibonacci(n) {
  // 斐波那契数列的前两项是0和1
  if (n === 0) return 0;
  if (n === 1) return 1;





  // 初始化前两项的值
  let prevPrev = 0;
  let prev = 1;
  let current;




  // 计算第n项的值
  for (let i = 2; i <= n; i++) {
    // 当前项等于前两项的和
    current = prevPrev + prev;



    // 更新前两项的值，准备下一次循环
    prevPrev = prev;
    prev = current;
  }


  return current;
}






const n = 7;
console.log(fibonacci(n)); // 输出: 13

解析：

  1. 使用迭代方式计算斐波那契数列的第n项。斐波那契数列的前两项是0和1，从第三项开始，每一项都是前两项的和。

五、求最大子序列

描述： 求解最大子序列和问题是要在给定整数数组中找到具有最大和的连续子序列。

function maxSubArray(nums) {
  // 初始化最大子序列和和当前子序列和为第一个元素
  let maxSum = nums[0];
  let currentSum = nums[0];
  // 从第二个元素开始遍历数组
  for (let i = 1; i < nums.length; i++) {
    // 如果当前子序列和加上当前元素大于当前元素本身，则将当前元素添加到子序列中
    // 否则，重新开始一个新的子序列
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    // 更新最大子序列和
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 输出: 6 (子序列为[4, -1, 2, 1])
function maxSubArray(nums) {
  // 初始化最大子序列和和当前子序列和为第一个元素
  let maxSum = nums[0];
  let currentSum = nums[0];





  // 从第二个元素开始遍历数组
  for (let i = 1; i < nums.length; i++) {
    // 如果当前子序列和加上当前元素大于当前元素本身，则将当前元素添加到子序列中
    // 否则，重新开始一个新的子序列
    currentSum = Math.max(nums[i], currentSum + nums[i]);



    // 更新最大子序列和
    maxSum = Math.max(maxSum, currentSum);
  }



  return maxSum;
}






const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 输出: 6 (子序列为[4, -1, 2, 1])
function maxSubArray(nums) {
  // 初始化最大子序列和和当前子序列和为第一个元素
  let maxSum = nums[0];
  let currentSum = nums[0];





  // 从第二个元素开始遍历数组
  for (let i = 1; i < nums.length; i++) {
    // 如果当前子序列和加上当前元素大于当前元素本身，则将当前元素添加到子序列中
    // 否则，重新开始一个新的子序列
    currentSum = Math.max(nums[i], currentSum + nums[i]);



    // 更新最大子序列和
    maxSum = Math.max(maxSum, currentSum);
  }



  return maxSum;
}






const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 输出: 6 (子序列为[4, -1, 2, 1])

解析：

  1. 这个算法使用动态规划的思想来求解最大子序列和。
  2. 我们用两个变量maxSum和currentSum分别记录最大子序列和和当前子序列和。
  3. 从数组的第二个元素开始遍历，对于每个元素，判断当前子序列和加上当前元素是否大于当前元素本身，如果是，则将当前元素添加到子序列中，否则，重新开始一个新的子序列。
  4. 在遍历过程中，不断更新最大子序列和的值，最终得到最大子序列和。

六、两数之和

描述： 给定一个整数数组和一个目标值，找到数组中和为目标值的两个数的索引。

function twoSum(nums, target) {
  // 使用哈希表存储数组元素和对应索引的映射关系
  const map = new Map();
  // 遍历数组元素
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]; // 计算目标值与当前元素的差值
    // 如果差值在哈希表中存在，则找到了两个数的索引
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    // 将当前元素及其索引加入哈希表中
    map.set(nums[i], i);
  }
  // 如果没有找到符合条件的两个数，返回空数组
  return [];
}
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // 输出: [0, 1]
function twoSum(nums, target) {
  // 使用哈希表存储数组元素和对应索引的映射关系
  const map = new Map();



  // 遍历数组元素
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]; // 计算目标值与当前元素的差值






    // 如果差值在哈希表中存在，则找到了两个数的索引
    if (map.has(complement)) {
      return [map.get(complement), i];
    }




    // 将当前元素及其索引加入哈希表中
    map.set(nums[i], i);
  }







  // 如果没有找到符合条件的两个数，返回空数组
  return [];
}









const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // 输出: [0, 1]
function twoSum(nums, target) {
  // 使用哈希表存储数组元素和对应索引的映射关系
  const map = new Map();



  // 遍历数组元素
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]; // 计算目标值与当前元素的差值






    // 如果差值在哈希表中存在，则找到了两个数的索引
    if (map.has(complement)) {
      return [map.get(complement), i];
    }




    // 将当前元素及其索引加入哈希表中
    map.set(nums[i], i);
  }







  // 如果没有找到符合条件的两个数，返回空数组
  return [];
}









const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // 输出: [0, 1]

解析：

  1. 我们使用一个哈希表map来存储数组元素和对应索引的映射关系。
  2. 遍历数组元素，在每次遍历时，计算目标值与当前元素的差值，并检查该差值是否在哈希表中存在。
  3. 如果差值在哈希表中存在，则说明找到了符合条件的两个数的索引，直接返回结果。
  4. 如果差值不在哈希表中存在，则将当前元素及其索引加入哈希表中，继续下一次遍历。
  5. 如果遍历结束后没有找到符合条件的两个数，返回空数组。

七、反转链表

描述： 给定一个单链表，将其反转。

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
function reverseLinkedList(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const nextNode = current.next; // 保存当前节点的下一个节点
    current.next = prev; // 将当前节点的next指向前一个节点，实现反转
    prev = current; // 更新prev为当前节点
    current = nextNode; // 更新current为原本的下一个节点
  }
  return prev; // prev现在是反转后的链表的头节点
}
// 示例：创建一个链表
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
const reversedHead = reverseLinkedList(head);
// 输出反转后的链表
let current = reversedHead;
while (current !== null) {
  console.log(current.val); // 输出: 5, 4, 3, 2, 1
  current = current.next;
}
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








function reverseLinkedList(head) {
  let prev = null;
  let current = head;



  while (current !== null) {
    const nextNode = current.next; // 保存当前节点的下一个节点
    current.next = prev; // 将当前节点的next指向前一个节点，实现反转
    prev = current; // 更新prev为当前节点
    current = nextNode; // 更新current为原本的下一个节点
  }







  return prev; // prev现在是反转后的链表的头节点
}









// 示例：创建一个链表
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);


const reversedHead = reverseLinkedList(head);
// 输出反转后的链表
let current = reversedHead;
while (current !== null) {
  console.log(current.val); // 输出: 5, 4, 3, 2, 1
  current = current.next;
}
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








function reverseLinkedList(head) {
  let prev = null;
  let current = head;



  while (current !== null) {
    const nextNode = current.next; // 保存当前节点的下一个节点
    current.next = prev; // 将当前节点的next指向前一个节点，实现反转
    prev = current; // 更新prev为当前节点
    current = nextNode; // 更新current为原本的下一个节点
  }







  return prev; // prev现在是反转后的链表的头节点
}









// 示例：创建一个链表
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);


const reversedHead = reverseLinkedList(head);
// 输出反转后的链表
let current = reversedHead;
while (current !== null) {
  console.log(current.val); // 输出: 5, 4, 3, 2, 1
  current = current.next;
}

解析：

  1. 定义两个指针prev和current，初始时prev为null，current为链表的头节点head。
  2. 遍历链表，每次迭代都将当前节点的next指针指向前一个节点prev，实现链表的反转。
  3. 更新prev为当前节点current，将current更新为原本的下一个节点。
  4. 当遍历完成后，prev指向反转后链表的头节点，返回prev。

八、判断链表是否有环

描述： 给定一个链表，判断链表中是否有环。

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
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 = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next; // 这里构造一个环，指向第二个节点
console.log(hasCycle(head)); // 输出: true
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








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 = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next; // 这里构造一个环，指向第二个节点

console.log(hasCycle(head)); // 输出: true
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








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 = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(-4);
head.next.next.next.next = head.next; // 这里构造一个环，指向第二个节点

console.log(hasCycle(head)); // 输出: true

解析：

  1. 使用快慢指针来判断链表中是否有环。
  2. 我们使用两个指针slow和fast，初始时都指向链表头节点。
  3. 在每一次循环中，慢指针slow每次移动一步，快指针fast每次移动两步。
  4. 如果链表中有环，快指针fast最终会追上慢指针slow，此时说明链表中有环。
  5. 如果链表中没有环，快指针fast会先到达链表末尾，此时循环结束，说明链表中没有环。

九、合并两个有序链表

描述： 合并两个有序的单链表，使得合并后的链表仍然有序。

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
function mergeTwoLists(l1, l2) {
  // 创建一个新的头节点，用于合并后的链表
  const dummy = new ListNode(0);
  let current = dummy; // current用于遍历合并后的链表
  // 遍历两个链表，直到其中一个链表遍历完毕
  while (l1 !== null && l2 !== null) {
    // 比较两个链表当前节点的值，将较小的节点添加到合并后的链表中
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    // 移动current指针到合并后的链表的末尾
    current = current.next;
  }
  // 将未遍历完的链表直接连接到合并后的链表的末尾
  if (l1 !== null) {
    current.next = l1;
  }
  if (l2 !== null) {
    current.next = l2;
  }
  // 返回合并后的链表，跳过头节点
  return dummy.next;
}
// 示例：创建两个有序链表
const l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
const l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
console.log(mergeTwoLists(l1, l2));
// 输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








function mergeTwoLists(l1, l2) {
  // 创建一个新的头节点，用于合并后的链表
  const dummy = new ListNode(0);
  let current = dummy; // current用于遍历合并后的链表



  // 遍历两个链表，直到其中一个链表遍历完毕
  while (l1 !== null && l2 !== null) {
    // 比较两个链表当前节点的值，将较小的节点添加到合并后的链表中
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }





    // 移动current指针到合并后的链表的末尾
    current = current.next;
  }



  // 将未遍历完的链表直接连接到合并后的链表的末尾
  if (l1 !== null) {
    current.next = l1;
  }


  if (l2 !== null) {
    current.next = l2;
  }

  // 返回合并后的链表，跳过头节点
  return dummy.next;
}

// 示例：创建两个有序链表
const l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);

const l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);


console.log(mergeTwoLists(l1, l2));
// 输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4
class ListNode {


  constructor(val) {



    this.val = val;



    this.next = null;


  }




}








function mergeTwoLists(l1, l2) {
  // 创建一个新的头节点，用于合并后的链表
  const dummy = new ListNode(0);
  let current = dummy; // current用于遍历合并后的链表



  // 遍历两个链表，直到其中一个链表遍历完毕
  while (l1 !== null && l2 !== null) {
    // 比较两个链表当前节点的值，将较小的节点添加到合并后的链表中
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }





    // 移动current指针到合并后的链表的末尾
    current = current.next;
  }



  // 将未遍历完的链表直接连接到合并后的链表的末尾
  if (l1 !== null) {
    current.next = l1;
  }


  if (l2 !== null) {
    current.next = l2;
  }

  // 返回合并后的链表，跳过头节点
  return dummy.next;
}

// 示例：创建两个有序链表
const l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);

const l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);


console.log(mergeTwoLists(l1, l2));
// 输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4

解析：

  1. 使用迭代的方式合并两个有序链表，创建一个新的有序链表。
  2. 我们使用一个新的头节点dummy来构造合并后的链表，同时使用一个指针current用于遍历新链表。
  3. 遍历两个有序链表，比较当前节点的值，将较小的节点添加到合并后的链表中，直到其中一个链表遍历完毕。
  4. 将未遍历完的链表直接连接到合并后的链表的末尾。
  5. 返回合并后的链表，跳过头节点dummy。

十、二叉树的遍历

描述： 实现二叉树前序、中序和后序遍历。

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
// 前序遍历：根节点 -> 左子树 -> 右子树
function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    result.push(node.val); // 访问根节点
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
  }
  traverse(root); // 从根节点开始遍历
  return result;
}
// 中序遍历：左子树 -> 根节点 -> 右子树
function inorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    result.push(node.val); // 访问根节点
    traverse(node.right); // 递归遍历右子树
  }
  traverse(root); // 从根节点开始遍历
  return result;
}
// 后序遍历：左子树 -> 右子树 -> 根节点
function postorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
    result.push(node.val); // 访问根节点
  }
  traverse(root); // 从根节点开始遍历
  return result;
}
// 示例：创建一个二叉树
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(preorderTraversal(root)); // 输出: [1, 2, 4, 5, 3]
console.log(inorderTraversal(root)); // 输出: [4, 2, 5, 1, 3]
console.log(postorderTraversal(root)); // 输出: [4, 5, 2, 3, 1]
class TreeNode {
  constructor(val) {



    this.val = val;



    this.left = null;
    this.right = null;
  }
}






// 前序遍历：根节点 -> 左子树 -> 右子树
function preorderTraversal(root) {
  const result = [];



  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    result.push(node.val); // 访问根节点
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
  }


  traverse(root); // 从根节点开始遍历
  return result;
}






// 中序遍历：左子树 -> 根节点 -> 右子树
function inorderTraversal(root) {
  const result = [];



  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    result.push(node.val); // 访问根节点
    traverse(node.right); // 递归遍历右子树
  }



  traverse(root); // 从根节点开始遍历
  return result;
}



// 后序遍历：左子树 -> 右子树 -> 根节点
function postorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
    result.push(node.val); // 访问根节点
  }


  traverse(root); // 从根节点开始遍历
  return result;
}

// 示例：创建一个二叉树
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(preorderTraversal(root)); // 输出: [1, 2, 4, 5, 3]
console.log(inorderTraversal(root)); // 输出: [4, 2, 5, 1, 3]
console.log(postorderTraversal(root)); // 输出: [4, 5, 2, 3, 1]
class TreeNode {
  constructor(val) {



    this.val = val;



    this.left = null;
    this.right = null;
  }
}






// 前序遍历：根节点 -> 左子树 -> 右子树
function preorderTraversal(root) {
  const result = [];



  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    result.push(node.val); // 访问根节点
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
  }


  traverse(root); // 从根节点开始遍历
  return result;
}






// 中序遍历：左子树 -> 根节点 -> 右子树
function inorderTraversal(root) {
  const result = [];



  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    result.push(node.val); // 访问根节点
    traverse(node.right); // 递归遍历右子树
  }



  traverse(root); // 从根节点开始遍历
  return result;
}



// 后序遍历：左子树 -> 右子树 -> 根节点
function postorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return; // 递归终止条件：节点为空
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
    result.push(node.val); // 访问根节点
  }


  traverse(root); // 从根节点开始遍历
  return result;
}

// 示例：创建一个二叉树
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(preorderTraversal(root)); // 输出: [1, 2, 4, 5, 3]
console.log(inorderTraversal(root)); // 输出: [4, 2, 5, 1, 3]
console.log(postorderTraversal(root)); // 输出: [4, 5, 2, 3, 1]

解析：

  1. 使用递归的方式实现二叉树的前序、中序和后序遍历。
  2. 前序遍历：先访问根节点，然后递归遍历左子树，再递归遍历右子树。
  3. 中序遍历：先递归遍历左子树，然后访问根节点，再递归遍历右子树。
  4. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

十一、求二叉树的最大深度

描述： 给定一个二叉树，计算其最大深度，即树的最大高度。

function maxDepth(root) {
  // 递归终止条件：节点为空时，深度为0
  if (!root) {
    return 0;
  }
  // 递归计算左子树和右子树的最大深度
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);
  // 返回左子树和右子树中深度较大的值加上根节点的深度1
  return Math.max(leftDepth, rightDepth) + 1;
}
// 示例：创建一个二叉树
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(maxDepth(root)); // 输出: 3
function maxDepth(root) {
  // 递归终止条件：节点为空时，深度为0
  if (!root) {

    return 0;
  }






  // 递归计算左子树和右子树的最大深度
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);




  // 返回左子树和右子树中深度较大的值加上根节点的深度1
  return Math.max(leftDepth, rightDepth) + 1;
}





// 示例：创建一个二叉树
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);






console.log(maxDepth(root)); // 输出: 3
function maxDepth(root) {
  // 递归终止条件：节点为空时，深度为0
  if (!root) {

    return 0;
  }






  // 递归计算左子树和右子树的最大深度
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);




  // 返回左子树和右子树中深度较大的值加上根节点的深度1
  return Math.max(leftDepth, rightDepth) + 1;
}





// 示例：创建一个二叉树
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);






console.log(maxDepth(root)); // 输出: 3

解析：

  1. 使用递归的方式计算给定二叉树的最大深度。
  2. 递归终止条件是节点为空时，深度为0。
  3. 递归计算左子树和右子树的最大深度。
  4. 返回左子树和右子树中深度较大的值加上根节点的深度1，即为整棵二叉树的最大深度。

十二、验证二叉搜索树

二叉搜索树的定义是： 对于每个节点，其左子树的所有节点都小于它的值，其右子树的所有节点都大于它的值，并且左子树和右子树都是二叉搜索树。

描述： 给定一个二叉树，判断它是否是一个二叉搜索树。

function isValidBST(root) {
  // 递归验证二叉搜索树的辅助函数
  function isValid(node, min, max) {
    // 递归终止条件：节点为空，或者节点的值不在[min, max]的范围内
    if (!node) {
      return true;
    }
    // 检查节点的值是否在[min, max]的范围内
    if (node.val <= min || node.val >= max) {
      return false;
    }
    // 递归验证左子树和右子树
    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
  }
  // 调用辅助函数，初始时，二叉搜索树的最小值为负无穷，最大值为正无穷
  return isValid(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}
function isValidBST(root) {
  // 递归验证二叉搜索树的辅助函数
  function isValid(node, min, max) {
    // 递归终止条件：节点为空，或者节点的值不在[min, max]的范围内
    if (!node) {
      return true;
    }






    // 检查节点的值是否在[min, max]的范围内
    if (node.val <= min || node.val >= max) {
      return false;
    }




    // 递归验证左子树和右子树
    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
  }







  // 调用辅助函数，初始时，二叉搜索树的最小值为负无穷，最大值为正无穷
  return isValid(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}
function isValidBST(root) {
  // 递归验证二叉搜索树的辅助函数
  function isValid(node, min, max) {
    // 递归终止条件：节点为空，或者节点的值不在[min, max]的范围内
    if (!node) {
      return true;
    }






    // 检查节点的值是否在[min, max]的范围内
    if (node.val <= min || node.val >= max) {
      return false;
    }




    // 递归验证左子树和右子树
    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
  }







  // 调用辅助函数，初始时，二叉搜索树的最小值为负无穷，最大值为正无穷
  return isValid(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}

解析：

  1. 使用递归的方式判断给定二叉树是否是一个二叉搜索树。
  2. 递归验证二叉搜索树的辅助函数isValid接收当前节点、当前节点的最小值和最大值作为参数，用于验证当前节点是否满足二叉搜索树的条件。
  3. 递归终止条件：如果当前节点为空，说明已经验证完了，返回true。如果当前节点的值不在[min, max]的范围内，说明不满足二叉搜索树的条件，返回false。
  4. 检查当前节点的值是否在[min, max]的范围内，如果不在，则返回false。
  5. 递归验证当前节点的左子树和右子树，分别传入新的最小值和最大值。

十三、深度优先遍历（类似树的前序遍历）

描述： 深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。在深度优先遍历中，从根节点开始，沿着子树的深度遍历直到遇到叶子节点，然后回溯到前一个节点，再继续遍历其他子树。

function dfs(root, result = []) {
  if (!root) {
    return result; // 基线条件：如果根节点为空，则直接返回
  }
  // 先访问当前节点的值
  result.push(root.val);
  // 递归遍历左子树
  dfs(root.left, result);
  // 递归遍历右子树
  dfs(root.right, result);
  return result;
}
// 示例：深度优先遍历一棵二叉树
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(root)); // 输出: [1, 2, 4, 5, 3]
function dfs(root, result = []) {
  if (!root) {
    return result; // 基线条件：如果根节点为空，则直接返回
  }







  // 先访问当前节点的值
  result.push(root.val);






  // 递归遍历左子树
  dfs(root.left, result);



  // 递归遍历右子树
  dfs(root.right, result);





  return result;
}





// 示例：深度优先遍历一棵二叉树
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(root)); // 输出: [1, 2, 4, 5, 3]
function dfs(root, result = []) {
  if (!root) {
    return result; // 基线条件：如果根节点为空，则直接返回
  }







  // 先访问当前节点的值
  result.push(root.val);






  // 递归遍历左子树
  dfs(root.left, result);



  // 递归遍历右子树
  dfs(root.right, result);





  return result;
}





// 示例：深度优先遍历一棵二叉树
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(root)); // 输出: [1, 2, 4, 5, 3]

十四、广度优先遍历（类似树的层序遍历）

广度优先遍历（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。从根节点开始，按照层次的顺序逐层遍历节点，先访问当前节点的所有子节点，再依次访问子节点的子节点，以此类推，直到遍历完整棵树或者图。

function bfs(root) {
  if (!root) {
    return []; // 基线条件：如果根节点为空，则直接返回空数组
  }
  const result = []; // 用于存放遍历结果的数组
  const queue = [root]; // 使用队列辅助进行广度优先遍历
  while (queue.length > 0) {
    const current = queue.shift(); // 出队当前节点
    result.push(current.val); // 将当前节点的值加入结果数组
    if (current.left) {
      queue.push(current.left); // 将左子节点入队
    }
    if (current.right) {
      queue.push(current.right); // 将右子节点入队
    }
  }
  return result;
}
// 示例：广度优先遍历一棵二叉树
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(bfs(root)); // 输出: [1, 2, 3, 4, 5]
function bfs(root) {
  if (!root) {

    return []; // 基线条件：如果根节点为空，则直接返回空数组
  }






  const result = []; // 用于存放遍历结果的数组
  const queue = [root]; // 使用队列辅助进行广度优先遍历


  while (queue.length > 0) {
    const current = queue.shift(); // 出队当前节点
    result.push(current.val); // 将当前节点的值加入结果数组



    if (current.left) {
      queue.push(current.left); // 将左子节点入队
    }






    if (current.right) {
      queue.push(current.right); // 将右子节点入队
    }


  }








  return result;
}







// 示例：广度优先遍历一棵二叉树
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(bfs(root)); // 输出: [1, 2, 3, 4, 5]

function bfs(root) {
  if (!root) {

    return []; // 基线条件：如果根节点为空，则直接返回空数组
  }






  const result = []; // 用于存放遍历结果的数组
  const queue = [root]; // 使用队列辅助进行广度优先遍历


  while (queue.length > 0) {
    const current = queue.shift(); // 出队当前节点
    result.push(current.val); // 将当前节点的值加入结果数组



    if (current.left) {
      queue.push(current.left); // 将左子节点入队
    }






    if (current.right) {
      queue.push(current.right); // 将右子节点入队
    }


  }








  return result;
}







// 示例：广度优先遍历一棵二叉树
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(bfs(root)); // 输出: [1, 2, 3, 4, 5]

解析：

  1. 使用一个队列辅助进行广度优先遍历。首先将根节点入队，然后在循环中取出队首节点，访问该节点并将其值加入结果数组，然后将该节点的所有子节点按顺序入队。
  2. 队列的先进先出（FIFO）特性确保了按层遍历的顺序。

© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END

# 前端# 算法# 排序算法
喜欢就支持一下吧
点赞0

Warning: mysqli_query(): (HY000/3): Error writing file '/tmp/MY3Kz0kC' (Errcode: 28 - No space left on device) in /www/wwwroot/583.cn/wp-includes/class-wpdb.php on line 2345
admin的头像-五八三
相关推荐
评论 抢沙发
头像
欢迎您留下宝贵的见解！
提交
头像

昵称

图形验证码
取消
昵称

请填写用户信息：

  • 昵称(必填)
  • 邮箱(必填)
代码

请输入代码：

确认
图片
文章目录
文章目录
热门推荐