leetcode刷题之路——20190805（70、83、101）

[yangxy6]

70

/*
 * @lc app=leetcode id=70 lang=javascript
 *
 * √ Your runtime beats 72.43 % of javascript submissions
 * √ Your memory usage beats 33.7 % of javascript submissions (33.9 MB)
 * [70] Climbing Stairs
 */
/**
 * @param {number} n
 * @return {number}
 * 动态规划->从后往前思想
 * 动态规划，最优解转化为其子问题
 * 第i-1阶后向上爬一个，第i-2阶后向上爬两个，爬到第i个 dp[i]=dp[i-1]+dp[i-2]
 * 时间复杂度O(n)，空间复杂度O(n)
 */
var climbStairs = function(n) {
  if (n === 1) return 1;
  let dp = [];
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

// /**
//  * @param {number} n
//  * @return {number}
//  * 典型的斐波那契数——递归（n过大时会超时）
//  */
var climbStairs = function(n) {
  // n===0不代表不走，而是走到后面正好剩一步
  if (n === 0) return 1;
  if (n === 1) return 1;
  if (n > 1) {
    return climbStairs(n - 1) + climbStairs(n - 2);
  }
};

/**
 *  √ 45/45 cases passed (48 ms)
 * √ Your runtime beats 89.65 % of javascript submissions
 * √ Your memory usage beats 58.01 % of javascript submissions (33.8 MB)
 * @param {number} n
 * @return {number}
 * 典型的斐波那契数——非递归
 * 这个想法很奇妙，一个循环一阶梯一阶梯往上走，没走一步记录方法，同时first，second重新赋值继续走。
 */
var climbStairs = function(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  let first = 1;
  let second = 2;
  let third = 0;
  for (let i = 3; i <= n; i++) {
    third = first + second;
    first = second;
    second = third;
  }
  return third;
};
console.log(climbStairs(8));

83

/*
 * @lc app=leetcode id=83 lang=javascript
 *
 * √ 165/165 cases passed (76 ms)
 * √ Your runtime beats 22.4 % of javascript submissions
 * √ Your memory usage beats 73.83 % of javascript submissions (35.6 MB)
 * [83] Remove Duplicates from Sorted List
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 * 开始打算用obj去重，发现实际是已经排序的链表直接通过current.next.val和curren.val进行比较
 */
var deleteDuplicates = function(head) {
  let current = head;
  while (current !== null && current.next !== null) {
    if (current.next.val === current.val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return head;
};

101

/*
 * @lc app=leetcode id=101 lang=javascript
 *
 * [101] Symmetric Tree 对称树
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 * 思路：中序遍历成回温数组，在通过字符串比较
 * 叶子节点是空节点？测试案例未全部通过
 */
var isSymmetric = function(root) {
  // [1,2,2,2,null,2] 未通过
  let arr = [];
  inOrderTraverseNode(root);
  return arr.join('') === arr.reverse().join('');
  function inOrderTraverseNode(node) {
    if (node !== null) {
      inOrderTraverseNode(node.left);
      arr.push(node.val);
      inOrderTraverseNode(node.right);
    }
  }
};

/**
 * √ 195/195 cases passed (60 ms)
 * √ Your runtime beats 74.44 % of javascript submissions
 * √ Your memory usage beats 74.24 % of javascript submissions (35.5 MB)
 * @param {TreeNode} root
 * @return {boolean}
 * 思路：有null节点时左右同时判断空节点，没有空节点时递归判断左右两边val
 */
const isSymmetric = function(root) {
  if (root === null) return true;
  return isMirror(root.left, root.right);
  function isMirror(left, right) {
    // 有null节点
    if (left === null && right === null) return true;
    if (left === null || right === null) return false;
    // left.left与right.right，right.left与left.right成镜像对称
    return left.val === right.val && isMirror(left.left, right.right) && isMirror(right.left, left.right);
  }
};