LeetCode(力扣)答案解析（四）

[Checkson]

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思路：
这道题目跟斐波那契数列很像。假设梯子有n层，那么如何爬到第n层呢，因为每次只能爬1或2步，那么爬到第n层的方法要么是从第n-1层一步上来的，要不就是从n-2层2步上来的，所以我们得出的递推公式是：dp[n] = dp[n-1] + dp[n-2]。

解法一（递归）

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
};

这种解法虽然优雅，但提交到leetcode发现超时了，不过是意料之中，我们稍微改进一下。

解法二（数组递推 + 通项公式）

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 1) return 1;
    var dp = [1, 2];
    for (var i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
};

perfect，AC了！但是还有没有优化的空间呢？可以发现，我们借助了数组来递推公式，那么我们能不能不借助数组，从而节省空间呢？

解法三（动态规划 + 空间复杂度O(1)）

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    var a = 1, b = 2;
    while (--n > 0) {
       b += a;
       a = b - a;
    }
    return a;
};

我们先用b存储a+b的结果，得到了下一步递推结果。然后用新的b值减去a就得到了旧的b值，然后赋值给a，这样就可以模拟上面递推的过程了。

557. 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例1：

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

注意： 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

思路：
这道题目用JavaScript做非常easy，或者，不用C做算法都算是作弊吧，我们先看函数式编程怎么写：

解法一（函数式编程）

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').map(function (item) { return item.split('').reverse().join(''); }).join(' ');
};

解法二（自己实现）

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
   var ans = '', word = '';
   for (var i = s.length - 1; i >= 0; i--) {
       if (s[i] === ' ') {
           ans = s[i] + word + ans;
           word = '';
           continue;
       }
       word += s[i];
       if (i === 0) {
           ans = word + ans;
       }
   }
   return ans;
};

这个解法的思路很粗暴，倒序遍历字符串，这样，每个单词倒序就可以被记录下来，遇到空格就添加到ans字符串中。若遍历到字符串第一个字符了，就直接把剩下的单词拼接上去。

292. Nim游戏

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例：

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路

这道题目非常简单，只有石头的个数为4的倍数，那么我们自己必输，其他情况都可以赢。

题解：

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