记录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

分享这篇文章
赞助鼓励:如果觉得内容对您有所帮助,您可以支付宝(左)或微信(右):

声明:如无特殊注明,所有博客文章版权皆属于作者,转载使用时请注明出处。谢谢!

发表评论:

皖ICP备15010162号-1 ©2015-2020 知向前端
qq:1614245331 邮箱:13515678147@163.com Powered by emlog sitemap