大厂面试经典算法题

前言

1. 近段时间在找工作，收集大厂中常见的面试算法题。
2. 大部分的题目解法都是自己思考研究测试过的，如有问题，我们可以探讨一下。

两个大数相加

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function addStrings(num1, num2) {
    // 获取两个数的最大长度
    let maxLen = Math.max(a.length, num2.length)
    // 位数不够的前面补0
    num1 = num1.padStart(maxLen, '0')
    num2 = num2.padStart(maxLen, '0')
    let t = 0 // 两位相加的和+进位
    let f = 0 // 进位
    let sum = ''
    // 从后面开始相加
    for (let i = maxLen - 1; i >= 0; i--) {
        // 每两位数相加的和
        t = parseInt(num1[i]) + parseInt(num2[i]) + f
        // 如果大于等于10，则往前进一位
        f = Math.floor(t / 10)
        // 一次累加
        sum = t % 10 + sum
    }
    // 如果首位相加大于等于10，还要往前进一位
    if (f == 1) {
        sum = '1' + sum
    }
    return sum
}

上面的是网上的答案，但我自己用了 BigInt 试一下也是可以的，目前还不知道有什么弊端

function addStringsForBigInt(a, b) {
    return (BigInt(a) + BigInt(b)).toString()
}

测试：

let a = "90071992547655740991";
let b = "1234567899999999999";
console.log(addStrings(a, b))
console.log(addStringsForBigInt(a, b))
console.log(addStrings(a, b) === addStringsForBigInt(a, b))  // true

两个数组交集

// 直接过滤去重，这个比较简单，解法很多
var intersection = function(nums1, nums2) {
    return [...new Set(nums1.filter(element=>nums2.includes(element)))]
};

翻转字符串里的单词

var reverseWords = function (s) {
    let result = ''
    // 先用空格分割成数组，再去掉多余的空格，然后再颠倒顺序
    let sliptArr = s.split(' ').filter(Boolean).reverse()
    sliptArr.forEach((element, index) => {
        result += element + (index === sliptArr.length - 1 ? '' : ' ')
    })
    return result
};

测试：

const num = "a good   example"
console.log(reverseWords(num))

两数之和

 /**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    // 定义一个map对象
    let map = new Map()
    // 循环遍历
    for (let i = 0; i < nums.length; i++) {
        let num1 = nums[i]
        let num2 = target - num1
        // 判断map是否含有的差值
        if (map.has(num2)) {
            return [map.get(num2), i]
        } else {
            map.set(num1, i)
        }
    }
};

测试：

let nums = [2, 7, 11, 15], target = 26
console.log(twoSum(nums, target)) //[2,3]

买股票的最佳时机

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let total = 0
    for (let i = 0; i < prices.length - 1; i++) {
        // 计算相邻两个数是否是正数
        total += Math.max(prices[i + 1] - prices[i], 0)
    }
    return total
};

测试：

const prices = [7, 1, 5, 3, 6, 4]
console.log(maxProfit(prices))

只出现一次的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let result = null;
    for (let i = 0; i < nums.length; i++) {
        // 使用异或运算符
        // a^a = 0,a^0=a,a^b^a=b
        result ^= nums[i]
    }
    return result
};

测试：

const nums = [4, 1, 2, 1, 2]
console.log(singleNumber(nums))

加一

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    return (BigInt(digits.join('')) + 1n).toString().split('')
};

测试：

const nums = [9, 1, 9, 2, 9]
console.log(plusOne(nums))

移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    return (nums.filter(Boolean).join('').padEnd(nums.length, '0')).split('')
};

测试：

const nums = [9, 0, 1, 0, 9, 0, 2, 9]
console.log(moveZeroes(nums))

旋转图像

/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/  
var rotate = function (matrix) {
    // 先生成一个长度一样的二维数组
    let len = matrix[0].length, result = Array.from({ length: len }, () => [])
    for (let i = matrix.length - 1; i >= 0; i--) {
        for (let j = len - 1; j >= 0; j--) {
            // 从尾部遍历插入
            result[i].push(matrix[j][i])
        }
    }
    return result
};

测试：

const nums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
console.log(rotate(nums))

翻转字符串

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    // 使用双指针
    let left = 0, right = s.length - 1
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
}

测试：

const nums = ["H", "a", "n", "n", "a", "h"]
reverseString(nums)
console.log(nums)

整数反转

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
    // 先判断是否大于等于0，前面加-号，先转成字符串，再用parseInt去掉前面的0
    let result = Number((x >= 0 ? '' : '-') + parseInt(x.toString().split('').reverse().join('')))
    // 边界值判断
    return (result >= -Math.pow(2, 31) && result <= Math.pow(2, 31) - 1) ? result : 0
};

测试：

const nums = 1020
reverse(nums)
console.log(reverse(nums)) // 201

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

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    for(let i = 0;i < s.length;i++){
        // 判断字符的第一个索引和最后一个索引是否一样
        if(s.indexOf(s[i]) === s.lastIndexOf(s[i])){
            return i
        }
    }
    return -1
};

测试：

const s = 'leetcode'
console.log(firstUniqChar(s)) // 0

验证回文串

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    // 现用正则过滤出字母和字符，再转成小写
    s = s.replace(/[^A-Za-z0-9]/ig, '').toLowerCase()
    // 定义首位指针
    let left = 0, right = s.length - 1
    while (left <= right) {
        // 如果首位不一致，则不是回文串
        if (s[left] !== s[right]) {
            return false
        } else {
            // 如果一致，则指针移动
            left++
            right--
        }
    }
    return true
};

测试：

const s = "race a car"
console.log(isPalindrome(s)) // false