1.Algorithm:https://leetcode-cn.com/problems/triangle/

120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
[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: