今日有朋友问我一些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左右。
其实无论何种方式,何种优化,关键是从何种角度去思考问题,解决问题。