+关注继续查看

# 1. 矩阵中的最长递增路径

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

0 <= matrix[i][j] <= 2^31 - 1

https://edu.csdn.net/practice/27049323

import java.util.*;
class longestIncreasingPath {
public static class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int max = 0;
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
max = Math.max(max, loop(matrix, Integer.MIN_VALUE, dp, i, j));
}
}
return max;
}
private int loop(int[][] mat, int pre, int[][] dp, int i, int j) {
if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || mat[i][j] <= pre) {
return 0;
}
if (dp[i][j] != 0) {
return dp[i][j];
}
int max = 0;
max = Math.max(max, loop(mat, mat[i][j], dp, i - 1, j));
max = Math.max(max, loop(mat, mat[i][j], dp, i + 1, j));
max = Math.max(max, loop(mat, mat[i][j], dp, i, j - 1));
max = Math.max(max, loop(mat, mat[i][j], dp, i, j + 1));
dp[i][j] = max + 1;
return dp[i][j];
}
}
public static void main(String[] args) {
Solution obj = new Solution();
int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
System.out.println(obj.longestIncreasingPath(matrix));
int[][] matrix2 = {{3,4,5},{3,2,6},{2,2,1}};
System.out.println(obj.longestIncreasingPath(matrix2));
}
}

4

4

# 2. 编辑距离

插入一个字符

删除一个字符

替换一个字符

0 <= word1.length, word2.length <= 500

word1 和 word2 由小写英文字母组成

Java

class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if (len1 * len2 == 0)
return len1 + len2;
String longerStr = len1 > len2 ? word1 : word2;
String shorterStr = len1 > len2 ? word2 : word1;
int shorterOne = Math.min(len1, len2);
int[] dp = new int[shorterOne + 1];
for (int i = 0; i < shorterOne + 1; i++) {
dp[i] = i;
}
for (int j = 1; j <= longerStr.length(); j++) {
int left = j;
for (int i = 1; i <= shorterStr.length(); i++) {
int updateDown = dp[i] + 1;
int updateLeft = left + 1;
int updateLeftDown = dp[i - 1];
if (longerStr.charAt(j - 1) != shorterStr.charAt(i - 1)) {
updateLeftDown++;
}
int min = Math.min(updateLeft, Math.min(updateDown, updateLeftDown));
dp[i - 1] = left;
_____________________;
}
}
return dp[shorterOne];
}
}




https://edu.csdn.net/practice/27049324

import java.util.*;
class minDistance {
public static class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if (len1 * len2 == 0)
return len1 + len2;
String longerStr = len1 > len2 ? word1 : word2;
String shorterStr = len1 > len2 ? word2 : word1;
int shorterOne = Math.min(len1, len2);
int[] dp = new int[shorterOne + 1];
for (int i = 0; i < shorterOne + 1; i++) {
dp[i] = i;
}
for (int j = 1; j <= longerStr.length(); j++) {
int left = j;
for (int i = 1; i <= shorterStr.length(); i++) {
int updateDown = dp[i] + 1;
int updateLeft = left + 1;
int updateLeftDown = dp[i - 1];
if (longerStr.charAt(j - 1) != shorterStr.charAt(i - 1)) {
updateLeftDown++;
}
int min = Math.min(updateLeft, Math.min(updateDown, updateLeftDown));
dp[i - 1] = left;
if (i == dp.length - 1) {
dp[i] = min;
} else {
left = min;
}
}
}
return dp[shorterOne];
}
}
public static void main(String[] args) {
Solution obj = new Solution();
String word1 = "horse";
String word2 = "ros";
System.out.println(obj.minDistance(word1, word2));
word1 = "intention";
word2 = "execution";
System.out.println(obj.minDistance(word1, word2));
}
}

3

5

# 3. 数据流的中位数

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

double findMedian() - 返回目前所有元素的中位数。

findMedian() -> 1.5

findMedian() -> 2

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

https://edu.csdn.net/practice/27049325

import java.util.*;
class MedianFinder {
PriorityQueue<Integer> min;
PriorityQueue<Integer> max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue<>();
max = new PriorityQueue<>((a, b) -> {
return b - a;
});
}
if (min.size() > max.size())
}
public double findMedian() {
if (max.size() == min.size())
return (max.peek() + min.peek()) / 2.0;
else
return max.peek();
}
public static void main(String[] args) {
MedianFinder obj = new MedianFinder();
System.out.println(obj.findMedian());
System.out.println(obj.findMedian());
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* double param_2 = obj.findMedian();
*/

1.5

2.0

|
28天前
|
Java
java——获取项目根路径方式
java——获取项目根路径方式
34 0
|
2月前
|

【Java项目】解决请求路径上明文ID传输导致可能被攻击的方法
【Java项目】解决请求路径上明文ID传输导致可能被攻击的方法
32 0
|
2月前
|

84 0
|
2月前
|
Java
Java遍历类路径所有类
WalkClasspathAllClasses
40 0
|
2月前
|

Java实现文件上传到本地(自定义保存路径)
Java实现文件上传到本地(自定义保存路径)
266 0
|
3月前
|

【Java设计模式 学习目标及大纲】高质量代码的标准及实现路径
【Java设计模式 学习目标及大纲】高质量代码的标准及实现路径
62 0
|
4月前
|
canal Java
Java每日一练(20230508) Excel表列名称、验证回文串、路径总和II
Java每日一练(20230508) Excel表列名称、验证回文串、路径总和II
52 0
|
4月前
|
Oracle Java 关系型数据库
Java操作oracle数据库提示：不支持的字符集 (在类路径中添加 orai18n.jar): ZHS16GBK，问题处理
Java操作oracle数据库提示：不支持的字符集 (在类路径中添加 orai18n.jar): ZHS16GBK，问题处理
273 0
|
5月前
|

Java 编程问题：六、Java I/O 路径、文件、缓冲区、扫描和格式化6
Java 编程问题：六、Java I/O 路径、文件、缓冲区、扫描和格式化
41 0
|
5月前
|
Java Spring
Java 编程问题：六、Java I/O 路径、文件、缓冲区、扫描和格式化5
Java 编程问题：六、Java I/O 路径、文件、缓冲区、扫描和格式化
42 0