1.Algorithm:https://leetcode-cn.com/problems/triangle/
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
参考代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static java.lang.Math.min;
//leetcode 120
public class Triangle {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
return helper(triangle, 0, 0, res);
}
private int helper(List<List<Integer>> triangle, int i, int j, int min) {
int res = 0;
if (triangle.size() == i) {
return res < min ? res : min;
}
return min(triangle.get(i).get(j) + helper(triangle, i + 1, j, min),
triangle.get(i).get(j) + helper(triangle, i + 1, j + 1, min));
}
public int minimumTotaldp(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int level = triangle.size();
int[][] min = new int[level][triangle.get(level-1).size()];
for (int j = 0; j < triangle.get(level-1).size(); j++){
min[level-1][j] = triangle.get(level-1).get(j);
}
for (int i = level - 2; i >= 0; i--) {
for(int j = 0; j < triangle.get(i).size();j++) {
min[i][j] = min(min[i+1][j],min[i+1][j+1]) + triangle.get(i).get(j);
}
}
return min[0][0];
}
public static int minimumTotalwithMem(List<List<Integer>> triangle) {
int level = triangle.size();
List<List<Integer>> memory = new ArrayList<>();
memory.add(new ArrayList<>());
return helper1(triangle, 0, 0, level, memory);
}
// 参数i表示当前层，level表示共有多少层
public static int helper1(List<List<Integer>> triangle, int i, int j, int level, List<List<Integer>> memory) {
if (i >= level || j >= triangle.get(i).size())
return 0;
// 到了最后一层，就将结果全部放入
if (i == level - 1 && memory.get(i).isEmpty()) {
for (int k = 0; k < triangle.get(i).size(); k++)
memory.get(i).add(triangle.get(i).get(k));
}
if (!memory.get(i).isEmpty() && j < memory.get(i).size() && memory.get(i).get(j) != null)
return memory.get(i).get(j);
if (memory.size() < level) // 防止添加回溯的过程又添加
memory.add(new ArrayList<>());
int left = helper1(triangle, i + 1, j, level, memory);
int right = helper1(triangle, i + 1, j + 1, level, memory);
memory.get(i).add(Math.min(left, right) + triangle.get(i).get(j));
return memory.get(i).get(j);
}
public static void main(String[] args) {
List<List<Integer>> list = Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3));
//int res = Triangle.minimumTotalwithMem(list);
int res = new Triangle().minimumTotaldp(list);
System.out.println("res 1111111111===>" + res);
}
}
2.Review：https://shipilev.net/jvm/anatomy-quarks/11-moving-gc-locality/
Moving GC and Locality 移动GC与局部性
主要讨论内存碎片移动压缩相关问题。
标记-压缩回收器可以保持堆中对象的分配顺序，也可以对其任意重排。虽然任意顺序能够比其他标记-压缩回收器速度更快，也不会带来空间开销，但是会破坏 Mutator（应用线程）的局部性。
CMS 运行良好其中一个原因，在把特定对象提交到“老年代”之前，对“年轻代”对象集合进行压缩而不是直接放入“老年代”。像 Serial 和 Parallel 这样的 STW 回收器都能从中受益。像 G1 和 Shenandoah 这样的区域化回收器可以而且也应该利用这个优势，尽管由于堆遍历与清空操作是分离需要更多的工作。声称局部性没有用是很武断的。在 NUMA 架构下，局部性带来的性能惩罚会飙升，把整体性能彻底搞砸。
翻译，参考
https://www.javazhiyin.com/41775.html
3.Tip：https://mp.weixin.qq.com/s/TnVL1chwTqlXmlOdcuJCSg
springboot中启动tomcat的过程，源码分析，还包括了一些tomcat的结构描述，对于了解springboot和tomcat都有帮助
4.share: