1、 reverse string

//Example:Given s = "hello", return "olleh".
/**
 * @param {string} s
 * @return {string}
 */
解法一：
var reverseString = function(s) {
    var result="";
    for(var i=1,len=s.length;i<=len;i++){
        result+=s[len-i]
    }
    return result;
};
或者利用js提供的數(shù)組的reverse()方法
解法二：
var reverseString = function(s) {
    return s.split("").reverse().join("")
};

關(guān)于數(shù)組的知識點(diǎn)：http://riny.net/2012/the-summary-of-javascript-string/

2、 Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
【分析】看清題設(shè)很重要，已經(jīng)提到Both of you are very clever and have optimal strategies for the game.所以我們在分析的時(shí)候就不能說通過遍歷這種想法看是否存在贏的可能，因?yàn)閷κ忠灿兄銐虻闹巧?。如果對手智障的話，那就除了n==4時(shí)必輸，其它情況都可能贏了。

當(dāng)n∈[1,3]時(shí)，先手必勝。

當(dāng)n == 4時(shí)，無論先手第一輪如何選取，下一輪都會轉(zhuǎn)化為n∈[1,3]的情形，此時(shí)先手必負(fù)。

當(dāng)n∈[5,7]時(shí)，先手必勝，先手分別通過取走[1,3]顆石頭，可將狀態(tài)轉(zhuǎn)化為n == 4時(shí)的情形，此時(shí)后手必負(fù)。

當(dāng)n == 8時(shí)，無論先手第一輪如何選取，下一輪都會轉(zhuǎn)化為n∈[5,7]的情形，聰明的對手也會將狀態(tài)轉(zhuǎn)為n==4的情形，此時(shí)先手必負(fù)。
...

通過以上分析可以得出，n%4!=0時(shí)，先手必勝。

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return n%4!==0
}

3、Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

【分析】
這個(gè)問題其實(shí)不難，但它的要求是：Your algorithm should have a linear runtime complexity. 所以像什么嵌套循環(huán)的想法要直接pass，最初我看到這要求是一聲冷笑的，因?yàn)槲以诤芫弥翱吹竭^ 鉤子函數(shù) ，也就是將這些數(shù)組中的元素當(dāng)做一個(gè)對象的key,出現(xiàn)次數(shù)作為其value。所以代碼很快如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    var obj = {},
        result;
    for (var i = 0, len = nums.length; i < len; i++) {
        var val = nums[i];
        if (!obj[val]) {
            obj[val] = 1;
        } else {
            obj[val] = 2;
        }
    }
    for (var item in obj) {
        if (obj[item] === 1) {
            result = item;
            return parseInt(result);
        }
    }
};

復(fù)雜度還是O(n)的，但是2n，效率超過了86%左右，然后去網(wǎng)上查查看還有啥解法，然后就發(fā)現(xiàn)了如下讓我大吃一驚的代碼：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    var result = 0;
    for (var i = 0,len=nums.length; i<len; i++)
    {
        result ^=nums[i];
    }
    return result;
};

他的效率超過了100% ! 是的，他用了XOR運(yùn)算，不需要額外內(nèi)存。因?yàn)锳 XOR A = 0，且XOR運(yùn)算是可交換的，所以對于實(shí)例{2,1,4,5,2,4,1}就會有這樣的結(jié)果：

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

這些基礎(chǔ)我們真的是走著走著就忘了。。。

4、Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

【分析】如果問題是這樣，這是個(gè)很直觀的循環(huán)搞定的問題。然而后面題目中又加了一句：Could you do it without any loop/recursion in O(1) runtime?------Excuse me ???!!!

先來個(gè)循環(huán)壓壓驚：

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    var val=0;
    while(num>=10){
        val=parseInt(num/10);
        num=num%10;
        num+=val;
    }
    return num;
};

既然題目問是否可以不用循環(huán)，那么首先就要想這里面應(yīng)該是有規(guī)律的。打印下前30個(gè)數(shù)看看：

顯然9個(gè)一循環(huán)，所以是對9取余的結(jié)果，但是，對于9的倍數(shù)對9取余為0，結(jié)果就不對了，所以修正為：

var addDigits = function(num) {
    return (num-1)%9+1
};