冲刺大厂每日算法&面试题，动态规划21天——第十三天 导读

发表于

「这是我参与11月更文挑战的第11天，活动详情查看：2021最后一次更文挑战」

导读

在这里插入图片描述

肥友们为了更好的去帮助新同学适应算法和面试题，最近我们开始进行专项突击一步一步来。我们先来搞一下让大家最头疼的一类算法题，动态规划我们将进行为时21天的养成计划。还在等什么快来一起肥学进行动态规划21天挑战吧！！

21天动态规划入门

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径
可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置
(row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1,
col + 1) 。

1
2
3
4
5
6
7
8
java复制代码示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]
1
2
3
4
5
6
7
java复制代码示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
 [-40,-5]]
1
2
3
4
java复制代码示例 3：

输入：matrix = [[-48]]
输出：-48
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
java复制代码分析

我们用 dp(r, c) 表示从位置为 (r, c) 的元素开始的下降路径最小和。根据题目的要求，位置 (r, c) 可以下降到 (r + 1, c - 1)，(r + 1, c) 和 (r + 1, c + 1) 三个位置（先不考虑超出数组边界的情况），因此状态转移方程为：

dp(r, c) = A[r][c] + min{dp(r + 1, c - 1), dp(r + 1, c), dp(r + 1, c + 1)}

由于下降路径可以从第一行中的任何元素开始，因此最终的答案为 \min\limits_c \mathrm{dp}(0, c) 
c
min
​
 dp(0,c)。



class Solution {
    public int minFallingPathSum(int[][] A) {
        int N = A.length;
        for (int r = N-2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                int best = A[r+1][c];
                if (c > 0)
                    best = Math.min(best, A[r+1][c-1]);
                if (c+1 < N)
                    best = Math.min(best, A[r+1][c+1]);
                A[r][c] += best;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int x: A[0])
            ans = Math.min(ans, x);
        return ans;
    }
}

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1
的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

1
2
3
4
5
6
7
8
9
10
java复制代码示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
1
2
3
4
java复制代码示例 2：

输入：triangle = [[-10]]
输出：-10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }
}

面试题

哈希 类

请说⼀说，Java中的HashMap的⼯作原理是什么？ 参考回答：
HashMap类有⼀个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。 每当往
hashmap⾥⾯存放key-value对的时候，都会为它们实例化⼀个Entry对象，这个Entry对象就
会存储在前⾯提到的Entry数组table中。Entry具体存在table的那个位置是 根据key的
hashcode()⽅法计算出来的hash值（来决定）。

讲⼀讲，如何构造⼀致性哈希算法。 参考回答： 先构造⼀个⻓度为232的整数环（这个环被称为⼀致性Hash环），根据节点名称的Hash值
（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到 其Hash值（其分布也为[0,
232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值 最近的服务器节点，完成Key到服务器的映射查找。
这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下 尽量有多的请求命中原来路由到的服务器。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%