LeetCode刷题记录

88. 合并两个有序数组

题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解题思路

逆向双指针：观察可知，nums1的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1的最后面。严格来说，在此遍历过程中的任意一个时刻，nums1数组中有 m − p1 − 1 个元素被放入nums1的后半部，nums2数组中有 n − p2 − 1 个元素被放入 nums1 的后半部，而在指针 p1 的后面，nums1 数组有 m + n − p1 − 1个位置。由于 m + n − p1 −1 ≥ m − p1 − 1 + n − p2 − 1 等价于 p2 ≥ −1 永远成立，因此 p1 后面的位置永远足够容纳被插入的元素，不会产生 p1 的元素被覆盖的情况。

代码实现

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m -1, p2 = n-1;
        int tail = m + n -1;
        //如果 p1到达 -1，则说明 nums2中可能还存在小 nums1[0]的元素，如果 p2到达 -1，则说明nums1中剩余元素无需处理
        while (p1 >= 0 && p2 >= 0) {
            nums1[tail--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
        }
        // 如果 nums2 中还有剩余元素，直接复制到 nums1 中
        while (p2 >= 0) {
            nums1[tail--] = nums2[p2--];
        }
    }
}

测试用例

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6,7]
n = 4

27. 移除元素

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路

双指针：如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。
如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。避免了需要保留的元素的重复赋值操作。(例如序列 [1,2,3,4,5]，当 val为 1 时，我们需要把每一个元素都左移一位)

代码实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while(left < right){
            //判断左指针是否和val相等，如果相等把右指针位置的元素赋值到左指针位置
            //此时左指针并不移动，右指针往右移动一位，这样可以避免右指针原始位置的元素也与val相等
            if(nums[left] == val){
                //先赋值再移动指针
                nums[left] = nums[--right];
            }else{
                left++;
            }
        }
        return left;
    }
}

测试用例

nums = [0,1,2,2,3,0,4,2]
val = 2

26.删除有序数组中的重复项

题目

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

解题思路

快慢指针：首先注意数组是有序的，那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。
考虑用 快慢指针，快指针fast，慢指针slow，算法流程如下：
1.从下标为1开始比较 fast和 fast前一个位置的元素是否相等。
如果不相等，将 fast 位置的元素复制到 slow 位置上，slow 后移一位
不管是否相等 都把fast向后移一位
重复上述过程，直到 fast 等于数组长度。
返回 slow，即为新数组长度。

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        //从下标 1 开始
        int fast = 1, slow = 1;
        while(fast < n){
            //如果不相等，将 fast 位置的元素复制到 slow 位置上，slow 后移一位
            if(nums[fast] != nums[fast -1]){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }
}

测试用例

[0,0,1,1,1,2,2,3,3,4]

80. 删除有序数组中的重复项 II

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解题思路

在解决本题前，可先尝试解决[删除有序数组中的重复项]
当且仅当nums[slow-2] == nums[fast]时才表示当前fast位置的元素需要被删除
特别地，数组的前两个数必然可以被保留，因此对于长度不超过 2的数组，我们无需进行任何处理，对于长度超过 2的数组，我们直接将双指针的初始值设为 2即可。

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n <= 2){
            return n;
        }
        // 从下标为2的位置开始
        int fast = 2, slow = 2;
        while(fast < n){
            if(nums[slow - 2] != nums[fast]){
                nums[slow++] = nums[fast]; 
            }
            fast++;
        }
        return slow;
    }
}

测试用例

[0,0,1,1,1,1,2,3,3]

169. 多数元素

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路

Boyer-Moore 投票算法：如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。算法详解

代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = nums[0];
        for(int num : nums){
            if(count == 0){
                candidate = num;
            }
            count += (candidate == num) ? 1 : -1;
        }
        return candidate;
    }
}

测试用例

[2,2,1,1,1,2,2]

189. 轮转数组

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

解题思路

数组翻转：当我们将数组的元素向右移动 k次后，尾部 k mod n个元素会移动至数组头部，其余元素向后移动 k mod n个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k mod n个元素就被移至数组头部，然后我们再翻转 [0,k mod n−1] 区间的元素和 [k mod n,n−1] 区间的元素即能得到最后的答案。

代码实现

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

测试用例

[1,2,3,4,5,6,7]

本栏目推荐文章
• 【LeetCode 2701. 连续递增交易】MySQL用户变量编程得到严格递增连续子序列的开始位置，结束位置，长度等统计信息
• 【Leetcode 2474. 购买量严格增加的客户】MySQL用户变量编程解决严格递增连续子序列问题
• 【LeetCode 2494. 合并在同一个大厅重叠的活动】MySQL用户变量编程解决区间合并问题
• 【LeetCode1747. 应该被禁止的 Leetflex 账户】MySQL用户变量编程；尝试维护一个multiset
• 【Leetcode1949. 坚定的友谊】使用MySQL在无向图中寻找{"CompleteTripartite", {1, 1, 3}}这个pattern
• 【LeetCode 2142. 每辆车的乘客人数 I】乘客到站等车，车到站载客。MySQL用户变量编程完成
• 【LeetCode 】练习str_to_date函数；over(rows between CURRENT ROW AND 2 following)实现【当月和接下来2个月】滑动窗口
• leetcode 15.三数之和
• [LeetCode] 2085. Count Common Words With One Occurrence
• 【LeetCode 1635. Hopper 公司查询 I】with recursive生成2020年每月的最后一天

LeetCodeleetcode1 leetcode2 leetcode 383 leetcode随笔 leetcode 283 day7-leetcode leetcode 206 leetcode_d leetcode 92 leetcode-java