这一周的LeetCode每日一题都非常的难，我现在是时隔很长接近一个月的时间去看这些题目，重新进行整理，都花费非常大的功夫，才能重新明白其中的思路。
真正再写一遍很难能写得出来，但是重新过一遍思想也是让人头秃的，所以整理的时候发现那段时间好像没有做其他的事情，只跟算法杠上了。
特别是鸡蛋掉落问题，重新分析一遍之后，中间的一些思想还是非常奇妙的。
1. although
1.1. 每日一练习
1.1.1. 编辑距离
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-06 21:15
* <p>
* 72. 编辑距离
* 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
* <p>
* 你可以对一个单词进行如下三种操作：
* <p>
* 插入一个字符
* 删除一个字符
* 替换一个字符
* <p>
* <p>
* 示例 1：
* <p>
* 输入：word1 = "horse", word2 = "ros"
* 输出：3
* 解释：
* horse -> rorse (将 'h' 替换为 'r')
* rorse -> rose (删除 'r')
* rose -> ros (删除 'e')
* 示例 2：
* <p>
* 输入：word1 = "intention", word2 = "execution"
* 输出：5
* 解释：
* intention -> inention (删除 't')
* inention -> enention (将 'i' 替换为 'e')
* enention -> exention (将 'n' 替换为 'x')
* exention -> exection (将 'n' 替换为 'c')
* exection -> execution (插入 'u')
**/
典型的动态规划问题，动态规划题目，最关键是写出推导公式。
将word1每个字母作为纵坐标，Word2的每个字母作为横坐标。
可以画出一个表格出来。我们使用一个二维数组来表示dp[word1.len][word2.len]
动作：
- 删除一个字符
dp[i-1][j] - 插入一个字符
dp[i][j-1] - 替换一个字符
dp[i-1][j-1]
地推公式为：
dp[i][j] = min(dp[i-1][j],dp[i-1][j],dp[i-1][j-1])+1
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n1][n2];
}
1.1.2. 鸡蛋掉落
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-11 21:06
* <p>
* 887. 鸡蛋掉落
* 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
* <p>
* 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
* <p>
* 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
* <p>
* 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
* <p>
* 你的目标是确切地知道 F 的值是多少。
* <p>
* 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
* <p>
* <p>
* <p>
* 示例 1：
* <p>
* 输入：K = 1, N = 2
* 输出：2
* 解释：
* 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
* 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
* 如果它没碎，那么我们肯定知道 F = 2 。
* 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
* 示例 2：
* <p>
* 输入：K = 2, N = 6
* 输出：3
* 示例 3：
* <p>
* 输入：K = 3, N = 14
* 输出：4
* <p>
* <p>
* 提示：
* <p>
* 1 <= K <= 100
* 1 <= N <= 10000
**/
这个题目李永乐老师题解讲的挺清楚的。
主要思路：
i:表示楼层数j:表示鸡蛋的个数dp[i][j]：一共有i层楼且有j个鸡蛋的时找到临界楼层的最优步骤数。
如何求出dp[i][j]最优步骤？
- 问题又继续拆分，我们假设从
k (1<=k<=i)层楼扔鸡蛋。那么其扔完之后只有两个结果：- 鸡蛋碎
- 鸡蛋碎了，说明尝试的楼层高了那么必定是在
1~k-1之间 dp[k-1][j-1]
- 鸡蛋碎了，说明尝试的楼层高了那么必定是在
- 鸡蛋不碎
- 不碎，说明尝试的楼层低了那么必定在
k~i之间 dp[i-k][j]
- 不碎，说明尝试的楼层低了那么必定在
- 也就是说
dp[i][j]我从第k层开始扔，最优解是这两个结果当中的最大值+1 - 为什么要最大值？
- 因为那一楼鸡蛋会碎这个值我们不知道，所以需要拿出最坏的情况
- 比如只有1个鸡蛋时，有100层楼
- 我们只有一个办法就是一层一层扔
- 但是会碎的楼层我们不知道，可能是10层也可能是99层也可能是100层
- 最终我们需要一个确切的数字，于是需要取最大值100
- 因为那一楼鸡蛋会碎这个值我们不知道，所以需要拿出最坏的情况
- 为什么要+1？
- 因为本身
k层我扔完之后，才有的后面的推论所以需要加上本次步骤
- 因为本身
- 鸡蛋碎
- 最后将所有可能的
k的结果中取出最小值。为什么是取最小值？- 因为这个所有
k是可以计算出来的，我们可能通过计算来知道第一步从那一层开始扔，有最优解。
- 因为这个所有
主要还是用到动态规划的思想，递推公式：
public int superEggDrop(int K, int N) {
int[][] dp = new int[N + 1][K + 1];
// 由于求的是最小值，因此初始化的时候赋值为一个较大的数，9999 或者 i 都可以
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i], i);
}
// 初始化：填写下标为 0、1 的行和下标为 0、1 的列
// 第 0 行：楼层为 0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0
for (int j = 0; j <= K; j++) {
dp[0][j] = 0;
}
// 第 1 行：楼层为 1 的时候，0 个鸡蛋的时候，扔 0 次，1 个以及 1 个鸡蛋以上只需要扔 1 次
dp[1][0] = 0;
for (int j = 1; j <= K; j++) {
dp[1][j] = 1;
}
// 第 0 列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0
// 第 1 列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度（想想复杂度的定义）
for (int i = 0; i <= N; i++) {
dp[i][0] = 0;
dp[i][1] = i;
}
for (int i = 2; i <= N; i++) {
for (int j = 2; j <= K ; j++) {
for (int k = 1; k <= i; k++) {
dp[i][j] = Math.min(dp[i][j],Math.max(dp[k-1][j-1],dp[i-k][j])+1);
}
}
}
return dp[N][K];
}
上面这个方法会超时，原因是我们全部每次找K的时候都遍历了所有的情况，导致时间复杂度为O(N^2*K)N:鸡蛋数，K:楼层数
继续优化，优化的核心是如何更快的找到第一次扔蛋的k层。
这可以从递推公式中找到答案：
画成图是这样的关系：
可以使用二分法来求出k层
public int superEggDrop1(int K, int N) {
int[][] dp = new int[N + 1][K + 1];
// 由于求的是最小值，因此初始化的时候赋值为一个较大的数，9999 或者 i 都可以
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i], i);
}
// 初始化：填写下标为 0、1 的行和下标为 0、1 的列
// 第 0 行：楼层为 0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0
for (int j = 0; j <= K; j++) {
dp[0][j] = 0;
}
// 第 1 行：楼层为 1 的时候，0 个鸡蛋的时候，扔 0 次，1 个以及 1 个鸡蛋以上只需要扔 1 次
dp[1][0] = 0;
for (int j = 1; j <= K; j++) {
dp[1][j] = 1;
}
// 第 0 列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0
// 第 1 列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度（想想复杂度的定义）
for (int i = 0; i <= N; i++) {
dp[i][0] = 0;
dp[i][1] = i;
}
for (int i = 2; i <= N; i++) {
for (int j = 2; j <= K ; j++) {
int left = 1;
int right = i;
while (left<right){
// int mid = (left+right)/2+1;
int mid = left+(right-left+1)/2;
int up = dp[mid-1][j-1];
int down = dp[i-mid][j];
if (up>down){
right = mid-1;
}else {
left = mid;
}
}
dp[i][j] = Math.max(dp[left-1][j-1],dp[i-left][j])+1;
//不需要每次遍历 使用二分查找的方式
// for (int k = 1; k <= i; k++) {
// dp[i][j] = Math.min(dp[i][j],Math.max(dp[k-1][j-1],dp[i-k][j])+1);
// }
}
}
return dp[N][K];
}
1.1.3. 括号生成
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-09 18:28
* <p>
* 22. 括号生成
* 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
* <p>
* <p>
* <p>
* 示例：
* <p>
* 输入：n = 3
* 输出：[
* "((()))",
* "(()())",
* "(())()",
* "()(())",
* "()()()"
* ]
**/
将生成过程想象成一棵树，并且剪掉明显非法的括号比如())这样的情况。
public List<String> generateParenthesis(int n) {
ArrayList<String> list = new ArrayList<>(n * 2);
dfs(list,n,n,"");
return list;
}
private void dfs(ArrayList<String> list, int l, int r, String s) {
if (l==0&&r==0){
list.add(s);
}
if (r>l)return;
if (l>0){
dfs(list,l-1,r,"("+s);
}
if (r>0){
dfs(list,l,r-1,")"+s);
}
}
使用char[]数组来代替字符串拼接。
/*
* DFS算法
* 时间复杂度:O(n)，空间复杂度:O(1)
*/
public List<String> generateParenthesis2(int n) {
List<String> list = new ArrayList<String>();
if (n < 0) return list;
dfs(0, n, n, new char[n << 1], list);
return list;
}
private void dfs(int idx, int leftRemain, int rightRemain, char[] string, List<String> list) {
if (idx == string.length) {
list.add(new String(string));
return;
}
// 枚举这一层所有可能的选择
// 选择一种可能之后，进入下一层搜索
// 什么情况可以选择左括号？左括号的数量 > 0
// 选择左括号，然后进入下一层搜索
if (leftRemain > 0) {
string[idx] = '(';
dfs(idx+1, leftRemain-1, rightRemain, string, list);
}
// 当左括号、右括号的数量一样时，只能选择左括号
// 什么情况可以选择右括号？(右括号的数量 > 0) && (右括号的数量 != 左括号的数量)
// 选择右括号，然后进入下一层搜索
if (rightRemain > 0 && leftRemain != rightRemain) {
string[idx] = ')';
dfs(idx+1, leftRemain, rightRemain-1, string, list);
}
}
1.1.4. 机器人的运动范围
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-08 22:06
*
* 面试题13. 机器人的运动范围
* 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
*
*
*
* 示例 1：
*
* 输入：m = 2, n = 3, k = 1
* 输出：3
* 示例 1：
*
* 输入：m = 3, n = 1, k = 0
* 输出：1
* 提示：
*
* 1 <= n,m <= 100
* 0 <= k <= 20
**/
第一个思路先写出一个函数可以获取一个数字的各个位数之和：
public int getnum(int i){
if(i/10==0){
return i%10;
}
return getnum(i/10) + i%10;
}
仔细分析不难发现我们是从[0,0]开始移动到[m,n]所以其实根本就不需要计算向上与向右的步数。
int count =0;
public int movingCount1(int m, int n, int k) {
int[][] maps = new int[m][n];
helper(maps,m-1,n-1,0,0,k);
return count;
}
private void helper(int[][] maps, int m, int n, int i, int j, int k) {
if (i<=m&&j<=n&&maps[i][j]!=1&&(getnum(i)+getnum(j))<=k){
count++;
maps[i][j]=1;
helper(maps,m,n,i+1,j,k);
helper(maps,m,n,i,j+1,k);
}
}
1.1.5. 翻转字符串里的单词
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-10 23:20
* <p>
* 151. 翻转字符串里的单词
* 给定一个字符串，逐个翻转字符串中的每个单词。
* <p>
* <p>
* <p>
* 示例 1：
* <p>
* 输入: "the sky is blue"
* 输出: "blue is sky the"
* 示例 2：
* <p>
* 输入: " hello world! "
* 输出: "world! hello"
* 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
* 示例 3：
* <p>
* 输入: "a good example"
* 输出: "example good a"
* 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
**/
这道题目算是我不看答案自己就能有思路的第一题吧。
public String reverseWords(String s) {
String[] words = s.split(" +");
List<String> collect = Arrays.stream(words).map(e -> e.trim()).collect(Collectors.toList());
Collections.reverse(collect);
return String.join(" ",collect);
}
不用API解法
public String reverseWords1(String s) {
String[] words = s.split(" ");
StringBuilder builder = new StringBuilder();
for (int i = words.length-1; i >= 0; i--) {
if ("".equals(words[i])){
continue;
}
builder.append(words[i]).append(" ");
}
String res = builder.toString();
if ("".equals(res))return "";
return res.substring(0,res.length()-1);
}
1.1.6. 旋转矩阵
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-07 22:05
* <p>
* 面试题 01.07. 旋转矩阵
* 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
* <p>
* 不占用额外内存空间能否做到？
* <p>
* <p>
* <p>
* 示例 1:
* <p>
* 给定 matrix =
* [
* [1,2,3],
* [4,5,6],
* [7,8,9]
* ],
* <p>
* 原地旋转输入矩阵，使其变为:
* [
* [7,4,1],
* [8,5,2],
* [9,6,3]
* ]
* 示例 2:
* <p>
* 给定 matrix =
* [
* [ 5, 1, 9,11],
* [ 2, 4, 8,10],
* [13, 3, 6, 7],
* [15,14,12,16]
* ],
* <p>
* 原地旋转输入矩阵，使其变为:
* [
* [15,13, 2, 5],
* [14, 3, 4, 1],
* [12, 6, 8, 9],
* [16, 7,10,11]
* ]
**/
这道题目主要的思想是，如果想要90度旋转。
其实可以拆分为两步：
- 先对角线旋转
- 再中轴旋转
public void rotate(int[][] matrix) {
//第一步先对角线反转
int n = matrix.length;
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//第二步再中轴旋转
int mid = n / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < mid; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n-1-j]=temp;
}
}
}
2. review
3. tip
4. share
在我一生的黄金时代。我有好多奢望。我想爱，想吃，还想在一瞬间变成天上半明半暗的云。后来我才知道，生活就是个缓慢受锤的过程，人一天天老下去，奢望也一天天消失，最后变得像挨了锤的牛一样。可是我过二十一岁生日时没有预见到这一点。我觉得自己会永远生猛下去，什么也锤不了我。
–《黄金时代》
