力扣大厂热门面试算法题 27-29

        27. 移除元素，28. 找出字符串中第一个匹配项的下标，29. 两数相除，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.14 可通过leetcode所有测试用例。

目录

27. 移除元素

解题思路

完整代码

Python

Java

28. 找出字符串中第一个匹配项的下标

解题思路

暴力匹配方法

完整代码

Python

Java

29. 两数相除

解题思路

完整代码

Python

Java

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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解题思路

解决移除数组中特定值元素的问题时，我们可以采取以下步骤：

1. 双指针法：

   使用两个指针：一个快指针j用于遍历数组，一个慢指针i用于指向更新后的数组的末尾。

2. 遍历数组：

   快指针j从头开始遍历数组nums。

3. 比较与目标值：

   对于每个元素，检查快指针j所指的元素是否等于目标值val。

4. 更新数组：

   如果当前元素不等于目标值，将快指针j所指的元素复制到慢指针i的位置，然后递增慢指针i。

5. 递增快指针：

   无论是否复制了元素，快指针j都会递增，继续检查下一个元素。

6. 返回新长度：

   遍历完成后，慢指针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 i

Java

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 。

解题思路

暴力匹配方法

1. 外层循环遍历haystack：从haystack的第一个字符开始，到"haystack的长度 - needle的长度"为止，这是因为如果剩下的字符少于needle的长度，那么肯定不会匹配成功。
2. 内层循环遍历needle：在每个外层循环的位置，开始一个新的内层循环，比较haystack从当前外层循环索引开始的子字符串是否与needle相匹配。
3. 匹配成功：如果内层循环成功匹配了needle的所有字符，那么返回当前外层循环的索引。
4. 全部不匹配：如果外层循环结束都没有找到匹配项，返回-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 -1

Java

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 。

解题思路

1. 处理符号：首先处理被除数和除数的符号，记录最终结果的符号，并将被除数和除数都转换为正数处理。
2. 边界情况处理：处理整数溢出的情况。
3. 位移加速：使用位移操作来模拟除法，将除数不断左移（即乘以2），直到它大于被除数之前的最大值。
4. 执行减法：从被除数中减去当前的除数值，同时累加结果。
5. 重复步骤3和4：直到除数不能再从被除数中减去。
6. 应用符号并返回结果：根据最开始记录的符号，应用到最终的结果上，并返回。

完整代码

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 * sign

Java

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;
    }
}