记录leetcode两道算法题“两数之和”&“整数反转”

2020-2-6 Jon js+jquery+ajax

题目难度：简单

1、两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路
首先想到的是方案1用两次循环，但是这样当传入的数组很大时，效率会很低。
其次方案2使用的是es6提供的Map对象
最后方案3是使用很巧妙地差值存到对象中，效率非常高
方案1
执行用时：120 ms
内存消耗：34.7 MB

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  for(var i = 0; nums.length>i; i++){
    for(var j = i+1; nums.length>j; j++){
      if(nums[i]+nums[j]===target){
        return [i, j]
      }
    }
  }
};
twoSum([2, 7, 11, 15], 22);

方案2
执行用时：64 ms
内存消耗：35.1 MB

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const diffs = new Map();
    const j = nums.findIndex((a, i) => diffs.has(target - a) || diffs.set(a, i) && 0);
    return [diffs.get(target - nums[j]), j];
};
twoSum([2, 7, 11, 15], 22);

方案3（推荐）
执行用时：64 ms
内存消耗：34.3 MB

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  var numObj = {};
  for(var i = 0; nums.length > i; i++){
   var n = target - nums[i];
   if(numObj[n]!==undefined){
      return [numObj[n], i]
   }
   numObj[nums[i]] = i;
 }
  return [];
};
twoSum([2, 7, 11, 15], 22);

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

示例 1:
输入: 123 输出: 321

示例 2:
输入: -123 输出: -321

示例 3:
输入: 120 输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解题思路
第一种思路用字符串和数组内置的方法实现调转问题，最后根据正负返回结果
第二种使用数学方法实现高效率的数字翻转，~~是强制转换为数字，负数向上取整，正数像下取正
方案1
执行用时：96 ms
内存消耗：36 MB

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
  if(x===0)return x;
  let isMinus = x>0?true:false;
  let value = (x+'').split('').reverse().join('');
  let result = isMinus?parseInt(value):-parseInt(value);
  let maxValue = Math.pow(2, 31);
  let minValue = -maxValue;
  if(minValue <= result && result <= maxValue-1){
    return result;
  }
  return 0;
};

方案2(推荐)
执行用时：88 ms
内存消耗：35.6 MB

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
  let maxValue = Math.pow(2, 31);
  let result = 0;
  while(x !== 0) {
    result = result*10 + x%10;
    x = ~~(x/10);
  }
  return (result <= maxValue-1 && result >= -1*maxValue)?result:0;
};

注意：
1、解决问题的方法远远不止这几种，若有更新奇、简洁或效率的方法欢迎留言讨论。
2、leetcode 的执行用时和内存消耗个人觉得不准，受影响因素较多，不作为唯一参考因素

题目来源：
力扣（LeetCode）
链接：https://leetcode-cn.com

标签: leetcode