前端面试宝典

LeetCode - 中等

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

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = s => {
  let map = Object.create(null);
  const len = s.length;
  let max = 0;
  let lastRepeater = -1;
  for (let i = 0; i < len; i++) {
    const word = s[i];
    if (word in map && lastRepeater < map[word]) {
      lastRepeater = map[word];
    }
    if (i - lastRepeater > max) {
      max = i - lastRepeater;
    }
    map[word] = i;
  }
  return max;
};

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = s => {
  let longestPalindrome = s[0] || '';

  for (let i = 0; i < s.length; i++) {
    let dist = 1;

    // Check odd-length palindromes
    while (s[i + dist] !== undefined && s[i + dist] === s[i - dist]) {
      dist++;
    }
    if (dist > 1) {
      dist--;
      if (i + dist - (i - dist) + 1 > longestPalindrome.length) {
        longestPalindrome = s.substring(i - dist, i + dist + 1);
      }
    }

    dist = 0;
    // Check even-length palindromes
    while (s[i - dist] !== undefined && s[i - dist] === s[i + 1 + dist]) {
      dist++;
    }
    if (dist > 0) {
      dist--;

      if (i + 1 + dist - (i - dist) + 1 > longestPalindrome.length) {
        longestPalindrome = s.substring(i - dist, i + dist + 2);
      }
    }
  }

  return longestPalindrome;
};

8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

  • 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing 返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
/**
 * @param {string} str
 * @return {number}
 */
const myAtoi = str => {
  const MIN = -2147483648;
  const MAX = 2147483647;
  let flag = 1;
  let first = 1;
  let sum = 0;
  str = str.trim();
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '+' && first) {
      first = 0;
    } else if (str[i] === '-' && first) {
      flag = -1;
      first = 0;
    } else if (str[i] <= '9' && str[i] >= '0') {
      first = 0;
      sum = sum * 10 + Number(str[i]);
    } else {
      break;
    }
  }
  sum *= flag;
  if (sum > MAX) sum = MAX;
  if (sum < MIN) sum = MIN;
  return sum;
};

11. 盛最多水的容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

  • 你不能倾斜容器，且 n 的值至少为 2。
/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = height => {
  const len = height.length;
  let ans = 0;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
    }
  }
  return ans;
};

15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

  • 答案中不可以包含重复的三元组。
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = nums => {
  const { length } = nums;
  nums.sort((a, b) => a - b);

  const result = [];
  for (let i = 0; i < length; i += 1) {
    const first = nums[i];
    if (first > 0) break;
    if (i > 0 && first === nums[i - 1]) continue;
    const target = 0 - nums[i];
    let l = i + 1;
    let r = length - 1;
    while (l < r) {
      const second = nums[l];
      const third = nums[r];
      if (second + third === target) {
        result.push([first, second, third]);
        while (l < r && second === nums[l + 1]) l += 1;
        while (l < r && third === nums[r - 1]) r -= 1;
        l += 1;
        r -= 1;
      } else if (second + third < target) {
        l += 1;
      } else {
        r -= 1;
      }
    }
  }

  return result;
};

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
const multiply = (num1, num2) => {
  const add = (a, b) => {
    let flag = 0;
    let la = a.length - 1;
    let lb = b.length - 1;
    let ans = '';
    let t = 0;
    while (la >= 0 && lb >= 0) {
      t = Number(a[la]) + Number(b[lb]) + flag;
      flag = Math.floor(t / 10);
      t %= 10;
      ans = t + ans;
      la--;
      lb--;
    }
    while (la >= 0) {
      t = Number(a[la]) + flag;
      flag = Math.floor(t / 10);
      t %= 10;
      ans = t + ans;
      la--;
    }
    while (lb >= 0) {
      t = Number(b[lb]) + flag;
      flag = Math.floor(t / 10);
      t %= 10;
      ans = t + ans;
      lb--;
    }
    if (flag > 0) ans = flag + ans;
    return ans;
  };
  const mult = (a, b, n) => {
    let ans = '';
    let flag = 0;
    let t = 0;
    let nb = Number(b);
    for (let i = a.length - 1; i >= 0; i--) {
      t = Number(a[i]) * nb + flag;
      flag = Math.floor(t / 10);
      t %= 10;
      ans = t + ans;
    }
    if (flag > 0) ans = flag + ans;
    while (n--) {
      ans += '0';
    }
    return ans;
  };
  let pre = '0';
  let ans = '';
  let len = num1.length;
  for (let i = len - 1; i >= 0; i--) {
    ans = add(mult(num2, num1[i], len - i - 1), pre);
    pre = ans;
  }
  for (i = 0; i < ans.length; i++) {
    if (ans[i] !== '0') break;
  }
  ans = ans.slice(i);
  return ans.length <= 0 ? '0' : ans;
};

46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

/**
 * 全排列
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = nums => {
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    let arr = permute(nums.slice(0, i).concat(nums.slice(i + 1, nums.length)));
    arr.forEach(a => {
      result.push([nums[i], ...a]);
    });
    if (arr.length === 0) {
      result.push([nums[i]]);
    }
  }
  return result;
};

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permuteUnique = nums => {
  const len = nums.length;
  let ans = [];
  const solve = k => {
    if (k === len) {
      ans.push(nums.join(''));
      return;
    }
    let t;
    for (let i = k; i < len; i++) {
      t = nums[i];
      nums[i] = nums[k];
      nums[k] = t;
      solve(k + 1);
      t = nums[i];
      nums[i] = nums[k];
      nums[k] = t;
    }
  };
  solve(0);
  let final = [];
  for (let i = 0; i < ans.length; i++) {
    if (final.indexOf(ans[i]) === -1) final.push(ans[i]);
  }
  final = final.map(item => {
    let it = [];
    let flag = 1;
    for (let j = 0; j < item.length; j++) {
      if (item[j] === '-') {
        flag = -1;
      } else {
        it.push(Number(item[j]) * flag);
        flag = 1;
      }
    }
    return it;
  });
  return final;
};

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

  • 每次只能向下或者向右移动一步。
/**
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = grid => {
  let xLen = grid[0].length;
  let yLen = grid.length;
  let minSums = grid;
  for (let i = 1; i < xLen; i++) {
    minSums[0][i] = minSums[0][i - 1] + grid[0][i];
  }
  for (let j = 1; j < yLen; j++) {
    minSums[j][0] = minSums[j - 1][0] + grid[j][0];
  }
  for (let i = 1; i < grid[0].length; i++) {
    for (let j = 1; j < yLen; j++) {
      const item = grid[j][i];
      minSums[j][i] = Math.min(
        minSums[j][i - 1] + item,
        minSums[j - 1][i] + item
      );
    }
  }

  return minSums[yLen - 1][xLen - 1];
};

165. 比较版本号

比较两个版本号 version1 和 version2。

  • 如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。
/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
const compareVersion = (version1, version2) => {
  if (!version1) {
    return -1;
  }
  if (!version2) {
    return 1;
  }
  const verArr1 = version1.split('.');
  const verArr2 = version2.split('.');

  const len = Math.max(verArr1.length, verArr2.length);
  for (let i = 0; i < len; i++) {
    let ver1 = verArr1[i] || 0;
    let ver2 = verArr2[i] || 0;
    ver1 -= 0;
    ver2 -= 0;
    if (ver1 > ver2) {
      return 1;
    } else if (ver1 < ver2) {
      return -1;
    }
  }

  return 0;
};

← LeetCode - 困难 →