js解leetcode(57)-簡單

1.二叉樹的深度

題目：輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。

思路：遞歸，某個樹的深度=左節點深度與右節點深度的較大值 + 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
if(!root)return 0
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
};
           

2.平衡二叉樹

題目：輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左右子樹的深度相差不超過1，那麼它就是一棵平衡二叉樹。

思路：遞歸判斷。判斷某個節點的左右節點是否是平衡的，如果均平衡，再判斷兩個左右節點的深度，即節點本身是否平衡

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
    return balanced(root) !== -1
};
var balanced = function (node) {
    if (!node) return 0
    const left = balanced(node.left)
    const right = balanced(node.right)
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1
    }
    return Math.max(left, right) + 1
}
           

3.和為S的兩個數字

題目：輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等于s，則輸出任意一對即可。

思路：和兩數之和很像，不過有另外的解法。

因為是遞增數組，是以用雙指針，分别指向開頭和結尾，如果和大于目标，則右指針左移；如果和小于目标，左指針右移

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const l = nums.length;
  let left = 0,
    right = l - 1;
  while (left < right) {
    if (nums[left] + nums[right] == target) return [nums[left], nums[right]];
    if (nums[left] + nums[right] > target) {
      right--;
    } else {
      left++;
    }
  }
};
           

4.和為S的連續正數列

題目：

輸入一個正整數 target ，輸出所有和為 target 的連續正整數序列（至少含有兩個數）。

序列内的數字由小到大排列，不同序列按照首個數字從小到大排列。

思路：雙指針法，因為所有數是整數，是以對于一個數組來說，如果加入後一個數，那麼和肯定會變大。

那麼，對于下标left-right的元素，記錄和，并且記錄目前left-right的元素。如果此時和大于目标值，則left右移，臨時數組删除首個元素，直到和小于等于目标為止。然後判斷目前的和是否等于目标值。

默默吐槽一句，劍指offer很多簡單題光從難度來說其實在主站是中等甚至困難的。。。這題個人感覺就是中等

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function(target) {
  const res = [];
  const temp = [];
  let sum = 0;
  for (let i = 1; i < target; i++) {
    temp.push(i);
    sum += i;

    while (sum > target) {
      const item = temp.shift();
      sum -= item;
    }
    if (sum == target) {
      res.push(temp.slice());
    }
  }
  return res;
};
           

5.翻轉單詞順序

題目：

輸入一個英文句子，翻轉句子中單詞的順序，但單詞内字元的順序不變。為簡單起見，标點符号和普通字母一樣處理。例如輸入字元串"I am a student. "，則輸出"student. a am I"。

思路：用空格分隔成單詞，過濾連續空格，然後用數組的reverse方法反轉，然後合并

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  return s.split(" ").filter((i) => i).reverse().join(" ");
};