Leetcode

leetcode

1.两数之和

/*
 * @lc app=leetcode.cn id=1 lang=typescript
 *
 * [1] 两数之和
 */

// @lc code=start type:哈希
function twoSum(nums: number[], target: number): number[] {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (!map.has(nums[i])) {
      map.set(target-nums[i],i)
    } else {
      return [map.get(nums[i]),i]
    }
  }
};
// @lc code=end

2.两数相加

/*
 * @lc app=leetcode.cn id=2 lang=typescript
 *
 * [2] 两数相加
 */

// @lc code=start type: 链表
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
/**

给定两个非空链表，分别表示两个非负整数。数字以相反的顺序存储，每个节点包含一个数字。将这两个数相加并以链表的形式返回。
@param l1 非空链表1
@param l2 非空链表2
@param carry 进位值，默认为 0
@return 相加后的链表
*/
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null, carry = 0): ListNode | null {
  if (l1 || l2) { // 如果任意一个链表不为空
    const next1 = getNextNode(l1) // 获取 l1 的下一个节点
    const next2 = getNextNode(l2) // 获取 l2 的下一个节点
    const sum = getNodeVal(l1) + getNodeVal(l2) + carry // 计算当前节点的和
    const nextCarry = sum >= 10 ? 1 : 0 // 计算进位值
    return new ListNode(sum % 10, addTwoNumbers(next1, next2, nextCarry)) // 创建当前节点，并递归创建下一个节点
  } else if (carry > 0) { // 如果两个链表都为空，但存在进位值
    return new ListNode(1) // 创建新节点，值为 1
  }
  return null // 如果两个链表都为空，且没有进位值，返回空
}
/**

获取链表节点的值，如果链表为空，返回 0。
@param l 链表节点
@return 链表节点的值
*/
function getNodeVal(l: ListNode | null): number {
  return l && l.val || 0
}
/**

获取链表的下一个节点，如果链表为空，返回空。
@param l 链表节点
@returns 链表的下一个节点
*/
function getNextNode(l: ListNode | null): ListNode | null {
  return l && l.next || null
}
// @lc code=end

3.无重复字符的最长子串

/*
 * @lc app=leetcode.cn id=3 lang=typescript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
// type: 双指针
function lengthOfLongestSubstring(s: string): number {

  if (s.length <= 1) return s.length
  let start = 0 // 定义起始位置
  let left = 0 // 定义左指针
  let len = s.length // 定义字符串长度
  let max = 0 // 定义最大长度
  const map = new Map() // 定义Map
  while (left < len) {
    if (map.has(s[left])) { // 如果Map中已经存在该字符
      start = map.get(s[left]) + 1 >= start ? map.get(s[left]) + 1 : start // 更新起始位置
    }
    map.set(s[left], left) // 将字符和下标存入Map
    max = Math.max(max, left - start + 1) // 更新最大长度
    left++ // 左指针右移
  }
  return max // 返回最大长度
};
// @lc code=end

4.寻找两个正序数组的中位数

/*
 * @lc app=leetcode.cn id=4 lang=typescript
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lc code=start
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {

};
// @lc code=end

5.最长回文子串

/*
 * @lc app=leetcode.cn id=5 lang=typescript
 *
 * [5] 最长回文子串
 */

// @lc code=start type: 扫描
/**
在一个字符串中，找到最长的回文子串，并返回该子串。
@param s 字符串
@return 最长的回文子串
*/
function longestPalindrome(s: string): string {
  for (let j = s.length - 1; j >= 0; j--) { // 枚举子串长度，从大到小扫描
    let i = 0 // i 表示子串的起始位置
    let k = j // k 表示子串的结束位置
    while (k < s.length) { // 当子串结束位置未越界时
      let substr = s.substring(i, k + 1) // 取出子串
      if (isPalindrome(substr)) return substr // 如果子串是回文串，返回子串
      i++, k++ // 子串起始位置右移，子串结束位置右移
    }
  }
  return "" // 扫描完所有长度的子串都不是回文串，返回空字符串
}
/**

判断一个字符串是否是回文串。
@param str 字符串
@return 如果是回文串，返回 true；否则，返回 false。
*/
function isPalindrome(str: string): boolean {
  let l = 0, r = str.length - 1; // 左右指针指向字符串的两端
  while (l < r) { // 左右指针相向而行，直到相遇
    if (str[l] !== str[r]) return false; // 如果左右指针所指的字符不相等，返回 false
    l++, r--; // 左右指针向中间移动
  }
  return true; // 如果左右指针所指的字符都相等，说明是回文串，返回 true
}
// @lc code=end

10.正则表达式匹配

/*
 * @lc app=leetcode.cn id=10 lang=typescript
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
function isMatch(s: string, p: string): boolean {

};
// @lc code=end

11.盛最多水的容器

/*
 * @lc app=leetcode.cn id=11 lang=typescript
 *
 * [11] 盛最多水的容器
 */

// @lc code=start
/**
在一个非负整数数组中，找到两个数，使得它们的乘积最大，返回乘积的最大值。
@param height 非负整数数组
@return 乘积的最大值
*/
function maxArea(height: number[]): number {
  let max = 0 // 存储最大面积
  let area = 0 // 存储当前面积
  let left = 0 // 左指针
  let right = height.length - 1 // 右指针
  while (left < right) { // 左右指针相向而行，直到相遇
    if (height[left] < height[right]) { // 如果左边的高度小于右边的高度
      area = (right - left) * height[left] // 计算当前面积
      left++ // 左指针右移
    } else { // 否则，右边的高度小于左边的高度
      area = (right - left) * height[right] // 计算当前面积
      right-- // 右指针左移
    }
    max = Math.max(area, max) // 更新最大面积
  }
  return max // 返回最大面积
}
// @lc code=end

15.三数之和

/*
 * @lc app=leetcode.cn id=15 lang=typescript
 *
 * [15] 三数之和
 */

// @lc code=start
/**
在一个整数数组中，找到所有三个数的和为 0 的三元组。
@param nums 整数数组
@return 所有三个数的和为 0 的三元组
*/
function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b) // 将数组排序
  const res: number[][] = [] // 存储结果
  for (let i = 0; i < nums.length; i++) { // 枚举第一个数，从左往右扫描
    let low = i + 1 // 左指针
    let high = nums.length - 1 // 右指针
    while (low < high) { // 左右指针相向而行，直到相遇
      const sum = nums[i] + nums[low] + nums[high] // 计算三个数的和
      if (sum < 0) { // 如果和小于 0，左指针向右移动
        low++
      } else if (sum > 0) { // 如果和大于 0，右指针向左移动
        high--
      } else { // 如果和等于 0，将三个数加入结果数组中
        res.push([nums[i], nums[low], nums[high]])
        while (nums[low + 1] === nums[low]) low++ // 左指针向右跳过重复元素
        while (nums[high - 1] === nums[high]) high-- // 右指针向左跳过重复元素
        low++ // 左指针右移
        high-- // 右指针左移
      }
    }
    while (nums[i + 1] === nums[i]) i++ // 跳过重复元素
  }
  return res // 返回结果数组
}
// @lc code=end

16.最接近的三数之和

/*
 * @lc app=leetcode.cn id=16 lang=typescript
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
/**
在一个整数数组中，找到三个数的和最接近目标值，返回这三个数的和。
@param nums 整数数组
@param target 目标值
@return 和最接近目标值的三个数的和
*/
function threeSumClosest(nums: number[], target: number): number {
  nums.sort((a, b) => a - b) // 将数组排序
  let closest = Infinity // 存储和最接近目标值的三个数的和
  for (let i = 0; i < nums.length - 2; i++) { // 枚举第一个数，从左往右扫描
    let left = i + 1 // 左指针
    let right = nums.length - 1 // 右指针
    while (left < right) { // 左右指针相向而行，直到相遇
      const sum = nums[i] + nums[left] + nums[right] // 计算三个数的和
      if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum // 更新和最接近目标值的三个数的和
      if (sum > target) { // 如果当前和大于目标值，右指针向左移动
        right--
      } else { // 否则，左指针向右移动
        left++
      }
    }
  }
  return closest; // 返回和最接近目标值的三个数的和
};
// @lc code=end

17.电话号码的字母组合

/*
 * @lc app=leetcode.cn id=17 lang=typescript
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
/**
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
@param digits 给定的仅包含数字的字符串
@return 返回所有能表示的字母组合
*/
function letterCombinations(digits: string): string[] {
  if (digits.length === 0) return [] // 如果字符串长度为 0，直接返回空数组
  const res: string[] = [] // 存储结果
  const values = { // 数字和字母的映射表
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  }
  const map = new Map<string, string>(Object.entries(values)) // 将映射表转换为 Map 对象
  // 递归
  const dfs = (start: number, str: string): void => {
    if (start === digits.length) { // 如果搜索到字符串末尾，将当前结果加入到 res 中
      res.push(str)
      return
    }
    if (map.has(digits[start])) { // 如果当前数字可以映射到字母
      for (const c of map.get(digits[start]) as string) {
        dfs(start + 1, str + c) // 递归搜索下一个数字的映射字母
      }
    }
  }
  dfs(0, '') // 从第一个数字开始搜索
  return res // 返回结果数组
};
// @lc code=end

19.删除链表的倒数第-n-个结点

/*
 * @lc app=leetcode.cn id=19 lang=typescript
 *
 * [19] 删除链表的倒数第 N 个结点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let slow = head;
  let fast = head;
  // 快指针先走n步
  while (n--) {
    fast = fast.next;
  }
  // 针对head = [1], n = 1
  if (!fast) return head.next
  // 快慢指针一起走，快指针走到尽头时候慢指针的下一个结点就是要删除的结点
  while (fast.next) {
    fast = fast.next
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
};
// @lc code=end

20.有效的括号

/*
 * @lc app=leetcode.cn id=20 lang=typescript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
判断一个字符串中的括号是否匹配。
@param s 给定字符串
@return 如果括号匹配，则返回 true，否则返回 false。
*/
function isValid(s: string): boolean {
  // 如果字符串长度为奇数，直接返回 false
  if (s.length & 1) return false;
  const stack: string[] = []; // 创建一个栈
  for (const c of s) { // 遍历字符串中的每一个字符
    if (c === '(') { // 如果是左括号，将其对应的右括号入栈
      stack.push(')');
    } else if (c === '[') {
      stack.push(']');
    } else if (c === '{') {
      stack.push('}');
    } else { // 如果是右括号
      if (c !== stack.pop()) return false; // 如果栈顶元素不是对应的左括号，返回 false
    }
  }
  return stack.length === 0; // 如果栈为空，则说明所有的括号都匹配上了，返回 true，否则返回 false
};
// @lc code=end

21.合并两个有序链表

/*
 * @lc app=leetcode.cn id=21 lang=typescript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
// 递归的方法更简洁，但如果链表很长，递归深度可能会导致栈溢出。因此，迭代方法是更好的选择。

/**
合并两个有序链表。
@param l1 第一个有序链表
@param l2 第二个有序链表
@return 合并后的有序链表
*/
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummyHead: ListNode | null = new ListNode(); // 创建哑节点
  let curr: ListNode | null = dummyHead; // 创建指针，初始指向哑节点
  while (l1 && l2) { // 如果两个链表都不为空
    if (l1.val < l2.val) { // 如果 l1 的值小于 l2 的值
      curr.next = l1; // 将 l1 添加到新链表中
      l1 = l1.next; // l1 指针往后移动
    } else {
      curr.next = l2; // 将 l2 添加到新链表中
      l2 = l2.next; // l2 指针往后移动
    }
    curr = curr.next; // 新链表指针往后移动
  }
  curr.next = l1 || l2; // 将剩余的节点添加到新链表中
  return dummyHead.next; // 返回新链表的头节点
};
function mergeTwoLists2(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if(!list1) return list2;
  if(!list2) return list1;
  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
};


// @lc code=end

22.括号生成

/*
 * @lc app=leetcode.cn id=22 lang=typescript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
给定一个正整数 n，生成所有由 n 对括号组成的合法组合。
@param n 正整数
@returns 由 n 对括号组成的所有合法组合
*/
function generateParenthesis(n: number): string[] {
  const res: string[] = []; // 用于存储所有的合法组合
  /**
  深度优先遍历函数。
  @param l 左括号的数量
  @param r 右括号的数量
  @param s 当前的组合
  */
  const dfs = (l: number, r: number, s: string) => {
    if (s.length === 2 * n) { // 如果当前组合的长度等于 2n，说明已经生成了一个合法组合，将其加入结果中
      res.push(s);
      return;
    }
    if (l < n) { // 如果左括号的数量小于 n，可以继续添加左括号
      dfs(l + 1, r, s + '(');
    }
    if (r < l) { // 如果右括号的数量小于左括号的数量，可以继续添加右括号
      dfs(l, r + 1, s + ')');
    }
  };
  dfs(0, 0, ''); // 从初始状态开始深度优先遍历
  return res; // 返回所有的合法组合
};

// @lc code=end

23.合并k个升序链表

/*
 * @lc app=leetcode.cn id=23 lang=typescript
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
/**
合并 k 个有序链表。
@param lists k 个有序链表
@returns 合并后的有序链表
*/
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  return helper(lists, 0, lists.length - 1); // 从第一个链表开始，合并所有的有序链表
};
// 定义递归函数，用于合并 lists 数组中从 start 到 end 的所有有序链表
function helper(lists: Array<ListNode | null>, start: number, end: number): ListNode | null {
  if (start === end) { // 如果只有一个链表，直接返回该链表
    return lists[start];
  } else if (start < end) {
    const mid = Math.floor((end + start) / 2); // 将 lists 数组分成两半
    const left = helper(lists, start, mid); // 递归合并左半部分的所有链表
    const right = helper(lists, mid + 1, end); // 递归合并右半部分的所有链表
    return mergeTwoLists(left, right); // 合并左右两部分的链表
  } else {
    return null;
  }
}
// 定义合并两个有序链表的函数
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}
// @lc code=end

31.下一个排列

/*
 * @lc app=leetcode.cn id=31 lang=typescript
 *
 * [31] 下一个排列
 */

// @lc code=start
/**
 Do not return anything, modify nums in-place instead.
 */            //pivot     
// E.g. [7, 2, 3, 1, 5, 4, 3, 2, 0]->[7, 2, 3, 2, 5, 4, 3, 1, 0]->[7, 2, 3, 2, 0, 1, 3, 4, 5]
// 解题思路：
// 1、从后往前找到第一个从后往前看不是从小到大的索引i
// 2、从后往前找到比i大的索引j,交换i、j的值
// 3、然后反转i+1之后的值
function nextPermutation(nums: number[]): void {
  let i = nums.length - 2;
  // 找到基准索引i,这里例子的位置是1，这里确保i后面的数据是从大到小排序了
  while (i >= 0 && nums[i + 1] <= nums[i]) {
    i--;
  }
  // 从后往前找，找到基准后面的数字比基准大的索引j，然后交互i,j位置
  if (i >= 0) {
    let j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  console.log(nums)
  // 基准索引后的反转i+1之后的值
  reverse(nums, i + 1);
}

function reverse(nums: number[], start: number): void {
  let i = start, j = nums.length - 1;
  while (i < j) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
    i++;
    j--;
  }
}

function reverse(nums: number[], start: number): void {
  let i = start, j = nums.length - 1;
  while (i < j) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
    i++;
    j--;
  }
}

// @lc code=end

32.最长有效括号

/*
 * @lc app=leetcode.cn id=32 lang=typescript
 *
 * [32] 最长有效括号
 */
// "()(()"
// @lc code=start
// 解题思路：
// 本题可以使用栈来解决。我们遍历整个字符串，如果遇到左括号，就将其下标压入栈中；
// 如果遇到右括号，就弹出栈顶元素表示匹配了一个左括号。如果弹出后栈为空，说明当前右括号没有匹配的左括号，需要将其下标压入栈中。
// 我们每次匹配完成后，计算当前右括号下标与栈顶元素下标之间的距离，更新最长有效括号的长度。最后返回最长有效括号的长度。
function longestValidParentheses(s: string): number {
  if (s.length <= 1) return 0; // 如果字符串长度小于等于1，直接返回0
  let longest = 0; // 最长有效括号的长度
  let stack = [-1]; // 栈中起始放入-1，方便计算距离
  for (let i = 0; i < s.length; i++) {
    let char = s[i];
    if (char === '(') { // 如果是左括号，将其下标压入栈中
      stack.push(i);
      continue;
    }
    stack.pop(); // 如果是右括号，弹出栈顶元素
    if (!stack.length) stack.push(i); // 如果弹出后栈为空，将当前下标压入栈中
    else longest = Math.max((i - stack[stack.length - 1]), longest); // 计算距离，更新最长有效括号
  }
  return longest; // 返回最长有效括号的长度
};
// @lc code=end

33.搜索旋转排序数组

/*
 * @lc app=leetcode.cn id=33 lang=typescript
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
function search(nums: number[], target: number): number {
  return nums.findIndex((item)=> item===target);
};

function search2(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    }

    // 当将旋转数组分为两半时，必须有一半是有序的。
    // 检查左半边是否有序。
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target <= nums[mid]) {
        // 目标在左边
        right = mid - 1;

      } else {
        // 目标在右边
        left = mid + 1;
      }
    }

    // 右半边有序。
    else {
      if (nums[mid] <= target && target <= nums[right]) {
        // 目标在右边
        left = mid + 1;

      } else {
        // 目标在左边
        right = mid - 1;
      }
    }
  }

  return -1;
};
// 这个函数使用二分查找来在旋转数组中查找目标值。我们将数组分成两半，并检查哪一半是有序的，然后在有序的那一半中查找目标值。
// 如果找到了目标值，就返回其下标。如果没找到，就返回 - 1。
// @lc code=end

34.在排序数组中查找元素的第一个和最后一个位置

/*
 * @lc app=leetcode.cn id=34 lang=typescript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
function searchRange(nums: number[], target: number): number[] {
  let minIndex = binarySearch(nums, target, false);
  if (minIndex !== -1) {
    let maxIndex = binarySearch(nums, target, true);
    return [minIndex, maxIndex];
  }
  return [-1, -1];
}

// 使用标准的二分查找算法来查找目标值的最小或最大下标。
// findMax 参数指示函数是否要查找最大下标
// 函数返回目标值的最小或最大下标，或者 - 1（如果目标值不在数组中）
function binarySearch(nums: number[], key: number, findMax: boolean) {
  let keyIndex = -1;

  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // 使用 Math.floor(left + (right - left) / 2) 而不是 Math.floor((right +left) / 2) 可避免溢出
    let middle = Math.floor(left + (right - left) / 2);

    if (key > nums[middle]) {
      left = middle + 1;
    } else if (key < nums[middle]) {
      right = middle - 1;
    } else {
      // 找到目标值
      keyIndex = middle;

      if (findMax) {
        // true 表示要找最大值
        left = middle + 1;
      } else {
        // false 表示要找最小值
        right = middle - 1;
      }
    }
  }

  return keyIndex;
}
// @lc code=end

39.组合总和

/*
 * @lc app=leetcode.cn id=34 lang=typescript
 *
 * [3] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
function combinationSum(candidates: number[], target: number): number[][] {
    const res: number[][] = []
    candidates.sort((a,b)=> a-b)
    const backTrace=(target:number,state:number[],start:number)=> {
        if(target===0) {
            res.push(state)
            return
        }
        for(let i = start;i<candidates.length;i++) {
            const c = candidates[i]
            // 这是因为数组已排序，后边元素更大，子集和一定超过 target
            if (target - c < 0) {
                break;
            }
            backTrace(target - c,[...state,c],i)
        }
 
    }
    backTrace(target,[],0)
    return res
};
// @lc code=end

42.接雨水

/*
 * @lc app=leetcode.cn id=42 lang=typescript
 *
 * [42] 接雨水
 */

// @lc code=start
function trap(height: number[]): number {
  let L = 0;
  let R = height.length - 1;
  let leftHeight = 0;
  let rightHeight = 0;
  let res = 0;
  while (L < R) {
    if (height[L] < height[R]) {
      leftHeight = Math.max(leftHeight, height[L]);
      res += leftHeight - height[L];
      L++;
    } else {
      // 右边高度小，看右边
      rightHeight = Math.max(rightHeight, height[R]);
      res += rightHeight - height[R];
      R--;
    }
  }
  return res;
};
// @lc code=end

46.全排列

/*
 * @lc app=leetcode.cn id=46 lang=typescript
 *
 * [46] 全排列
 */

// @lc code=start
function permute(nums: number[]): number[][] {
  const res: number[][] = []; // 存储结果的数组
  const dfs = (set: Set<number>) => { // 递归
    if (set.size == nums.length) { // 如果当前排列的长度等于原数组的长度，就将它加入结果数组中
      res.push(Array.from(set));
      return;
    }
    for (let i = 0; i < nums.length; i++) { // 遍历原数组中的每个数
      if (set.has(nums[i])) continue; // 如果当前排列中已经包含该数，就跳过它
      set.add(nums[i]); // 将该数加入当前排列中
      dfs(set); // 递归生成排列
      set.delete(nums[i]); // 回溯到上一级递归，将该数从当前排列中删除
    }
  }
  dfs(new Set()); // 从空排列开始生成所有排列
  return res; // 返回结果数组
};


// @lc code=end

48.旋转图像

/*
 * @lc app=leetcode.cn id=48 lang=typescript
 *
 * [48] 旋转图像
 */

// @lc code=start
/**
 Do not return anything, modify matrix in-place instead.
 */
function rotate(matrix: number[][]): void {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = i; j < matrix[0].length; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (let m of matrix) {
    m.reverse();
  }
};
// @lc code=end

49.字母异位词分组

/*
 * @lc app=leetcode.cn id=49 lang=typescript
 *
 * [49] 字母异位词分组
 */

// @lc code=start
function groupAnagrams(strs: string[]): string[][] {
  if (strs.length === 1) return [strs]
  const map = new Map()
  for (const str of strs) {
    const s = str.split('').sort().join('') // 将字符串按字母顺序排序，得到一个唯一的标识符 s
    if (map.has(s)) map.set(s, [...map.get(s)!, str]) // 如果 map 中已经有 s 对应的字符串数组，则将当前字符串添加到该数组中
    else map.set(s, [str]) // 否则，创建一个新的字符串数组，并将当前字符串添加到其中

  }
  return Array.from(map.values()) // 将 map 中的所有字符串数组转换为一个二维数组，并返回
};
// @lc code=end

53.最大子数组和

/*
 * @lc app=leetcode.cn id=53 lang=typescript
 *
 * [53] 最大子数组和
 */

// @lc code=start
function maxSubArray(nums: number[]): number {
  let max = nums[0]; // 初始化最大子序和为数组的第一个元素
  for (let i = 1; i < nums.length; i++) { // 从第二个元素开始遍历数组
    // 计算以当前元素为结尾的最大子序和，Math.max(0, nums[i - 1])巧妙地将子数组前缀为负数剔除
    nums[i] = Math.max(0, nums[i - 1]) + nums[i]; 
    // 如果当前最大子序和大于之前的最大子序和，则更新最大子序和
    if (nums[i] > max) { 
      max = nums[i];
    }
  }
  return max; // 返回最大子序和
};

// function maxSubArray2(nums: number[]): number {
//   const n = nums.length;
//   let curSum = nums[0];
//   let maxSum = nums[0];
//   for (let i = 1; i < n; i++) {
//     curSum = Math.max(nums[i], curSum + nums[i]);
//     maxSum = Math.max(maxSum, curSum);
//   }
//   return maxSum;
// };
// @lc code=end

55.跳跃游戏

/*
 * @lc app=leetcode.cn id=55 lang=typescript
 *
 * [55] 跳跃游戏
 */

// @lc code=start
function canJump(nums: number[]): boolean {
  let idx = 0; // 当前索引
  let max = 0; // 最远可到达的索引
  let target = nums.length - 1; // 目标索引为最后一个元素的索引
  while (idx < nums.length) { // 遍历数组
    max = Math.max(max, idx + nums[idx]); // 更新最远可到达的索引
    if (max >= target) { // 如果最远可到达的索引大于等于目标索引，则可以到达
      return true;
    }
    if (max <= idx && nums[idx] === 0) { // 如果最远可到达的索引小于等于当前索引且当前元素为0，则无法继续跳跃
      return false;
    }
    idx++; // 继续跳跃
  }
  return false; // 遍历完数组后仍无法到达目标索引，返回false
};
// @lc code=end

56.合并区间

/*
 * @lc app=leetcode.cn id=56 lang=typescript
 *
 * [56] 合并区间
 */

// @lc code=start
function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]); // 按照起始点从小到大排序
  const res: number[][] = []; // 初始化结果数组
  for (let i = 1; i < intervals.length; i++) { // 遍历排序后的数组
    if (intervals[i][0] <= intervals[i - 1][1]) { // 如果当前区间与前一个区间有重叠
      const max = Math.max(intervals[i - 1][1], intervals[i][1]); // 合并区间
      intervals[i] = [intervals[i - 1][0], max]; // 用合并后的区间替换当前区间
    } else { // 如果当前区间与前一个区间没有重叠
      res.push(intervals[i - 1]); // 将前一个区间加入结果数组
    }
  }
  res.push(intervals[intervals.length - 1]); // 将最后一个区间加入结果数组
  return res; // 返回结果数组
};

function merge2(intervals: number[][]): number[][] {
  if (!intervals.length) return intervals; // 如果输入数组为空，则直接返回
  intervals.sort((a, b) => a[0] - b[0]); // 按照起始点从小到大排序
  let prev = intervals[0]; // 初始化前一个区间为第一个区间
  const res: number[][] = [prev]; // 初始化结果数组为第一个区间

  for (const cur of intervals) { // 遍历剩余的区间
    if (cur[0] <= prev[1]) { // 如果当前区间与前一个区间有重叠
      prev[1] = Math.max(prev[1], cur[1]); // 合并区间
    } else { // 如果当前区间与前一个区间没有重叠
      res.push(cur); // 将当前区间加入结果数组
      prev = cur; // 将当前区间设为前一个区间
    }
  }
  return res; // 返回结果数组
};
// @lc code=end

62.不同路径

/*
 * @lc app=leetcode.cn id=62 lang=typescript
 *
 * [62] 不同路径
 */

// @lc code=start
function uniquePaths(m: number, n: number): number {
  // 创建一个 m 行 n 列的二维数组 dp，所有元素初始化为 0
  const dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0))

  // 第一列的所有单元格只有一条唯一的路径，所以将它们初始化为 1
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }

  // 第一行的所有单元格只有一条唯一的路径，所以将它们初始化为 1
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1
  }

  // 遍历剩余单元格，计算每个单元格的唯一路径数
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 唯一路径数等于上面单元格的路径数加上左侧单元格的路径数
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }

  // 返回右下角单元格的唯一路径数
  return dp[m - 1][n - 1]
};
// @lc code=end

63.不同路径-ii

/*
 * @lc app=leetcode.cn id=63 lang=typescript
 *
 * [63] 不同路径 II
 */

// @lc code=start
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length  // 获取网格的行数
  const n = obstacleGrid[0].length  // 获取网格的列数

  // 检查左上角和右下角是否有障碍物，若有则直接返回0
  if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) {
    return 0
  }

  // 遍历网格中的每个单元格，并根据其周围的障碍物和空地计算到达该单元格的唯一路径数
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 如果当前单元格是起点，将它的值设为1
      if (i === 0 && j === 0) {
        obstacleGrid[i][j] = 1
        continue
      }

      // 如果当前单元格是障碍物，将它的值设为0
      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0
        continue
      }

      // 如果当前单元格在第一行，将它的值设为左侧单元格的值
      if (i === 0) {
        obstacleGrid[i][j] = obstacleGrid[i][j - 1]
        continue
      }

      // 如果当前单元格在第一列，将它的值设为上面单元格的值
      if (j === 0) {
        obstacleGrid[i][j] = obstacleGrid[i - 1][j]
        continue
      }

      // 对于其他单元格，它的值等于上面单元格的值加上左侧单元格的值，除非该单元格是障碍物，那么将它的值设为0
      obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
    }
  }

  // 返回网格右下角的值，即为唯一路径数
  return obstacleGrid[m - 1][n - 1]

// @lc code=end

64.最小路径和

/*
 * @lc app=leetcode.cn id=64 lang=typescript
 *
 * [64] 最小路径和
 */

// @lc code=start
function minPathSum(grid: number[][]): number {
  const m = grid.length  // 获取矩阵的行数
  const n = grid[0].length  // 获取矩阵的列数

  // 将第一列的单元格最小路径和的值计算出来
  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0]
  }

  // 将第一行的单元格最小路径和的值计算出来
  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j - 1]
  }

  // 遍历除第一行和第一列以外的所有单元格
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 计算当前单元格的最小路径和，即它本身的值加上它上面和左侧单元格中的最小值
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
    }
  }

  // 返回矩阵右下角单元格的值，即为从左上角到右下角的最小路径和
  return grid[m - 1][n - 1]
}
// @lc code=end

67.二进制求和

/*
 * @lc app=leetcode.cn id=67 lang=typescript
 *
 * [67] 二进制求和
 */

// @lc code=start
function addBinary(a: string, b: string): string {
  return (BigInt(`0B${a}`) + BigInt(`0B${b}`)).toString(2)
};
// @lc code=end

70.爬楼梯

/*
 * @lc app=leetcode.cn id=70 lang=typescript
 *
 * [70] 爬楼梯
 */

// @lc code=start
function climbStairs(n: number): number {
  const dp: number[] = [0, 1, 2] // 初始化dp数组
  for (let i = 3; i <= n; i++) { // 从第三个数开始计算
    dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
  }
  return dp[n]; // 返回结果
};

function climbStairs2(n: number): number {
  let pre = 0; // 初始化前一个数
  let cur = 1; // 初始化当前数
  for (let i = 1; i <= n; i++) { // 从第二个数开始计算
    [pre, cur] = [cur, cur + pre] // 状态转移方程
  }
  return cur; // 返回结果
};

// 斐波那契数列
const cache = new Map<number, number>()
function fib(n: number): number {
  if (n < 2) {
    return n
  }
  if (cache.has(n)) {  // 如果缓存中已经存在当前要计算的斐波那契数列的值，则直接返回缓存中的值
    return cache.get(n)!
  }
  // 否则进行递归计算，并将计算结果存入缓存中
  const result = fib(n - 1) + fib(n - 2)
  cache.set(n, result)
  return result
};
// @lc code=end

72.编辑距离

/*
 * @lc app=leetcode.cn id=72 lang=typescript
 *
 * [72] 编辑距离
 */

// @lc code=start
function minDistance(word1: string, word2: string): number {

};
// @lc code=end

75.颜色分类

/*
 * @lc app=leetcode.cn id=75 lang=typescript
 *
 * [75] 颜色分类
 */

// @lc code=start
/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
  let left = 0 // 定义左指针
  let right = nums.length - 1 // 定义右指针
  let i = 0 // 定义遍历指针
  while (i <= right) { // 遍历数组
    if (nums[i] === 0) { // 如果当前元素是0
      [nums[i], nums[left]] = [nums[left], nums[i]] // 将当前元素与左指针指向的元素交换
      left++ // 左指针向右移动一位
      i++ // 遍历指针向右移动一位
    } else if (nums[i] === 2) { // 如果当前元素是2
      [nums[i], nums[right]] = [nums[right], nums[i]] // 将当前元素与右指针指向的元素交换
      right-- // 右指针向左移动一位
    } else { // 如果当前元素是1
      i++ // 遍历指针向右移动一位
    }
  }
};
// @lc code=end

78.子集

/*
 * @lc app=leetcode.cn id=78 lang=typescript
 *
 * [78] 子集
 */

// @lc code=start
function subsets(nums: number[]): number[][] {
  const res: number[][] = [] 
  const dfs = (arr: number[], k: number) => { 
    res.push(arr) 
    for (let i = k; i < nums.length; i++) { // 从k开始遍历剩余的元素
      dfs([...arr, nums[i]], i + 1) // 以当前数组为基础，加入一个新元素，同时记录i+1下一次递归的k值，然后继续搜索剩余元素
    }
  }
  dfs([], 0) // 从空数组开始搜索
  return res 
};
// @lc code=end

79.单词搜索

/*
 * @lc app=leetcode.cn id=79 lang=typescript
 *
 * [79] 单词搜索
 */

// @lc code=start
function exist(board: string[][], word: string): boolean {
  let result = false
  const check = (r: number, c: number, i:number) => {
    if (!result) {
      if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return  // 超出边界
      if (board[r][c] !== word[i]) return // 不存在符合路径
      if (i === word.length - 1) { // 最后一个字母也相等意味着发现存在正确路径
        result = true
        return
      }
      board[r][c] = '#'  // 标记走过的路径
      //往四个方向走
      check(r + 1, c, i + 1)
      check(r - 1, c, i + 1)
      check(r, c + 1, i + 1)
      check(r, c -1 , i + 1)

      board[r][c] = word[i] // 回溯重置路径，否则会影响下一次迭代符合board[i][j] === word[0]) 的结果
    }

    
  }
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      // 找到一个开始的位置
      if (board[i][j] === word[0]) {
        // 往四个方向递归
        check(i, j, 0)
        if (result) return result
      }
    }
    
  }
  return result
};
// @lc code=end

94.二叉树的中序遍历

/*
 * @lc app=leetcode.cn id=94 lang=typescript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
/**
 * 中序遍历给定二叉树（递归实现）
 * @param root 给定二叉树的根节点
 * @returns 遍历结果数组
 */
function inorderTraversal5(root: TreeNode | null): number[] {
  if (!root) return [] // 如果根节点为空，直接返回空数组
  const res: number[] = [] // 定义结果数组
  const dfs = (node: TreeNode | null) => { // 定义深度优先搜索函数
    if (!node) return // 如果当前节点为空，直接返回
    node.left && dfs(node.left) // 遍历左子树
    res.push(node.val) // 将当前节点的值加入结果数组
    node.right && dfs(node.right) // 遍历右子树
  }
  dfs(root) // 从根节点开始遍历
  return res // 返回结果数组
};

/**
 * 中序遍历给定二叉树（递归实现）
 * @param root 给定二叉树的根节点
 * @returns 遍历结果数组
 */
function inorderTraversal2(root: TreeNode | null): number[] {
  if (root === null) return []; // 如果根节点为空，直接返回空数组
  return [...inorderTraversal2(root.left), root.val, ...inorderTraversal2(root.right)]; // 返回左子树的遍历结果、当前节点的值、右子树的遍历结果的拼接数组
};

/**
 * 中序遍历给定二叉树（迭代实现）
 * @param root 给定二叉树的根节点
 * @returns 遍历结果数组
 */
function inorderTraversal3(root: TreeNode | null): number[] {
  const stack: TreeNode[] = []; // 定义栈
  const res: number[] = []; // 定义结果数组

  while (root || stack.length) { // 当根节点不为空或栈不为空时循环
    if (root) { // 如果根节点不为空
      stack.push(root); // 将根节点压入栈
      root = root.left; // 遍历左子树
    } else { // 如果根节点为空
      root = stack.pop(); // 弹出栈顶元素
      res.push(root.val); // 将栈顶元素的值加入结果数组
      root = root.right; // 遍历右子树
    }
  }

  return res; // 返回结果数组
}


// @lc code=end

98.验证二叉搜索树

/*
 * @lc app=leetcode.cn id=98 lang=typescript
 *
 * [98] 验证二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
// 利用中序遍历
function isValidBST(root: TreeNode | null): boolean {
  const inOrder = (node: TreeNode | null):number[] => {
    if (!node) return []
    return [...inOrder(node.left),node.val,...inOrder(node.right)]
  }
  // 中序遍历后的数组如果是二叉搜索树应该是从小到大排序的
  const sortedArr = inOrder(root)
  for (let i = 0; i < sortedArr.length; i++) {
    if (sortedArr[i + 1] <= sortedArr[i]) {
      return false
    }
  }
  return true
};

// 递归 左边存在比他小的值且比根节点小，右边存在比他大的值且比根节点大
// function isValidBST2(root, min = null, max = null) {
//   if (!root) return true;
//   if (min && root.val <= min.val) return false;
//   if (max && root.val >= max.val) return false;
//   return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
// };

// @lc code=end

101.对称二叉树

/*
 * @lc app=leetcode.cn id=101 lang=typescript
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
// 递归
function isSymmetric(root: TreeNode | null): boolean {
  if (!root) return true
  const dfs = (left: TreeNode | null, right: TreeNode | null):boolean => {
    // 都为null则对称
    if (!left && !right) return true
    if (!left || !right || left.val !== right.val) return false
    return dfs(left.left,right.right) && dfs(left.right,right.left)
  }
  return dfs(root.left, root.right)
};
// 迭代
function isSymmetric2(root: TreeNode | null): boolean {
  if (!root) return true; // 如果根节点为空，直接返回 true
  const queue: TreeNode[] = [root.left, root.right]; // 定义队列，并将左右子节点依次加入队列中
  while (queue.length) { // 当队列不为空时循环
    const left = queue.shift()!; // 取出队列中的两个节点
    const right = queue.shift()!;
    if (!left && !right) continue; // 如果两个节点都为空，则继续循环
    if (!left || !right || left.val !== right.val) return false; // 如果两个节点有一个为空，或者它们的值不相等，则返回 false
    queue.push(left.left, right.right); // 将左节点的左子节点和右节点的右子节点依次加入队列中
    queue.push(left.right, right.left); // 将左节点的右子节点和右节点的左子节点依次加入队列中
  }
  return true; // 如果循环结束后没有返回 false，则表示二叉树是对称的，返回 true
}
// @lc code=end

102.二叉树的层序遍历

/*
 * @lc app=leetcode.cn id=102 lang=typescript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []; // 如果根节点为空，直接返回空数组
  const res: number[][] = []; // 定义结果数组
  const dfs = (root: TreeNode | null, level: number) => { // 定义深度优先搜索函数
    if (!root) return; // 如果当前节点为空，直接返回
    if (!res[level]) {
      res.push([root.val]); // 如果当前层的数组不存在，则创建一个新的数组
    } else {
      res[level].push(root.val); // 如果当前层的数组已经存在，则在数组末尾添加当前节点的值
    }
    root.left && dfs(root.left, level + 1); // 遍历左子树
    root.right && dfs(root.right, level + 1); // 遍历右子树
  }
  dfs(root, 0); // 从根节点开始遍历
  return res; // 返回结果数组
}

function levelOrder2(root: TreeNode | null): number[][] {
  if (!root) return []; // 如果根节点为空，直接返回空数组
  const res: number[][] = []; // 定义结果数组
  let level = 0; // 定义当前层数
  let queue = [root]; // 定义队列，并将根节点加入队列中
  while (queue.length) { // 当队列不为空时循环
    let size = queue.length; // 记录当前层的节点个数
    res.push([]); // 创建一个新的数组，用于存储当前层的节点值
    while (size--) { // 循环处理当前层的节点
      let node = queue.shift()!; // 取出队列中的第一个节点
      res[level].push(node.val); // 将节点的值加入当前层对应的数组中
      node.left && queue.push(node.left); // 如果节点有左子节点，则将左子节点加入队列中
      node.right && queue.push(node.right); // 如果节点有右子节点，则将右子节点加入队列中
    }
    level++; // 处理下一层的节点
  }
  return res; // 返回结果数组
}
// @lc code=end

104.二叉树的最大深度

/*
 * @lc app=leetcode.cn id=104 lang=typescript
 *
 * [104] 二叉树的最大深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0; // 如果根节点为空，直接返回 0
  let max = 0; // 定义变量 max，表示当前已经遍历到的最大深度
  const dfs = (node: TreeNode | null, depth: number) => { // 定义深度优先搜索函数
    if (!node) return; // 如果当前节点为空，直接返回
    max = Math.max(max, depth); // 将当前节点的深度与 max 进行比较，取较大值作为新的 max
    node.left && dfs(node.left, depth + 1); // 遍历左子树
    node.right && dfs(node.right, depth + 1); // 遍历右子树
  }
  dfs(root, 1); // 从根节点开始遍历，初始深度为 1
  return max; // 返回最大深度
}

function maxDepth2(root: TreeNode | null): number {
  if (!root) return 0; // 如果根节点为空，直接返回 0
  let depth = 0; // 定义变量 depth，表示当前已经遍历到的深度
  let queue: TreeNode[] = [root]; // 定义队列，并将根节点加入队列中
  while (queue.length) { // 当队列不为空时循环
    depth++; // 处理下一层的节点，深度加 1
    let size = queue.length; // 记录当前层的节点个数
    while (size--) { // 循环处理当前层的节点
      let node = queue.shift()!; // 取出队列中的第一个节点
      node.left && queue.push(node.left); // 如果节点有左子节点，则将左子节点加入队列中
      node.right && queue.push(node.right); // 如果节点有右子节点，则将右子节点加入队列中
    }
  }
  return depth; // 返回最大深度
}
// @lc code=end

105.从前序与中序遍历序列构造二叉树

/*
 * @lc app=leetcode.cn id=105 lang=typescript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree1(preorder: number[], inorder: number[]): TreeNode | null {
  if (!preorder.length || !inorder.length) return null; // 如果前序遍历或中序遍历为空，直接返回 null
  const root = new TreeNode(preorder[0]); // 取出前序遍历的第一个节点作为根节点
  const mid = inorder.indexOf(preorder[0]); // 在中序遍历中找到根节点的位置
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid)); // 递归构建左子树
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1)); // 递归构建右子树
  return root; // 返回根节点
}


// @lc code=end

114.二叉树展开为链表

/*
 * @lc app=leetcode.cn id=114 lang=typescript
 *
 * [114] 二叉树展开为链表
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/**
 Do not return anything, modify root in-place instead.
 */
function flatten(root: TreeNode | null): void {
  if (!root) return; // 空节点直接返回
  flatten(root.left); // 递归处理左子树
  flatten(root.right); // 递归处理右子树
  const left = root.left; // 记录左子树
  const right = root.right; // 记录右子树
  root.left = null; // 将左子树置为空
  root.right = left; // 将左子树插入到当前节点的右子树
  let p = root;
  while (p.right) { // 找到当前链表的最后一个节点
    p = p.right;
  }
  p.right = right; // 将右子树插入到当前链表的最后一个节点之后
}
// @lc code=end

121.买卖股票的最佳时机

/*
 * @lc app=leetcode.cn id=121 lang=typescript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
function maxProfit(prices: number[]): number {
  let profit = 0; // 初始最大利润为 0
  let min = prices[0]; // 初始最低价格为第一天的价格
  for (let i = 1; i < prices.length; i++) { // 遍历每一天的价格
    if (min > prices[i]) { // 如果当前价格比最低价格还低
      min = prices[i]; // 更新最低价格
    } else if (prices[i] - min > profit) { // 如果当前价格减去最低价格的差值比当前最大利润更大
      profit = prices[i] - min; // 更新最大利润
    }
  }
  return profit; // 返回最大利润
}

function maxProfit2(prices: number[]): number {
  const n = prices.length
  if(n<2) return 0 //少于两天没有收益
  const dp = Array.from({length:n},()=> [0,0])
  // 第一天不持有
  dp[0][0] = 0
  // 第一天持有
  dp[0][1] = -prices[0]
  for (let i = 1; i < n; i++) {
    // 第i天不持有的最大值等于前一天不持有与前一天持有今天卖出
    dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i-1][0])
    // 第i天持有的最大值等于今天天持有与前一天持有今天不持有今天买入
    dp[i][1] = Math.max(- prices[i], dp[i-1][1])
  }
  // 最后一天最大值为不持有
  return dp[n-1][0]
};
// @lc code=end

124.二叉树中的最大路径和

/*
 * @lc app=leetcode.cn id=124 lang=typescript
 *
 * [124] 二叉树中的最大路径和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxPathSum(root: TreeNode | null): number {
  let max = Number.MIN_SAFE_INTEGER; // 初始化最大路径和为最小安全整数
  function getMaxSum(node) {
    if (!node) return 0; // 空节点的最大路径和为 0
    const leftSum = getMaxSum(node.left); // 递归处理左子树，得到左子树的最大路径和
    const rightSum = getMaxSum(node.right); // 递归处理右子树，得到右子树的最大路径和
    max = Math.max(max, node.val + leftSum + rightSum); // 更新最大路径和
    return Math.max(0, node.val + leftSum, node.val + rightSum); // 返回当前节点的值加上左子树的最大路径和和右子树的最大路径和中的较大值
  }
  getMaxSum(root); // 求解最大路径和
  return max; // 返回最大路径和
}
// @lc code=end

128.最长连续序列

/*
 * @lc app=leetcode.cn id=128 lang=typescript
 *
 * [128] 最长连续序列
 */

// @lc code=start
function longestConsecutive(nums: number[]): number {
  if (!nums.length) return 0;
  const set = new Set(nums);  // 将数组转换为 Set，去重
  let max = 0;  // 记录最长连续序列长度
  for (let num of set) {
    // 如果 num - 1 在 Set 中，说明当前数字已经在某个连续序列中了，跳过本次循环
    if (set.has(num - 1)) continue;
    let currNum = num;  // 记录当前连续序列的起始数字
    let currMax = 1;  // 记录当前连续序列的长度（至少为 1）
    // 循环查找连续序列中的数字
    while (set.has(currNum + 1)) {
      currNum++;  // 当前数字加 1，继续查找下一个数字
      currMax++;  // 连续序列长度加 1
    }
    max = Math.max(max, currMax);  // 更新最长连续序列长度
  }
  return max;
};
// @lc code=end

129.求根节点到叶节点数字之和

/*
 * @lc app=leetcode.cn id=129 lang=typescript
 *
 * [129] 求根节点到叶节点数字之和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
// 字符串拼接 最后+num转为数字
function sumNumbers(root: TreeNode | null): number {
  function traverse(node, num) {
    if (!node) return null; // 空节点返回 null
    num += node.val; // 将当前节点的值加到 num 上
    if (!node.left && !node.right) return +num; // 如果当前节点为叶子节点，则返回当前路径对应的数字
    return traverse(node.left, num) + traverse(node.right, num); // 否则，继续递归处理左子树和右子树
  }
  return traverse(root, ""); // 遍历二叉树
};

// 方法2
function sumNumbers2(root: TreeNode | null): number {
  let dfs = (cur, root) => {
    // 终止条件
    if (!root) return 0;
    // 计算当前节点的值
    cur = cur * 10 + root.val;
    // 找到一条路径，返回路径和
    if (!root.left && !root.right) {
      return cur;
    }
    // 对左右子树递归，求总和
    return dfs(cur, root.left) + dfs(cur, root.right);
  };
  return dfs(0, root);
};
// 方法3
function sumNumbers3(root: TreeNode | null): number {
  if (!root) return null; // 空节点返回 null
  let sum = 0; // 初始化数字之和为 0
  function traverse(node, num) {
    num += node.val; // 将当前节点的值加到 num 上
    if (!node.left && !node.right) sum += +num; // 如果当前节点为叶子节点，则将当前路径对应的数字加到 sum 上
    if (node.left) traverse(node.left, num); // 继续递归处理左子树
    if (node.right) traverse(node.right, num); // 继续递归处理右子树
  }
  traverse(root, ""); // 遍历二叉树
  return sum; // 返回数字之和
};
// @lc code=end

136.只出现一次的数字

/*
 * @lc app=leetcode.cn id=136 lang=typescript
 *
 * [136] 只出现一次的数字
 */

// @lc code=start
/**
* 按位异或操作是一种位运算，它可以对两个二进制数的每一位进行操作。按位异或操作的规则是：

当两个二进制位相同时，结果为0。
当两个二进制位不同时，结果为1。
对于本题中的输入数组，如果一个数字出现两次，
那么它的二进制表示的每一位都是相同的。例如，对于数字2，它的二进制表示是10，
所以它的每一位都是1和0。当我们对两个相同的数字进行按位异或操作时，
它们的二进制表示的每一位都会变成0。因此，这些数字的按位异或操作的结果都是0。

如果我们将所有的数字进行按位异或操作，那么相同的数字将互相抵消，只留下只出现一次的数字。因为只出现一次的数字在按位异或操作中不会被抵消，所以最终的结果将是只出现一次的数字。


*/
function singleNumber(nums: number[]): number {
  let result = 0;
  for (let num of nums) {
    result ^= num;
  }
  return result;
};
// @lc code=end

139.单词拆分

/*
 * @lc app=leetcode.cn id=139 lang=typescript
 *
 * [139] 单词拆分
 */

// @lc code=start
// 广度优先算法
function wordBreak(s: string, wordDict: string[]): boolean {
  if (!wordDict.length) return false // 如果字典为空，则无法拆分，返回 false
  const visited = new Set() // 记录已经访问过的起始位置
  const set = new Set(wordDict) // 将字典中的单词存入 set 中
  const queue: number[] = [0] // 将字符串的起始位置 0 放入队列中
  while (queue.length) { // 当队列非空时循环
    const start = queue.shift() as number // 取出队首元素作为起始位置
    if (!visited.has(start)) { // 如果起始位置没有被访问过
      for (let end = start + 1; end <= s.length; end++) { // 从起始位置向后扫描字符串
        if (set.has(s.slice(start, end))) { // 如果扫描到的字符串在字典中出现
          if (end === s.length) return true // 如果扫描到字符串的末尾，则可以拆分成字典中的单词，返回 true
          queue.push(end) // 否则将扫描到的位置加入队列中，继续向后扫描
        }
      }
      visited.add(start) // 将起始位置标记为已访问过
    }
  }
  return false // 如果队列为空，则说明无法拆分成字典中的单词，返回 false
};


// 动态规划
function wordBreak2(s: string, wordDict: string[]): boolean {
  const n = s.length; // 字符串的长度
  const dp = new Array(n + 1).fill(false); // 创建一个布尔型数组，初始值为 false，长度为字符串长度加 1
  dp[0] = true; // 空字符串可以被拆分成一个空单词，将 dp[0] 置为 true

  for (let i = 1; i <= n; i++) { // 遍历字符串中的每一个位置
    for (let j = 0; j < i; j++) { // 遍历字符串前缀中的每一个位置
      // 如果字符串前 j 个字符可以被拆分成字典中的一个或多个单词，并且剩余的字符 s.slice(j, i) 也在字典中出现
      if (dp[j] && wordDict.includes(s.slice(j, i))) { 
        dp[i] = true; // 则字符串前 i 个字符也可以被拆分成一个或多个字典中的单词
        break; // 因为只需要找到一种拆分方式即可，所以可以直接跳出循环
      }
    }
  }
  return dp[n]; // 如果 dp[n] 为 true，则说明字符串 s 可以被拆分成一个或多个字典中的单词；否则，无法拆分成字典中的单词
}








// @lc code=end

141.环形链表

/*
 * @lc app=leetcode.cn id=141 lang=typescript
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
  let slow = head // 慢指针，每次移动一步
  let fast = head // 快指针，每次移动两步
  while (fast && fast.next) { // 快指针不为空且下一个节点也不为空时继续循环
    slow = slow.next // 慢指针移动一步
    fast = fast.next.next // 快指针移动两步
    while (slow === fast) { // 如果两个指针相遇，则说明链表有环
      return true // 返回 true
    }
  }
  return false // 遍历完整个链表都没有相遇的情况下，说明链表没有环，返回 false
};
// @lc code=end

142.环形链表-ii

/*
 * @lc app=leetcode.cn id=142 lang=typescript
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
  let fast = head; // 快指针，每次移动两步
  let slow = head; // 慢指针，每次移动一步
  while (fast && fast.next) { // 快指针不为空且下一个节点也不为空时继续循环
    fast = fast.next.next; // 快指针移动两步
    slow = slow.next; // 慢指针移动一步
    if (fast === slow) { // 如果两个指针相遇，则说明链表有环
      let p = head; // 定义一个指针 p，指向链表头结点
      while (p !== slow) { // 当 p 和 slow 不相同时，说明 p 还没有到达环的入口点
        p = p.next; // p 和 slow 同时向前移动一步
        slow = slow.next;
      }
      return p; // 返回环的入口点
    }
  }
  return null; // 遍历完整个链表都没有相遇的情况下，说明链表没有环，返回 null
};
// @lc code=end

146.lru-缓存

/*
 * @lc app=leetcode.cn id=146 lang=typescript
 *
 * [146] LRU 缓存
 */

// @lc code=start
class LRUCache {
    private capacity: number;
    private cache: Map<number, number>;
    constructor(capacity: number) {
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key: number): number {
        if (!this.cache.has(key)) return -1;

        const v = this.cache.get(key) as number;
        this.cache.delete(key);
        this.cache.set(key, v);
        return this.cache.get(key) as number;
    }

    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        }
        this.cache.set(key, value);
        if (this.cache.size > this.capacity) {
            this.cache.delete(this.cache.keys().next().value);  // keys().next().value returns first item's key
        }
    }
}
class Node {
  constructor(key, val) {
      this.key = key;
      this.val = val;
      this.next = null;
      this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
  }
  
  push(key, val) {
      const newNode = new Node(key, val);
      if(!this.head) {
          this.head = newNode;
          this.tail = newNode;
      } else {
          this.tail.next = newNode;
          newNode.prev = this.tail;
          this.tail = newNode;
      }
      this.length++;
      return newNode;
  }
  
  remove(node) {
      if(!node.next && !node.prev) { // if there's only 1 node
          this.head = null;
          this.tail = null;
      } else if(!node.next) { // if the node is tail node
          this.tail = node.prev;
          this.tail.next = null;
      } else if(!node.prev) { // if the node is head node
          this.head = node.next;
          this.head.prev = null;
      } else { // if the node is in between
          const prev = node.prev;
          const next = node.next;
          prev.next = next;
          next.prev = prev;
      }
      this.length--;
  }
}

class LRUCache {
  constructor(capacity) {
      this.DLL = new DoublyLinkedList();
      this.map = {};
      this.capacity = capacity;
  }

  get(key) {
      if(!this.map[key]) return -1;
      const value = this.map[key].val;
      this.DLL.remove(this.map[key]);
      this.map[key] = this.DLL.push(key, value);
      return value;
  }

  put(key, value) {
      if(this.map[key]) this.DLL.remove(this.map[key]);
      this.map[key] = this.DLL.push(key, value);
      if(this.DLL.length > this.capacity) {
          const currKey = this.DLL.head.key;
          delete this.map[currKey];
          this.DLL.remove(this.DLL.head);
      }
  }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
// @lc code=end

148.排序链表

/*
 * @lc app=leetcode.cn id=148 lang=typescript
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
// 1、归并排序的思想，局部有序到整体有序，最后相当于将两条有序的链表h合并
function sortList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head

  // 将联表分成两半
  let slow = head
  let fast = head.next
  while (fast?.next) {
    slow = slow.next
    fast = fast.next.next
  }
  const mid = slow.next
  // 切断链表，避免循环引用
  slow.next = null

  // 递归排序两个子链表
  let left = sortList(head)
  let right = sortList(mid)

  // 两个链表从小到大排序
  const dummy = new ListNode(0)
  let cur = dummy
  while (left && right) {
    if (left.val < right.val) {
      cur.next = left
      left = left.next
    } else {
      cur.next = right
      right = right.next

    }
    cur = cur.next
  }
  cur.next = left || right
  return dummy.next
};
// @lc code=end

152.乘积最大子数组

/*
 * @lc app=leetcode.cn id=152 lang=typescript
 *
 * [152] 乘积最大子数组
 */

// @lc code=start
function maxProduct(nums: number[]): number {
  if (nums.length === 1) return nums[0]
  const length = nums.length
  const dpMax: number[] = new Array(length)
  const dpMin: number[] = new Array(length)
  dpMax[0] = dpMin[0] = nums[0]
  let max = nums[0]
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] >= 0) {
      dpMax[i] = Math.max(nums[i], nums[i] * dpMax[i-1])
      dpMin[i] = Math.min(nums[i], nums[i] * dpMin[i - 1])
    } else {
      dpMax[i] = Math.max(nums[i], nums[i] * dpMin[i - 1])
      dpMin[i] = Math.min(nums[i], nums[i] * dpMax[i - 1])
    }
    max = Math.max(max, dpMax[i])
  }
  return max
};
// @lc code=end

155.最小栈

/*
 * @lc app=leetcode.cn id=155 lang=typescript
 *
 * [155] 最小栈
 */

// @lc code=start
class MinStack {
    private stack: number[] = []
    private mixStack:number[] = []
    constructor() {

    }

    push(val: number): void {
        this.stack.push(val)
        if (this.mixStack.length === 0 || val <= this.getMin()) {
            this.mixStack.push(val)
        }
    }

    pop(): void {
        if (this.stack.pop() === this.getMin()) {
            this.mixStack.pop()
        }
    }

    top(): number {
       return this.stack[this.stack.length-1]
    }

    getMin(): number {
        return this.mixStack[this.mixStack.length-1]
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */
// @lc code=end

160.相交链表

/*
 * @lc app=leetcode.cn id=160 lang=typescript
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let pA: ListNode | null = headA
  let pB: ListNode | null = headB
  let lenA = 0
  let lenB = 0
  while (pA) {
    lenA++
    pA = pA.next
  }
  while (pB) {
    lenB++
    pB = pB.next
  }
  pA = headA
  pB = headB
  if (lenA > lenB) {
    for (let i = 0; i < lenA - lenB; i++) {
      pA = pA.next;
    }
  } else {
    for (let i = 0; i < lenB - lenA; i++) {
      pB = pB.next;
    }
  }
  while (pA && pB) {
    if (pA === pB) {
      return pA
    }
    pA = pA.next
    pB = pB.next
  }
  return null

};
// function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
//   let pA: ListNode = headA
//   let pB: ListNode = headB
// // 因为如果两个链表没有交点，最终两个指针都会指向 null，循环自然结束
//   while (pA !== pB) {
//     pA = pA === null ? headB : pA.next
//     pB = pB === null ? headA : pB.next
//   }
//   return pA
  
// };
// @lc code=end

167.两数之和-ii-输入有序数组

/*
 * @lc app=leetcode.cn id=167 lang=typescript
 *
 * [167] 两数之和 II - 输入有序数组
 */

// @lc code=start
function twoSum(numbers: number[], target: number): number[] {
  const m = new Map()
  const res: number[] = []
  for (let i = 0; i < numbers.length; i++) {
    if (m.has(numbers[i])) {
      res.push(m.get(numbers[i]), i + 1)
    } else {
      m.set(target - numbers[i], i + 1)
    }

  }
  return res
};
// @lc code=end

169.多数元素

/*
 * @lc app=leetcode.cn id=169 lang=typescript
 *
 * [169] 多数元素
 */

// @lc code=start
function majorityElement(nums: number[]): number {
  if (nums.length === 1) return nums[0]
  const map = new Map()
  let max = 0
  let res = nums[0]
  for (const n of nums) {
    if (!map.has(n)) {
      map.set(n,1)
    } else {
      map.set(n, map.get(n) + 1)
      if (map.get(n) > max) {
        max = map.get(n)
        res = n
      }
    }
  }
  return res
};

// function majorityElement(nums: number[]): number {
//   let candidate = 0;
//   let count = 0;
//   for (let num of nums) {
//     if (count === 0) {
//       candidate = num;
//     }
//     count += (num === candidate) ? 1 : -1;
//   }
//   return candidate;
// }
// @lc code=end

198.打家劫舍

/*
 * @lc app=leetcode.cn id=198 lang=typescript
 *
 * [198] 打家劫舍
 */

// @lc code=start
function rob(nums: number[]): number {
  const n = nums.length
  if (n === 1) return nums[0]
  const dp: number[] = new Array(n)
  // 前一个房子只有一个，直接抢劫为金额最大
  dp[0] = nums[0]
  // 前两个房子抢劫金额的最大值
  dp[1] = Math.max(nums[0], nums[1])
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
  }
  return dp[n - 1]
};
// @lc code=end

200.岛屿数量

/*
 * @lc app=leetcode.cn id=200 lang=typescript
 *
 * [200] 岛屿数量
 */

// @lc code=start
function numIslands(grid: string[][]): number {
  const m = grid.length
  const n = grid[0].length
  let count = 0
  const dfs = (i:number,j:number) => {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return
    grid[i][j] = '0' // 重要，标志为已访问
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++
        dfs(i, j)
      }
    }
  }
  return count
};
// @lc code=end

206.反转链表

/*
 * @lc app=leetcode.cn id=206 lang=typescript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
// easy 循环解法
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let cur: ListNode | null = head
  while (cur) {
    [cur.next, prev, cur] = [prev,cur,cur.next]
  }
  return prev
};
// 递归解法
// function reverseList2(head) {
//   const reverse = (pre, cur) => {
//     if (!cur) return pre;
//     let tmp = cur.next;
//     cur.next = pre;
//     return reverse(cur, tmp);
//   };
//   return reverse(null, head);
// };
// @lc code=end

207.课程表

/*
 * @lc app=leetcode.cn id=207 lang=typescript
 *
 * [207] 课程表
 */

// @lc code=start
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // numCourses只有两个节点
  // 构建图，使用邻接表存储图，graph[i] 表示节点 i 所能到达的所有节点
  const graph: number[][] = new Array(numCourses).fill(0).map(() => [])
  // 记录每个节点的入度
  const inDegree: number[] = new Array(numCourses).fill(0)
  // 使用队列存储入度为 0 的节点
  const queue: number[] = []
  // let visited: number = 0
  for (const [course, prerequisiteCourse] of prerequisites) {
    // 记录先决条件的相邻节点
    graph[prerequisiteCourse].push(course);
    inDegree[course]++;
  }
  // 初始化队列,入度为0的先加入队列
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  // 循环遍历队列中的节点，直到队列为空
  while (queue.length > 0) {
    // 取出队列头部的节点
    const course = queue.shift()!;
    // 将已访问的节点数减 1
    numCourses--;
    // 遍历与当前节点相邻的节点
    for (const adjCourse of graph[course]) {
      // 将相邻节点的入度减 1
      if (--inDegree[adjCourse] === 0) {
        // 如果相邻节点的入度为 0，则将其加入队列
        queue.push(adjCourse);
      }
    }
  }
  // 如果所有课程都被访问过，则图中不存在环
  return numCourses === 0;
};
// @lc code=end

208.实现-trie-前缀树

/*
 * @lc app=leetcode.cn id=208 lang=typescript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start
class Trie {
    private node:TrieNode
    constructor() {
        this.node = new TrieNode()
        
    }
    insert(word: string): void {
        let node = this.node
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch,new TrieNode())
            }
            node = node.children.get(ch)!
        }   
        node.isEnd = true
    }

    search(word: string): boolean {
        let node = this.node
        for (const ch of word) {
            if (!node.children.has(ch)) {
                return false
            }
            node = node.children.get(ch)!
        }
        return node.isEnd
    }

    startsWith(prefix: string): boolean {
        let node = this.node
        for (const ch of prefix) {
            if (!node.children.has(ch)) {
                return false
            }
            node = node.children.get(ch)!
        }
        return true
    }
}

class TrieNode {
    children: Map<string, TrieNode>
    isEnd: boolean
    constructor() {
        this.children = new Map()
        this.isEnd = false
    }
    
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
// @lc code=end

209.长度最小的子数组

/*
 * @lc app=leetcode.cn id=209 lang=typescript
 *
 * [209] 长度最小的子数组
 */

// @lc code=start
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0
  let right = 0
  let res = Infinity
  let sum= 0
  while (right < nums.length) {
    sum += nums[right]
    while (sum >= target) {
      res = Math.min(res, right - left + 1)
      sum -= nums[left]
      left++
    }
    right++
  }
  return res === Infinity ? 0 : res
};
// @lc code=end

215.数组中的第k个最大元素

/*
 * @lc app=leetcode.cn id=215 lang=typescript
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start

/**
 * 在数组中查找第 k 大的元素
 * @param nums 数组
 * @param k 第 k 大
 * @returns 第 k 大的元素
 */
function findKthLargest(nums: number[], k: number): number {
  // 调用快速选择算法查找第 k 大的元素
  // 数组长度减 k，因为我们要查找的是第 k 大的元素，而快速选择算法查找的是第 k 小的元素
  return quickSelect(nums, 0, nums.length - 1, nums.length - k)
};
/**
 * 使用快速选择算法查找第 k 小的元素
 * @param nums 数组
 * @param left 左边界
 * @param right 右边界
 * @param k 要查找的元素的下标
 * @returns 要查找的元素的值
 */
function quickSelect(nums: number[], left: number, right: number, k: number):number {
  // 对数组进行分区，返回分区点的下标

  const pivotIndex = partition(nums, left, right)
  // 如果分区点的下标等于要查找的元素的下标，说明找到了要查找的元素，直接返回该元素的值
  if (pivotIndex === k) {
    return nums[k]
  }
  // 如果分区点的下标小于要查找的元素的下标，说明要查找的元素在右半部分，递归调用 quickSelect 函数查找右半部分
  else if (pivotIndex < k) {
    return quickSelect(nums, pivotIndex + 1, right, k)
  }
  // 如果分区点的下标大于要查找的元素的下标，说明要查找的元素在左半部分，递归调用 quickSelect 函数查找左半部分
  else {
    return quickSelect(nums, left, pivotIndex - 1, k)
  }
}
/**
 * 将数组分成两部分，一部分是小于等于 pivot 的元素，另一部分是大于 pivot 的元素
 * @param nums 数组
 * @param left 左边界
 * @param right 右边界
 * @returns 分区点的下标
 */
function partition(nums: number[], left: number, right: number):number {
  // 取最后一个元素作为分区点
  let i = left
  const pivot = nums[right]
  // 从左往右遍历数组，将小于等于 pivot 的元素交换到左边
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]]
      i++
    }
  }
  // 将分区点交换到正确的位置
  [nums[i], nums[right]] = [nums[right], nums[i]]
  return i
}

// function quickSort(nums: number[]) {
//   if(nums.length<=1) return nums
//   let left: number[] = []
//   let right: number[] = []
//   // 选择第一个元素作为基准值
//   const pivot = nums[0]
//   for (let i = 1; i < nums.length; i++) {
//     if (nums[i] < pivot) {
//       left.push(nums[i])
//     } else {
//       right.push(nums[i])
//     }
//   }
//   return [...quickSort(left),pivot,...quickSort(right)]
// }

// @lc code=end

221.最大正方形

/*
 * @lc app=leetcode.cn id=221 lang=typescript
 *
 * [221] 最大正方形
 */

// @lc code=start
function maximalSquare(matrix: string[][]): number {
  if (!matrix || matrix.length === 0) return 0;
  const m = matrix.length
  const n = matrix[0].length
  let maxLen = 0

  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  // copy matrix第一列的值到dp第一列 ，记录dp第一列的最大maxLen
  for (let i = 0; i < m; i++) {
    dp[i][0] = parseInt(matrix[i][0])
    maxLen = Math.max(maxLen, dp[i][0])

  }
  // copy matrix第一行的值到dp第一行，记录dp第一行的最大maxLen
  for (let j = 0; j < n; j++) {
    dp[0][j] = parseInt(matrix[0][j])
    maxLen = Math.max(maxLen, dp[0][j])
  }
  
  for (let i = 1; i < matrix.length; i++) {
    for (let j = 1; j < matrix[0].length; j++) {
      if (matrix[i][j] === '1') {
        // 记录左边、上边、左上角的最小值（最坏情况），加上当前的长度1
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        maxLen = Math.max(maxLen, dp[i][j])
      }
      
    }
  }
  return maxLen * maxLen
};
// @lc code=end

226.翻转二叉树

/*
 * @lc app=leetcode.cn id=226 lang=typescript
 *
 * [226] 翻转二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
  // 如果根节点为空，则返回 null
  if (!root) {
    return null;
  }

  // 保存当前节点的左子树
  const left = root.left;

  // 递归翻转当前节点的左右子树，并将左右子树交换
  root.left = invertTree(root.right);
  root.right = invertTree(left);

  // 返回翻转后的根节点
  return root;
};
// @lc code=end

234.回文链表

/*
 * @lc app=leetcode.cn id=234 lang=typescript
 *
 * [234] 回文链表
 */


// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) {
    // 链表为空或只有一个节点，是回文链表
    return true;
  }
  // 快慢指针找到中点
  let slow = head
  let fast = head
  while (fast?.next?.next) {
    slow = slow.next
    fast = fast.next.next
  }
  // 从中间分两条链表
  let pre: ListNode | null = null
  let cur: ListNode | null = slow.next
  // 截断链表
  slow.next = null
  // 反转后半截链表
  while (cur) {
    [cur.next, pre, cur] = [pre, cur, cur.next]
  }
  let p1 = head
  let p2 = pre
  // 两条链表同时走
  while (p2) {
    if (p2.val !== p1.val) return false
    p2 = p2.next
    p1 = p1.next
  }
  return true
};

// function reverseList(head: ListNode | null): ListNode | null {
//   let pre: ListNode | null = null
//   let cur: ListNode | null = head
//   while (cur) {
//     [cur.next,pre,cur] = [pre,cur,cur.next]
//   }
//   return pre
// }

function isPalindrome2(head: ListNode | null): boolean {
  if (!head || !head.next) {
    // 链表为空或只有一个节点，是回文链表
    return true;
  }
  let str = ''
  while (head) {
    str += head.val
    head = head.next
  }
  return strIsPalindmore(str)
};

function strIsPalindmore(str: string):boolean {
  let start = 0
  let end = str.length - 1
  while (start<end) {
    if (str[start] !== str[end]) {
        return false
    }
    start++
    end--
  }
  return true
}
// @lc code=end

236.二叉树的最近公共祖先

/*
 * @lc app=leetcode.cn id=236 lang=typescript
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  if (!root) return null; // 递归边界
  if (root === p || root === q) return root; // 如果当前节点为 p 或 q，则直接返回当前节点

  const left = lowestCommonAncestor(root.left, p, q); // 在左子树中查找 p 或 q
  const right = lowestCommonAncestor(root.right, p, q); // 在右子树中查找 p 或 q

  if (left && right) return root; // p 和 q 分别在左右子树中，返回当前节点
  return left || right; // p 和 q 在同一子树中，返回该子树的根节点
};


function lowestCommonAncestor2(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;

  const parentMap = new Map<TreeNode, TreeNode | null>();
  const queue: TreeNode[] = [root];

  // BFS 遍历树，将节点和它们的父节点映射到哈希表中
  while (queue.length) {
    const node = queue.shift()!;
    if (node.left) {
      parentMap.set(node.left, node);
      queue.push(node.left);
    }
    if (node.right) {
      parentMap.set(node.right, node);
      queue.push(node.right);
    }
  }

  const ancestors = new Set<TreeNode>();

  // 遍历 p 节点及其祖先节点，并将它们添加到祖先节点集合中
  while (p) {
    ancestors.add(p);
    p = parentMap.get(p)!;
  }

  // 遍历 q 节点及其祖先节点，查找是否存在与 p 相同的节点
  while (q) {
    if (ancestors.has(q)) {
      return q;
    }
    q = parentMap.get(q)!;
  }

  return null; // 没有找到最近公共祖先节点
}
// @lc code=end

238.除自身以外数组的乘积

/*
 * @lc app=leetcode.cn id=238 lang=typescript
 *
 * [238] 除自身以外数组的乘积
 */

// @lc code=start
function productExceptSelf(nums: number[]): number[] {
  const n=  nums.length
  const res: number[] = []
  // 计算左边累计，num[i] = num[i-1]*[i-2]*[i-3]...
  let leftProduct = 1
  for (let i = 0; i < n; i++) {
    res[i] = leftProduct
    leftProduct *= nums[i]
  }
  // 计算右边累计，num[i] = num[i+1]*[i+2]*[i+3]...
  // 同时用左边累计与右边累计相乘既可，即num[i] = num[i-1]*[i-2]*[i-3]...*num[i+1]*[i+2]*[i+3]...
  let rightProduct = 1
  for (let i = n-1; i >= 0; i--) {
    res[i] *= rightProduct
    rightProduct *= nums[i]
  }
  return res
};
// @lc code=end

239.滑动窗口最大值

/*
 * @lc app=leetcode.cn id=239 lang=typescript
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // 双端队列，用于存放下标

  for (let i = 0; i < nums.length; i++) {
    // 保证 deque 中下标对应的元素是单调递减的
    while (deque.length && nums[i] > nums[deque[deque.length - 1]]) {
      deque.pop();
    }

    deque.push(i);

    // 检查队首元素是否超出窗口大小
    if (i - deque[0] >= k) {
      deque.shift();
    }

    // 当前窗口大小为 k 时，将队首元素添加到结果数组中
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

// function maxSlidingWindow2(nums: number[], k: number): number[] {
//   if (nums.length === 0) return [];
//   const res = [];
//   for (let i = 0; i <= nums.length - k; i++) {
//     let max = nums[i];
//     for (let j = i + 1; j < i + k; j++) {
//       max = Math.max(max, nums[j]);
//     }
//     res.push(max);
//   }
//   return res;
// };


// @lc code=end

240.搜索二维矩阵-ii

/*
 * @lc app=leetcode.cn id=240 lang=typescript
 *
 * [240] 搜索二维矩阵 II
 */

// @lc code=start
//搜索空间缩减
function searchMatrix(matrix: number[][], target: number): boolean {
  const m = matrix.length
  const n = matrix[0].length
  let row = m - 1
  let col = 0
  // 从左下角开始找，缩写范围找
  // 比target大,证明在右边;比target小，证明在上边
  while (row>=0 && col<n) {
    if (matrix[row][col] === target) {
      return true
    } else if (matrix[row][col] > target) {
      row--
    } else {
      col++
    }
  }
  return false
};
// 暴力法，每一行二分查找
function searchMatrix2(matrix: number[][], target: number): boolean {
  const m = matrix.length
  const n = matrix[0].length

  for (let i = 0; i < m; i++) {
    let left = 0
    let right = n - 1
    while (left <= right) {
      const mid = (left + right) / 2
      if (matrix[i][mid] === target) {
        return true
      } else if (matrix[i][mid] > target) {
        right = mid-1
      } else {
        left = mid+1
      }
    }
  }
  return false
};
// @lc code=end

242.有效的字母异位词

/*
 * @lc app=leetcode.cn id=242 lang=typescript
 *
 * [242] 有效的字母异位词
 */

// @lc code=start
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false
  const hash = {}
  for (const c of s) {
    hash[c] = (hash[c] || 0) + 1
  }
  for (const c of t) {
    if (!hash[c]) return false
    hash[c]--
  }
  return true
};
// @lc code=end

279.完全平方数

/*
 * @lc app=leetcode.cn id=279 lang=typescript
 *
 * [279] 完全平方数
 */

// @lc code=start
function numSquares(n: number): number {
  // 创建一个动态规划数组，dp[i] 表示数字 i 最少能被几个完全平方数的和表示出来
  const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER)
  // 初始化 dp[0] 为 0
  dp[0] = 0
  // 遍历从 1 到 n 的每一个数字
  for (let i = 1; i <= n; i++) {
      // 对于每个数字，枚举所有小于它的完全平方数 j*j
    for (let j = 1; j * j <= i; j++) {
      // 状态转移方程：dp[i] = min(dp[i], dp[i - j*j] + 1)
      dp[i] = Math.min(dp[i],dp[i-j*j]+1)
    }
  }
  // 返回 dp[n]，即数字 n 最少能被几个完全平方数的和表示出来
  return dp[n]
};
// @lc code=end

283.移动零

/*
 * @lc app=leetcode.cn id=283 lang=typescript
 *
 * [283] 移动零
 */

// @lc code=start
/**
 Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
  // 双指针解决
  let i = 0
  for (let j = 0; j < nums.length; j++) {
    //不为0的移动到前面，同时i++，这样最后的为0的就在最后面了
    if (nums[j] !== 0) {
      [nums[i], nums[j]] = [nums[j], nums[i]]
      i++
    }
  }
};
// @lc code=end

287.寻找重复数

/*
 * @lc app=leetcode.cn id=287 lang=typescript
 *
 * [287] 寻找重复数
 */

// @lc code=start
function findDuplicate(nums: number[]): number {
  let slow = nums[0]; // 慢指针指向第一个元素
  let fast = nums[0]; // 快指针指向第一个元素

  // 使用快慢指针，类似于寻找链表中的环
  do {
    slow = nums[slow]; // 慢指针每次走一步
    fast = nums[nums[fast]]; // 快指针每次走两步
  } while (slow !== fast); // 直到慢指针和快指针相遇

  // 将快指针重新指向第一个元素
  fast = nums[0];

  // 快慢指针每次都走一步，直到它们相遇
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow; // 返回重复的元素
}

function findDuplicate2(nums: number[]): number {
  // 排序
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length-1; i++) {
    if (nums[i] === nums[i + 1]) {
      return nums[i]
    }
  }
};
// @lc code=end

300.最长递增子序列

/*
 * @lc app=leetcode.cn id=300 lang=typescript
 *
 * [300] 最长递增子序列
 */

// @lc code=start
function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  // 特判
  if (n < 2) {
    return n;
  }
  // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
  const dp = new Array(n).fill(1)
  // dp[0] = 1
  for (let i = 1; i < n; i++) {
   for (let j = 0; j < i; j++) {
     if (nums[j] < nums[i]) {
      dp[i] = Math.max(dp[i],dp[j]+1)
    }
   }
  }
  return Math.max(...dp)
};

function lengthOfLIS2(nums: number[]): number {
  const n = nums.length;
  // tails 存储所有最长上升子序列，初始化为第一个数
  const tails = [nums[0]];
  // 遍历 nums 数组，寻找最长上升子序列
  for (let i = 1; i < n; i++) {
    // 如果当前数比 tails 中的最后一个数还大，直接添加到 tails 中
    if (nums[i] > tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      // 否则使用二分查找找到第一个大于等于当前数的数的下标，替换掉它
      let left = 0, right = tails.length - 1;
      while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (tails[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tails[left] = nums[i];
    }
  }
  // 最终 tails 的长度就是最长上升子序列的长度
  return tails.length;
}



// @lc code=end

301.删除无效的括号

/*
 * @lc app=leetcode.cn id=309 lang=typescript
 *
 * [309] 最佳买卖股票时机含冷冻期
 */
function removeInvalidParentheses(s: string): string[] {
    let res: string[] = []
    let left = 0
    let right = 0
    for(const c of s) {
        if(c==='(') {
            left++
        } else if(c===')') {
           if(left===0) {
               right++
           } else {
               left--
           }
        }
    }

    const dfs = (l:number,r:number, str:string,start:number)=> {
        if(l===0 && r===0 ) {
            if(isValid(str)) {
                res.push(str)
            }
            return
        }
        for(let i=start;i<str.length;i++) {
            // 后一个等于前一个字符串，跳过避免重复子集
            if(i>start && str[i]===str[i-1]) continue
            // 不是括号
            if (str[i] !== '(' && str[i] !== ')') continue;
            // 缺少的括号大于剩余的括号
            if(l+r > str.length-i) return
            const nextStr = str.slice(0,i)+str.slice(i+1)
            if(l>0 && str[i]==='(') {
                dfs(l-1,r,nextStr,i)
            }
            if(r>0 && str[i]===')') {
                dfs(l,r-1,nextStr,i)
            }
        }

    }
    dfs(left,right,s,0)
    return res

};

function isValid(s:string) {
    let count = 0
    for(const c of s) {
        if(c==='(') {
            count++
        } else if(c===')') {
            count--
            // 右括号在前，直接剪枝
            if(count<0) {
                return false
            }
        }
    }
    return count===0
}

309.最佳买卖股票时机含冷冻期

/*
 * @lc app=leetcode.cn id=309 lang=typescript
 *
 * [309] 最佳买卖股票时机含冷冻期
 */

// @lc code=start
function maxProfit(prices: number[]): number {
  const n = prices.length;
  if (n == 0) return 0;

  // 初始化状态转移数组
  const dp: number[][] = Array.from({ length: n }, () => [0, 0, 0]);

  // 初始化第一天的状态
  dp[0][0] = 0; // 不持有股票且没有进行过交易
  dp[0][1] = -prices[0]; // 持有股票
  dp[0][2] = 0; // 不持有股票但进行过一次买入交易

  // 从第二天开始遍历价格数组
  for (let i = 1; i < n; i++) {
    // 第i天不持有股票且没有进行过交易，状态转移方程
    // i-1天完成了一次交易交易，今天刚好处与冷却期
    // i-1天不持有
    // i-1天持有今天抛出就是dp[i][2]的情况，刚好完成一次交易，属于dp[i][2] = dp[i - 1][1] + prices[i]
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);

    // 第i天持有股票，状态转移方程
    // i-1天持有，或者昨天持有
    // i-1天不持有，今天持有
    // i-1天持有完成一次交易，则第i天是冷却期，不存在今天持有
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

    // 第i天不持有股票但刚好进行过一次买入交易，状态转移方程
    // i - 1天持有今天抛出就是dp[i][2]的情况，刚好完成一次交易
    dp[i][2] = dp[i - 1][1] + prices[i];
  }

  // 返回最终的状态值
  return Math.max(dp[n - 1][0], dp[n - 1][2]);
};
// @lc code=end

322.零钱兑换

/*
 * @lc app=leetcode.cn id=322 lang=typescript
 *
 * [322] 零钱兑换
 */

// @lc code=start
function coinChange(coins: number[], amount: number): number {
  const dp: number[] = new Array(amount + 1).fill(Infinity); // 初始化，凑出每个金额都需要的最小硬币数都为 Infinity
  dp[0] = 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]
};
// @lc code=end

337.打家劫舍-iii

/*
 * @lc app=leetcode.cn id=337 lang=typescript
 *
 * [337] 打家劫舍 III
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function rob(root: TreeNode | null): number {
  const robSub = (node: TreeNode | null): [number, number] => {
    if (node === null) {
      // j节点为空，抢和不抢收益都为零
      return [0,0]
    }
    // 递归左右子树
    const left = robSub(node.left)
    const right = robSub(node.right)
    // 抢当前节点的情况，等于当前节点+左右节点不抢的情况
    const rob = node.val + left[1] + right[1]
    // 不抢当前节点的情况，等于不抢当前节点+左右节点抢和不抢最大值相加的情况
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
    // 返回抢和不抢的二维数组情况
    return [rob,notRob]
  }
  const result = robSub(root)
  // 比较跟节点抢和不抢的最大值情况
  return Math.max(...result)
};
// @lc code=end

338.比特位计数

/*
 * @lc app=leetcode.cn id=338 lang=typescript
 *
 * [338] 比特位计数
 */

// @lc code=start
function countBits(num: number): number[] {
  const res: number[] = [0]; // 创建一个结果数组，初始值为 [0]。
  for (let i = 1; i <= num; i++) {
    if (i % 2 === 1) { // 如果 i 是奇数，那么 res[i] 等于 res[i-1] 的值加 1。
      res.push(res[i - 1] + 1);
    } else { // 如果 i 是偶数，那么 res[i] 等于 res[i/2] 的值。
      res.push(res[i / 2]);
    }
  }
  return res; // 返回结果数组。
}

function countBits2(n: number): number[] {
  const res: number[] = [0]
  const oneTotal = (n: number): number => {
    let count = 0
    while (n > 0) {
      // 奇数才+1
      if (n % 2 === 1) {
        count++
      }
      n = Math.floor(n / 2) // n/2 >> 或者n/2 | 0 都是向下取整的好方法
    }
    return count
  }
  for (let i = 1; i <= n; i++) {
    const count = oneTotal(i)
    res.push(count)
  }

  return res
};
// @lc code=end

344.反转字符串

/*
 * @lc app=leetcode.cn id=344 lang=typescript
 *
 * [344] 反转字符串
 */

// @lc code=start
/**
 Do not return anything, modify s in-place instead.
 */
function reverseString(s: string[]): void {
  let left = 0
  let right = s.length-1
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]]
    left++
    right--
  }
};
// @lc code=end

347.前-k-个高频元素

/*
 * @lc app=leetcode.cn id=347 lang=typescript
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
function topKFrequent(nums: number[], k: number): number[] {
  const map: Map<number, number> = new Map();
  const bucket: (Set<number> | undefined)[] = [];
  const result: number[] = [];
  for (const num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
  }

  for (const [num, freq] of map) {
    bucket[freq] = (bucket[freq] || new Set<number>()).add(num);
  }
  for (let i = bucket.length - 1; i >= 0; i--) {
    if (bucket[i]) result.push(...bucket[i]!);
    if (result.length === k) break;
  }
  return result;
};
// @lc code=end

394.字符串解码

/*
 * @lc app=leetcode.cn id=394 lang=typescript
 *
 * [394] 字符串解码
 */

// @lc code=start
function decodeString(s: string): string {
  // 如果是s是数字字符串直接返回'',例如s是'3'
  if(!isNaN(Number(s))) return ''
  const stack: string[] = []
  for (const c of s) {
    if (c === ']') {
      let str = ''
      // 累加[...]中括号的里面的字符
      while (stack.length && stack[stack.length - 1] !== '[') {
        str = stack.pop()+str
      }
      // 移除'['
      stack.pop()
      // 判断前面数字，然后累加次数
      let numStr = ''
      while (stack.length && !isNaN(Number(stack[stack.length-1]))) {
        numStr = stack.pop() +numStr
      }
      const num = Number(numStr)
      // 重复数字后的字符串
      stack.push(str.repeat(num))
    } else {
      stack.push(c)
    }
  }
  return stack.join('')
};
// @lc code=end

399.除法求值

/*
 * @lc app=leetcode.cn id=399 lang=typescript
 *
 * [399] 除法求值
 */

// @lc code=start
type Graph = Record<string, Record<string, number>>;

function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
  const res: number[] = []
  const graph: Graph = {}
  // 建立图
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i]
    if (!graph[a]) graph[a] = {}
    if (!graph[b]) graph[b] = {}
    graph[a][b] = values[i]
    graph[b][a] = 1 / values[i]
  }
  for (const [src, dest] of queries) {
    if (!graph[src] || !graph[dest]) {
      res.push(-1)
      continue
    }
    const visited = new Set<string>()
    res.push(dfs(src, dest, visited, graph))
  }

  return res
};

function dfs(src: string, dest: string, visited: Set<string>, graph:Graph) {
  if (src === dest) {
    return 1
  }
  visited.add(src)
  for (const [neighbor, val] of Object.entries(graph[src])) {
    if (visited.has(neighbor)) continue
    const product = dfs(neighbor, dest, visited, graph)
    if (product !== -1) {
      return product * val
    }
  }
  return -1
}
// @lc code=end

406.根据身高重建队列

/*
 * @lc app=leetcode.cn id=406 lang=typescript
 *
 * [406] 根据身高重建队列
 */

// @lc code=start
function reconstructQueue(people: number[][]): number[][] {
  const result:number[][] = []
  // 身高从高到底排序，身高相同按编号从低到高排序
  people.sort((a, b) => {
    if (a[0] !== b[0]) {
     return b[0]-a[0]
    } else {
      return a[1]-b[1]
    }
  })
  // 根据序号插入对应的位置
  for (const person of people) {
    result.splice(person[1], 0, person)
  }
  return result
  // 时间复杂度是 O(n ^ 2)，其中 n 是输入数组 people 的长度。
  //虽然代码中只有一个 for 循环，但在每次循环中，都会调用 splice 方法将元素插入到数组中，
  //这个方法的时间复杂度是 O(n)，因此总时间复杂度是 O(n ^ 2)。
};
// @lc code=end

416.分割等和子集

/*
 * @lc app=leetcode.cn id=416 lang=typescript
 *
 * [416] 分割等和子集
 */

// @lc code=start
// 0-1背包
// 0 - 1 背包问题是一类经典的背包问题，它的定义如下：
/*有一个容量为 C 的背包，和 n 个物品，每个物品的重量为 w[i]，价值为 v[i]。需要在这些物品中选择一些装入背包中，使得装入的物品总重量不超过 C，且装入的物品总价值最大。
该问题可以用动态规划求解。定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品装入容量为 j 的背包中所能获得的最大价值。对于第 i 个物品，有两种选择：
不选择第 i 个物品，则背包的价值为前 i - 1 个物品装入容量为 j 的背包中所能获得的最大价值，即 dp[i][j] = dp[i - 1][j]。
选择第 i 个物品，则背包的价值为前 i - 1 个物品装入容量为 j - w[i] 的背包中所能获得的最大价值加上第 i 个物品的价值，即 dp[i][j] = dp[i - 1][j - w[i]] + v[i]。
因此，最终状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])。其中，dp[i - 1][j] 表示不选择第 i 个物品，背包的价值为前 i - 1 个物品装入容量为 j 的背包中所能获得的最大价值；dp[i - 1][j - w[i]] + v[i] 表示选择第 i 个物品，背包的价值为前 i - 1 个物品装入容量为 j - w[i] 的背包中所能获得的最大价值加上第 i 个物品的价值。
最终，dp[n][C] 就是所求的结果，即前 n 个物品装入容量为 C 的背包中所能获得的最大价值。
*/
function knapsack(C: number, w: number[], v: number[]): number {
  const n = w.length;

  // 初始化二维数组 dp
  // dp[i][j] 表示前 i 个物品装入容量为 j 的背包中所能获得的最大价值
  const dp: number[][] = new Array(n + 1).fill(null).map(() => new Array(C + 1).fill(0));

  // 动态规划求解
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= C; j++) {
      if (w[i - 1] > j) {
        // 背包容量不足，不能选择第 i 个物品
        dp[i][j] = dp[i - 1][j];
      } else {
        // 背包容量足够，可以选择第 i 个物品
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
      }
    }
  }

  return dp[n][C];
}



function canPartition2(nums: number[]): boolean {
  const n = nums.length
  // 计算数组元素的总和
  const sum = nums.reduce((pre, cur) => pre + cur, 0)
  // 如果总和是奇数，无法分割成等和子集
  if (sum % 2 === 1) {
    return false
  }
  // 计算需要达到的等和子集的目标和
  const target = sum / 2
  // 存在元素比target大的元素，无法分割成等和子集
  const existGreaterTarget = nums.find(num => num > target)
  if (existGreaterTarget) return false
  // 初始化二维数组 dp
  // dp[i][j] 表示前 i 个元素能否组成和为 j 的子集。这里是n不是n+1，因为存在两个子集和相等
  const dp: boolean[][] = Array.from({ length: n }, () => new Array(target + 1).fill(false))
  // 初始化第一列
  // dp[0][0] 表示前 0 个元素组成和为 0 的子集，所以为 true
  dp[0][0] = true

  // 动态规划求解
  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= target; j++) {
      if (nums[i] === j) {
        // 如果第 i 个元素等于 j，可以直接选第 i 个元素组成和为 j 的子集
        dp[i][j] = true
      } else if (nums[i] < j) {
        // 如果第 i 个元素小于 j，可以选择或不选择第 i 个元素
        // 如果不选择，继承前 i - 1 个元素的结果
        // 如果选择，需要组成和为 j - nums[i] 的子集，因此继承前 i - 1 个元素组成和为 j - nums[i] 的子集的结果
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
      } else {
        dp[i][j] = dp[i - 1][j]; // 不选择第 i 个元素，继承前 i - 1 个元素的结果
      }
    }
  }
  // 返回前 n-1个元素是否可以组成和为 target 的子集
  return dp[n-1][target]
};

function canPartition(nums: number[]): boolean {
  // 计算nums数组的总和
  const sum = nums.reduce((a, b) => a + b, 0);
  // 如果sum是奇数，就无法将数组分成两个子集，使得两个子集的元素和相等
  if (sum % 2 !== 0) {
    return false;
  }
  // 将数组分成两个子集，使得两个子集的元素和相等，等价于在nums数组中选择一些元素，使它们的和等于nums数组的一半
  const target = sum / 2;
  // 定义一个布尔类型的dp数组，其中dp[i]表示是否可以从nums数组中选择一些元素，使它们的和等于i
  const dp: boolean[] = [true];
  // 遍历nums数组中的每个元素
  for (const num of nums) {
    // 从target开始向下遍历dp数组
    for (let i = target; i >= num; i--) {
      // 如果dp[i - num]是true，那么dp[i]也是true
      dp[i] ||= dp[i - num]; // dp[i] = dp[i] || dp[i - num]
    }
  }
  // 返回dp[target]的值
  return dp[target] ?? false;
};



// @lc code=end

437.路径总和-iii

/*
 * @lc app=leetcode.cn id=437 lang=typescript
 *
 * [437] 路径总和 III
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, targetSum: number): number {
  let count = 0
  const dfs = (node: TreeNode| null,path:number[]) => {
    if (!node) return
    // 将当前节点的值添加到路径中
    path.push(node.val)
    let sum = 0
    // 从当前节点往前遍历路径，计算每个子路径的和
    for (let i = path.length - 1; i >= 0; i--) {
      sum += path[i]
      if (sum === targetSum) {
        // 如果子路径和等于目标和，则路径数量加一
        count++
      }
    }
    // 继续遍历左右子树，传递当前路径
    dfs(node.left, path)
    dfs(node.right, path)
    // 回溯，将当前节点的值从路径中删除
    path.pop()
  }
    // 从根节点开始深度优先遍历二叉树
  dfs(root, [])
  return count
};
// @lc code=end

438.找到字符串中所有字母异位词

function findAnagrams(s: string, p: string): number[] {
  const map = new Map<string, number>();
  const res: number[] = [];

  // 预处理模式字符串，统计每个字符的频率。
  for (const c of p) {
    map.set(c, (map.get(c) ?? 0) + 1);
  }

  // 使用滑动窗口遍历搜索字符串。
  let l = 0;
  let r = 0;
  let count = p.length;

  while (r < s.length) {
    // 如果当前字符在模式字符串中，并且其频率大于零，
    // 则表示找到了一个有效的字母异位词窗口。
    if (map.has(s[r]) && map.get(s[r])! > 0) {
      count--;
    }

    // 将当前字符在映射中的频率减一。
    map.set(s[r], (map.get(s[r]) ?? 0) - 1);

    // 右指针向前移动。
    r++;

    // 如果找到了一个有效的字母异位词窗口，则将左指针添加到结果数组中。
    if (count === 0) {
      res.push(l);
    }
  
    // 如果窗口大小大于等于模式字符串长度，left指针向后移动。
    // 释放s[l]的占用
    if (r - l >= p.length) {
      // 则需要将左指针向前移动，需要的count加1。
      if (map.has(s[l]) && map.get(s[l])! >= 0) {
        count++;
      }

      // 为使用字符s[l] 加1
      map.set(s[l], (map.get(s[l]) ?? 0) + 1);

      l++;
    }
  }

  return res;
}

/*
 * @lc app=leetcode.cn id=438 lang=typescript
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
/**
 * @param {string} s - 输入字符串
 * @param {string} p - 模式字符串
 * @return {number[]} - 满足条件的子串起始位置数组
 */
function findAnagrams(s: string, p: string): number[] {
  // 定义变量存储结果数组和模式字符串的字符数量
  const res:number[] = [];
  const map = new Map<string, number>();

  // 遍历模式字符串，统计其中每个字符的数量
  for (const c of p) {
    map.set(c, (map.get(c) || 0) + 1);
  }

  let left = 0;
  let right = 0;
  let count = p.length;

  // 遍历输入字符串
  while (right < s.length) {
    const c = s[right];
    if (map.has(c) && map.get(c)! > 0) {
      // 如果当前字符在模式字符串中出现过，并且其数量大于 0
      count--;
    }
    map.set(c, (map.get(c) || 0) - 1);
    right++;

    if (count === 0) {
      // 如果子串中的字符数量都符合要求
      res.push(left);
    }

    if (right - left === p.length) {
      // 如果子串长度达到模式字符串的长度
      const c = s[left];
      if (map.has(c) && map.get(c)! >= 0) {
        // 如果当前字符在模式字符串中出现过，并且其数量大于等于 0
        count++;
      }
      map.set(c, (map.get(c) || 0) + 1);
      left++;
    }
  }

  return res;
}

// @lc code=end

461.汉明距离

/*
 * @lc app=leetcode.cn id=461 lang=typescript
 *
 * [461] 汉明距离
 */

// @lc code=start
function hammingDistance(x: number, y: number): number {
  let xor = x ^ y; // 计算 x 和 y 的异或值
  let count = 0;

  // 统计异或值中 1 的个数
  while (xor !== 0) {
    if (xor & 1) { // 判断最低位是否为 1
      count++;
    }
    xor = xor >>> 1; // 右移一位，判断下一位
  }

  return count;
}

// @lc code=end

494.目标和

/*
 * @lc app=leetcode.cn id=494 lang=typescript
 *
 * [494] 目标和
 */

// @lc code=start
function findTargetSumWays(nums: number[], target: number): number {
  // 创建一个Map，用于存储前i个数字组成的和为j的方案数
  const map = new Map<string, number>()
  const dfs = (i: number, j: number):number => {
    // 如果有缓存，直接返回
    const key = `${i}#${j}`
    if (map.has(key)) {
      return map.get(key)!
    }
     // 如果已经处理完所有数字，判断是否满足条件
    if (i === nums.length) {
      return j === 0 ? 1 : 0
    }
     // 对于每个数字，计算使用+或-符号的方案数之和
    const res: number = dfs(i + 1, j - nums[i]) + dfs(i + 1, j + nums[i])
    // 缓存结果，避免重复计算
    map.set(key,res)
    return res
  }
  // 从第一个数字开始递归
  return dfs(0, target)
}
// 斐波那契数 使用map添加缓存
function fibonacci(n: number): number {
  // 创建一个Map，用于存储已经计算过的斐波那契数列值
  const map = new Map<number, number>();

  function fib(n: number): number {
    if (n < 2) {
      return n;
    }
    // 如果已经计算过当前值，直接从Map中获取
    if (map.has(n)) {
      return map.get(n)!;
    }
    // 计算斐波那契数列值
    const res = fib(n - 1) + fib(n - 2);
    // 将计算结果存储到Map中
    map.set(n, res);
    return res;
  }

  // 从第0项开始计算斐波那契数列
  return fib(n);
}



function findTargetSumWays2(nums: number[], target: number): number {
  const n = nums.length
  const sum = nums.reduce((pre, cur) => pre + cur, 0)
  // 如果目标和大于所有元素的和，或者目标和和所有元素的和的奇偶性不同，则无解
  if (target > sum || (target + sum) % 2 !== 0) {
    return 0
  }
  if (Math.abs(target) > sum) {
    return 0;
  }
  const goal = (target + sum) / 2
  // dp[i][j] 表示前 i 个元素中选取若干个元素，使它们的和为 j 的方案数
  const dp = Array.from({ length: n + 1 }, () => new Array(goal + 1).fill(0))
  // 如果目标和为 0，则只有一种方案，即不选取任何元素
  dp[0][0] = 1
  for (let i = 1; i <= n; i++) {
    const num = nums[i - 1]
    for (let j = 0; j <= goal; j++) {
      dp[i][j] = dp[i - 1][j]
      if (num <= j) {
        dp[i][j] += dp[i - 1][j - num] // 不选取当前元素或选取当前元素
      }
    }
  }
  return dp[n][goal]

};
// @lc code=end

525.连续数组

/*
 * @lc app=leetcode.cn id=525 lang=typescript
 *
 * [525] 连续数组
 */

// @lc code=start
function findMaxLength(nums: number[]): number {
  const hash = {};
  let max_length = 0;
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    const current = nums[i];
    if (current === 0) {
      // if the current element is 0, then we decrement the count
      count--;
    } else if (current === 1) {
      // if the current element is 1, then we increment the count
      count++;
    }

    if (count === 0) {
      // if the count is equal to o then we have a contiguous subarray of length equal to i+1
      max_length = i + 1;
    }
    if (count in hash) {

      max_length = Math.max(max_length, i - hash[count]); // update our max length
    } else {
      hash[count] = i;
    }

  }
  return max_length;
};
// @lc code=end

538.把二叉搜索树转换为累加树

/*
 * @lc app=leetcode.cn id=538 lang=typescript
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function convertBST(root: TreeNode | null): TreeNode | null {
  let sum = 0
  function reverseInorderTraversal(node: TreeNode | null):void {
    // 如果节点为空，则直接返回
    if (!node) return
    // 先递归右子树
    reverseInorderTraversal(node.right)
     // 累加上前面节点的值和自身节点的值,更新当前节点的值
    sum += node.val
    node.val = sum
    // 递归遍历左子树
    reverseInorderTraversal(node.left)
  }
  // 调用辅助函数进行遍历，并返回根节点
  reverseInorderTraversal(root)
  return root
};
// @lc code=end

543.二叉树的直径

/*
 * @lc app=leetcode.cn id=543 lang=typescript
 *
 * [543] 二叉树的直径
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function diameterOfBinaryTree(root: TreeNode | null): number {
  // 定义一个变量 maxDiameter 用于记录最大直径
  let maxDiameter = 0

  function dfs(node: TreeNode | null): number {
    if (!node) return 0

    // 递归左右子树的深度
    const left = dfs(node.left)
    const right = dfs(node.right)

    // 获取最大直径
    maxDiameter = Math.max(maxDiameter, left + right)

    // 返回深度，加上自身节点的深度1
    return Math.max(left, right) + 1
  }
  // 调用辅助函数计算深度，并返回最大直径
  dfs(root)
  return maxDiameter

};
// @lc code=end

560.和为-k-的子数组

/*
 * @lc app=leetcode.cn id=560 lang=typescript
 *
 * [560] 和为 K 的子数组
 */
/**
 * 初始化{0，1}可以看作是在前缀和前多加了一个和，是为了防止从序号0开始加到i时刚好为k的情况出现时，没法找到对应数值计数
*为什么如果前缀和减去 k 在 map 中出现过，则说明以当前位置为结尾的子数组和为 k
*如果前缀和减去 k 在 map 中出现过，则说明在之前的前缀和中有一个值等于当前前缀和减去 k。假设当前位置为 i，前缀和为 sum，前缀和减去 k 的值为 sum - k，则满足 sum - k 在 map 中出现过的条件为：
*sum - (sum - k) = k 在之前的前缀和中出现过。
*因此，以当前位置 i 为结尾的子数组中，存在一个子数组的和为 k，这个子数组的起始位置可以是之前任意一个位置 j（0 <= j < i），满足从 j 到 i 的子数组和为 k。因此，以当前位置 i 为结尾的符合要求的子数组的个数就等于之前前缀和中 sum - k 出现的次数。
*/

// @lc code=start
function subarraySum(nums: number[], k: number): number {
  // 创建一个 Map，用于存储前缀和及其出现的次数
  const map = new Map();
  // 初始化，将前缀和为 0 的情况出现次数设为 1
  map.set(0, 1);

  // 定义变量 sum 和 count，分别表示当前的前缀和和符合要求的子数组个数
  let sum = 0;
  let count = 0;

  // 遍历数组 nums 中的每个元素
  for (let num of nums) {
    // 更新前缀和
    sum += num;

    // 如果前缀和减去 k 在 map 中出现过，则说明以当前位置为结尾的子数组和为 k
    if (map.has(sum - k)) {
      // 累加符合要求的子数组个数
      count += map.get(sum - k);
    }

    // 将当前前缀和及其出现次数加入 map 中
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  // 返回符合要求的子数组个数
  return count;
};
// @lc code=end

581.最短无序连续子数组

/*
 * @lc app=leetcode.cn id=581 lang=typescript
 *
 * [581] 最短无序连续子数组
 */

// @lc code=start
function findUnsortedSubarray(nums: number[]): number {
  const n = nums.length
  let l = 0
  let r = n - 1
  // 从左往右找到第一个不是按升序的元素
  while (l < n - 1 && nums[l] <= nums[l + 1]) {
    l++
  }
  // 数组已经有序，直接返回 0
  if (l === n - 1) {
    return 0;
  }
  // 从右往左找到第一个不是降序的元素
  while (r > 0 && nums[r - 1] <= nums[r]) {
    r--
  }
  // 找l~r之间的最小值和最大值
  let minNum = Infinity 
  let maxNum = -Infinity
  for (let i = l; i <= r; i++) {
    minNum = Math.min(minNum,nums[i])
    maxNum = Math.max(maxNum, nums[i])
  }

  // 向左扩展 l，直到找到第一个大于 minNum 的位置
  while (l >= 0 && nums[l] > minNum) {
    l--
  }
  
  // 向右扩展 r，直到找到第一个小于 maxNum 的位置
  while (r < n  && nums[r] < maxNum) {
    r++
  }

  return r - l - 1
};
// @lc code=end

617.合并二叉树

/*
 * @lc app=leetcode.cn id=617 lang=typescript
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
  // 如果没有节点，直接返回另一个节点
  if (!root1) return root2
  if (!root2) return root1
  // 新建节点并，值为两个根节点的值之和
  const mergeTree = new TreeNode(root1.val + root2.val)
  // 递归左节点
  mergeTree.left = mergeTrees(root1.left, root2.left)
  // 递归右节点
  mergeTree.right = mergeTrees(root1.right, root2.right)
  
  return mergeTree
};
// @lc code=end

621.任务调度器

/*
 * @lc app=leetcode.cn id=621 lang=typescript
 *
 * [621] 任务调度器
 */

// @lc code=start
function leastInterval(tasks: string[], n: number): number {
  const taskCounts = new Map<string, number>(); // 使用 Map 记录每个任务出现的次数
  let maxCount = 0; // 出现次数最多的任务的个数
  let maxTaskCount = 0; // 出现次数最多的任务的出现次数

  for (const task of tasks) {
    const count = (taskCounts.get(task) ?? 0) + 1; // 获取任务的出现次数
    taskCounts.set(task, count); // 更新任务的出现次数
    if (count > maxTaskCount) { // 如果当前任务的出现次数超过了出现次数最多的任务的出现次数
      maxTaskCount = count;
      maxCount = 1;
    } else if (count === maxTaskCount) { // 如果当前任务的出现次数等于出现次数最多的任务的出现次数
      maxCount++;
    }
  }
  // 总排队时间 = (最大桶个数 - 1) * (n + 1) + 出现次数最多的桶的个数
  return Math.max(tasks.length, (maxTaskCount - 1) * (n + 1) + maxCount);

};
// @lc code=end

647.回文子串

/*
 * @lc app=leetcode.cn id=647 lang=typescript
 *
 * [647] 回文子串
 */

// @lc code=start
function countSubstrings(s: string): number {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    expand(i, i) // 奇数长度的回文子串
    expand(i, i + 1) // 偶数长度的回文子串
  }
  return count
  // 定义扩展函数expand
  function expand(l:number, r:number) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { // 当左右指针指向字符相等时，继续扩展

      count++ // 增加回文子串计数器
      l-- // 向左扩展
      r++ // 向右扩展
    }
  }
};



// @lc code=end

713.乘积小于-k-的子数组

/*
 * @lc app=leetcode.cn id=713 lang=typescript
 *
 * [713] 乘积小于 K 的子数组
 */

// @lc code=start
function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0
  let left = 0
  let right = 0
  let res = 0
  let target = 1
  while (right < nums.length) {
    target *= nums[right]
    while (target >= k) {
      target /= nums[left]
      left++
    }
    res += right - left + 1
    right++
  }
  return res
};
// @lc code=end

739.每日温度

/*
 * @lc app=leetcode.cn id=739 lang=typescript
 * 在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。
 * [739] 每日温度
 */

// @lc code=start
function dailyTemperatures(temperatures: number[]): number[] {

  const stack: number[] = []
  // 初始化气温列表，默认值为0
  const res = new Array(temperatures.length).fill(0)
  for (let i = 0; i < temperatures.length; i++) {
    //将栈顶元素下标对应的值和当前元素进行比较
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop() as number
      res[idx] = i-idx
    }
    stack.push(i)
  }
  return res
};
// @lc code=end

763.划分字母区间

/*
 * @lc app=leetcode.cn id=763 lang=typescript
 *
 * [763] 划分字母区间
 */

// @lc code=start
function partitionLabels(s: string): number[] {
  let res: number[] = []
  let maxIndex = 0
  let start = 0
  // 记录每个字符出现的最大索引
  const map = new Map<string, number>()
  for (let i = 0; i < s.length; i++) {
    map.set(s[i],i)
  }
  for (let i = 0; i < s.length; i++) {
    // 更新当前片段出现字符的最大索引
    maxIndex = Math.max(maxIndex, map.get(s[i])!)
    
    // 如果当前索引等于最大索引，切割
    if (maxIndex === i) {
      res.push(i - start + 1)
      start = i+1
    }
  }
  return res
};
// @lc code=end

921.使括号有效的最少添加

/*
 * @lc app=leetcode.cn id=921 lang=typescript
 *
 * [921] 使括号有效的最少添加
 */

// @lc code=start
function minAddToMakeValid(s: string): number {
  const stack:string[]= []
  for (let i = 0; i < s.length; i++) {
    // 如果是)并且绽的最后一个元素是(匹配，则出栈
    if (s[i] === ')' && stack[stack.length - 1] === '(') stack.pop()
    else stack.push(s[i])
  }
  return stack.length
};
// @lc code=end

925.长按键入

/*
 * @lc app=leetcode.cn id=925 lang=typescript
 *
 * [925] 长按键入
 */

// @lc code=start
function isLongPressedName(name: string, typed: string): boolean {
  let j = 0 // 初始化 name 的索引为 0
  for (let i = 0; i < typed.length; i++) {
    // 如果当前字符相同，将 name 的索引加 1
    if (typed[i] === name[j]) {
      j++
      // 如果当前字符与 name 的前一个字符相同，继续扫描 typed
    } else if (typed[i] === name[j - 1]) {
      continue
    } else {
      // 如果当前字符与 name 中的字符不同且与 name 前一个字符也不同，返回 false
      return false
    }
  }
  // 如果扫描完 typed 后，name 的索引等于 name 的长度，返回 true，否则返回 false
  return j === name.length
};
// @lc code=end

946.验证栈序列

/*
 * @lc app=leetcode.cn id=946 lang=typescript
 *
 * [946] 验证栈序列
 */

// @lc code=start
function validateStackSequences(pushed: number[], popped: number[]): boolean {
  const stack: number[] = []
  for (const cur of pushed) {
    stack.push(cur)
    // 和出栈元素进行比对，如果匹配都弹出栈
    while (stack[stack.length - 1] === popped[0] && stack.length) {
      stack.pop()
      popped.shift()
    }
  }
  return !stack.length

};
// @lc code=end

1190.反转每对括号间的子串

/*
 * @lc app=leetcode.cn id=1190 lang=typescript
 *
 * [1190] 反转每对括号间的子串
 */

// @lc code=start
function reverseParentheses(s: string): string {
  const stack:string[] = [""]
  for (const c of s) {
    if (c === '(') stack.push("")
    else if (c === ')') {
      const str = stack.pop()?.split("").reverse().join("")
      stack[stack.length - 1] += str
    } else {
      stack[stack.length-1]+= c
    }
  }
  return stack.pop() as string
};
// @lc code=end

1249.移除无效的括号

/*
 * @lc app=leetcode.cn id=1249 lang=typescript
 *
 * [1249] 移除无效的括号
 */

// @lc code=start
function minRemoveToMakeValid(s: string): string {
  const arr = [...s] // 将字符串转化为字符数组
  const stack: number[] = [] // 定义栈，用于存储未匹配的左括号 '(' 的下标

  // 第一遍扫描，找出未匹配的左括号，并将其下标存入栈中
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === '(') { // 如果当前字符为左括号 '('，将其下标存入栈中
      stack.push(i)
    } else if (arr[i] === ')') { // 如果当前字符为右括号 ')'
      if (stack.length) { // 如果栈非空，说明当前右括号匹配到了一个左括号
        stack.pop() // 弹出栈顶的左括号
      } else { // 如果栈为空，说明当前右括号没有匹配的左括号，将其替换为空字符串
        arr[i] = ''
      }
    }
  }
  // 第二遍扫描，将剩余未匹配的左括号替换为空字符串
  for (const i of stack) {
    arr[i] = ''
  }
  return arr.join('') // 将字符数组转化为字符串并返回
};
// @lc code=end

Previous算法 Next面向对象和设计模式

Last updated 2 years ago