简单

1. 回文数

序号：9
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

示例 1：

  1. 输入：x = 121
  2. 输出：true

示例 2：

  1. 输入：x = -121
  2. 输出：false
  3. 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

  1. 输入：x = 10
  2. 输出：false
  3. 解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

  • -231 <= x <= 231 - 1

题解：

反转一半数字

  1. // 执行用时 136ms 内存消耗48.6 MB
  2. /**
  3.  * @param {number} x
  4.  * @return {boolean}
  5.  */
  6. var isPalindrome = function(x) {
  7.     // 特殊情况：
  8.     // 如上所述，当 x < 0 时，x 不是回文数。
  9.     // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
  10.     // 则其第一位数字也应该是 0
  11.     // 只有 0 满足这一属性
  12.     if (x < 0 || (x % 10 === 0 && x !== 0)) {
  13.         return false;
  14.     }
  16.     let revertedNumber = 0;
  17.     while (x > revertedNumber) {
  18.         revertedNumber = revertedNumber * 10 + x % 10;
  19.         x = Math.floor(x / 10);
  20.     }
  22.     // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
  23.     // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
  24.     // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
  25.     return x === revertedNumber || x === Math.floor(revertedNumber / 10);
  26. };

复杂度分析

  • 时间复杂度：O(logn)，对于每次迭代，我们会将输入除以 10，因此时间复杂度为 O(logn)。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

    字符串反转

    1. // 执行用时 152ms 内存消耗50.1 MB
    2. var isPalindrome = function(x) {
    3.   let revertedNumber = (x + "").split('').reverse().join("");
    4.   return (x + "") === revertedNumber;
    5. };

    2. 爬楼梯

    序号：70
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    示例 1： ```javascript 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。
  1. 1 阶 + 1 阶
  2. 2 阶 **示例 2：**javascript 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。
  3. 1 阶 + 1 阶 + 1 阶
  4. 1 阶 + 2 阶
  5. 2 阶 + 1 阶 ``` 提示：
  • 1 <= n <= 45

题解：
我们用 f(x)表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x) = f(x - 1) + f(x - 2)
它意味着爬到第 x 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

动态递归

  1. // 执行用时 60ms 内存消耗40.8 MB
  2. /**
  3.  * @param {number} n
  4.  * @return {number}
  5.  */
  6. var climbStairs = function(n) {
  7.     let p = 0, q = 0, r = 1;
  8.     for (let i = 0; i < 0; i++) { // let i = 1; i <= n; ++i
  9.         p = q;
  10.         q = r;
  11.         r = p + q;
  12.     }
  13.     return r;
  14. };

复杂度分析

  • 时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
  • 空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。