1. 两数之和 (leetcode)

今日有朋友问我一些python入门的免费教程。不知怎的就想到了刷题,就想看看是怎么个流程, 然后就搜索了下,网上推荐的网站:https://leetcode-cn.com/

为了看这个检查的流程,就找了个最简单的,语言使用最近经常使用的javascript.刚开始的时候, 无论如何执行,执行结果都没有。后来发现是浏览器的广告拦截插件的原因。于是关闭后刷新总算 执行正常了。

因为两数之合很简单,就随便写了个常规的流程,提交后发现可以看到执行效率的排名,内存占用的排名。 比如下面的常规的流程:

  //方法1:
//执行用时: 100 ms
//内存消耗: 41.3 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
    for(let i =0; i < nums.length; i++) {
            for(let j=i+1; j < nums.length; j++) {
                if(nums[i]+nums[j] === target) {
                    return [i,j];
                }
            }
        }
    return [-1,-1];
    };

我的提交显示 执行效率超过46%(100ms),内存超过44%(41.3 MB)

这激发了我的兴趣,就想着如何优化或者负优化吧。于是就有了下面更多的提交:

//方法2:
//执行用时: 520 ms
//内存消耗: 42.6 MB
  /**
   * @param {number[]} nums
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function(nums, target) {
  for(let i =0; i < nums.length; i++) {
      let test = target - nums[i];
      let index = nums.findIndex((e, j)=> j != i && e == test );
      if(index >= 0) {
          return [i, index];
      }
  }
  return [-1,-1];
  };

上面这个方法似乎效率超越了2%, 我不知道哪个比这个还要慢了。

  //方法3:
//执行用时: 72 ms
//内存消耗: 41.7 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
        let obj = {};
    for(let i =0; i < nums.length; i++) {
        if(obj[nums[i]] != undefined) {
            return [obj[nums[i]], i];
        } else {
            obj[target-nums[i]] = i;
        }
    }
    return [-1,-1];
    };

上面的方法使用了json的格式,利用判断key是否存在,但json格式的key只能是字符串,利用题目中的 索引都是数字的特性,简单优化了下类型:

    //方法4:
  //执行用时: 64 ms
//内存消耗: 41.6 MB
  /**
   * @param {number[]} nums
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function(nums, target) {
  let obj = [];
  for(let i =0; i < nums.length; i++) {
      if(obj[nums[i]] != undefined) {
          return [obj[nums[i]], i];
      } else {
          obj[target-nums[i]] = i;
      }
  }
  return [-1,-1];
  };

数组的方式比object的方式快一些

  //方法5:
//执行用时: 60 ms
//内存消耗: 41.5 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
    let obj = [];
    for(let i =0, j=nums.length-1; i <= j; i++, j--) {
        if(obj[nums[i]] != undefined) {
            return [i, obj[nums[i]]];
        } else {
            obj[target-nums[i]] = i;
            if(obj[nums[j]] != undefined) return [obj[nums[j]],j];
            else
            obj[target-nums[j]] = j;
        }
    }
    return [-1,-1];
    };

上面的方式还是使用数组的方式,只是将循环减半了。因此复杂度也少了些了。

    //方法6
 //执行用时: 60 ms
//内存消耗: 41.4 MB 
  /**
   * @param {number[]} nums
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function(nums, target) {
  let obj = new Map();
  for(let i =0, j=nums.length-1; i <= j; i++, j--) {
      if(obj.has(nums[i])) {
          return [i, obj.get(nums[i])];
      } else {
          obj.set(target-nums[i], i);
          if(obj.has(nums[j])) return [obj.get(nums[j]),j];
          else
          obj.set(target-nums[j], j);
      }
  }
  };

使用map,不影响效率的同时,降低了内存消耗

  //方法7
//执行用时: 64 ms
//内存消耗: 41.4 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
    let obj = new Map();
    let i = 0;
    let j = nums.length-1; 
    while(i<=j) {
        let left = nums.shift();
        let right = nums.pop();
        if(obj.has(left)) {
            return [i, obj.get(left)];
        }
        obj.set(target-left, i);
        if(obj.has(right)) {
            return [obj.get(right), j];
        }
        obj.set(target-right, j);
        ++i;
        --j;
    }
    };

方法7与方法6基本一样,只是将for循环使用while循环来代替了,并且,旨在为了降低内存使用的shift, pop 操作,从测试结果而言,并没有效果。这应该和javascript的内存分配机制有关系,毕竟变量nums还在不断的使用中。

  //方法8
//执行用时: 64 ms
//内存消耗: 41.6 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
    let obj = [];
    let i = 0;
    let j = nums.length-1; 
    while(i<=j) {
        let left = nums.shift();
        let right = nums.pop();
        if(obj[left] != undefined) {
            return [i, obj[left]];
        }
        obj[target-left] = i;
        if(obj[right] != undefined) {
            return [obj[right], j];
        }
        obj[target-right] = j;
        ++i;
        --j;
    }
    };

方法8与方法7一样,只是将map修改成了数组。执行效率一样,但内存占用多了些。

    //方法9:
//执行用时: 72 ms
//内存消耗: 41.5 MB
  /**
   * @param {number[]} nums
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function(nums, target) {
  let obj = new Map();
  let i = 0;
  let j = nums.length-1; 
  while(i<=j) {
      let left = nums[i];
      let right = nums[j];
      if(obj.has(left)) {
          return [i, obj.get(left)];
      }
      obj.set(target-left, i);
      if(obj.has(right)) {
          return [obj.get(right), j];
      }
      obj.set(target-right, j);
      ++i;
      --j;
  }
  };

方法9与方法7一样,只是将数据的提取使用数组的方式,而非shift,pop的方式, 即使这一简单改变,也导致 测试执行效率降低了些。

  //方法10
//执行用时: 52 ms
//内存消耗: 41.7 MB
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
    let obj = {};
    let i = 0;
    let j = nums.length-1; 
    while(i<=j) {
        let left = nums.shift();
        let right = nums.pop();
        if(obj[left] != undefined) {
            return [i, obj[left]];
        }
        obj[target-left]= i;
        if(obj[right] != undefined) {
            return [obj[right], j];
        }
        obj[target-right]= j;
        ++i;
        --j;
    }
    };

方式10和方法9一样,只是使用了object和数组的shift,pop的方法,

除了负优化的方法2之外,总体而言,减少循环可以优化效率。使用object和map的方式会比较节约些内存。 受到数据样本情况,上面的测试结果也不是非常准确的,比如,如果数据样本大都集中在前面几个就有 答案的话,方法1可能比较快的,反之,方法1则是比较慢的;如果数据样本的答案集中在两侧的话,循环减半 的方式则相对比较快,(对于前一种情况,循环减半效果也比较好)。即使是同一个算法,每次提交 执行用时也不相同,不如方法10,我这边在测试的时候,最快在52ms, 而排在前面的小于40ms的,我将 算法提交上去后,却在64ms,方法7有时候也会执行用时也会在56ms左右。

其实无论何种方式,何种优化,关键是从何种角度去思考问题,解决问题。

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据