5. 最长回文子串

121. 买卖股票的最佳时机

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  6. // 求targetDecrease值最大
  7. var maxProfit = function(prices) {
  8.     var min = prices[0]
  9.     var maxprofit = 0
  11.     for (let j = 0; j < prices.length; j++) {
  12.         if (prices[j] < min) {
  13.             min = prices[j]
  14.         } else if (prices[j] - min > maxprofit) {
  15.             maxprofit = prices[j] - min
  16.         }
  17.     }
  18.     return maxprofit
  19. };

54. 螺旋矩阵

按照层每次顺时针往前，每层结束时更新各个角的坐标，直到走完。
image.png
https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/

  1. var spiralOrder = function(matrix) {
  2.     if (!matrix.length || !matrix[0].length) {
  3.         return [];
  4.     }
  6.     const rows = matrix.length, columns = matrix[0].length;
  7.     const order = [];
  8.     let left = 0, right = columns - 1, top = 0, bottom = rows - 1;
  9.     // while的条件为什么是这样
  10.     while (left <= right && top <= bottom) {
  11.         // 上
  12.         for (let column = left; column <= right; column++) {
  13.             order.push(matrix[top][column]);
  14.         }
  15.         // 右
  16.         for (let row = top + 1; row <= bottom; row++) {
  17.             order.push(matrix[row][right]);
  18.         }
  19.         ??
  20.         if (left < right && top < bottom) {
  21.             for (let column = right - 1; column > left; column--) {
  22.                 order.push(matrix[bottom][column]);
  23.             }
  24.             for (let row = bottom; row > top; row--) {
  25.                 order.push(matrix[row][left]);
  26.             }
  27.         }
  28.         [left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
  29.     }
  30.     return order;
  31. };

695. 岛屿的最大面积

  1. /**
  2.  * @param {number[][]} grid
  3.  * @return {number}
  4.  */
  5.  // 题意是求有边界的1有多少个岛
  6.  // 两次循环走网格，
  7.  // 终止条件为x轴的点大于grid[0]，y轴的点小于grid.size
  8.  // 如果检测点为1，count++
  10. var maxAreaOfIsland = function(grid) {
  11.     var max = 0
  12.     var count = 0
  13.     var isArea = (i, j) => {
  14.         // 这里巨饶，因为i其实是y轴
  15.         return (i >=0 && i < grid.length && j >=0 && j < grid[0].length)
  16.     }
  17.     var dfs = (grid, i, j) => {
  18.         // 超出区域
  19.         if (!isArea(i, j)) {
  20.             return
  21.         }
  22.         // 如果不是岛屿
  23.         if (grid[i][j] !== '1') {
  24.             count = 0
  25.             return
  26.         }
  27.         // 标记过已经走的
  28.         grid[i][j] = '2'
  30.         // 寻找上下左右
  31.         dfs(grid, i, j - 1)
  32.         dfs(grid, i, j + 1)
  33.         dfs(grid, i - 1, j)
  34.         dfs(grid, i + 1, j)
  35.     }
  37.     // 外层循环是每个y轴的
  38.     for (let i = 0; i < grid.length; i++) {
  39.         // 内层循环是每个x轴的
  40.         for (let j = 0; j < grid[0].length; j++) {
  41.             if (grid[i][j] === '1') {
  42.                 max = Math.max(max, ++count)
  43.                 dfs(grid, i, j)
  44.             }
  45.         }
  46.     }
  47.     return count
  48. };

209. 长度最小的子数组

  1. /**
  2.  * @param {number} target
  3.  * @param {number[]} nums
  4.  * @return {number}
  5.  */
  7.  // 找到最短的数组之和 >= target，返回数组长度 
  8.  // 双指针
  9. var minSubArrayLen = function(target, nums) {
  10.     var res = 0
  12.     for (let j = 0; j < nums.length; j++) {
  13.         var tmp = 0
  14.         var left = j
  15.         var right = nums.length - 1
  16.         // 思路理解，但是不对
  17.         while(left < right && target > tmp) {
  18.             tmp += nums[left]
  19.             if (nums[left] + tmp >= target) {
  20.                 temp = 0
  21.                 res = Math.min(res, left - j) 
  22.             }
  23.             left++
  24.         }
  25.     }
  26.     return res
  28. };

剑指 Offer 22. 链表中倒数第K个节点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @param {number} k
  11.  * @return {ListNode}
  12.  */
  13. var getKthFromEnd = function(head, k) {
  14.     // 1、计算长度，再len - k即为断的节点
  15.     // 2、先反转链表，在到第K个时候断掉，再反转
  16.     let len = 0
  17.     let link = head
  19.     while(link) {
  20.         len++
  21.         link = link.next
  22.     }
  23.     link = head
  24.     for (let i = 0; i < len - k; i++) {
  25.         link = link.next
  26.     }
  27.     return link
  28. };

226. 翻转二叉树

1、递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null) {
        return null;
    }
    // 递归
    let left = invertTree(root.left)
    let right = invertTree(root.right)
    root.right = left
    root.left = right
    return root
};

2、bfs

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null) {
        return null;
    }
    var q = [root]
    while(q.length) {
      var tmp = q.pop()
      var left = tmp.left

      tmp.left = tmp.right
      tmp.right = left

      if (tmp.left) {
        q.push(tmp.left)
      }
      if (tmp.right) {
        q.push(tmp.right)
      }
    }
  return root
};