Lt70.爬楼梯、Lt345.反转字符串中的元音字母、Lt404.左叶子之和

70.爬楼梯

Category	Difficulty	Likes	Dislikes
algorithms	Easy (50.49%)	1218	-

Tags
dynamic-programming
Companies
adobe | apple
假设你正在爬楼梯。需要 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 阶

---

Discussion | Solution

思路

经典动态规划问题，得出的结果即为斐波那契数列

递归

当 n=1 时，只能爬一层，方法 1 种。
当 n=2 时，可以爬一层或二层，方法 2 种。
当 n=3 时，相当于 F(2)+F(1)
所以可以得出当 n 大于 2 时，到达 n 层的方法相当于 n-1（最后一步只能走 1）层的方法加 n-2（最后一步只能走 2）层的爬法。
F{
1 (n=1),
2 (n=2),
F(n-1) + F(n-2) (n>2)
}
但是递归的方法太暴力，肯定超时。

/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 */

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

动态规划

改为动态规划，自底向上进行求解

解答

/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n < 1) return 0;
  else if (n === 1) return 1;
  else if (n === 2) return 2;
  let a = 1;
  let b = 2;
  let temp;
  for (let i = 2; i < n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
};
// @lc code=end

Accepted
45/45 cases passed (64 ms)
Your runtime beats 93.23 % of javascript submissions
Your memory usage beats 12.26 % of javascript submissions (37.8 MB)

345.反转字符串中的元音字母

Category	Difficulty	Likes	Dislikes
algorithms	Easy (50.62%)	112	-

TagsCompanies
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1：

输入："hello"
输出："holle"

示例 2：

输入："leetcode"
输出："leotcede"

提示：

• 元音字母不包含字母 “y” 。

---

Discussion | Solution

思路

首尾指针遍历，当 p>q 时结束循环，判断是否是元音，是的话交换首尾指针指向的值即可

解答

/*
 * @lc app=leetcode.cn id=345 lang=javascript
 *
 * [345] 反转字符串中的元音字母
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function (s) {
  let p = 0;
  let q = s.length - 1;
  let obj = {
    a: true,
    i: true,
    u: true,
    e: true,
    o: true,
    A: true,
    I: true,
    U: true,
    E: true,
    O: true,
  };
  s = s.split("");
  while (p < q) {
    if (obj[s[p]] && obj[s[q]]) {
      let temp = s[p];
      s[p] = s[q];
      s[q] = temp;
      p++;
      q--;
    } else if (obj[s[p]] && !obj[s[q]]) {
      q--;
    } else if (!obj[s[p]] && obj[s[q]]) {
      p++;
    } else {
      p++;
      q--;
    }
  }
  return s.join("");
};
// @lc code=end

Accepted
481/481 cases passed (104 ms)
Your runtime beats 62.27 % of javascript submissions
Your memory usage beats 16.38 % of javascript submissions (44.6 MB)

404.左叶子之和

Category	Difficulty	Likes	Dislikes
algorithms	Easy (55.54%)	190	-

Tags
tree
Companies
facebook
计算给定二叉树的所有左叶子之和。
示例：

3
   / \
  9  20
    /  \
   15   7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

---

Discussion | Solution

思路

加一个是否为左节点字段，遍历所有节点，如果是左子叶才返回值

解答

/*
 * @lc app=leetcode.cn id=404 lang=javascript
 *
 * [404] 左叶子之和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function (root) {
  let sum = 0;
  sum = visit(root, false);
  return sum;
};

const visit = (node, isLeft) => {
  if (!node) return 0;
  if (isLeft && node.val && !node.left && !node.right) return node.val;
  return visit(node.left, true) + visit(node.right, false);
};
// @lc code=end

Accepted
102/102 cases passed (80 ms)
Your runtime beats 73.65 % of javascript submissions
Your memory usage beats 5.15 % of javascript submissions (40.6 MB)