前端面试宝典

LeetCode - 简单

7. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

  • 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
/**
 * @param {number} x
 * @return {number}
 */
const reverse = x => {
  if (x > Math.pow(2, 31) - 1 || x < -Math.pow(2, 31)) {
    return;
  }
  let ifNegative = false; // 负数判断
  let xStringed = String(x); // 转化为字符串
  let noCharNum = ''; // 用于存放无符号数字
  if (xStringed.includes('-')) {
    ifNegative = true;
    noCharNum = xStringed.slice(1);
  } else {
    noCharNum = xStringed;
  }
  // 反转
  let resNum = Number(
    noCharNum
      .split('')
      .reverse()
      .join('')
  );
  if (ifNegative) {
    resNum = -resNum;
  }
  if (resNum > Math.pow(2, 31) - 1 || resNum < -Math.pow(2, 31)) {
    return 0;
  }
  return resNum;
};

9. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

/**
 * @param {number} x
 * @return {boolean}
 */
const isPalindrome = function(x) {
  let s = 0;
  for (let i = 0; i < x.toString().length / 2; i++) {
    if (x.toString()[i] == x.toString()[x.toString().length - 1 - i]) {
      s++;
    }
  }
  return s == Math.ceil(x.toString().length / 2);
};

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

  • 所有输入只包含小写字母 a-z 。
/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = strs => {
  if (strs.length <= 0) {
    return '';
  }
  for (let i = 0; i < strs[0].length; i++) {
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== strs[0][i]) {
        return strs[0].substr(0, i);
      }
    }
  }

  return strs[0];
};

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

  • 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
/**
 * @param {number[]} nums
 * @return {number}
 */
const removeDuplicates = nums => {
  let theNum;

  for (let i = 0; i < nums.length; ) {
    if (nums[i] === theNum) {
      nums.splice(i, 1);
    } else {
      theNum = nums[i];
      i++;
    }
  }

  return nums.length;
};

28. 实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
const strStr = (haystack, needle) => {
  let haystackLen = haystack.length;
  let needleLen = needle.length;
  if (!needleLen) {
    return 0;
  }
  if (needleLen > haystackLen) {
    return -1;
  }
  for (let i = 0; i <= haystackLen - needleLen; i++) {
    let pivot = i;

    for (let j = 0; j < needleLen; j++) {
      if (haystack[pivot] == needle[j]) {
        pivot++;
      } else {
        break;
      }
    }
    if (pivot - i == needleLen) {
      return i;
    }
  }
  return -1;
};

118. 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

  • 在杨辉三角中，每个数是它左上方和右上方的数的和。
/**
 * @param {number} numRows
 * @return {number[][]}
 */
// 给定行数，生成帕斯卡三角形（杨辉三角）
// 思路：循环或递归
const generate = numRows => {
  let res = [];

  const create = arr => {
    let len = arr.length;

    if (len === 1) {
      return [1, 1];
    }
    // 第一位是1
    let res = [1];
    for (let i = 1; i < len; ++i) {
      res.push(arr[i - 1] + arr[i]);
    }
    // 最后一位也是1
    res.push(1);
    return res;
  };

  if (numRows > 0) {
    res.push([1]);
    for (let i = 1; i < numRows; ++i) {
      let arr = create(res[i - 1]);
      res.push(arr);
    }
  }

  return res;
};

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

  • 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
  • 注意你不能在买入股票前卖出股票。
/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = prices => {
  if (!prices) {
    return 0;
  }
  let profit = 0;
  let low = prices[0];
  const len = prices.length;
  for (let i = 1; i < len; i++) {
    if (prices[i] < low) {
      low = prices[i];
    } else if (prices[i] - low > profit) {
      profit = prices[i] - low;
    }
  }

  return profit;
};

141. 环形链表

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

  • 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = head => {
  if (!head) return false;
  if (head.prev) return head.prev;
  else {
    head.prev = true;
    return hasCycle(head.next);
  }
};

169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

  • 你可以假设数组是非空的，并且给定的数组总是存在众数。
/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function(nums) {
  let counterMap = Object.create(null);
  const len = nums.length;
  let majorityEle;
  let i = 0;
  while (i < len) {
    var num = nums[i];
    if (!counterMap[num]) {
      counterMap[num] = 1;
    } else {
      counterMap[num] += 1;
    }
    if (counterMap[num] > len >>> 1) {
      majorityEle = num;
      break;
    }
    i++;
  }
  return majorityEle;
};

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

  • 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
  • 要求使用空间复杂度为 O(1) 的原地算法。
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const rotate = (nums, k) => {
  if (!k) return nums;
  while (k--) nums.unshift(nums.pop());
};

← LeetCode - 中等 →