69. x 的平方根 ，71. 简化路径，72. 编辑距离，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.22 可通过leetcode所有测试用例。
69. x 的平方根
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。
示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题思路
我们可以使用二分查找法。这种方法适用于因为我们知道平方根的值不会超过 x 的一半加一。以下是解决问题的步骤：
- 初始化：设置左边界
left为 0，右边界right为x / 2 + 1。因为任何数的平方根不会大于其自身的一半加一（对于x > 1的情况）。 - 二分查找：
- 计算中点
mid = (left + right) / 2。 - 计算
mid的平方midSq = mid * mid。 - 如果
midSq等于x，则mid即为所求的平方根。 - 如果
midSq小于x，说明平方根在mid的右侧，因此设置left = mid + 1。 - 如果
midSq大于x，说明平方根在mid的左侧，因此设置right = mid - 1。
- 计算中点
- 循环：重复上述步骤，直到
left大于right，此时right就是x的平方根的整数部分。
完整代码
Java
public class Solution {
public int mySqrt(int x) {
if (x < 2) return x;
long left = 2, right = x / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
long num = mid * mid;
if (num == x) return (int) mid;
if (num < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int) right;
}
}Python
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left, right = 2, x // 2
while left <= right:
mid = (left + right) // 2
num = mid * mid
if num == x:
return mid
elif num < x:
left = mid + 1
else:
right = mid - 1
return right
71. 简化路径
给你一个字符串
path，表示指向某一文件或目录的 Unix 风格 绝对路径 （以'/'开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（
.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠'/'。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。- 两个目录名之间必须只有一个斜杠
'/'。- 最后一个目录名（如果存在）不能 以
'/'结尾。- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。示例 2：
输入：path = "/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。示例 3：
输入：path = "/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。示例 4：
输入：path = "/a/./b/../../c/" 输出："/c"
解题思路
- 分割路径：首先，我们将输入的路径按照斜杠 '/' 分割成各个部分。这样我们可以得到一个包含所有目录和命令（如 '.' 和 '..'）的列表。
- 处理路径：遍历上一步得到的列表，使用一个栈来处理每个部分：
- 如果当前部分是一个普通的目录名（非空且不是 '.' 或 '..'），就将其推入栈中。
- 如果当前部分是两个点 '..'，则从栈中弹出一个目录，这相当于返回上一级目录。如果栈为空，则忽略该操作（已经在根目录）。
- 如果当前部分是一个点 '.' 或者为空（即连续的斜杠），则忽略该部分，不进行任何操作。
- 构建规范路径：最后，将栈中的所有目录拼接成一个字符串，目录之间用斜杠 '/' 分隔，并确保结果以斜杠 '/' 开头。
完整代码
Java
class Solution {
public String simplifyPath(String path) {
String[] parts = path.split("/");
Stack<String> stack = new Stack<>();
for (String part : parts) {
if (part.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else if (!part.isEmpty() && !part.equals(".")) {
stack.push(part);
}
}
return "/" + String.join("/", stack);
}
}Python
class Solution:
def simplifyPath(self, path: str) -> str:
parts = path.split('/')
stack = []
for part in parts:
if part == '..':
if stack:
stack.pop()
elif part and part != '.':
stack.append(part)
return '/' + '/'.join(stack)72. 编辑距离
给你两个单词
word1和word2， 请返回将word1转换成word2所使用的最少操作数 。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
解题思路
动态规划的关键在于找到状态转移方程。
-
定义状态：设
dp[i][j]表示从word1的前i个字符转换到word2的前j个字符所使用的最少操作数。其中i范围为0到len(word1)，j范围为0到len(word2)。 -
初始化：当
word1或word2为空时，转换所需的操作数即为另一个单词的长度。因此，初始化dp[i][0] = i（0 <= i <= len(word1)）和dp[0][j] = j（0 <= j <= len(word2)）。 -
状态转移方程：
- 如果
word1[i - 1] == word2[j - 1]，则dp[i][j] = dp[i - 1][j - 1]，因为最后一个字符相同，不需要额外操作。 - 如果
word1[i - 1] != word2[j - 1]，则有三种操作可以考虑：- 插入：
dp[i][j] = dp[i][j - 1] + 1 - 删除：
dp[i][j] = dp[i - 1][j] + 1 - 替换：
dp[i][j] = dp[i - 1][j - 1] + 1
- 插入：
- 取这三种操作的最小值作为
dp[i][j]的值。
- 如果
-
返回结果：
dp[len(word1)][len(word2)]就是从word1转换到word2所需的最少操作数。
完整代码
Java
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
}Python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
