Goolloo

## Java Double Iterations ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val...

@yzw-Joey 之前的案例是在`stack.push(object)` 的时候加入visited里，所以任何**已经访问过**和**即将被访问**的元素都在里面。 Double BFS的代码里是在`stack.pop(object)`的时候才加入visited里，只有**已经访问过**的元素在里面。而q1和q2里面的元素都属于**即将被访问**。 这两个加入visited的不同时机并不影响结果，算是博主代码风格的不统一吧。

@YANLING-H 对于面试没区别，工业上会有应用。`.add()`来自`Collection`，而offer来自`Queue`。 [.add()](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html#add(E)) > Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an...

@MengyuanL `dp_i_1`用来存储买入的情况下的现金额。如果初次买入必然是负的买入价，即`-price[i]`。结合状态转移方程中使用`Math.max()`来传递最大利润，base case必须保证初始值必须总是小于任何的`-price[i]`。不然“贷款”买入股票的行为就不能在方程中转移。

Java Compressed DP "Table" ```java class Solution { public int minFallingPathSum(int[][] matrix) { int height = matrix.length; int width = matrix[0].length; int[] sums = new int[width]; int[] previousSums = new...

@doubleSkinMilk @southrivers 首先有几个算法里的前置条件 1. 每一次移动都会导致路径的权重增加，即路径权重大于等于0 1. 每次在PriorityQueue里取出的node(i)是已经到达的点，而不是即将到达 1. 每次在PriorityQueue里取出的node(i)，不管这个node(i)是不是离目标地最近，至少是**从起点到node**的路线里最短的 1. 接着上一点，相比于node(i), 在PriorityQueue里面的node(j), node(k)等等，他们到达各自当前的点的距离必然是**大于等于**node(i)的权重 由此可以推断 - 根据(2)和(3)，当PriorityQueue里取出的node(destination)的时候，我们至少得到了一种到达终点的路径path(i)和这条路径的权重weight(i) - 根据(4)，目前得到的这个路径path(i)的权重weight(i)是**小于等于**PriorityQueue中其他还没到达终点的路径 - 根据(1)，其他的路径到达终点时因为还有走更多的路，所以必然**大于等于**他们当前的权重，除非其他的路径也正好到达了终点。所以，其他的备选路径的最终权重**大于等于**当前权重 - 结合前两点，路径path(i)到达终点的权重**小于等于**其他路径的最终权重 用公式表达 - 因为PriorityQueue对权重排序 - `weight(i)`

@JackShang94 在加入PirorityQueue的时候已经更新过了。类似的还有BFS模版里在加入Queue的时候同时加入visited。 ```java for(int[] nextNode : graph[curId]){ int nextId = nextNode[0]; int nextDistFromStart = distTo[curId] + nextNode[1]; if(nextDistFromStart < distTo[nextId]){ //****************************************************** distTo[nextId] = nextDistFromStart; //****************************************************** pq.offer(new State(nextId, nextDistFromStart)); } }...

提供一下直接计算组合数量的思路 ### Solution.1 从上一行的可能的来源，计算当前数值的组合树 `numConbinations[i][j] = numConbinations[i-1][j-num] + numConbinations[i-1][j+num]` ```java class Solution { public int findTargetSumWays(int[] nums, int target) { int numSize = nums.length; int sum = Arrays.stream(nums).sum(); if(target >...

### 3D table ```java class Solution { public boolean stoneGame(int[] piles) { int size = piles.length; int[][][] dp = new int[size][size][2]; for(int i = size-1; i >= 0; i--) {...

1. Complete BT必然从root开始，有一半是perfect BT(O(logN))，另一半可能也是perfect BT或者Complete BT 2. 如果是Complete BT，那么又回到上一层的逻辑——即一半子树是perfect BT，另一半是Complete BT 3. 那么最坏的情况下就是，**每一层**都是一半是perfect BT，另一半半complete BT。并且你需要继续去下一层去计算complete BT的那一半子树。 4. 那么最多需要计算几次这种一半子树呢？就是整个树的深度/高度——O(logN)。每次计算量是多少呢？O(logN)。所以总的计算量是O((logN)^2) 举例子算一下，如果6层树，最坏情况下 - 第一层，只有root - 第二层，一半是perfect BT，O(logN)，另一半需要在第三层分左右子树计算 - 第三层，一半是perfect BT，O(logN)，另一半需要在第四层分左右子树计算 - 第四层，一半是perfect BT，O(logN)，另一半需要在第五层分左右子树计算...