第46周 ARTS 2019 09 01

Algorithm：75. 颜色分类
Review： Synchronization and Object Locking
Tip/Tech：快排的非递归实现
Share：爱尔兰青少年因从海洋中去除微塑料而获得谷歌科学奖

Algorithm

174. 地下城游戏

https://leetcode-cn.com/problems/dungeon-game/

其实这题一看就晓得要用动态规划了，但是动态规划最难就是想出最优子结构，一旦有了最优子结构一切都好办，但是如果你硬想，那么估计如何都想不出来的。
那么一切都要从暴力法开始。
动态规划问题都可以被转化为回溯问题来解决，也可以称之为暴力法但是毫无疑问会时间超时，但是这不影响我们把它作为突破口，因为回溯只要你能够理解题意，写出正确的递归条件和跳出条件，那么一切都好解决了。

回溯（暴力）

首先我们假设问题只有四个格子。

全是负的对吧，那么这个要算出最小耗费的生命值就简单了。
先定义一下，最小耗费的生命值表示骑士救完公主刚刚好死了所需要用的生命值。
走 -1, -4, -3这个路线的，骑士最小耗费生命值就是 8，走 -1, -5, -3这个路线的，骑士最小耗费生命值就是 9，所以骑士最小耗费生命值就是 8。
那么我们因为-1 只能去-5或者-3，最后一个都是一样的-3,那么也就是说：如果我们要得到起始点的最小的耗费的生命值：

就是从其实起始点的右边和起始点的下边，两者之中选择一个耗费生命较小的，然后扣除我们这个格子的要耗费的生命值，也就是起始点最小耗费的生命值了。

当然了，要确保骑士活着，要在最小耗费生命值之上加上1，才是骑士的最低血量。

那么我们假设一个函数$f(i,j)$，这函数可以算出骑士需要耗费的最小的生命值，i和j分别是坐标；
那么起始点的公式要咋个表达？因为格子中的数字是负的，所以我们可以直接进行相加即可。
$f(0,0)+dungeon[0][0]=min(f(0+1,0),f(0,0+1))$
==> $f(0,0)+dungeon[0][0]=min(f(1,0),f(0,1))$
吧i和j带入一下子，就可以得到我们的一个递归的条件了：

$f(i,j)+dungeon[i][j]=min(f(i+1,j),f(i,j+1))$

有了这个还不够，你需要知道退出条件，因为上面的四个格子足够简单，那么我们继续举例：

$f(1,0)+dungeon[1][0]=f(1,1)$
$f(0,1)+dungeon[0][1]=f(1,1)$

dungeon[1][0]是已经确定了的，那么f(1, 1)是多少呢？
我们知道最后一个格子是-3，那么最小耗费的生命值就是3了, f(1, 1) = 3，其实这个就是退出条件了。当我们到了最后一个格子的时候，就是代表着我们已经到了终点了，就可以退出了，
so …
$f(1,0)=f(1,1)?dungeon[1][0]=7$
$f(0,1)=f(1,1)?dungeon[0][1]=8$
$f(0,0)=min(f(1,0),f(0,1))?dungeon[0][0]=8$
所以起始点的最小耗费生命值为8。

其实问题到了这里已经解决一大半了额，因为如果每个格子只有扣血的设定，没有加血的设定，基本上已经够了，但是题目中每个格子即可以扣血，也可以加血，那么这样就导致答案要复杂一些了。我们再举个例子：

这里依然是四个格子，但是，（1, 0）是4，也就说，如果用上面的公式带入：
$f(1,0)=f(1,1)?dungeon[1][0]=?1$，也就是会耗费生命值为负值的情况，但是如果骑士的最低的耗费的生命值为负的，那肯定不符合定义的，因为如果是负的，骑士就死了，所以最低的都要为0。其实也很好理解，如果魔法值给你加血了4，而且最后的一个格子为耗血量为3，就表示，骑士只要活着进入这4的这个格子，他肯定可以进入到达最后一个格子的，那么其实最低消耗的生命为0。
那么如果最后一个格子的是给你加血不是扣血呢？那么最后一个格子的退出条件会不会改变呢？比如下图：

这样一来，最后一个格子的退出条件就就变了0,也就说是只要骑士进入最后一个格子里面只要活着就可以，所以最低的耗血量为0；

可以来看看回溯思想的代码：

public int calculateMinimumHP(int[][] dungeon) {
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
    return 0;}int rowLen = dungeon.length;int colLen = dungeon[0].length;// 最低的耗血量为 + 1；就是骑士的救公主的最低血量。return dfs(0, 0, rowLen, colLen, dungeon) + 1;
}public int dfs (int rowIndex, int colIndex, int rowSize, int colSize, int[][] dungeon) {
    //if (rowIndex >= rowSize || colIndex >= colSize) {
    return Integer.MAX_VALUE;}// 退出条件if (rowIndex == rowSize - 1 && colIndex == colSize - 1) {
    if (dungeon[rowIndex][colIndex] >= 0) {
    // 如果最后一个大于等于0，就返还0。return 0;} else {
    //如果最后一个小于零，就返回负的值。return -dungeon[rowIndex][colIndex];}}int rightMin = dfs(rowIndex, colIndex + 1, rowSize, colSize, dungeon);int downMin = dfs(rowIndex + 1, colIndex, rowSize, colSize, dungeon);// f(i,j) = min(f(i+1, j), f(i, j+1))+dungeon[i][j]int needMin = Math.min(rightMin, downMin) - dungeon[rowIndex][colIndex];int res = 0;if (needMin < 0) {
    res =  0;} else {
    res = needMin;}System.out.println(rowIndex+ " "+colIndex + " "  + res);return res;
}

以上的代码在是正确了，但是有个问题，时间会超时的，所以，我们需要优化。

递归优化：记忆化搜索

我在上个程序里面放了个输出函数，如果想要懂得这个输出干啥子用的，就要放到题目中执行一下，你就明白作用了。
执行一下就会发现一个下面这个截图：

完全的输出就是：

1 2 4
0 2 1
1 2 4 （重复）
2 1 0 
1 1 10 
0 1 4 
1 2 4 （重复）
2 1 0 （重复）
1 1 10 （重复）
2 1 0 （重复）
2 0 0
1 0 5
0 0 6

根据上面的输出，我们发现，这个递归函数经历了很多次重复计算，所以我们可以通过吧这个结果记录下来，直接采用，这样就不会有重复计算了。（其实到了这一步，我们已经离最优解，动态规划解题很近了）。
我们构造一个memory数组，用来存放已经计算过的结果。每次递归函数进入，我们就确认一下，是否已经计算过了，如果计算过了，就直接返回结果。

private int rowSize = 0;
private int colSize = 0;
private int[][] globalDun = null;
public int calculateMinimumHP(int[][] dungeon) {
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
    return 0;}rowSize = dungeon.length;colSize = dungeon[0].length;globalDun = dungeon;int[][] memory = new int[rowSize][colSize];// 初始化为-1，便于区别是否计算过结果了。for (int i = 0; i < rowSize; ++i) {
    for (int j = 0; j < colSize; ++j) {
    memory[i][j] = -1;}}return dfs(0, 0, memory) + 1;
}public int dfs (int rowIndex, int colIndex,  int[][] memory) {
    if (rowIndex >= rowSize || colIndex  >=  colSize) {
    return Integer.MAX_VALUE;}// 不为-1就是计算过了，直接返回结果。if (memory[rowIndex][colIndex] != -1) {
    return memory[rowIndex][colIndex];}if (rowIndex == rowSize - 1 && colIndex == colSize - 1) {
    if (globalDun[rowIndex][colIndex] >= 0) {
    return 0;} else {
    return -globalDun[rowIndex][colIndex];}}int right = dfs(rowIndex, colIndex + 1, memory);int down = dfs(rowIndex + 1, colIndex, memory);int needMin = Math.min(right, down) - globalDun[rowIndex][colIndex];int res = 0;if (needMin < 0) {
    res =  0;} else {
    res =  needMin;}memory[rowIndex][colIndex] = res;System.out.println(rowIndex+ " "+colIndex + " "  + res);return res;
}

以上的代码可以通过的。

动态规划

如果你能看到这里，相信你已经有点感觉了，其实记忆化搜索的那个memory已经就是动态规划的思想了，这次我们的动态规划是从最后一个开始走的，每走一步，出来就记录一下，然后不断复用。
其实核心的公式我们已经知道了，也就是最优子结构：

needMin + globalDun[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1])
其实这段代码：

if (needMin < 0) {
    res =  0;
} else {
    res =  needMin;
}

可以等价于下面这段：
dp[i][j] = Math.max(0, needMin);
所以我们可以来看下这个代码：

public int calculateMinimumHPBest(int[][] dungeon) {
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
    return 0;}int rowSize = dungeon.length;int colSize = dungeon[0].length;int[][] dp = new int[rowSize][colSize];// 设置最后一个值。dp[rowSize - 1][colSize -1] = Math.max(0, -dungeon[rowSize - 1][colSize - 1]);// 设置最后一列的值for (int i = rowSize - 2; i >= 0; --i) {
    int needMin = dp[i + 1][colSize - 1] - dungeon[i][colSize - 1];dp[i][colSize -1] = Math.max(0, needMin);}// 设置最后一行的值for (int i = colSize - 2; i >= 0; --i) {
    int needMin = dp[rowSize - 1][i + 1] - dungeon[rowSize - 1][i];dp[rowSize - 1][i] = Math.max(0, needMin);}for (int i = rowSize - 2; i >= 0; --i) {
    for (int j = colSize - 2; j >= 0; --j) {
    // 从右边和下边选择一个最小值，然后减去当前的 dungeon 值int needMin = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = Math.max(0, needMin);}}return dp[0][0] + 1;
}

时间复杂度$O(N)$,空间复杂度$O(N)$。

Review

Math in Data Science

https://www.dataquest.io/blog/math-in-data-science/

• 数据科学中的数学基础
• 朴素贝叶斯
• 线性回归
• Logistic回归
• 神经网络
• K-Means聚类

如果有看到概率论，统计学和线性代数的书籍，我强烈建议您选择深入涵盖这些主题的书籍，以真正了解所涵盖的机器算法幕后发生的事情

Tip/Tech

Java 跳表实现

import java.util.Random;public class SkipList {
    private static final int MAX_LEVEL = 16;private int levelCount = 1;private Node head = new Node();  // 带头链表private Random r = new Random();public Node find(int value) {
    Node p = head;for (int i = levelCount - 1; i >= 0; --i) {
    while (p.forwards[i] != null && p.forwards[i].data < value) {
    p = p.forwards[i];}}if (p.forwards[0] != null && p.forwards[0].data == value) {
    return p.forwards[0];} else {
    return null;}}public void insert(int value) {
    int level = randomLevel();Node newNode = new Node();newNode.data = value;newNode.maxLevel = level;Node update[] = new Node[level];for (int i = 0; i < level; ++i) {
    update[i] = head;}// record every level largest value which smaller than insert value in update[]Node p = head;for (int i = level - 1; i >= 0; --i) {
    while (p.forwards[i] != null && p.forwards[i].data < value) {
    p = p.forwards[i];}update[i] = p;// use update save node in search path}// in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) {
    newNode.forwards[i] = update[i].forwards[i];update[i].forwards[i] = newNode;}// update node hightif (levelCount < level) levelCount = level;}public void delete(int value) {
    Node[] update = new Node[levelCount];Node p = head;for (int i = levelCount - 1; i >= 0; --i) {
    while (p.forwards[i] != null && p.forwards[i].data < value) {
    p = p.forwards[i];}update[i] = p;}if (p.forwards[0] != null && p.forwards[0].data == value) {
    for (int i = levelCount - 1; i >= 0; --i) {
    if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
    update[i].forwards[i] = update[i].forwards[i].forwards[i];}}}while (levelCount>1&&head.forwards[levelCount]==null){
    levelCount--;}}// 随机 level 次，如果是奇数层数 +1，防止伪随机private int randomLevel() {
    int level = 1;for (int i = 1; i < MAX_LEVEL; ++i) {
    if (r.nextInt() % 2 == 1) {
    level++;}}return level;}public void printAll() {
    Node p = head;while (p.forwards[0] != null) {
    System.out.print(p.forwards[0] + " ");p = p.forwards[0];}System.out.println();}public class Node {
    private int data = -1;private Node forwards[] = new Node[MAX_LEVEL];private int maxLevel = 0;@Overridepublic String toString() {
    StringBuilder builder = new StringBuilder();builder.append("{ data: ");builder.append(data);builder.append("; levels: ");builder.append(maxLevel);builder.append(" }");return builder.toString();}}}

Share

也许5G时代会让教育受益良多

我们都在进入一种很快网速的时代，但是优秀的教育资源依然是很稀缺的，现在很多高素质的教师已经开始在互联网上发布教学视频来改善这一现象，很快，相信只有有联网的同学就有机会接触到这些。
但是网上学习主要有几个问题：
（1）注意力的问题：在网上学习，注意力很容易被别的内容吸引走，这样往往达不到学习的目的，容易学着学着就去看别的视频去了，
（2）效果问题：看视频虽然可以学习知识，但是如果有疑问不能直接发问，只能通过留言互动。
（3）资源优劣的问题：老师有好也有坏，网络上的资源更是如此，区分好的资源和坏的资源需要花大把的时间。
以上的 问题可以被未来5G+VA+VR的技术得到良好的解决。
首先是增强现实，和虚拟现实带来的沉浸式学习，会帮助学生集中注意力，
学生和教师之间的互动也会随着网速的加快而更加方便
让专业的优秀的老师来授课肯定效果会非常的不一样的。
毕竟北京四中的老师和三流中学的老师肯定不是一个档次的。