这是第一篇关于leetcode的题解,就先扯点关于leetcode的话。
其实很早前就在博客园看到过leetcode一些题解,总以为跟一般OJ大同小异,直到最近点开了一篇博文Leetcode 编程训练,无意间点进leetcode的主页看了下,乖乖,居然能用JavaScript提交代码(还能用python、ruby等)!瞬间来了兴趣,一口气把几十道水题都切完了,代码放在了github,有兴趣的可以参考或者帮忙review一下。对于个人认为有意思的题目,楼主也会时不时地写些题解和大家分享下。
今天要说的是Rotate Array这题,并不是说这题有多么地难(leetcode把它难度定位为EASY),而是让我理解了JavaScript中以前听说过但是一直没引起重视的一个很重要的性质。
先回到这道题本身,题目很简单,给一个数组,向右移动k位,求新的数组,关键来了,题目要求你Do not return anything, modify nums in-place instead.。右移k位,相当于把数组最右边的k位放到数组开头,还要考虑k大于数组长度的情况,似乎也很容易想到,写下如下代码:
var rotate = function(nums, k) { k %= nums.length; var tmp = []; if (k) tmp = nums.slice(-k); nums.splice(-k, k); nums = tmp.concat(nums);};
tmp保存了右边要移动要前面的数组(slice),而nums自己则截掉后面要移动的数组(splice),然后把两段数组一拼,不是说直接修改nums数组么,那把结果直接赋给nums就ok了!但是无情地返回了wrong answer,leetcode不提供sample,但是出错了会给一组出错了的数据,数据如下:
Input: [1,2], 1Output: [1]Expected: [2,1]
尝试着把数组带入,打印结果:
var rotate = function(nums, k) { k %= nums.length; var tmp = []; if (k) tmp = nums.slice(-k); nums.splice(-k, k); nums = tmp.concat(nums); console.log(nums); // [2, 1]};rotate([1, 2], 1);
靠,输出的真的是你expected的东西啊!正当我百思不得其解的时候,我突然意识到我犯了一个很严重的错误。leetcode服务器匹配你的结果正确与否,不可能进入你写的函数里去判断!而实际上,它应该是这样判断的:
var rotate = function(nums, k) { k %= nums.length; var tmp = []; if (k) tmp = nums.slice(-k); nums.splice(-k, k); nums = tmp.concat(nums);};var a = [1, 2];rotate(a, 1);console.log(a); // [1]
确实与expected的不符!为什么数组a会变成1?怎样才能变成expected的答案?我们接下去看。
关于变量值的复制我们都已经很清楚了,基本类型(undefined、null、boolean、number、string)和引用类型(object)是不一样的。如果从一个变量向另一个变量复制基本类型的值,会在变量对象上创建一个新值,然后把该值赋值到为新变量分配的位置上,此后这两个变量可以参与任何操作而不会互相影响。而当从一个变量向另一个变量复制引用类型的值时,同样也会将存储在变量对象中的值复制一份放到为新变量分配的空间中,不同的是,这个值的副本实际上是一个指针,而这个指针指向存储在堆中的一个对象。复制操作结束后,两个变量实际上将引用同一个对象。因此,改变其中一个变量,就会影响另一个变量:
var a = [0, 1, 2, 3];var b = a;b.push(4, 5, 6);console.log(a); // [0, 1, 2, 3, 4, 5, 6]
而ECMAScript中所有函数的参数都是按值传递的,也就是说,把函数外部的值复制给函数内部的参数,就和把值从一个变量复制到另一个变量一样!弄清楚了这一点,我们再回到上面的代码。
当没有执行nums = tmp.concat(nums);
这行代码时,数组a
和函数rotate的参数nums
都引用着同一个地址,于是它们的值一起改变;当执行这行代码后,nums
指向了一个新的地址,无论它指向哪里,此时的它已经和数组a
没有任何关系,也就是说a
的值在这一刻之后不会再变化了。
于是我们很清楚地知道,要想在nums
上体现a
的变化,函数内的nums
参数不能去引用一个新的对象,只能在自身上操作,思考下写下如下代码,终于AC:
var rotate = function(nums, k) { k %= nums.length; var tmp = []; if (k) tmp = nums.slice(-k); nums.splice(-k, k); Array.prototype.unshift.apply(nums, tmp);};
利用JavaScript的这个性质,能出现一些很神奇的效果,这些我也在做题过程中逐渐体会到了一点,具体题目到时再跟大家分享吧!