Attraction11

Appearance

On this page

LeetCode Record

1. 两数之和

思路：通过 Map 数据结构，每次遍历数字都去判断数组中是否存在差的那个值，第一个值一定是会在遍历的时候存进去的，等到第二次遍历就可以取出并且返回

链接：https://leetcode.cn/problems/two-sum/

ts
function twoSum(nums: number[], target: number): number[] {
  const resultMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    const difNum = target - nums[i];
    if (resultMap.has(difNum)) {
      return [resultMap.get(difNum), i];
    }
    resultMap.set(nums[i], i);
  }
}

function twoSum(nums: number[], target: number): number[] {
  const resultMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    const difNum = target - nums[i];
    if (resultMap.has(difNum)) {
      return [resultMap.get(difNum), i];
    }
    resultMap.set(nums[i], i);
  }
}

1518. 换酒问题

链接：https://leetcode.cn/problems/water-bottles

思路：通过 while 循环记录每次兑换酒后会剩下的空酒瓶，如果剩下的空酒拼不能换酒则终止循环

ts
function numWaterBottles(numBottles: number, numExchange: number): number {
  // 第一次兑换的酒瓶
  const firstExchangeBottles = Math.floor(numBottles / numExchange);
  // 第一次兑换后剩下的空酒瓶
  let otherBottles =
    numBottles - firstExchangeBottles * numExchange + firstExchangeBottles;
  // 能喝到的总瓶数
  let allBottles = numBottles + firstExchangeBottles;
  while (otherBottles >= numExchange) {
    // 再次兑换的酒瓶数量
    const exchangeNum = Math.floor(otherBottles / numExchange);
    // 剩下的空酒瓶
    otherBottles = otherBottles - exchangeNum * numExchange + exchangeNum;
    // 更新能喝到的总瓶数
    allBottles = allBottles + exchangeNum;
  }
  return allBottles;
}

function numWaterBottles(numBottles: number, numExchange: number): number {
  // 第一次兑换的酒瓶
  const firstExchangeBottles = Math.floor(numBottles / numExchange);
  // 第一次兑换后剩下的空酒瓶
  let otherBottles =
    numBottles - firstExchangeBottles * numExchange + firstExchangeBottles;
  // 能喝到的总瓶数
  let allBottles = numBottles + firstExchangeBottles;
  while (otherBottles >= numExchange) {
    // 再次兑换的酒瓶数量
    const exchangeNum = Math.floor(otherBottles / numExchange);
    // 剩下的空酒瓶
    otherBottles = otherBottles - exchangeNum * numExchange + exchangeNum;
    // 更新能喝到的总瓶数
    allBottles = allBottles + exchangeNum;
  }
  return allBottles;
}

506. 相对名次

链接：https://leetcode.cn/problems/relative-ranks/

思路： 使用 map 将 score 数组进行降序排序，所在下标+1 即名次

ts
var findRelativeRanks = function (score) {
  const result = new Array(score.length).fill(-1);
  const rankArray = score
    .map((item, index) => {
      return {
        value: item, // 得分
        index: index, // 所在下标
      };
    })
    .sort((a, b) => b.value - a.value);

  rankArray.forEach((item, index) => {
    if (index === 0) {
      result[item.index] = "Gold Medal";
    } else if (index === 1) {
      result[item.index] = "Silver Medal";
    } else if (index === 2) {
      result[item.index] = "Bronze Medal";
    } else {
      // item.index 所在下标
      // index 所在名次
      result[item.index] = (index + 1).toString();
    }
  });

  return result;
};

var findRelativeRanks = function (score) {
  const result = new Array(score.length).fill(-1);
  const rankArray = score
    .map((item, index) => {
      return {
        value: item, // 得分
        index: index, // 所在下标
      };
    })
    .sort((a, b) => b.value - a.value);

  rankArray.forEach((item, index) => {
    if (index === 0) {
      result[item.index] = "Gold Medal";
    } else if (index === 1) {
      result[item.index] = "Silver Medal";
    } else if (index === 2) {
      result[item.index] = "Bronze Medal";
    } else {
      // item.index 所在下标
      // index 所在名次
      result[item.index] = (index + 1).toString();
    }
  });

  return result;
};

605. 种花问题

链接：https://leetcode.cn/problems/can-place-flowers/

思路：通过 While 循环来对数组进行遍历，通过 recordN 和 recordIndex 来记录花种的数量和种的花坛的位置。循环条件是花坛的位置<数组的长度。如果花种的数量 等于 n 代表可以种

ts
function canPlaceFlowers(flowerbed: number[], n: number): boolean {
  if (flowerbed.length === 1 && flowerbed[0] === 0 && n === 1) {
    return true;
  }

  // 记录已经种下去的花的数量
  let recordN = 0;
  // 记录种花的步 下标
  let recordIndex = 0;

  while (recordIndex < flowerbed.length) {
    if (recordN === n) break;

    const place = flowerbed[recordIndex];
    if (place === 1) {
      recordIndex = recordIndex + 1;
    } else {
      // 可以种植
      // 种植两端的情况
      if (
        (recordIndex === 0 && flowerbed[recordIndex + 1] === 0) ||
        (recordIndex === flowerbed.length - 1 &&
          flowerbed[recordIndex - 1] === 0)
      ) {
        recordN = recordN + 1;
        flowerbed[recordIndex] = 1;
      } else if (
        flowerbed[recordIndex - 1] === 0 &&
        flowerbed[recordIndex + 1] === 0
      ) {
        recordN = recordN + 1;
        flowerbed[recordIndex] = 1;
      }

      recordIndex = recordIndex + 1;
    }
  }

  if (recordN === n) {
    return true;
  }

  return false;
}

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
  if (flowerbed.length === 1 && flowerbed[0] === 0 && n === 1) {
    return true;
  }

  // 记录已经种下去的花的数量
  let recordN = 0;
  // 记录种花的步 下标
  let recordIndex = 0;

  while (recordIndex < flowerbed.length) {
    if (recordN === n) break;

    const place = flowerbed[recordIndex];
    if (place === 1) {
      recordIndex = recordIndex + 1;
    } else {
      // 可以种植
      // 种植两端的情况
      if (
        (recordIndex === 0 && flowerbed[recordIndex + 1] === 0) ||
        (recordIndex === flowerbed.length - 1 &&
          flowerbed[recordIndex - 1] === 0)
      ) {
        recordN = recordN + 1;
        flowerbed[recordIndex] = 1;
      } else if (
        flowerbed[recordIndex - 1] === 0 &&
        flowerbed[recordIndex + 1] === 0
      ) {
        recordN = recordN + 1;
        flowerbed[recordIndex] = 1;
      }

      recordIndex = recordIndex + 1;
    }
  }

  if (recordN === n) {
    return true;
  }

  return false;
}

206. 反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/

typescript
/**
 * 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 reverseList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let pre = null;
  let cur = head;

  while (cur) {
    // 当前节点的下一个节点
    const swap = cur.next;
    // 改变节点的指向 指向上一个节点
    cur.next = pre;
    pre = cur;
    cur = swap;
  }
  return pre;
}

/**
 * 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 reverseList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let pre = null;
  let cur = head;

  while (cur) {
    // 当前节点的下一个节点
    const swap = cur.next;
    // 改变节点的指向 指向上一个节点
    cur.next = pre;
    pre = cur;
    cur = swap;
  }
  return pre;
}

1800. 最大升序子数组和

思路：遍历数组，有遇到比上一项小的数就代表一个升序子数组的结束，然后通过变量记录最大的升序子数组和，以及上一项升序子数组的和，当前的升序子数组的和。最后变量结束后返回最大的升序子数组和就行。

链接：https://leetcode.cn/problems/maximum-ascending-subarray-sum/description/

ts
function maxAscendingSum(nums: number[]): number {
  // 存储子升序数组的和
  let sumResult = nums[0];
  let preResult = nums[0];
  let maxSumResult = nums[0];
  // 子升序数组的起始下标和终端下标
  let start,
    end = 0;

  for (let index = 1; index < nums.length; index++) {
    const curNum = nums[index];
    if (curNum > nums[index - 1]) {
      sumResult = sumResult + nums[index];
      end = end + 1;
    } else {
      start = index;
      end = index;

      if (sumResult > maxSumResult) {
        maxSumResult = sumResult;
      }

      preResult = sumResult;
      sumResult = nums[index];
    }
  }

  if (sumResult > maxSumResult) {
    maxSumResult = sumResult;
  }

  return maxSumResult;
}

function maxAscendingSum(nums: number[]): number {
  // 存储子升序数组的和
  let sumResult = nums[0];
  let preResult = nums[0];
  let maxSumResult = nums[0];
  // 子升序数组的起始下标和终端下标
  let start,
    end = 0;

  for (let index = 1; index < nums.length; index++) {
    const curNum = nums[index];
    if (curNum > nums[index - 1]) {
      sumResult = sumResult + nums[index];
      end = end + 1;
    } else {
      start = index;
      end = index;

      if (sumResult > maxSumResult) {
        maxSumResult = sumResult;
      }

      preResult = sumResult;
      sumResult = nums[index];
    }
  }

  if (sumResult > maxSumResult) {
    maxSumResult = sumResult;
  }

  return maxSumResult;
}

258. 各位相加

链接：https://leetcode.cn/problems/add-digits/

ts
function addDigits(num: number): number {
  if (num === 0) return 0;

  let numberArr = [];
  let handleNum = num;

  while (handleNum >= 10) {
    numberArr = handleNum.toString().split("");

    handleNum = numberArr.reduce(
      (preValue: string | number, curValue: string) => {
        return Number(preValue) + Number(curValue);
      },
      0
    );
  }

  return handleNum;
}

function addDigits(num: number): number {
  if (num === 0) return 0;

  let numberArr = [];
  let handleNum = num;

  while (handleNum >= 10) {
    numberArr = handleNum.toString().split("");

    handleNum = numberArr.reduce(
      (preValue: string | number, curValue: string) => {
        return Number(preValue) + Number(curValue);
      },
      0
    );
  }

  return handleNum;
}

260. 只出现一次的数字 III

链接：https://leetcode.cn/problems/single-number-iii/

ts
function singleNumber(nums: number[]): number[] {
  if (nums.length === 2) return nums;

  const result = [];
  const handleNums = nums;

  while (nums.length !== 0) {
    const shiftItem = handleNums.shift()!;

    const isExistIndex = handleNums.indexOf(shiftItem);

    if (isExistIndex !== -1) {
      handleNums.splice(isExistIndex, 1);
    } else {
      result.push(shiftItem);
    }
  }
  return result;
}

function singleNumber(nums: number[]): number[] {
  if (nums.length === 2) return nums;

  const result = [];
  const handleNums = nums;

  while (nums.length !== 0) {
    const shiftItem = handleNums.shift()!;

    const isExistIndex = handleNums.indexOf(shiftItem);

    if (isExistIndex !== -1) {
      handleNums.splice(isExistIndex, 1);
    } else {
      result.push(shiftItem);
    }
  }
  return result;
}
ts
function singleNumber(nums: number[]): number[] {
  const set: Set<number> = new Set();
  for (const z of nums) {
    if (set.has(z)) set.delete(z);
    else set.add(z);
  }
  return Array.from(set);
}

function singleNumber(nums: number[]): number[] {
  const set: Set<number> = new Set();
  for (const z of nums) {
    if (set.has(z)) set.delete(z);
    else set.add(z);
  }
  return Array.from(set);
}

1470. 重新排列数组

链接：https://leetcode.cn/problems/shuffle-the-array/

typescript
function shuffle(nums: number[], n: number): number[] {
  if (n === 1) return nums;
  const result: number[] = [];
  for (let index = 0; index < n; index++) {
    result.push(nums[index], nums[index + n]);
  }
  return result;
}

function shuffle(nums: number[], n: number): number[] {
  if (n === 1) return nums;
  const result: number[] = [];
  for (let index = 0; index < n; index++) {
    result.push(nums[index], nums[index + n]);
  }
  return result;
}

704. 二分查找

思路：利用两个变量来限定查找的范围，判断目标值在左区间还是右区间

链接：https://leetcode.cn/problems/binary-search/

ts
function search(nums: number[], target: number): number {
  if (nums.length === 1 && nums[0] === target) return 0;
  let leftIndex = 0;
  let rightIndex = nums.length - 1;
  let result = null;

  while (leftIndex < rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    if (nums[midIndex] === target) {
      result = midIndex;
      break;
    } else if (nums[midIndex] < target) {
      leftIndex = midIndex + 1;
    } else if (nums[midIndex] > target) {
      rightIndex = midIndex - 1;
    }
  }

  // 找到目标值了
  if (leftIndex === rightIndex && nums[leftIndex] === target) return leftIndex;

  if (result !== null) return result;

  return -1;
}

function search(nums: number[], target: number): number {
  if (nums.length === 1 && nums[0] === target) return 0;
  let leftIndex = 0;
  let rightIndex = nums.length - 1;
  let result = null;

  while (leftIndex < rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    if (nums[midIndex] === target) {
      result = midIndex;
      break;
    } else if (nums[midIndex] < target) {
      leftIndex = midIndex + 1;
    } else if (nums[midIndex] > target) {
      rightIndex = midIndex - 1;
    }
  }

  // 找到目标值了
  if (leftIndex === rightIndex && nums[leftIndex] === target) return leftIndex;

  if (result !== null) return result;

  return -1;
}

35. 搜索插入位置

思路：二分查找法，不断缩小查找区间，返回严格小于或等于目标元素的下标值

链接：https://leetcode.cn/problems/search-insert-position/

typescript
function searchInsert(nums: number[], target: number): number {
  let len = nums.length;
  if (len === 0) return 0;
  if (nums[len - 1] < target) return len;

  let leftIndex = 0;
  let rightIndex = len - 1;

  while (leftIndex < rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    // 找到 nums[midIndex] 严格小于目标元素
    // 不断缩小范围比较范围
    if (nums[midIndex] < target) {
      leftIndex = midIndex + 1;
    } else {
      rightIndex = midIndex;
    }
  }
  return leftIndex;
}

function searchInsert(nums: number[], target: number): number {
  let len = nums.length;
  if (len === 0) return 0;
  if (nums[len - 1] < target) return len;

  let leftIndex = 0;
  let rightIndex = len - 1;

  while (leftIndex < rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    // 找到 nums[midIndex] 严格小于目标元素
    // 不断缩小范围比较范围
    if (nums[midIndex] < target) {
      leftIndex = midIndex + 1;
    } else {
      rightIndex = midIndex;
    }
  }
  return leftIndex;
}

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

链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

ts
function searchRange(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
  const result = [];
  // 寻找左边界
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 不同的点
      right = mid - 1;
    }
  }
  if (left >= nums.length || nums[left] != target) {
    return [-1, -1];
  }
  result.push(left);
  // 寻找右边界
  left = 0;
  right = nums.length - 1;
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 不同的点
      left = mid + 1;
    }
  }
  if (right < 0 || nums[right] != target) {
    return [-1, -1];
  }
  result.push(right);

  return result;
}

function searchRange(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
  const result = [];
  // 寻找左边界
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 不同的点
      right = mid - 1;
    }
  }
  if (left >= nums.length || nums[left] != target) {
    return [-1, -1];
  }
  result.push(left);
  // 寻找右边界
  left = 0;
  right = nums.length - 1;
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 不同的点
      left = mid + 1;
    }
  }
  if (right < 0 || nums[right] != target) {
    return [-1, -1];
  }
  result.push(right);

  return result;
}

70. 爬楼梯

规律： Fn = Fn-1 + Fn-2（N 阶楼梯 = N-1 阶 + N-2 阶）

链接：https://leetcode.cn/problems/climbing-stairs/

ts
function climbStairs(n: number): number {
  // 1级 1种
  // 2级 2种
  // 3级 3种
  // 4级 5种 （1+1+1+1、+1+2、2+1+1、2+2）
  // 5级 8种 （1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、 2+1+1+1、1+2+2、2+1+2、2+2+1）
  // n级 Fn = F(n-1) + F(n-2)
  const resultClimbStairs = [0, 1, 2, 3];
  let recordNum = 3;

  if (n <= recordNum) return resultClimbStairs[n];

  while (recordNum !== n) {
    recordNum = recordNum + 1;
    resultClimbStairs[recordNum] =
      resultClimbStairs[recordNum - 1] + resultClimbStairs[recordNum - 2];
  }
  return resultClimbStairs[n];
}

function climbStairs(n: number): number {
  // 1级 1种
  // 2级 2种
  // 3级 3种
  // 4级 5种 （1+1+1+1、+1+2、2+1+1、2+2）
  // 5级 8种 （1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、 2+1+1+1、1+2+2、2+1+2、2+2+1）
  // n级 Fn = F(n-1) + F(n-2)
  const resultClimbStairs = [0, 1, 2, 3];
  let recordNum = 3;

  if (n <= recordNum) return resultClimbStairs[n];

  while (recordNum !== n) {
    recordNum = recordNum + 1;
    resultClimbStairs[recordNum] =
      resultClimbStairs[recordNum - 1] + resultClimbStairs[recordNum - 2];
  }
  return resultClimbStairs[n];
}

387. 字符串中的第一个唯一字符

思路：使用 Set 数据结构来分别存放单一字符和重复字符，最后遍历字符串，在遍历完字符串后返回单一字符数组的第一个字符去获取它的下标即可

链接：https://leetcode.cn/problems/first-unique-character-in-a-string/

typescript
function firstUniqChar(s: string): number {
  // [l, t, c, o ,d,e] l
  // [v,t,c,d,e] o
  // []
  // 以队列数据结构返回第一个
  // 遍历每个字符串，挨个添加至数组中，添加前判断数组中是否存在该字符串，如果存在删除数组的那个字母，不存在添加到队列尾部。直到字符串遍历完成
  const singleChar: Set<string> = new Set();
  const repeatChar: Set<string> = new Set();
  for (let i = 0; i < s.length; i++) {
    const isHave = singleChar.has(s[i]) || repeatChar.has(s[i]);
    if (isHave) {
      // 删除Set字符
      singleChar.delete(s[i]);
      // 添加字符串到重复字符串数据中
      repeatChar.add(s[i]);
    } else {
      singleChar.add(s[i]);
    }
  }
  const resultArr = new Array(...singleChar);
  if (resultArr.length === 0) return -1;
  return s.indexOf(resultArr[0]);
}

function firstUniqChar(s: string): number {
  // [l, t, c, o ,d,e] l
  // [v,t,c,d,e] o
  // []
  // 以队列数据结构返回第一个
  // 遍历每个字符串，挨个添加至数组中，添加前判断数组中是否存在该字符串，如果存在删除数组的那个字母，不存在添加到队列尾部。直到字符串遍历完成
  const singleChar: Set<string> = new Set();
  const repeatChar: Set<string> = new Set();
  for (let i = 0; i < s.length; i++) {
    const isHave = singleChar.has(s[i]) || repeatChar.has(s[i]);
    if (isHave) {
      // 删除Set字符
      singleChar.delete(s[i]);
      // 添加字符串到重复字符串数据中
      repeatChar.add(s[i]);
    } else {
      singleChar.add(s[i]);
    }
  }
  const resultArr = new Array(...singleChar);
  if (resultArr.length === 0) return -1;
  return s.indexOf(resultArr[0]);
}

面试题 01.06 字符串压缩

链接：https://leetcode.cn/problems/compress-string-lcci/

ts
function compressString(S: string): string {
  let compressString = "";
  const recordArr: [string, number] = ["-1", -1];
  const SArr = S.split("");

  for (let i = 0; i < SArr.length; i++) {
    const currentRecordChar = recordArr[0];
    if (currentRecordChar === "-1") {
      recordArr[0] = SArr[i];
      recordArr[1] = 1;
    } else if (currentRecordChar === SArr[i]) {
      recordArr[1] += 1;
    } else {
      compressString += `${recordArr[0]}${recordArr[1]}`;
      recordArr[0] = SArr[i];
      recordArr[1] = 1;
    }
  }
  compressString += `${recordArr[0]}${recordArr[1]}`;
  if (compressString.length >= S.length) return S;
  return compressString;
}

function compressString(S: string): string {
  let compressString = "";
  const recordArr: [string, number] = ["-1", -1];
  const SArr = S.split("");

  for (let i = 0; i < SArr.length; i++) {
    const currentRecordChar = recordArr[0];
    if (currentRecordChar === "-1") {
      recordArr[0] = SArr[i];
      recordArr[1] = 1;
    } else if (currentRecordChar === SArr[i]) {
      recordArr[1] += 1;
    } else {
      compressString += `${recordArr[0]}${recordArr[1]}`;
      recordArr[0] = SArr[i];
      recordArr[1] = 1;
    }
  }
  compressString += `${recordArr[0]}${recordArr[1]}`;
  if (compressString.length >= S.length) return S;
  return compressString;
}

1832. 判断句子是否为全字母句

链接：https://leetcode.cn/problems/check-if-the-sentence-is-pangram/

typescript
function checkIfPangram(sentence: string): boolean {
  // ASCII 码 [97, 122]
  // 变量每个字符，获取它们的ASCII码，然后分别存储在Set集合中，最后进行升序排列，去比较它们的长度
  const ASCIISet: Set<number> = new Set();
  for (let i = 0; i < sentence.length; i++) {
    const ASCIICharNum = sentence.charCodeAt(i);
    ASCIISet.add(ASCIICharNum);
  }
  const ASCIIArr = Array.from(ASCIISet);
  const result = ASCIIArr.sort((a, b) => a - b);
  if (result.length === 26) return true;
  return false;
}

function checkIfPangram(sentence: string): boolean {
  // ASCII 码 [97, 122]
  // 变量每个字符，获取它们的ASCII码，然后分别存储在Set集合中，最后进行升序排列，去比较它们的长度
  const ASCIISet: Set<number> = new Set();
  for (let i = 0; i < sentence.length; i++) {
    const ASCIICharNum = sentence.charCodeAt(i);
    ASCIISet.add(ASCIICharNum);
  }
  const ASCIIArr = Array.from(ASCIISet);
  const result = ASCIIArr.sort((a, b) => a - b);
  if (result.length === 26) return true;
  return false;
}

459. 重复的子字符串

链接：https://leetcode.cn/problems/repeated-substring-pattern/

typescript
function repeatedSubstringPattern(s: string): boolean {
  let recordStr = "";
  for (let i = 0; i < s.length; i++) {
    recordStr += s[i];
    const repeatNum = Math.floor(s.length / recordStr.length);
    // repeatNum === 1 证明字符串遍历到尾了 不需要再去找子字符串了
    if (repeatNum === 1) {
      return false;
    } else if (s === recordStr.repeat(repeatNum)) {
      return true;
    }
  }
  return false;
}

function repeatedSubstringPattern(s: string): boolean {
  let recordStr = "";
  for (let i = 0; i < s.length; i++) {
    recordStr += s[i];
    const repeatNum = Math.floor(s.length / recordStr.length);
    // repeatNum === 1 证明字符串遍历到尾了 不需要再去找子字符串了
    if (repeatNum === 1) {
      return false;
    } else if (s === recordStr.repeat(repeatNum)) {
      return true;
    }
  }
  return false;
}

993. 二叉树的堂兄弟节点

思路：递归遍历，记录连个节点的父节点和节点深度，最后进行比较

链接：https://leetcode.cn/problems/cousins-in-binary-tree/

typescript
/**
 * 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)
 *     }
 * }
 */
interface ResultNode {
  parentNode: TreeNode;
  depth: number;
}

function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  let XResultNode: ResultNode = {
    parentNode: null,
    depth: 0,
  };
  let YResultNode: ResultNode = {
    parentNode: null,
    depth: 0,
  };

  function eachTree(eachNode: TreeNode, parentNode: TreeNode, depth: number) {
    let each = eachNode;
    if (each.val === x) {
      XResultNode.parentNode = parentNode;
      XResultNode.depth = depth;
    }
    if (each.val === y) {
      YResultNode.parentNode = parentNode;
      YResultNode.depth = depth;
    }

    if (each.left) {
      eachTree(each.left, each, depth + 1);
    }
    if (each.right) {
      eachTree(each.right, each, depth + 1);
    }
  }

  eachTree(root, null, 0);
  if (
    XResultNode.depth === YResultNode.depth &&
    XResultNode.parentNode !== YResultNode.parentNode
  )
    return true;
  return false;
}

/**
 * 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)
 *     }
 * }
 */
interface ResultNode {
  parentNode: TreeNode;
  depth: number;
}

function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  let XResultNode: ResultNode = {
    parentNode: null,
    depth: 0,
  };
  let YResultNode: ResultNode = {
    parentNode: null,
    depth: 0,
  };

  function eachTree(eachNode: TreeNode, parentNode: TreeNode, depth: number) {
    let each = eachNode;
    if (each.val === x) {
      XResultNode.parentNode = parentNode;
      XResultNode.depth = depth;
    }
    if (each.val === y) {
      YResultNode.parentNode = parentNode;
      YResultNode.depth = depth;
    }

    if (each.left) {
      eachTree(each.left, each, depth + 1);
    }
    if (each.right) {
      eachTree(each.right, each, depth + 1);
    }
  }

  eachTree(root, null, 0);
  if (
    XResultNode.depth === YResultNode.depth &&
    XResultNode.parentNode !== YResultNode.parentNode
  )
    return true;
  return false;
}

989. 数组形式的整数加法

思路：将 k 也转换为 number[] 的数组，比较之间谁更大更小，填充数字 0，使得两个数组长度相同。进行 while 循环，从末尾元素两两相加，和大于 10 的数进一位即可

链接：https://leetcode.cn/problems/add-to-array-form-of-integer/

ts
function addToArrayForm(num: number[], k: number): number[] {
  let kNumArr = k
    .toString()
    .split("")
    .map((item) => Number(item));
  const dif = Math.abs(kNumArr.length - num.length);
  if (kNumArr.length > num.length) {
    num = [...new Array(dif).fill(0), ...num];
  } else if (kNumArr.length < num.length) {
    kNumArr = [...new Array(dif).fill(0), ...kNumArr];
  }
  const result = [];
  let currentIndex = num.length - 1;
  // 是否相加进一位
  let isEnterOne = false;
  while (currentIndex >= 0) {
    let sum = kNumArr[currentIndex] + num[currentIndex];
    // 位数的数 + 1
    if (isEnterOne) sum = sum + 1;
    if (sum >= 10) {
      result[currentIndex] = sum % 10;
      isEnterOne = true;
    } else {
      result[currentIndex] = sum;
      isEnterOne = false;
    }
    currentIndex--;
  }
  // 处理第一位元素相加大于10的情况
  if (isEnterOne) result.unshift(1);
  return result;
}

function addToArrayForm(num: number[], k: number): number[] {
  let kNumArr = k
    .toString()
    .split("")
    .map((item) => Number(item));
  const dif = Math.abs(kNumArr.length - num.length);
  if (kNumArr.length > num.length) {
    num = [...new Array(dif).fill(0), ...num];
  } else if (kNumArr.length < num.length) {
    kNumArr = [...new Array(dif).fill(0), ...kNumArr];
  }
  const result = [];
  let currentIndex = num.length - 1;
  // 是否相加进一位
  let isEnterOne = false;
  while (currentIndex >= 0) {
    let sum = kNumArr[currentIndex] + num[currentIndex];
    // 位数的数 + 1
    if (isEnterOne) sum = sum + 1;
    if (sum >= 10) {
      result[currentIndex] = sum % 10;
      isEnterOne = true;
    } else {
      result[currentIndex] = sum;
      isEnterOne = false;
    }
    currentIndex--;
  }
  // 处理第一位元素相加大于10的情况
  if (isEnterOne) result.unshift(1);
  return result;
}

剑指 Offer 30. 包含 min 函数的栈

链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

ts
class MinStack {
  private minValue: number = null;
  private recordArr: number[] = [];

  constructor() {}

  push(x: number): void {
    // 向 recordArrr 入栈 元素x
    // 并且获取最小值
    if (this.recordArr.length === 0) {
      this.minValue = x;
    } else {
      if (x < this.minValue) this.minValue = x;
    }
    this.recordArr.push(x);
  }

  pop(): void {
    // 删除最后一个元素，重新获取最小值
    const deleteNum = this.recordArr.pop();
    if (deleteNum === this.minValue) {
      const copySortRecordArr = [...this.recordArr].sort((a, b) => a - b);
      this.minValue = copySortRecordArr[0];
    }
  }

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

  min(): number {
    return this.minValue;
  }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

class MinStack {
  private minValue: number = null;
  private recordArr: number[] = [];

  constructor() {}

  push(x: number): void {
    // 向 recordArrr 入栈 元素x
    // 并且获取最小值
    if (this.recordArr.length === 0) {
      this.minValue = x;
    } else {
      if (x < this.minValue) this.minValue = x;
    }
    this.recordArr.push(x);
  }

  pop(): void {
    // 删除最后一个元素，重新获取最小值
    const deleteNum = this.recordArr.pop();
    if (deleteNum === this.minValue) {
      const copySortRecordArr = [...this.recordArr].sort((a, b) => a - b);
      this.minValue = copySortRecordArr[0];
    }
  }

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

  min(): number {
    return this.minValue;
  }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

118. 杨辉三角

链接：https://leetcode.cn/problems/pascals-triangle/

ts
function generate(numRows: number): number[][] {
  // [1] 1
  // [1,1] 2
  // [1, (2_0, 2_1) , 1] 3
  // [1, (3_0, 3_1), (3_1, 3_2) ,1] 4
  // [1, (4_0, 4_1), (4_1,4_2) , (4_2, 4_3) ,1]
  const resultArr: number[][] = [];

  for (let i = 1; i <= numRows; i++) {
    if (i === 1) {
      resultArr.push([1]);
    } else if (i === 2) {
      resultArr.push([1, 1]);
    } else {
      let rowArr: number[] = new Array(i).fill(-1);
      rowArr = rowArr.map((item, index) => {
        if (index === 0 || index === rowArr.length - 1) return 1;
        return resultArr[i - 2][index - 1] + resultArr[i - 2][index];
      });
      resultArr.push(rowArr);
    }
  }

  return resultArr;
}

function generate(numRows: number): number[][] {
  // [1] 1
  // [1,1] 2
  // [1, (2_0, 2_1) , 1] 3
  // [1, (3_0, 3_1), (3_1, 3_2) ,1] 4
  // [1, (4_0, 4_1), (4_1,4_2) , (4_2, 4_3) ,1]
  const resultArr: number[][] = [];

  for (let i = 1; i <= numRows; i++) {
    if (i === 1) {
      resultArr.push([1]);
    } else if (i === 2) {
      resultArr.push([1, 1]);
    } else {
      let rowArr: number[] = new Array(i).fill(-1);
      rowArr = rowArr.map((item, index) => {
        if (index === 0 || index === rowArr.length - 1) return 1;
        return resultArr[i - 2][index - 1] + resultArr[i - 2][index];
      });
      resultArr.push(rowArr);
    }
  }

  return resultArr;
}

剑指 Offer 63. 股票的最大利润

链接：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/

ts
function maxProfit(prices: number[]): number {
  let minPrice = Number.MAX_VALUE;
  let maxProfit = 0;
  for (const price of prices) {
    maxProfit = Math.max(price - minPrice, maxProfit);
    minPrice = Math.min(price, minPrice);
  }
  return maxProfit;
}

function maxProfit(prices: number[]): number {
  let minPrice = Number.MAX_VALUE;
  let maxProfit = 0;
  for (const price of prices) {
    maxProfit = Math.max(price - minPrice, maxProfit);
    minPrice = Math.min(price, minPrice);
  }
  return maxProfit;
}

20.有效的括号

链接：https://leetcode.cn/problems/valid-parentheses/

ts
function isValid(s: string): boolean {
  const stock: string[] = [];
  for (let i = 0; i < s.length; i++) {
    // 如果字符串符号是 ( [ { 则需要先入栈
    const currentChar = s[i];
    if (currentChar === "(" || currentChar === "[" || currentChar === "{") {
      stock.push(currentChar);
    } else {
      // 比对符号
      const lastChar = stock[stock.length - 1];
      if (
        (lastChar === "(" && currentChar === ")") ||
        (lastChar === "[" && currentChar === "]") ||
        (lastChar === "{" && currentChar === "}")
      ) {
        stock.pop();
      } else {
        return false;
      }
    }
  }
  return stock.length === 0;
}

function isValid(s: string): boolean {
  const stock: string[] = [];
  for (let i = 0; i < s.length; i++) {
    // 如果字符串符号是 ( [ { 则需要先入栈
    const currentChar = s[i];
    if (currentChar === "(" || currentChar === "[" || currentChar === "{") {
      stock.push(currentChar);
    } else {
      // 比对符号
      const lastChar = stock[stock.length - 1];
      if (
        (lastChar === "(" && currentChar === ")") ||
        (lastChar === "[" && currentChar === "]") ||
        (lastChar === "{" && currentChar === "}")
      ) {
        stock.pop();
      } else {
        return false;
      }
    }
  }
  return stock.length === 0;
}

144. 二叉树的前序遍历

思路：先返回当前节点的值，在向下遍历左子节点、遍历右子节点

链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/

ts
/**
 * 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 preorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      result.push(node.val);
      if (node.left) eachNode(node.left);
      if (node.right) eachNode(node.right);
    }
  }
  eachNode(root);
  return result;
}

/**
 * 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 preorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      result.push(node.val);
      if (node.left) eachNode(node.left);
      if (node.right) eachNode(node.right);
    }
  }
  eachNode(root);
  return result;
}

94. 二叉树的中序遍历

思路：二叉树的中序遍历是先遍历所有的左子节点然后是根节点最后是遍历所有的右子节点

链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/

ts
/**
 * 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 inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      if (node.left) eachNode(node.left);
      result.push(node.val);
      if (node.right) eachNode(node.right);
    }
  }
  eachNode(root);
  return result;
}

/**
 * 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 inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      if (node.left) eachNode(node.left);
      result.push(node.val);
      if (node.right) eachNode(node.right);
    }
  }
  eachNode(root);
  return result;
}

145. 二叉树的后续遍历

思路：二叉树的后序遍历是先遍历所有的左子节点和右子节点最后才是自己

链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/

ts
/**
 * 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 postorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      if (node.left) eachNode(node.left);
      if (node.right) eachNode(node.right);
      result.push(node.val);
    }
  }
  eachNode(root);
  return result;
}

/**
 * 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 postorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function eachNode(node: TreeNode) {
    if (node !== null) {
      if (node.left) eachNode(node.left);
      if (node.right) eachNode(node.right);
      result.push(node.val);
    }
  }
  eachNode(root);
  return result;
}

232. 用栈实现队列

链接：https://leetcode.cn/problems/implement-queue-using-stacks/

ts
class MyQueue {
  private recordArr: number[] = [];

  constructor() {}
  // [1,2]
  push(x: number): void {
    this.recordArr.push(x);
  }

  pop(): number {
    return this.recordArr.shift();
  }

  peek(): number {
    return this.recordArr[0];
  }

  empty(): boolean {
    return this.recordArr.length === 0;
  }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

class MyQueue {
  private recordArr: number[] = [];

  constructor() {}
  // [1,2]
  push(x: number): void {
    this.recordArr.push(x);
  }

  pop(): number {
    return this.recordArr.shift();
  }

  peek(): number {
    return this.recordArr[0];
  }

  empty(): boolean {
    return this.recordArr.length === 0;
  }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

71. 简化路径

思路：根据规范路径规则，通过 .split('/') 进行分割，遇到 ../ 代表返回上一级，就可以出栈一个文件夹，遇到 . 不入栈，其他的文件夹名称进行入栈。最后进行字符串拼接

链接：https://leetcode.cn/problems/simplify-path/

ts
function simplifyPath(path: string): string {
  const stack: string[] = [];
  let arr = path.split("/");
  // console.log('arr->',arr)
  arr.forEach((item) => {
    // 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级
    // 所以使用 ../ 前的目录文件夹均是无效
    if (item && item === "..") {
      stack.pop();
    } else if (item && item !== ".") {
      stack.push(item);
    }
  });
  // console.log('stack->',stack)

  return stack.length === 0 ? "/" : `/${stack.join("/")}`;
}

function simplifyPath(path: string): string {
  const stack: string[] = [];
  let arr = path.split("/");
  // console.log('arr->',arr)
  arr.forEach((item) => {
    // 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级
    // 所以使用 ../ 前的目录文件夹均是无效
    if (item && item === "..") {
      stack.pop();
    } else if (item && item !== ".") {
      stack.push(item);
    }
  });
  // console.log('stack->',stack)

  return stack.length === 0 ? "/" : `/${stack.join("/")}`;
}

933. 最近的请求次数

链接：https://leetcode.cn/problems/number-of-recent-calls/

耗时易懂解法

ts
class RecentCounter {
  constructor() {}
  private timeQueue: number[] = [];
  ping(t: number): number {
    this.timeQueue.push(t);
    let accordRangeValue = 0;
    const minTimeValue = t - 3000;
    const maxTimeValue = t;
    let currentIndex = 0;
    while (true) {
      const currentValue = this.timeQueue[currentIndex];
      if (currentValue >= minTimeValue && currentValue <= maxTimeValue)
        accordRangeValue++;
      currentIndex++;
      if (currentIndex >= this.timeQueue.length) break;
    }
    return accordRangeValue;
  }
}

class RecentCounter {
  constructor() {}
  private timeQueue: number[] = [];
  ping(t: number): number {
    this.timeQueue.push(t);
    let accordRangeValue = 0;
    const minTimeValue = t - 3000;
    const maxTimeValue = t;
    let currentIndex = 0;
    while (true) {
      const currentValue = this.timeQueue[currentIndex];
      if (currentValue >= minTimeValue && currentValue <= maxTimeValue)
        accordRangeValue++;
      currentIndex++;
      if (currentIndex >= this.timeQueue.length) break;
    }
    return accordRangeValue;
  }
}

使用队列解法

ts
class RecentCounter {
  constructor() {}
  private timeQueue: number[] = [];
  ping(t: number): number {
    // 入列
    this.timeQueue.push(t);
    while (this.timeQueue[0] < t - 3000) {
      // 出列
      this.timeQueue.shift();
    }
    // 之后的所有值都是处于 >= t-3000 范围内的
    // 因为有个条件就是 t的值每次都是严格递增的
    return this.timeQueue.length;
  }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

class RecentCounter {
  constructor() {}
  private timeQueue: number[] = [];
  ping(t: number): number {
    // 入列
    this.timeQueue.push(t);
    while (this.timeQueue[0] < t - 3000) {
      // 出列
      this.timeQueue.shift();
    }
    // 之后的所有值都是处于 >= t-3000 范围内的
    // 因为有个条件就是 t的值每次都是严格递增的
    return this.timeQueue.length;
  }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

141. 环形链表

思路：如果是环形链接那么循环就不会停止会无限执行下去，我们可以通过两个指针来不断调整位置，直到找到同一个就终止循环。如果不是环形的，最后一个链的 next 一定指向的是空的

链接：https://leetcode.cn/problems/linked-list-cycle/

ts
/**
 * 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 one = head;
  let two = head;
  // 指针为空就代表不是闭环的
  // 确保 two.next.next 是有的
  while (two && two.next) {
    one = one.next;
    two = two.next.next;
    // 代表是闭环的
    if (one === two) return true;
  }
  return false;
}

/**
 * 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 one = head;
  let two = head;
  // 指针为空就代表不是闭环的
  // 确保 two.next.next 是有的
  while (two && two.next) {
    one = one.next;
    two = two.next.next;
    // 代表是闭环的
    if (one === two) return true;
  }
  return false;
}

83. 删除排序链表中的重复元素

链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

ts
/**
 * 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 deleteDuplicates(head: ListNode | null): ListNode | null {
  let currentNode: ListNode = head;
  while (currentNode && currentNode.next) {
    if (currentNode.val === currentNode.next.val) {
      currentNode.next = currentNode.next.next;
    } else {
      currentNode = currentNode.next;
    }
  }
  return head;
}

/**
 * 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 deleteDuplicates(head: ListNode | null): ListNode | null {
  let currentNode: ListNode = head;
  while (currentNode && currentNode.next) {
    if (currentNode.val === currentNode.next.val) {
      currentNode.next = currentNode.next.next;
    } else {
      currentNode = currentNode.next;
    }
  }
  return head;
}

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

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

ts
/**
 * 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 node = head;
  let listLevel = 0;
  while (node) {
    node = node.next;
    listLevel++;
  }
  // 示例2 特殊处理
  if (listLevel === 1 && n === 1) {
    head = null;
    return head;
  }
  // 要删除的节点在哪个位置
  let deleteNodeNumber = listLevel - n + 1;
  let currentNode = head;
  let parentNode = null;
  let currentListLevel = 1;
  while (currentListLevel < deleteNodeNumber) {
    currentListLevel++;
    parentNode = currentNode;
    currentNode = currentNode.next;
  }
  // 如果当前节点的父节点为空，就代表是头节点
  if (parentNode === null) {
    head = currentNode.next;
  } else {
    // 如果删除的不是头结点
    // 就把父节点指向删除节点的子节点
    parentNode.next = currentNode.next;
    // 把当前节点的子节点覆盖当前节点
    currentNode = currentNode.next;
  }
  return head;
}

/**
 * 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 node = head;
  let listLevel = 0;
  while (node) {
    node = node.next;
    listLevel++;
  }
  // 示例2 特殊处理
  if (listLevel === 1 && n === 1) {
    head = null;
    return head;
  }
  // 要删除的节点在哪个位置
  let deleteNodeNumber = listLevel - n + 1;
  let currentNode = head;
  let parentNode = null;
  let currentListLevel = 1;
  while (currentListLevel < deleteNodeNumber) {
    currentListLevel++;
    parentNode = currentNode;
    currentNode = currentNode.next;
  }
  // 如果当前节点的父节点为空，就代表是头节点
  if (parentNode === null) {
    head = currentNode.next;
  } else {
    // 如果删除的不是头结点
    // 就把父节点指向删除节点的子节点
    parentNode.next = currentNode.next;
    // 把当前节点的子节点覆盖当前节点
    currentNode = currentNode.next;
  }
  return head;
}

682. 棒球比赛

链接：https://leetcode.cn/problems/baseball-game/

ts
function calPoints(ops: string[]): number {
  let opsSum = 0;
  const opsValidValueArr: number[] = [];

  ops.forEach((value, index) => {
    if (value === "C") {
      // 使前一次得分的记录无效并将其移除
      const delValue = opsValidValueArr.pop();
      opsSum -= delValue;
    } else if (value === "D") {
      // 表示本回合新获得的得分是前一次得分的两倍
      const curValue = opsValidValueArr[opsValidValueArr.length - 1] * 2;
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    } else if (value === "+") {
      // 表示本回合新获得的得分是前两次得分的总和
      const curValue =
        opsValidValueArr[opsValidValueArr.length - 1] +
        opsValidValueArr[opsValidValueArr.length - 2];
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    } else {
      const curValue = Number(value);
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    }
  });
  return opsSum;
}

function calPoints(ops: string[]): number {
  let opsSum = 0;
  const opsValidValueArr: number[] = [];

  ops.forEach((value, index) => {
    if (value === "C") {
      // 使前一次得分的记录无效并将其移除
      const delValue = opsValidValueArr.pop();
      opsSum -= delValue;
    } else if (value === "D") {
      // 表示本回合新获得的得分是前一次得分的两倍
      const curValue = opsValidValueArr[opsValidValueArr.length - 1] * 2;
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    } else if (value === "+") {
      // 表示本回合新获得的得分是前两次得分的总和
      const curValue =
        opsValidValueArr[opsValidValueArr.length - 1] +
        opsValidValueArr[opsValidValueArr.length - 2];
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    } else {
      const curValue = Number(value);
      opsSum += curValue;
      opsValidValueArr.push(curValue);
    }
  });
  return opsSum;
}

217. 存在重复数字

链接：https://leetcode.cn/problems/contains-duplicate/

ts
function containsDuplicate(nums: number[]): boolean {
  const resultMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (resultMap.has(nums[i])) {
      return true;
    }
    resultMap.set(nums[i], i);
  }
  return false;
}

function containsDuplicate(nums: number[]): boolean {
  const resultMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (resultMap.has(nums[i])) {
      return true;
    }
    resultMap.set(nums[i], i);
  }
  return false;
}

349. 两个数组的交集

思路：https://leetcode.cn/problems/intersection-of-two-arrays/

ts
function intersection(nums1: number[], nums2: number[]): number[] {
  const nums1Map = new Map();
  const result: Set<number> = new Set();
  for (let i = 0; i < nums1.length; i++) {
    nums1Map.set(nums1[i], i);
  }
  for (let i = 0; i < nums2.length; i++) {
    if (nums1Map.has(nums2[i])) {
      result.add(nums2[i]);
    }
  }
  return Array.from(result);
}

function intersection(nums1: number[], nums2: number[]): number[] {
  const nums1Map = new Map();
  const result: Set<number> = new Set();
  for (let i = 0; i < nums1.length; i++) {
    nums1Map.set(nums1[i], i);
  }
  for (let i = 0; i < nums2.length; i++) {
    if (nums1Map.has(nums2[i])) {
      result.add(nums2[i]);
    }
  }
  return Array.from(result);
}

1207. 独一无二的出现次数

链接：https://leetcode.cn/problems/unique-number-of-occurrences/

ts
function uniqueOccurrences(arr: number[]): boolean {
  let recordObj: Record<string, number> = {};
  for (let i = 0; i < arr.length; i++) {
    if (!recordObj[arr[i]]) {
      recordObj[arr[i]] = 1;
    } else {
      recordObj[arr[i]] += 1;
    }
  }
  const result = new Set();
  let recordObjLength = 0;
  for (let key in recordObj) {
    recordObjLength++;
    result.add(recordObj[key]);
  }
  // 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false
  if (result.size === recordObjLength) return true;
  return false;
}

function uniqueOccurrences(arr: number[]): boolean {
  let recordObj: Record<string, number> = {};
  for (let i = 0; i < arr.length; i++) {
    if (!recordObj[arr[i]]) {
      recordObj[arr[i]] = 1;
    } else {
      recordObj[arr[i]] += 1;
    }
  }
  const result = new Set();
  let recordObjLength = 0;
  for (let key in recordObj) {
    recordObjLength++;
    result.add(recordObj[key]);
  }
  // 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false
  if (result.size === recordObjLength) return true;
  return false;
}

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

链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

ts
var lengthOfLongestSubstring = function (s) {
  let strArr = [];
  let maxStrNum = 0;
  for (let i = 0; i < s.length; i++) {
    if (strArr.includes(s[i])) {
      const findIndex = strArr.indexOf(s[i]);
      strArr.splice(0, findIndex + 1);
    }
    strArr.push(s[i]);
    maxStrNum = Math.max(maxStrNum, strArr.length);
  }
  return maxStrNum;
};

var lengthOfLongestSubstring = function (s) {
  let strArr = [];
  let maxStrNum = 0;
  for (let i = 0; i < s.length; i++) {
    if (strArr.includes(s[i])) {
      const findIndex = strArr.indexOf(s[i]);
      strArr.splice(0, findIndex + 1);
    }
    strArr.push(s[i]);
    maxStrNum = Math.max(maxStrNum, strArr.length);
  }
  return maxStrNum;
};

111. 二叉树的最小深度

思路：利用栈的特性，只要发现了最小子节点，就立马返回，不在向下查找

链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

ts
/**
 * 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 minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  const stock: [TreeNode, number][] = [[root, 1]];
  while (stock.length !== 0) {
    const [node, level] = stock.shift();
    if (!node.left && !node.right) {
      return level;
    }
    node.left && stock.push([node.left, level + 1]);
    node.right && stock.push([node.right, level + 1]);
  }
}

/**
 * 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 minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  const stock: [TreeNode, number][] = [[root, 1]];
  while (stock.length !== 0) {
    const [node, level] = stock.shift();
    if (!node.left && !node.right) {
      return level;
    }
    node.left && stock.push([node.left, level + 1]);
    node.right && stock.push([node.right, level + 1]);
  }
}

104. 二叉树的最大深度

链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

ts
/**
 * 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 {
  let maxLevel = 0;
  const stock: [TreeNode, number][] = [[root, 1]];
  while (stock.length !== 0) {
    const [node, level] = stock.shift();
    if (node) {
      // 是最小子节点
      if (!node.left && !node.right) {
        maxLevel = level;
      }
      node.left && stock.push([node.left, level + 1]);
      node.right && stock.push([node.right, level + 1]);
    }
  }
  return maxLevel;
}

/**
 * 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 {
  let maxLevel = 0;
  const stock: [TreeNode, number][] = [[root, 1]];
  while (stock.length !== 0) {
    const [node, level] = stock.shift();
    if (node) {
      // 是最小子节点
      if (!node.left && !node.right) {
        maxLevel = level;
      }
      node.left && stock.push([node.left, level + 1]);
      node.right && stock.push([node.right, level + 1]);
    }
  }
  return maxLevel;
}

226. 翻转二叉树

链接：https://leetcode.cn/problems/invert-binary-tree/

ts
/**
 * 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 {
  if (!root) return root;

  const stock: TreeNode[] = [root];
  while (stock.length !== 0) {
    const node = stock.shift();
    if (node) {
      const swap = node.left || null;
      node.left = node.right || null;
      node.right = swap;
      stock.push(node.left);
      stock.push(node.right);
    }
  }
  return root;
}

/**
 * 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 {
  if (!root) return root;

  const stock: TreeNode[] = [root];
  while (stock.length !== 0) {
    const node = stock.shift();
    if (node) {
      const swap = node.left || null;
      node.left = node.right || null;
      node.right = swap;
      stock.push(node.left);
      stock.push(node.right);
    }
  }
  return root;
}

100. 相同的树

思路：循坏遍历，必须每一个节点和子节点都相同

链接：https://leetcode.cn/problems/same-tree/

ts
/**
 * 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 isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;

  if (!p || !q) return false;

  if (p.val !== q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

/**
 * 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 isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;

  if (!p || !q) return false;

  if (p.val !== q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

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

链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

双指针解法：

ts
function twoSum(numbers: number[], target: number): number[] {
  let left = 0,
    right = numbers.length - 1;
  while (true) {
    if (numbers[left] + numbers[right] === target) {
      return [++left, ++right];
    } else if (numbers[left] + numbers[right] > target) {
      right--;
    } else {
      left++;
    }
  }
}

function twoSum(numbers: number[], target: number): number[] {
  let left = 0,
    right = numbers.length - 1;
  while (true) {
    if (numbers[left] + numbers[right] === target) {
      return [++left, ++right];
    } else if (numbers[left] + numbers[right] > target) {
      right--;
    } else {
      left++;
    }
  }
}

136.只出现一次的数字

链接：https://leetcode.cn/problems/single-number/

利用 Set 数据结构的特性

ts
function singleNumber(nums: number[]): number {
  const recordSet: Set<number> = new Set();
  nums.forEach((num) => {
    if (recordSet.has(num)) {
      recordSet.delete(num);
    } else {
      recordSet.add(num);
    }
  });
  return Array.from(recordSet)[0];
}

function singleNumber(nums: number[]): number {
  const recordSet: Set<number> = new Set();
  nums.forEach((num) => {
    if (recordSet.has(num)) {
      recordSet.delete(num);
    } else {
      recordSet.add(num);
    }
  });
  return Array.from(recordSet)[0];
}

409. 最长回文串

链接：https://leetcode.cn/problems/longest-palindrome/

ts
function longestPalindrome(s: string): number {
  let map = new Map();
  let nCount: number = 0;
  for (let i = 0, len = s.length; i < len; i++) {
    if (map.has(s[i])) {
      nCount += 2;
      map.delete(s[i]);
    } else {
      map.set(s[i], 1);
    }
  }
  // console.log('nCount->',nCount)
  // console.log('map->',map)
  // 用map计算数量，同一元素达到2个就可以加入回文串。最后map里只会剩下数为1的元素，或者没有元素
  // 如果还有多余的数可以 +1，因为单一的元素可以放在中间
  // 如果没有数就可以返回了
  return map.size ? ++nCount : nCount;
}

function longestPalindrome(s: string): number {
  let map = new Map();
  let nCount: number = 0;
  for (let i = 0, len = s.length; i < len; i++) {
    if (map.has(s[i])) {
      nCount += 2;
      map.delete(s[i]);
    } else {
      map.set(s[i], 1);
    }
  }
  // console.log('nCount->',nCount)
  // console.log('map->',map)
  // 用map计算数量，同一元素达到2个就可以加入回文串。最后map里只会剩下数为1的元素，或者没有元素
  // 如果还有多余的数可以 +1，因为单一的元素可以放在中间
  // 如果没有数就可以返回了
  return map.size ? ++nCount : nCount;
}

844. 比较含退格的字符串

链接：https://leetcode.cn/problems/backspace-string-compare/

ts
function backspaceCompare(s: string, t: string): boolean {
  // 利用栈的先进后出的特点
  const sStock: string[] = [];
  const tStrock: string[] = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] !== "#") {
      sStock.push(s[i]);
    } else {
      sStock.pop();
    }
  }
  for (let i = 0; i < t.length; i++) {
    if (t[i] !== "#") {
      tStrock.push(t[i]);
    } else {
      tStrock.pop();
    }
  }
  return sStock.join("") === tStrock.join("") ? true : false;
}

function backspaceCompare(s: string, t: string): boolean {
  // 利用栈的先进后出的特点
  const sStock: string[] = [];
  const tStrock: string[] = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] !== "#") {
      sStock.push(s[i]);
    } else {
      sStock.pop();
    }
  }
  for (let i = 0; i < t.length; i++) {
    if (t[i] !== "#") {
      tStrock.push(t[i]);
    } else {
      tStrock.pop();
    }
  }
  return sStock.join("") === tStrock.join("") ? true : false;
}

Bigram 分词

链接：https://leetcode.cn/problems/occurrences-after-bigram/

ts
function findOcurrences(text: string, first: string, second: string): string[] {
  const wordStock: string[] = text.split(" ");
  const result: string[] = [];
  let eachStock = wordStock;
  while (true) {
    // 获取第一个单词在字符串中的下标
    const firstIndex = eachStock.indexOf(first);
    const secondIndex = firstIndex + 1;
    // 如果不存在元素 或者 第二个单词不存在（第一个单词在最后的情况） 终止循环
    if (firstIndex === -1 || !wordStock[secondIndex]) break;
    if (eachStock[firstIndex] === first && eachStock[secondIndex] === second) {
      // 如果存在这元素就把元素放进桶里
      if (eachStock[secondIndex + 1]) {
        result.push(eachStock[secondIndex + 1]);
      }
    }
    // 删除这一个元素，从第二个元素开始寻找下一个单词
    eachStock = eachStock.slice(secondIndex);
  }
  return result;
}

function findOcurrences(text: string, first: string, second: string): string[] {
  const wordStock: string[] = text.split(" ");
  const result: string[] = [];
  let eachStock = wordStock;
  while (true) {
    // 获取第一个单词在字符串中的下标
    const firstIndex = eachStock.indexOf(first);
    const secondIndex = firstIndex + 1;
    // 如果不存在元素 或者 第二个单词不存在（第一个单词在最后的情况） 终止循环
    if (firstIndex === -1 || !wordStock[secondIndex]) break;
    if (eachStock[firstIndex] === first && eachStock[secondIndex] === second) {
      // 如果存在这元素就把元素放进桶里
      if (eachStock[secondIndex + 1]) {
        result.push(eachStock[secondIndex + 1]);
      }
    }
    // 删除这一个元素，从第二个元素开始寻找下一个单词
    eachStock = eachStock.slice(secondIndex);
  }
  return result;
}

Released under the MIT License.

Copyright © 2022-present Attraction11