每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！
第一题：71. 简化路径 - 力扣（LeetCode）
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new LinkedList<>();
for (String item : path.split("/")) {
//如果是俩点，上一级不为空，则出栈（返回上一级）
if (item.equals("..")) {
if (!stack.isEmpty()) stack.pop();
} else if (!item.isEmpty() && !item.equals(".")) stack.push(item);
//否则，如果是正常的一个点. 代表进入下一级
}
String res = "";
for (String d : stack) res = "/" + d + res;
return res.isEmpty() ? "/" : res;
}
}
第二题：72. 编辑距离 - 力扣（LeetCode）
class Solution {
public int minDistance(String word1, String word2) {
//经典dp题，题目要求最小操作数
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
//初始化一下特殊情况
dp[0][0] = 0;
for(int i = 1; i <= m; i++){
dp[i][0] = i;
}
for(int j = 1; j <= n; j++){
dp[0][j] = j;
}
//给出递推公式
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
//注意所设dp范围，所以相等的时候是word1.charAt(i - 1) == word2.charAt(j - 1)
dp[i][j] = dp[i - 1][j - 1];
}else{
//三种情况，从第一个字符串的角度来说是增加：dp[i - 1][j]
//修改：dp[i - 1][j - 1] 删除：dp[i][j - 1])
//在这三者中取到最小的一种，增加1
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
}
}
}
return dp[m][n];
}
}第三题：73. 矩阵置零 - 力扣（LeetCode）
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// 定义两个数组来跟踪需要置零的行和列
boolean[] zeroRows = new boolean[m];
boolean[] zeroCols = new boolean[n];
// 遍历矩阵以标记包含零的行和列
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
zeroRows[i] = true;
zeroCols[j] = true;
}
}
}
// 将零置于行
for (int i = 0; i < m; i++) {
if (zeroRows[i]) {
for (int j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
}
// 将零置于列
for (int j = 0; j < n; j++) {
if (zeroCols[j]) {
for (int i = 0; i < m; i++) {
matrix[i][j] = 0;
}
}
}
}
}
第四题：74. 搜索二维矩阵 - 力扣（LeetCode）
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//由于题目提到了每一行第一个数>上一行最后一个数
//明显提示了使用二分查找
int m = matrix.length;
int n = matrix[0].length;
int left = -1;
int right = m * n;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
int x = matrix[mid / n][mid % n];
if (x == target) {
return true;
}
if (x < target) {
left = mid;
} else {
right = mid;
}
}
return false;
}
}
第五题：75. 颜色分类 - 力扣（LeetCode）
class Solution {
public void sortColors(int[] nums) {
//直接快排
quicksort(nums, 0, nums.length - 1);
return;
}
private static void quicksort(int[] nums, int low, int high){
if(low < high){
int partindex = partition(nums, low, high);
quicksort(nums, low, partindex - 1);
quicksort(nums, partindex + 1, high);
return;
}
}
private static int partition(int[] nums, int low, int high){
int pivot = nums[high];
int i = low - 1;
for(int j = low; j < high; j++){
if(nums[j] < pivot){
i++;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
int tmp = nums[high];
nums[high] = nums[i + 1];
nums[i + 1] = tmp;
return i + 1;
}
}class Solution {
public void sortColors(int[] nums) {
//刷油漆法，这个思路是真强啊
int n0 = 0, n1 = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
//刷油漆法，先全部刷为2
nums[i] = 2;
//如果该值为1或0 那么我们往后刷一个1出来
if (num < 2) {
nums[n1++] = 1;
}
//和上面做法一样，我们直接刷为0
if (num < 1) {
nums[n0++] = 0;
}
}
}
}
