js

算法题

基础练习

Posted by keyood on July 17, 2019

1. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。

解法：判断正负，将绝对值转字符串，再翻转字符串，判断是否超出范围，返回整数

var reverse = function(x) {
  let max = Math.pow(2, 31) - 1
  let isPositive = x > 0
  let str = Math.abs(x) + ''
  let reverseStr = +str.split('').reverse().join('')
  if ( isPositive ) {
    return reverseStr > max ? 0 : reverseStr
  } else {
    return reverseStr > max + 1 ? 0 : -reverseStr
  }
  return 0
};

2. 回文数

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

解法一：将整数转化成字符串，再将字符串翻转，对比前后字符串

var isPalindrome = function(x) {
    let str = x + ''
    let reverseStr = str.split('').reverse().join('')
    return str === reverseStr
};

解法二：将整数转化成字符串，截取后半段翻转与前半段相比

var isPalindrome = function(x) {
    let str = x + ''
    let len = str.length
    let cutLen = Math.ceil(len / 2) // 一半的长度
    let leftStr = ''
    if (len % 2 > 0) {
        leftStr = str.slice(0, cutLen - 1)
    } else {
        leftStr = str.slice(0, cutLen)
    }
    let rightStr = str.slice(cutLen).split('').reverse().join('')
    return leftStr === rightStr
};

解法三：将整数转化成字符串，遍历字符串，对比正序和倒序相对应的项

var isPalindrome = function(x) {
    let str = x + ''
    let len = str.length -1
    let cutLen = Math.ceil(len / 2) // 一半的长度
    for (let i = 0; i < cutLen; i ++) {
        if (str[i] !== str[len-i]) {
            return false
        }
    }
    return true
};

性能表现 解法三 > 解法一 ～= 解法二

3. 到达终点数字

在一根无限长的数轴上，你站在0的位置。终点在target的位置。 每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。返回到达终点需要的最小移动次数。

解法: 假设a为正向移动步数，b为负向移动步数，有a-b==/target/，sum==a+b； 则有sum-/target/ == 2b;

var reachNumber = function(target) {
    let sum = 0
    let i = 1
    let tmp = Math.abs(target)
    while (sum < tmp || (sum - tmp) % 2) {
        sum += i
        ++i
    }
    return i - 1;
};

4.数组去重

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解法一：双层循环

var removeDuplicates = function(nums) {
    for(let i = 0; i < nums.length;i++) {
        for(let j = i + 1; j < nums.length;) {
            if (nums[i] == nums[j]) {
                nums.splice(j, 1)
            } else {
                j++
            }
        }
    }
    return nums.length
}

解法二：单层循环

已知输入是排序后的数组，所以只要考虑前后是否相等

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

解法三：ES6 Set

var removeDuplicates = function(nums) {
    nums = [...new Set(nums)]
    return nums.length
}

5.寻找数组的中心索引

数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

解法：左右两边加中心索引的值为总和

left + num[i] + right = sum
left = right
2 * left + num[i] = sum

var pivotIndex = function(nums) {
    if (!nums.length) return -1
    let left = 0
    let sum = nums.reduce((a, b) => a + b)
    for (let i = 0; i < nums.length; i++) {
        if (left * 2 + nums[i]  === sum ) {
            return i
        }
        left += nums[i]
    }
    return -1
}

6.至少是其他数字两倍的最大数

在一个给定的数组nums中，总是存在一个最大元素 。 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。 如果是，则返回最大元素的索引，否则返回-1

var dominantIndex = function(nums) {
    if (nums.length === 1) return 0
    let maxIndex = 0
    for (let i = 1, len = nums.length; i < len; i++) {
      if (nums[i] > nums[maxIndex]) {
        maxIndex = i
      }
    }
    let max = nums.splice(maxIndex, 1)[0]
    let flag = false
    for (let i = 0, len = nums.length; i < len; i++) {
        if (max < nums[i] * 2) {
            flag = true
        }
    }
    return flag ? -1 : maxIndex
}

7.加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

输入: [1,2,3] 输出: [1,2,4]

var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] === 9) {
            digits[i] = 0
            if (i == 0) {
                digits.splice(0, 0, 1)
                return digits
            }
        } else {
            digits[i] = digits[i] + 1
            return digits
        }
    }
}

8.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组。

原生

var reverseString = function(s) {
    return s.reverse()
}

解法一：遍历

var reverseString = function(s) {
    let len = s.length
    for (let i = 0; i < Math.floor(len / 2); i++ ) {
        let temp = s[i]
        s[i] = s[len - i - 1]
        s[len - i - 1] = temp
    }
    return s
}

解法二：递归

var reverseString = function(s) {
    var reverse = function (s, i) {
        let len = s.length
        if (i >= Math.floor(len / 2)) return s
        let temp = s[i]
        s[i] = s[len - i - 1]
        s[len - i - 1] = temp
        return reverse(s, ++i)
    }
    return reverse(s, 0)
};

9.翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词,输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括

var reverseWords = function(s) {
    let arr = s.split(' ')
    let reverseArr = arr.reverse().filter(item => item)
    return reverseArr.join(' ')
}

10.求众数

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

你可以假设数组是非空的，并且给定的数组总是存在众数

解法：先计算到每个值出现的次数，再找出最大次数的那个值

var majorityElement = function(nums) {
    let map = {}
    for (let i = 0; i < nums.length; i++) {
        if (map[nums[i]]) {
            map[nums[i]] = (map[nums[i]]) + 1
        } else {
            map[nums[i]] = 1
        }
    }
    let maxCount = 0
    let maxValue
    for (prop in map) {
        if (map[prop] > maxCount) {
            maxCount = map[prop]
            maxValue = prop
        }
    }
    return maxValue
}

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

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

var lengthOfLongestSubstring = function(s) {
    let tempArr = []
    let maxArr = []
    for (let i = 0; i < s.length; i++) {
        let index = tempArr.indexOf(s[i])
        if (index > -1) {
            if (tempArr.length > maxArr.length) {
                maxArr = tempArr
            }
            tempArr = tempArr.slice(index + 1)
        }
        tempArr.push(s[i])
    }
    return Math.max(maxArr.length, tempArr.length)
}

12.盛最多水的容器

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

解法一：暴力法，遍历每一个值

var maxArea = function(height) {
    let max = 0
    let len = height.length
    for (let i = 0; i < len -1 ; i++) {
      for (let j = i+1; j < len; j++) {
        let area = Math.min(height[i], height[j]) * (j - i)
        max = Math.max(max, area)
      }
    }
    return max
}

解法二：双指针

var maxArea = function(height) {
    let length = height.length
    let left = 0
    let right = length - 1
    let max = 0

    while (left < right) {
      let area = Math.min(height[left], height[right]) * (right - left)
      max = Math.max(max, area)

      height[left] > height[right] ? right-- : left++
    }

    return max
}

13.救生艇

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

解法：双指针，先给数组排序，每次都让最重的上船

var numRescueBoats = function(people, limit) {
    let left = 0
    let right = people.length - 1
    let total = 0
    people.sort((a, b) => a - b)
    while (left <= right) {
      if (people[left] + people[right] <= limit) {
        left++
      }
      total++
      right--
    }
    return total
};

14.移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

var removeElement = function(nums, val) {
    for (let i = 0; i < nums.length;) {
       nums[i] === val ? nums.splice(i, 1) : i++
    }
    return nums.length
};

15.相同的树

给定两个二叉树，编写一个函数来检验它们是否相同,如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同。

思路：先判断节点的值，再判断节点的左右节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if ( p == null && q == null){
        return true;
    }

    if (p !== null && q !== null && p.val === q.val){
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    } else {
        return false;
    }
};

16.Pow(x, n)

实现幂函数，n 范围[-2^31, 2^31-1]

解法一：先判断n的正负, 再使用递归

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    var pow = function(p, n) {
        if (n === 1) return p
        return pow(p * x, --n)
    }
    if (n === 0) {
        return 0
    } else if ( n > 0) {
        return pow(x, n)
    } else {
        return 1 / pow(x, Math.abs(n))
    }
}
FEATURED TAGS
nuxt compiler react vscode js 浏览器
FRIENDS
阅读量 0