https://codetop.cc/home (opens new window)

听天事，尽人命

无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ (opens new window)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let left = 0;
  let right = 0;
  let length = s.length;
  const set = new Set();
  let res = 0;
  while (right < length) {
    if (!set.has(s[right])) {
      set.add(s[right]);
      right++;
    } else {
      res = Math.max(set.size, res);
      set.delete(s[left]);
      left++;
    }
  }
  return Math.max(set.size, res);
};

两数之和

https://leetcode-cn.com/problems/two-sum/ (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const length = nums.length;
  let diffs = {};
  for (let i = 0; i < length; i++) {
    if (diffs[target - nums[i]] !== undefined) {
      return [diffs[target - nums[i]], i];
    } else {
      diffs[nums[i]] = i;
    }
  }
};

链表中的倒数第 k 个节点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/ (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function (head, k) {
  let slow = head;
  let fast = head;
  while (k > 0) {
    fast = fast.next;
    k--;
  }
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
};

复原 ip 地址

https://leetcode-cn.com/problems/restore-ip-addresses/ (opens new window)

var restoreIpAddresses = function (s) {
  const segments = new Array(4);
  const ans = [];
  const dfs = (s, segId, segStart) => {
    // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
    if (segId === 4) {
      if (segStart === s.length) {
        ans.push(segments.join("."));
      }
      return;
    }
    // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
    if (segStart === s.length) {
      return;
    }
    // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
    if (s.charAt(segStart) === "0") {
      segments[segId] = 0;
      dfs(s, segId + 1, segStart + 1);
    }
    // 一般情况，枚举每一种可能性并递归
    let addr = 0;
    for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
      addr = addr * 10 + (s.charAt(segEnd) - "0");
      if (addr > 0 && addr <= 0xff) {
        segments[segId] = addr;
        dfs(s, segId + 1, segEnd + 1);
      } else {
        break;
      }
    }
  };
  dfs(s, 0, 0);
  return ans;
};

合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/ (opens new window)

let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (i >= 0 && j >= 0) {
  if (nums1[i] > nums2[j]) {
    nums1[k] = nums1[i];
    i--;
    k--;
  } else {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}
while (j >= 0) {
  nums1[k] = nums2[j];
  j--;
  k--;
}
return nums1;

矩形重叠

/**
 * @param {number[]} rec1
 * @param {number[]} rec2
 * @return {boolean}
 */
var isRectangleOverlap = function (rec1, rec2) {
  return !(
    rec1[2] <= rec2[0] ||
    rec1[3] <= rec2[1] ||
    rec1[0] >= rec2[2] ||
    rec1[1] >= rec2[3]
  );
};

有效括号

https://leetcode-cn.com/problems/valid-parentheses/ (opens new window)

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

比较版本号

https://leetcode-cn.com/problems/compare-version-numbers (opens new window)

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
var compareVersion = function (version1, version2) {
  const v1 = version1.split(".");
  const v2 = version2.split(".");
  for (let i = 0; i < v1.length || i < v2.length; i++) {
    let x = 0;
    let y = 0;
    if (i < v1.length) {
      x = parseInt(v1[i]);
    }
    if (i < v2.length) {
      y = parseInt(v2[i]);
    }
    if (x > y) {
      return 1;
    }
    if (x < y) {
      return -1;
    }
  }
  return 0;
};

全排列

https://leetcode-cn.com/problems/permutations/ (opens new window)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const res = [];
  const used = {};
  function dfs(path) {
    if (path.length === nums.length) {
      res.push(path.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      const num = nums[i];
      if (used[num]) continue;
      path.push(num);
      used[num] = true;
      dfs(path);
      path.pop();
      used[num] = false;
    }
  }
  dfs([]);
  return res;
};

路径总和

https://leetcode-cn.com/problems/path-sum/ (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (root === null) return false;
  if (root.left === null && root.right === null) {
    return root.val === targetSum;
  }
  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  );
};