本篇内容主要是2021年9月针对leetcode进行刷题，过程中学习《labuladong的算法小抄》作为刷题主要参考，整理的部分笔记。

数据结构存储方式

只有两种，数组（顺序存储）和链表（链式存储）。 数组方式，连续存储、结构紧密，需要分配一块连续的存储空间，所以每次扩容会面对重新分配连续空间，将原数据整体复制。如果要进行中间插入删除，每次必须搬移中间位置开始后所有数据。
链表方式，元素不连续，指针指向下一元素。不存在扩容问题，但无法随机访问，每个元素包含前后元素指针，消耗更多空间。 其他数据结构是基于该两种数据结构的基础上产生的，只是对外暴露的方法是不同。

基本操作

基本操作无外乎遍历+访问，再进行增删改查。

各种数据结构遍历方式可抽象为两种，线性与非线性。

线性即for、while迭代。 非线性即递归。

  1. class T {
  3.     /**
  4.      * 线性迭代 
  5.      */
  6.     void traverse(int[] arr) {
  7.         for (int i = 0; i < arr.length; i++) {
  8.             // 迭代访问arr[i]
  9.         }
  10.     }
  12.     /**
  13.      * 链表遍历 
  14.      */
  15.     class ListNode {
  16.         int val;
  17.         ListNode next;
  18.     }
  20.     void traverse(ListNode head) {
  21.         for (ListNode p = head.next; p != null; p = p.next) {
  22.             // 迭代访问 p.val
  23.         }
  24.     }
  26.     void traverse(ListNode head) {
  27.         // 递归访问head.val
  28.         traverse(head.next);
  29.     }
  31.     /**
  32.      * 二叉树遍历框架
  33.      */
  34.     class TreeNode {
  35.         int val;
  36.         TreeNode left, right;
  37.     }
  39.     void traverse(TreeNode root) {
  40.         traverse(root.left);
  41.         traverse(root.right);
  42.     }
  44.     /**
  45.      * 拓展：n叉树遍历框架
  46.      */
  47.     class TreeNode {
  48.         int val;
  49.         TreeNode[] children;
  50.     }
  52.     void traverse(TreeNode root) {
  53.         for (TreeNode child : root.children) {
  54.             traverse(child);
  55.         }
  56.     }
  58.     /**
  59.      * 拓展：在n叉树上，可得到图的遍历方式，图即若干棵n叉树
  60.      * 注意：图上如果出现环怎么处理，使用boolean[] visited做标记
  61.      */
  62. }

体会上述代码，各种数据结构的访问方式无外乎从基础访问方式中延伸出来。 掌握基础的数据结构，从中汲取通用方式即可。

二叉树问题集锦

  1. /**
  2.  * 二叉树
  3.  */
  4. class BinaryTree {
  6.     /**
  7.      * 二叉树最大路径和
  8.      */
  9.     class leetcode124 {
  10.         int ans = INT_MIN;
  12.         int oneSideMax(TreeNode root) {
  13.             if (root == nullptr) {
  14.                 return 0;
  15.             }
  16.             int left = max(0, oneSideMax(root.left));
  17.             int right = max(0, oneSideMax(root.right));
  18.             ans = max(ans, left + right + root.val);
  19.             return max(left, right) + root.val;
  20.         }
  21.     }
  23.     /**
  24.      * 根据前序遍历和中序遍历的结果还原二叉树
  25.      */
  26.     class leetcode105 {
  27.         TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Interger, Interger> inMap) {
  28.             if (preStart > preEnd || inStart > inEnd) {
  29.                 return null;
  30.             }
  32.             TreeNode root = new TreeNode(preorder[preStart]);
  33.             int inRoot = inMap.get(root.val);
  34.             int numsLeft = inRoot - inStart;
  36.             root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
  37.             root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
  39.             return root;
  40.         }
  41.     }
  43.     /**
  44.      * 恢复一棵BST
  45.      * 中序遍历
  46.      */
  47.     class leetcode99 {
  48.         void traverse(TreeNode node) {
  49.             if (!node) {
  50.                 return;
  51.             }
  52.             traverse(node.left);
  53.             if (node.val < prev.val) {
  54.                 s = (s == NULL) ? prev : s;
  55.                 t = node;
  56.             }
  57.             prev = node;
  58.             traverse(node.right);
  59.         }
  60.     }
  61. }

二叉树的问题解决若干->get递归的精髓->递归的问题就是树的问题。 这种分类刷题的方法，可以抽象成，学习一类框架，通过例子加深学习，最终掌握框架、活学活用。

动态规划凑零钱的例子非常形象，本质上也是个递归的问题，但是在思考题目本身的问题时，很容易被各种条件，边界等等影响思路，实际上，先回归到该种类型本身，可以抽象出一个简单模型

  1. class Coin {
  2.     void coin(List<Integer> coins, int amount) {
  4.     }
  6.     int dp(int n) {
  7.         if (n == 0) {
  8.             return 0;
  9.         }
  10.         if (n < 0) {
  11.             return -1;
  12.         }
  13.         int res = INT_MIN;
  14.         for (Integer coin : coins) {
  15.             subproblem = dp(n - coin);
  16.             if (subproblem == -1) {
  17.                 continue;
  18.             }
  19.             res = min(res, 1 + subproblem);
  20.         }
  21.         return res != INT_MIN ? res : -1;
  22.     }
  24.     /**
  25.      * 我猜你也看不懂上面的
  26.      * 换成下面的人话就简单很多
  27.      */
  28.     int dp(int n) {
  29.         for (Integer coin : coins) {
  30.             dp(n - coin);
  31.         }
  32.     }
  33. }

动态规划解题详解

动态规划问题的一般形式在于求解最值，核心问题在于穷举，但因为动态规划问题存在重叠子问题，所以必然具备最优子结构。 求解过程：

  1. 明确 状态
  2. 定义dp数组or函数的含义
  3. 明确 选择
  4. 明确 base case

下面通过两个例子来辅助理解：

案例

斐波那契数列

该例子主要用于讲解算法设计是一个螺旋上升的优化过程。

  1. 暴力递归
  1. class Solution {
  2.     public int fib(int n) {
  3.         if (n == 1 || n == 2) {
  4.             return 1;
  5.         }
  6.         return fib(n - 1) + (n - 2);
  7.     }
  8. }

入门篇 - 图1

从上方图片可以看到，在暴力递归的过程中，递归树会有许多重复计算问题，相同子树多次运算，这使得算法效率底下。 递归算法时间复杂度为：子问题个数x单个子问题需要运算的时间。二叉树的子树为指数级别，子问题分解为2^n个。
故而该算法时间复杂度为O(2^n)。

  1. 带备忘录的递归法

该算法为针对上面的重叠子问题的一种优化：将已运算的子问题解缓存，每次求解子问题先从缓存中查找，没有再进行计算，更新缓存。

  1. class Solution {
  2.     public int fib(int n) {
  3.         int[] results = new int[n + 1];
  4.         return help(n, results);
  5.     }
  7.     public int help(int n, int[] results) {
  8.         if (n == 1 || n == 2) {
  9.             return 1;
  10.         }
  11.         if (results[n] != 0) {
  12.             return results[n];
  13.         }
  14.         results[n] = help(n - 1, results) + help(n - 2, results);
  15.         return results[n];
  16.     }
  17. }
  1. dp数组迭代法

备忘录方法是自顶向下的，缺少什么就运算什么，反过来，自底向上可以从最小规模求解，逐步推到答案。

  1. class Solution {
  2.     public int fib(int n) {
  3.         int[] results = new int[n + 1];
  4.         results[1] = 1;
  5.         results[2] = 1;
  6.         for (int i = 3; i <= n; i++) {
  7.             results[i] = results[i - 1] + results[i - 2];
  8.         }
  9.         return results[n];
  10.     }
  11. }

凑零钱问题

给K种面值的硬币，面值不同，数量无限，再给出总金额，求问最少需要几枚硬币可以凑出总金额，如果不行则返回-1

  1. 确定状态：状态即原问题和子问题中的变量，唯一状态是目标金额amount；
  2. 定义dp函数：目标金额为n。至少需要dp(n)个硬币；
  3. 确定选择：从coins选出硬币，目标金额减少；
  4. 明确base case：目标金额为0时，所需硬币为0，小于0时无解。

回溯算法解题详解

回溯问题 = 决策树遍历过程 思考：路径、选择列表、结束条件 框架伪代码如下：

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  6.     for 选择 in 选择列表:
  7.         做选择
  8.         backtrack(路径, 选择列表)
  9.         撤销选择

回溯算法不存在重叠子问题，纯暴力枚举，复杂度高。

【例】给你⼀个 N×N 的棋盘， 让你放置 N 个 皇后， 使得它们不能互相攻击。 PS： 皇后可以攻击同⼀⾏、 同⼀列、 左上左下右上右下四个⽅向的任意单 位。

  1. class Solution {
  2.     List<List<Charater>> res = new ArrayList<>();
  4.     List<List<Charater>> solveNQueens(int n) {
  5.         List<List<Charater>> board = new ArrayList<>(8);
  6.         for (int i = 0; i < n; i++) {
  7.             for (int j = 0; j < n; j++) {
  8.                 board[i][j] = '.';
  9.             }
  10.         }
  11.         backtrack(board, 0);
  12.         return res;
  13.     }
  16.     void backtrack(int row) {
  17.         if (row == board.length) {
  18.             res.put(board);
  19.             return;
  20.         }
  22.         int n = board[row].length;
  23.         for (int col = 0; col < n; col++) {
  24.             if (!isValid(board, row, col)) {
  25.                 continue;
  26.             }
  27.             board[row][col] = 'Q';
  28.             backtrack(board, row + 1);
  29.             board[row][col] = ',';
  30.         }
  31.     }
  33.     boolean isValid(List<List<Charater>> board, int row, int col) {
  34.         int n = board.length;
  35.         for (int i = 0; i < n; i++) {
  36.             if (board[i][col] == 'Q')
  37.                 return false;
  38.         }
  39.         for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
  40.             if (board[i][j] == 'Q') {
  41.                 return false;
  42.             }
  43.         }
  45.         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
  46.             if (board[i][j] == 'Q') {
  47.                 return false;
  48.             }
  49.         }
  50.         return true;
  51.     }
  53.     // 解法复杂度过高，优化算法
  54.     boolean backtrack(List<List<Charater>> board, int row) {
  55.         if (row == board.size()) {
  56.             res.put(board);
  57.             return;
  58.         }
  60.         int n = board[row].size();
  61.         for (int col = 0; col < n; col++) {
  62.             board[row][col] = 'Q';
  63.             if (backtrack(board, row + 1)) {
  64.                 return true;
  65.             }
  66.             board[row][col] = ',';
  67.         }
  68.     }
  69. }

BFS广度优先搜索

通常写广搜算法都使用队列实现，BFS与DFS相比，BFS找到的路径最短，空间复杂度却相对大很多 广搜算法求解问题通常本质是在图上找从起点到终点的最近距离。 框架代码如下：

  1. class Solution {
  2.     int bfs(Node start, Node target) {
  3.         Queue<Node> q = new LinkedList<>();
  4.         // 避免走回头路
  5.         Set<Node> visited;
  7.         // 将七点加入队列
  8.         q.offer(start);
  9.         visited.add(start);
  11.         // 记录扩散步数
  12.         int step = 0;
  14.         while (q.size() > 0) {
  15.             int size = q.size();
  16.             for (int i = 0; i < size; i++) {
  17.                 Node current = q.poll();
  18.                 // 判断是否达到终点
  19.                 if (current.equals(target)) {
  20.                     return step;
  21.                 }
  23.                 for (Node x : current.adj()) {
  24.                     // 将相邻节点加入队列
  25.                     if (visited.contains(x)) {
  26.                         q.offer(x);
  27.                         visited.add(x);
  28.                     }
  29.                 }
  31.                 // 更新步数
  32.                 step++;
  33.             }
  34.         }
  35.     }
  36. }

BFS算法缺点，队列每次都会存储着二叉树一层的节点，最坏情况下队列中存储树的最底层节点数量，即N/2，空间复杂度为O(n)，所以通常在寻找最短路径时使用BFS，其余用DFS.

这里引用leetcode752题，该题目设计精巧，在复杂背景下容易忽略如何选择对应框架，抓住题干中关键信息，最小旋转次数，即可推断使用广搜，改题目深搜相当麻烦，存在无解情况需要判断。

双向BFS优化

传统BFS框架是从七点开始向四周扩散，遇到终点停止，双向BFS则是从七点和终点同时开始扩散，当两边有交集停止。 该问题从树上无法直观感受，结合密码锁问题可以理解多一点点。 双向BFS局限性：必须知道终点在哪里。

算法框架：不再使用队列，而是使用HashSet快速判断两个集合是否有交集，while循环的最后，交换q1和q2的内容，默认扩散q1相当于轮流扩散q1，q2。

再优化：在循环的开始，判断哪个集合元素多，每次都选择扩散集合中元素较少的一个，空间增长速度慢，效率更高。

入门篇 - 图2

在做leetcode127题时，看到这个图解非常清晰，作为补充理解

  1. class Solution {
  2.     /**
  3.      * 该方法比较特别，单个人认为不学也罢，这种方法下居然超时了...
  4.      * @param deadends
  5.      * @param target
  6.      * @return
  7.      */
  8.     int openLock(String[] deadends, String target) {
  9.         // 使用两个set来记录当前扩散位找交集即结束
  10.         Set<Integer> q1 = new HashSet<>();
  11.         Set<Integer> q2 = new HashSet<>();
  13.         int[] dead = new int[10000];
  14.         int tar = Integer.parseInt(target);
  15.         for (String deadend : deadends) {
  16.             dead[Integer.parseInt(deadend)] = 1;
  17.         }
  18.         if (dead[0] == 1 || dead[tar] == 1) {
  19.             return -1;
  20.         }
  21.         int step = 0;
  22.         q1.add(0);
  23.         q2.add(tar);
  24.         while (!q1.isEmpty() && !q2.isEmpty()) {
  25.             // 再优化技巧点：判断q1，q2长度，每次扩散更小的那个
  26.             // 原因是空间增加速度慢，效率更高
  27. //            if (q1.size() > q2.size()) {
  28. //                temp = q1;
  29. //                q1 = q2;
  30. //                q2 = temp;
  31. //            }
  32.             Set<Integer> temp = new HashSet<>();
  33.             for (Integer cur : q1) {
  34.                 if (cur != null) {
  35.                     if (dead[cur] == 1) {
  36.                         continue;
  37.                     }
  38.                     if (q2.contains(cur)) {
  39.                         return step;
  40.                     }
  41.                     for (int j = 0; j < 4; ++j) {
  42.                         int pow = (int) Math.pow(10, j);
  43.                         int next = cur + ((cur / pow % 10 + 1) % 10) * pow - (cur / pow % 10 * pow);
  44.                         if (next >= 10000 || next < 0 || dead[next] == 1) {
  45.                         } else {
  46.                             temp.add(next);
  47.                         }
  48.                         next = cur + ((cur / pow % 10 - 1 + 10) % 10) * pow - (cur / pow % 10 * pow);
  49.                         if (next >= 10000 || next < 0 || dead[next] == 1) {
  50.                         } else {
  51.                             temp.add(next);
  52.                         }
  53.                     }
  54.                 }
  55.             }
  56.             q1 = q2;
  57.             q2 = temp;
  58.             step++;
  59.         }
  60.         return -1;
  61.     }
  62. }

二分查找

难点：思路很简单，细节是魔鬼，mid +1 or -1，while <= or <

框架代码：

  1. class BinarySearch {
  2.     // 常规搜索方法
  3.     int binarySearch(int[] nums, int target) {
  4.         int left = 0, right = nums.length - 1;
  6.         while (left <= right) {
  7.             // 防止mid溢出，这样可以避免left + right整型溢出问题
  8.             int mid = left + (right - left) / 2;
  9.             if (nums[mid] == target) {
  10.                 return mid;
  11.             } else if (nums[mid] < target) {
  12.                 left = mid + 1;
  13.             } else if (nums[mid] > target) {
  14.                 right = mid - 1;
  15.             }
  16.         }
  17.         return -1;
  18.     }
  20.     // 左侧搜索方法
  21.     int leftBinarySearch(int[] nums, int target) {
  22.         int left = 0, right = nums.length;
  24.         while (left < right) {
  25.             int mid = (left + right) / 2;
  26.             if (nums[mid] == target) {
  27.                 right = mid;
  28.             } else if (nums[mid] < target) {
  29.                 left = mid + 1;
  30.             } else if (nums[mid] > target) {
  31.                 right = mid;
  32.             }
  33.         }
  35.         if (left == nums.length) {
  36.             return -1;
  37.         }
  39.         return nums[left] == target ? left : -1;
  40.     }
  42.     // 【闭区间】左侧搜索方法
  43.     int leftBoundBinarySearch(int[] nums, int target) {
  44.         int left = 0, right = nums.length - 1;
  46.         while (left <= right) {
  47.             int mid = left + (right - left) / 2;
  48.             if (nums[mid] == target) {
  49.                 right = mid - 1;
  50.             } else if (nums[mid] < target) {
  51.                 left = mid + 1;
  52.             } else if (nums[mid] > target) {
  53.                 right = mid - 1;
  54.             }
  55.         }
  57.         if (left >= nums.length - 1 || nums[left] != target) {
  58.             return -1;
  59.         }
  60.         return nums[left];
  61.     }
  63.     // 右侧搜索方法
  64.     int rightBinarySearch(int[] nums, int target) {
  65.         int left = 0, right = nums.length;
  67.         while (left < right) {
  68.             int mid = (left + right) / 2;
  69.             if (nums[mid] == target) {
  70.                 left = mid;
  71.             } else if (nums[mid] < target) {
  72.                 right = mid;
  73.             } else if (nums[mid] > target) {
  74.                 left = mid + 1;
  75.             }
  76.         }
  78.         if (left >= nums.length) {
  79.             return -1;
  80.         }
  81.         return nums[left] == target ? left : -1;
  82.     }
  84.     // 【闭区间】右侧搜索方法
  85.     int rightBoundBinarySearch(int[] nums, int target) {
  86.         int left = 0, right = nums.length - 1;
  88.         while (left <= right) {
  89.             int mid = left + (right - left) / 2;
  90.             if (nums[mid] == target) {
  91.                 left = mid + 1;
  92.             } else if (nums[mid] < target) {
  93.                 right = mid - 1;
  94.             } else if (nums[mid] > target) {
  95.                 left = mid + 1;
  96.             }
  97.         }
  99.         if (right < 0) {
  100.             return -1;
  101.         }
  102.         return nums[right] == target ? right : -1;
  103.     }
  104. }

滑动窗口

【例：76 Minimum Window Substring】
入门篇 - 图3

算法思路：

  1. 在字符串S中使用双指针中左右指针技巧，初始化left = right = 0, 把索引左闭右开区间称作一个窗口[left, right)
  2. 不断增加right指针扩大窗口，直到窗口中字符串符合要求
  3. 停止增加right，转而增加left指针缩小窗口，直到不再符合要求
  4. 重复2、3，直到right到达S尽头。

简言之，第2步找到可行解，第3步优化可行解，最终找到最优解。

  1. class Solution {
  2.     String minWindow(String s, String t) {
  3.         if (t == null || "".equals(t)) {
  4.             return t;
  5.         }
  6.         Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
  7.         char[] tc = t.toCharArray();
  8.         char[] sc = s.toCharArray();
  9.         for (char c : tc) {
  10.             need.put(c, need.getOrDefault(c, 0) + 1);
  11.         }
  13.         int left = 0, right = 0, valid = 0;
  14.         // 记录最小覆盖字串起始
  15.         int start = 0, len = Integer.MAX_VALUE;
  17.         while (right < sc.length) {
  18. //            移入窗口的字符串
  19.             char c = sc[right];
  20. //            窗口右移
  21.             right++;
  22. //            进行窗口内数据的一系列更新
  23.             if (need.containsKey(c)) {
  24.                 window.put(c, window.getOrDefault(c, 0) + 1);
  25.                 if (window.get(c).equals(need.get(c))) {
  26.                     valid++;
  27.                 }
  28.             }
  29. //            判断左侧窗口是否收缩
  30.             while (valid == need.size()) {
  31. //                更新最小覆盖子串
  32.                 if (right - left < len) {
  33.                     start = left;
  34.                     len = right - left;
  35.                 }
  36. //                d是将被一处窗口的字符
  37.                 char d = sc[left];
  38. //                窗口左移
  39.                 left++;
  40. //                进行窗口内数据的一系列更新
  41.                 if (need.containsKey(d)) {
  42.                     if (window.get(d).equals(need.get(d))) {
  43.                         valid--;
  44.                     }
  45.                     window.put(d, window.getOrDefault(d, 0) - 1);
  46.                 }
  47.             }
  48.         }
  49. //        返回最小覆盖字串
  50.         return len == Integer.MAX_VALUE ? "" : s.substring(start, len);
  51.     }
  52. }

股票买卖问题-状态机

这一节中介绍了很多leetcode上股票买卖相关的问题，抽象来看，都是状态机的问题，找出总共有哪些状态，然后列举出每种状态的选择，就可以 抽象代码为：

  1. for 状态1 in 状态1的所有取值：
  2.     for 状态2 in 状态2的所有取值：
  3.         for ...
  4.             dp[状态1][状态2][...] = 择优(选择1， 选择2...)

以股票问题为例，每天面对三种选择：买入buy、卖出sell、无操作rest，注意，并不是每天都可以进行上述三种操作，sell必须再buy后，buy必须再sell后，rest也分为buy后rest和sell后rest。
同时，还有交易次数限制k次，即买入必须在k>0的情况下操作。 换入对应的问题，列举该问题的状态：天数i、交易次数k、当前持有状态，则选择三维数组存放状态。

  1. dp[i][k][0 or 1]
  2. // n为总天数，K为最大允许交易次数
  3. 0 <= i <= n - 1, 1 <= k <= K
  4. 此问题总共有n X K X 2中状态，则穷举即可。
  5. for 0 <= i < n:
  6.     for 1 <= k <= K:
  7.         for s in {0, 1}:
  8.             dp[i][k][s] = max(buy, sell, rest)

可见，最终求解答案为dp[n - 1][K][0]，即最后一天允许K次操作，最终卖出股票获得利润。 列举完了所有状态，来考虑状态转移框架。
如果我当前卖出，则下次操作无法卖出，买入后则状态变为买入，资金减去今天买入金额，无操作则保持为卖出状态。 如果我当前买入，则下次操作无法买入，卖出后则状态变为卖出，资金加上今天卖出金额，无操作则保持为买入状态。

  1. dp[i][k][0] = max(dp[i - 1][k][1] + price[i], dp[i - 1][k][0])
  2.             = max(买入, 休息)
  3. dp[i][k][1] = max(dp[i - 1][k + 1][0] - price[i], dp[i - 1][k][0])
  4.             = max(卖出, 休息)

注意，上面的K次操作包含了买入+卖出为一次，故只需要在一种操作时增加次数即可。 在得到上面的状态转移方程后，只需要再定义出base case就可以，即最简单的问题。

i = -1 即还没有开始，最初始的状态，此时利润为0，没有持有股票，故不可能卖出。 dp[-1][k][0] = 0 dp[-1][k][1] = -infinity k = 0
即还没有开始操作，此时利润为0，没有持有股票，故不可能卖出。 dp[i][0][0] = 0 dp[i][0][1] = -infinity

优化思路：

  1. dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
  2. dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
  3.             = max(dp[i-1][1][1], -prices[i])
  4. 解释： k = 0 的 base case， 所以 dp[i-1][0][0] = 0。
  6. 可以看到，这里的k仅存在一种状态，都是 1， 不会改变， 即 k 对状态转移已经没有影响了。
  7. 可以进⾏进⼀步化简去掉所有 k：
  9. dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
  10. dp[i][1] = max(dp[i-1][1], -prices[i])

题解如下：

  1. class Solutions {
  3.     /**
  4.      * 第一题， K = 1
  5.      * @return
  6.      */
  7.     int getMoney1() {
  8.         int[][] dp = new int[n][2];
  9.         int[] price = new int[n];
  10.         for (int i = 0; i < n; ++i) {
  11.             if (i - 1 == -1) {
  12.                 dp[i][0] = 0;
  13.                 dp[i][1] = -price[i];
  14.                 continue;
  15.             }
  16.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + price[i]);
  17.             dp[i][1] = Math.max(-price[i], dp[i - 1][1]);
  18.         }
  19.         return dp[n - 1][0];
  20.     }
  22.     int getMoney1youhua() {
  23. //        int[][] dp = new int[n][2];
  24.         // 因为该题目中状态仅仅与前一次状态有关，而不需要完整过程，故而可以降低空间复杂度到O(1)
  25.         int dp_i_0 = 0, dp_i_1 = -price[0];
  26.         int[] price = new int[n];
  27.         for (int i = 0; i < n; ++i) {
  28. //            if (i - 1 == -1) {
  29. //                dp[i][0] = 0;
  30. //                dp[i][1] = -price[i];
  31. //                continue;
  32. //            }
  33.             dp_i_0 = Math.max(dp_i_0, dp_i_1 + price[i]);
  34.             dp_i_1 = Math.max(-price[i], dp_i_1);
  36. //            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + price[i]);
  37. //            dp[i][1] = Math.max(-price[i], dp[i - 1][1]);
  38.         }
  39.         return dp_i_0;
  40.     }
  41. }

打家劫舍问题-经典动态规划问题

leetcode上有三道打家劫舍问题，层层递进，属于非常经典的动态规划问题。

入门篇 - 图4

入门篇 - 图5

入门篇 - 图6

前文有讲过，动态规划的过程就是找[状态]和[选择]，从第一题入手分析，盗贼从左向右走过房屋，每间房子都可以选择抢or不抢，如果抢了该间则不能抢下一间，不抢该间则可以抢下一间，走过最后一间则没有抢了。

那么第i间房屋就是状态，抢与不抢就是选择。 下面是代码实现与优化：

  1. class Solution {
  3.     /**
  4.      * 第一种解法，最简单的形式，直接dp求解
  5.      * @return
  6.      */
  7.     public int rob(int[] nums) {
  8.         return dp(nums, 0);
  9.     }
  11.     public int dp(int[] nums, int start) {
  12.         if (start >= nums.length) {
  13.             return 0;
  14.         }
  15.         return Math.max(nums[start] + dp(nums, start + 2), dp(nums, start + 1));
  16.     }
  18.     /**
  19.      * 第二种解法，带备忘录的动态规划递归解法，效率明显提升
  20.      * @param nums
  21.      * @return
  22.      */
  23.     public int rob(int[] nums) {
  24.         int[] memo = new int[nums.length];
  25.         return dp(memo, nums, 0);
  26.     }
  28.     public int dp(int[] memo, int[] nums, int start) {
  29.         if (start >= nums.length) {
  30.             return 0;
  31.         }
  32.         if (memo[start] != 0) {
  33.             return memo[start];
  34.         }
  35.         memo[start] = Math.max(dp(memo, nums, start + 2) + nums[start], dp(memo, nums, start + 1));
  36.         return memo[start];
  37.     }
  39.     /**
  40.      * 第三种解法，非递归，自底向上的解法
  41.      * @param nums
  42.      * @return
  43.      */
  44.     public int rob(int[] nums) {
  45.         int[] result = new int[nums.length + 2];
  46.         for (int i = nums.length - 1; i >= 0; i--) {
  47.             result[i] = Math.max(result[i + 1], result[i + 2] + nums[i]);
  48.         }
  49.         return result[0];
  50.     }
  52.     /**
  53.      * 第四种解法，非递归，自底向上的解法
  54.      * 较上一种解法在空间上更优，最后只需要result[0]，只与前两个状态相关，而与其他无关
  55.      * @param nums
  56.      * @return
  57.      */
  58.     public int rob(int[] nums) {
  59.         int result_i_1 = 0, result_i_2 = 0;
  60.         for (int i = nums.length - 1; i >= 0; i--) {
  61.             int temp_result = Math.max(result_i_1, result_i_2 + nums[i]);
  62.             result_i_2 = result_i_1;
  63.             result_i_1 = temp_result;
  64.         }
  65.         return result_i_1;
  66.     }
  68.     /**
  69.      * 题目二的求解，实质上就是题目一的分治，通过情况划分，找到两个局部最优再得到最终最优解
  70.      * 这个题目的解法让我想起来之前做30题的时候，我苦于不知道如何对aa这种词做拆分，实际上，如果也能理解成这种局部最优，就可以理解按照词长取余即可
  71.      * @param nums
  72.      * @return
  73.      */
  74.     public int robII(int[] nums) {
  75.         if (nums.length == 1) {
  76.             return nums[0];
  77.         }
  78.         return Math.max(rob3(Arrays.copyOfRange(nums, 0, nums.length - 1)), rob3(Arrays.copyOfRange(nums, 1, nums.length)));
  79.     }
  81.     /**
  82.      * 题目三的求解，这道题在我本身递归二叉树的解法上增加了数组保存两种结果，不需要重复计算相同递归结果，也没有引入数据结构复杂的备忘录，称得上是一道好解法，需要留意噢
  83.      * 本质上可能还是接近通过仅保留最近的两种状态即可，无需记录完整历史
  84.      * @param root
  85.      * @return
  86.      */
  87.     public int robIII2(TreeNode root) {
  88.         int[] res = dp1(root);
  89.         return Math.max(res[0], res[1]);
  90.     }
  92.     public int[] dp1(TreeNode root) {
  93.         if (root == null) {
  94.             // {不抢, 抢}
  95.             return new int[]{0, 0};
  96.         }
  97.         int[] left = dp1(root.left);
  98.         int[] right = dp1(root.right);
  99.         // 注意这里是这家不抢，下家可以抢也可以不抢，取决于价值大小
  100.         int res0 = Math.max(left[1], left[0]) + Math.max(right[0], right[1]);
  101.         int res1 = root.val + left[0] + right[0];
  102.         return new int[]{res0, res1};
  103.     }
  104. }

N数之和

N数之和的题目，通常是给定一个数组，要求使用其中n个数组，凑出和是给定target的组合。
当题目给定的N是2时，通常第一想法是先对数组排序，通过双指针拿到符合两数之和为target的组合。
再次基础上，可以将题目泛化成nums中有多对元素之和等于target，请返回所有不重复的元素对。

class Solutions {
    public List<int[]> twoSumTarget(int[] nums, int target) {
      Arrays.sort(nums);
      List<int[]> result = new ArrayList<>();
      int lo = 0, hi = nums.length - 1;
      while (lo < hi) {
          int sum = nums[lo] + nums[hi];
          // 记录索引 lo 和 hi 最初对应的值
          int left = nums[lo], right = nums[hi];
          if (sum < target) {
              while (lo < hi && nums[lo] == left) {
                  lo++;
              }
          } else if (sum > target) {
              while (lo < hi && nums[hi] == right) {
                  hi--;
              }
          } else {
              result.add(new int[]{left, right});
              // 跳过所有重复的元素
              while (lo < hi && nums[lo] == left) {
                  lo++;
              }
              while (lo < hi && nums[hi] == right) {
                  hi--;
              }
          }
      }
      return result;
    }

    /**
     * 通刷nSum
     * @param nums
     * @param target
     * @param n
     * @param index
     * @param res
     */
    public void nSumTarget(int[] nums, int target, int n, int index, List<Integer> res) {
        if (n <= 2) {
            int lo = index + 1, hi = nums.length - 1;
            while (lo < hi) {
                // 记录索引 lo 和 hi 最初对应的值
                int left = nums[lo], right = nums[hi];
                int sum = target - (left + right);
                if (sum > 0) {
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                } else if (sum < 0) {
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                } else {
                    res.add(nums[lo]);
                    res.add(nums[hi]);
                    nSumResults.add(new ArrayList<>(res));
                    // 跳过所有重复的元素
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                    res.remove(res.size() - 1);
                    res.remove(res.size() - 1);
                }
            }
        } else {
            for (int i = index + 1; i < nums.length;) {
                int current = nums[i];
                res.add(current);
                nSumTarget(nums, target - current, n - 1, i, res);
                while (i < nums.length && nums[i] == current) {
                    i++;
                }
                res.remove(res.size() - 1);
            }
        }
    }
}