27. 移除元素，28. 找出字符串中第一个匹配项的下标，29. 两数相除，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.14 可通过leetcode所有测试用例。
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解题思路
解决移除数组中特定值元素的问题时，我们可以采取以下步骤：
-
双指针法：
使用两个指针：一个快指针j用于遍历数组，一个慢指针i用于指向更新后的数组的末尾。 -
遍历数组：
快指针j从头开始遍历数组nums。 -
比较与目标值：
对于每个元素，检查快指针j所指的元素是否等于目标值val。 -
更新数组：
如果当前元素不等于目标值，将快指针j所指的元素复制到慢指针i的位置，然后递增慢指针i。 -
递增快指针：
无论是否复制了元素，快指针j都会递增，继续检查下一个元素。 -
返回新长度：
遍历完成后，慢指针i的位置即为新数组的长度，因为所有不等于val的元素都已经被移至数组的前i个位置。
完整代码
Python
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return iJava
public class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
}
return i;
}
}
28. 找出字符串中第一个匹配项的下标
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
解题思路
暴力匹配方法
- 外层循环遍历haystack：从haystack的第一个字符开始，到"haystack的长度 - needle的长度"为止，这是因为如果剩下的字符少于needle的长度，那么肯定不会匹配成功。
- 内层循环遍历needle：在每个外层循环的位置，开始一个新的内层循环，比较haystack从当前外层循环索引开始的子字符串是否与needle相匹配。
- 匹配成功：如果内层循环成功匹配了needle的所有字符，那么返回当前外层循环的索引。
- 全部不匹配：如果外层循环结束都没有找到匹配项，返回-1。
完整代码
Python
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
L, n = len(needle), len(haystack)
for start in range(n - L + 1):
if haystack[start:start + L] == needle:
return start
return -1Java
public class Solution {
public int strStr(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
for (int start = 0; start < n - L + 1; ++start) {
if (haystack.substring(start, start + L).equals(needle)) {
return start;
}
}
return -1;
}
}
29. 两数相除
给你两个整数，被除数
dividend和除数divisor。将两数相除，要求 不使用 乘法、除法和取余运算。整数除法应该向零截断，也就是截去（
truncate）其小数部分。例如，8.345将被截断为8，-2.7335将被截断至-2。返回被除数
dividend除以除数divisor得到的 商 。注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是
[−231, 231 − 1]。本题中，如果商 严格大于231 − 1，则返回231 − 1；如果商 严格小于-231，则返回-231。
示例 1:
输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = 3.33333.. ，向零截断后得到 3 。示例 2:
输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。
解题思路
- 处理符号：首先处理被除数和除数的符号，记录最终结果的符号，并将被除数和除数都转换为正数处理。
- 边界情况处理：处理整数溢出的情况。
- 位移加速：使用位移操作来模拟除法，将除数不断左移（即乘以2），直到它大于被除数之前的最大值。
- 执行减法：从被除数中减去当前的除数值，同时累加结果。
- 重复步骤3和4：直到除数不能再从被除数中减去。
- 应用符号并返回结果：根据最开始记录的符号，应用到最终的结果上，并返回。
完整代码
Python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MAX, INT_MIN = 2**31 - 1, -2**31
# 处理符号
sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
# 处理溢出
if dividend == INT_MIN and divisor == -1:
return INT_MAX
# 取绝对值
dividend, divisor = abs(dividend), abs(divisor)
result = 0
while dividend >= divisor:
temp, i = divisor, 1
while dividend >= temp:
dividend -= temp
result += i
i <<= 1
temp <<= 1
return result * signJava
public class Solution {
public int divide(int dividend, int divisor) {
int INT_MAX = Integer.MAX_VALUE, INT_MIN = Integer.MIN_VALUE;
// 处理符号
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
// 处理溢出
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
// 转换为长整型，防止绝对值时溢出
long ldividend = Math.abs((long) dividend), ldivisor = Math.abs((long) divisor);
long result = 0;
while (ldividend >= ldivisor) {
long temp = ldivisor, m = 1;
while (ldividend >= (temp << 1)) {
temp <<= 1;
m <<= 1;
}
ldividend -= temp;
result += m;
}
result *= sign;
return (int) result;
}
}
