面试编程题整理

Question

数组 0 后置

将数组中的 0 项搁置到数组的尾部，其他项的相对位置保持不变。要求时间复杂度为 O(n)

例如：
输入：[2, 3, 0, 1, 0, 8];
输出：[2, 3, 1, 8, 0, 0];

代码：

function sortZero(arr) {
    let zero;
    let flag = 0;
    for(let i = 0, len = arr.length; i < len; i++) {
        if(arr[i] === 0) {
            flag = 0;
            index++;
        } else {
            arr[i - index] =arr[i];
            (flag === 0) && (arr[i] = 0);
        }
    }
    return arr;
}

思路：想要达到较低的时间复杂度，使一次遍历完成需求，需要做到边遍历边完成移动，并在原数组的直接完成操作，不再额外创建新的空间。
步骤：
首先，在没有遇到 0 时，数组项保持不动；
遇到第一个 0 项时，用一个标识符 flag 来标识遇到 0 项的次数，这时，不对该项做任何处理；
下一项时（为 0 的后面所有项），将该项往前移动 flag 个位置，并将该项置为 0；

总的来说就是，数组每一项往前移动的位置跟 0 出现的次数有关。而 0 这一项是连同其他项一起移动的（后置）。

【tips】：(a = b) && (c = d) && (x = n) 的输出是什么？

相当于：if(a = b && c = d) x = n; 输出 x的值为n; 同时对 a 和 d 进行赋值了；

var a, b, c;
if((a = 1)&& (b = 2)) c = 9; // 9
console.log(a, b, c); // 1, 2, 9

第二题

有 100 个人编号为 1 ~ 100，一同进入一个房间；该房间有 100 个灯泡，编号也为 1 ~ 100，灯泡的状态有两种，亮或灭，可通过开关来控制，初始时灯全都是关的。每个编号为 n 的人，只能按编号为 n 的倍数的灯泡。（例如第一位同学把编号是1的倍数的灯的按钮按一下（此时100盏灯全亮），第二位同学把编号是2的倍数的灯的按钮按一下（此时只有50盏灯亮着，50盏被这个人按灭了）……第100位同学把编号是100的倍数的灯（即编号为100的灯）的按钮按一下。）
问，请问依次走完后，还有多少盏灯亮着？

答案：编号为 n 的平方次数的灯泡是亮着的(n 为 1 ~100)，所以有 10 个灯泡是亮着的。（1，4，9，16，25，36，49，64，81，100）

【更正】：约数只能对在整数范围内而言，而因数就不限于整数的范围。在这里说约数比较合适。
分析：显然灯泡最终的亮或灭的状态取决于被按的次数，奇数次该灯泡亮，偶数次该灯泡灭。
那么，编号为 n 的灯泡会被哪些人按呢，显然是编号为 n 的因数的人。
[例如，编号为 1 的灯泡，最终亮着，因为 1 的因数为 1；
编号为 2 的灯泡，最终灭着，因为 2 的因数为 1、2（两次）；
编号为 3 的灯泡灭着，因为 3 的因数为 1、3（两次）；
4 的因数为 1、2、4（三次），亮着；
5 的因数为1、5（两次），灭着；
6 的因数是1、2、3、6（四次），灭着；
7 的因数是1、7（两次）， 灭着；
....
以此类推，编号为 1、4、9、16、25....的灯泡是亮着的。可以发现，一般情况下，一个数的因数是成对的构成这个数，如 1x6, 2x3; 所以数字 6 有 4个因数；除非这个数是完全平方数，才会出现奇数个因数，如数字9，其中一对 3x3 只算一个因数。

所以最后亮着的，是编号为完全平方数的灯泡。

JavaScript 连等赋值问题

let a = { n: 1 };
let b = a;
a.x = a = { n: 2 };
console.log(a.x); // undefined
console.log(a, b); // { n: 2} {n: 1, x: {n: 2}}
console.log(b.x === a); // true

分析：

对于连等赋值表达式，先运算，后赋值。运算是从左往右顺序进行，而赋值操作是从右往左顺序进行。即赋值运算符是右结合性的：A = B = C = D等价于A = (B = (C = D))。

对于a.x = a = { n: 2 };首先运算 a.x,（ 这时 a 还是原地址引用）,运算完成开始从右往左进行赋值操作，即 a 的引用开始发生改变，完成a = { n: 2 }；然后继续往左赋值，a = { n: 2 }的返回值赋值给 a.x。

那对于赋值表达式，为什么会先运算后赋值呢，即为什么先确定左值呢。可以这样理解，如果不确定我要去的地方，取到值又有什么用呢？所以，左边的值在执行赋值之前就已经确定了，然后再将右边表达式的返回值给到左值。

所以，在使用的时候，尽量少用连等赋值操作符啦，除非你非常明白其内部机制。

再看一段代码，加深一下理解：

let a = { n: 1 };
let b = a;
a = a.x = { n: 2 };
console.log(a, b); // { n: 2} {n: 1, x: {n: 2}}
console.log(b.x === a); // true

var a = {n: 1};
var b = a;
a.x = a = a.y = {n: 2};
console.log(a, b);

函数声明的两种方式

function ftn() {
    console.log('old');
}
var b = ftn;
function ftn() {
    b();
    console.log('new');
}
ftn();//浏览器报内存溢出

var ftn = function() {
    console.log('old');
}
var b = ftn;
var ftn = function() {
    b();
    console.log('new');
}
ftn();//old,new依次弹出

分析：先看这两段代码：

function fn() {console.log('old')}
var b = fn;
function fn() {console.log('new')}
console.log(b); // function fn() {console.log('new')}

var fn = function () {console.log('old');}
var b = fn;
var fn = function () {console.log('new');}
console.log(b); // function () {console.log('old');}

函数声明有两种方式：function 声明和函数表达式声明。javascript里面是没有方法重载的，后面定义的重名 function 会覆盖前面的 function ,所以，第一段代码中 b 和 ftn 的引用指向同一个堆里面的内存。

而第二段代码，是函数表达式，fn 后面改变了引用，而 b 还指向 fn 原来的引用。

改写开头第一段代码的内存溢出：

function ftn() {alert('old');}
var b = ftn;
var ftn = function(){
    b();
    alert('new');
}
console.log(b);//老的ftn
console.log(ftn);//新的ftn
ftn();//old ,new