1、無(wú)重復(fù)最長(zhǎng)子串(8.14)

題目：
給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

解答：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let arr = s.split('');
  if(arr.length === 0){
    return 0;
  }
  let num = 1;
  let res = []
  for(let i = 0; i < arr.length-1; i++){
    res = [];
    res.push(arr[i]);
 for(let j = i+1; j < arr.length; j++){
   if(res.indexOf(arr[j])<0){
       res.push(arr[j]);   
       num = num < res.length ? res.length:num
   }else{
       break;
   } 
 }
}
  return num
};

最優(yōu)解答，時(shí)間復(fù)雜度O（n），滑動(dòng)窗口解法：

var lengthOfLongestSubstring = function(s) {
    // 哈希集合，記錄每個(gè)字符是否出現(xiàn)過(guò)
    const occ = new Set();
    const n = s.length;
    // 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒(méi)有開(kāi)始移動(dòng)
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指針向右移動(dòng)一格，移除一個(gè)字符
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不斷地移動(dòng)右指針
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

2、最長(zhǎng)回文子串(8.15)

題目：
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
示例 2：

輸入: "cbbd"
輸出: "bb"

/*
 * @lc app=leetcode id=5 lang=javascript
 *
 * [5] Longest Palindromic Substring
 */
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  // babad
  // tag : dp
  if (!s || s.length === 0) return "";
  let res = s[0];

  const dp = [];

  // 倒著遍歷簡(jiǎn)化操作， 這么做的原因是dp[i][..]依賴(lài)于dp[i + 1][..]
  for (let i = s.length - 1; i >= 0; i--) {
    dp[i] = [];
    for (let j = i; j < s.length; j++) {
      if (j - i === 0) dp[i][j] = true;
      // specail case 1
      else if (j - i === 1 && s[i] === s[j]) dp[i][j] = true;
      // specail case 2
      else if (s[i] === s[j] && dp[i + 1][j - 1]) {
        // state transition
        dp[i][j] = true;
      }

      if (dp[i][j] && j - i + 1 > res.length) {
        // update res
        res = s.slice(i, j + 1);
      }
    }
  }

  return res;
};

3、圖像渲染（8.16）

題目：
有一幅以二維整數(shù)數(shù)組表示的圖畫(huà)，每一個(gè)整數(shù)表示該圖畫(huà)的像素值大小，數(shù)值在 0 到 65535 之間。

給你一個(gè)坐標(biāo) (sr, sc) 表示圖像渲染開(kāi)始的像素值（行 ，列）和一個(gè)新的顏色值 newColor，讓你重新上色這幅圖像。

為了完成上色工作，從初始坐標(biāo)開(kāi)始，記錄初始坐標(biāo)的上下左右四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn)，接著再記錄這四個(gè)方向上符合條件的像素點(diǎn)與他們對(duì)應(yīng)四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn)，……，重復(fù)該過(guò)程。將所有有記錄的像素點(diǎn)的顏色值改為新的顏色值。

最后返回經(jīng)過(guò)上色渲染后的圖像。

示例 1:
輸入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
輸出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在圖像的正中間，(坐標(biāo)(sr,sc)=(1,1)),
在路徑上所有符合條件的像素點(diǎn)的顏色都被更改成2。
注意，右下角的像素沒(méi)有更改為2，
因?yàn)樗皇窃谏舷伦笥宜膫€(gè)方向上與初始點(diǎn)相連的像素點(diǎn)。
注意:

image 和 image[0] 的長(zhǎng)度在范圍 [1, 50] 內(nèi)。
給出的初始點(diǎn)將滿(mǎn)足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的顏色值在范圍 [0, 65535]內(nèi)。

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function(image, sr, sc, newColor) {
    const m = image.length;
    const n = image[0].length;
    let oldColor = image[sr][sc];
    if(oldColor  == newColor){
        return image
    }
    const fill = (i, j) => {
        if (i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oldColor) {
            return;
        }
        image[i][j] = newColor; 
        fill(i - 1, j);
        fill(i + 1, j);
        fill(i, j - 1);
        fill(i, j + 1);
    };
  fill(sr, sc);
  return image;
};

4、平衡二叉樹(shù)(8.17)

題目：
給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
本題中，一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。

示例 1:
給定二叉樹(shù) [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:
給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

解答：

/**
 * 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) {
  const balanced = (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
  }
  return balanced(root) !== -1
};

5、 兩數(shù)之和(8.18)

題目：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。

示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  // 1. 構(gòu)造哈希表
    let map = new Map();
    // 2. 遍歷數(shù)組
    for(var i = 0; i < nums.length; i++){
       // 2.1 如果找到 target - nums[i] 的值
        if(map.has(target-nums[i])){
            return [map.get(target-nums[i]), i]
        }else{
          // 2.2 如果沒(méi)找到則進(jìn)行設(shè)置
            map.set(nums[i],i);
        }
    } 
};

6、 二叉樹(shù)的最小深度（8.20）

題目：
給定一個(gè)二叉樹(shù)，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹(shù) [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(root === null) return 0;
    var m1 =  minDepth(root.left);
    var m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有為空的情況，直接返回m1+m2+1
        //2.如果都不為空，返回較小深度+1
     return root.left === null || root.right === null ? m1+m2+1 : Math.min(m1, m2)+1
};

7、兩數(shù)相加（8.21）

題目：
給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) { 
    var  l = new ListNode(null);
    var temp = l;
    var sum = 0;
    var n = 0;
    while(l1 || l2){
        sum = (l1?l1.val:0 )+ (l2?l2.val:0 )+ n;
        n = sum > 9 ? 1 : 0;
        temp.next = new ListNode(sum % 10);
        temp = temp.next;
        l1 && (l1 = l1.next);
        l2 && (l2 = l2.next);
    }
    if(n > 0) temp.next = new ListNode(n);

   return l.next;
};

8、整數(shù)反轉(zhuǎn)（8.22）

給出一個(gè) 32 位的有符號(hào)整數(shù)，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲(chǔ)得下 32 位的有符號(hào)整數(shù)，則其數(shù)值范圍為 [?2^31, 2^31 ? 1]。請(qǐng)根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
   var result = 0;
   while(x!==0){
       result = result * 10 + x % 10;
       x = parseInt(x/10) || 0;
   }
   if(result< 0){
        return result < - Math.pow(2,31) ? 0 : result;
    }else{
        return result < Math.pow(2,31) ? result : 0;
    }
   
};

9. 回文數(shù)(8.23)

題目：
判斷一個(gè)整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是一個(gè)回文數(shù)。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個(gè)回文數(shù)。
進(jìn)階:
你能不將整數(shù)轉(zhuǎn)為字符串來(lái)解決這個(gè)問(wèn)題嗎？

var isPalindrome = function(x) {
    return x.toString() == x.toString().split("").reverse().join("");
}

10、 遞增子序列（8.25）

題目：
給定一個(gè)整型數(shù)組, 你的任務(wù)是找到所有該數(shù)組的遞增子序列，遞增子序列的長(zhǎng)度至少是2。

示例:

輸入: [4, 6, 7, 7]
輸出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
說(shuō)明:

給定數(shù)組的長(zhǎng)度不會(huì)超過(guò)15。
數(shù)組中的整數(shù)范圍是 [-100,100]。
給定數(shù)組中可能包含重復(fù)數(shù)字，相等的數(shù)字應(yīng)該被視為遞增的一種情況。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
      let s = new Set(), res = []
    
    function helper(nums, level, subArr) {
        if (level >= nums.length) {
            // 去重 且 子序列長(zhǎng)度大于等于 2
            if (subArr.length >= 2 && !s.has(subArr.join(','))) {
                s.add(subArr.join(','))
                res.push(subArr)
            }
            return 
        }

         // 選 剪枝 保證遞增
        if (subArr.length === 0 || subArr[subArr.length - 1] <= nums[level]) {
            helper(nums, level+1, [...subArr, nums[level]])   
        }

        // 不選
        helper(nums, level+1, [...subArr]) 
        
    }

    helper(nums, 0, [])

    return res

};