JZTXT

2023-09-09 刷题日记

发布时间 2023-09-09 22:01:56作者: 洛阳秋风

leetcode 刷题笔记

88. 合并两个有序数组

题目链接

个人解题思路

建立一个新的长度为 \(m+n\) 长度的数组, 分别使用 point1 和 point2 两个指针 从头遍历 两个数组, 较小的放入新数组中, 直到两个数组遍历完成.

之后再将新数组中的数据复制到 nums1 中.

image.png

最优解

正序遍历存在的问题是, nums2 数组中的数据可能会覆盖 nums1 数组的数据, 因此不得不借助一个新的数组, 使用了额外的 \(m+n\) 长度的空间.

最优解仍使用双指针方式, 但采用逆序遍历的方式, 较大的数放在 nums1 数组的末尾, 这样就不会覆盖 nums1 中的数据了.

正确性证明:
当 nums1 逆序遍历到 \(p_{1}\) 位置, nums2 逆序遍历到 \(p_{2}\) 位置时:

  • nums1 已遍历的数据量为: \(m-p_{1}-1\)
  • nums2 已遍历的数据量为: \(n-p_{2}-1\)
  • nums1 中可用空间为: \(m-p_{1}-1+n\)
    可得:

\[m-p_{1}-1+n \geq m-p_{1}-1+n-p_{2}-1 \]

即逆序遍历时, nums1 中的可用空间永远够用, 不会发生覆盖的情况.

image.png

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n == 0) return;

        int p1 = m-1, p2 = n-1;
        for (int i = nums1.length - 1; i >= 0; i--) {
            if (p1 >= 0 && p2 >= 0) {
                nums1[i] = nums1[p1] >= nums2[p2] ? nums1[p1--] : nums2[p2--];
                continue;
            }

            // 当 nums1 或 nums2 遍历完后, 剩下的追加到 nums1 数组前 
            if (p1 >= 0) {
                nums1[i] = nums1[p1--];
            } else {
                nums1[i] = nums2[p2--];
            }
        }

    }
}

sql刷题笔记

SQL88 返回订单数量总和不小于100的所有订单的订单号

题目链接

知识点

关键字 having 的使用:

  • where : 用于过滤指定的行
  • having : 用于过滤分组, 与 group by 连用

SQL89 计算总和

题目链接

知识点

  1. 使用 group by 聚合之后, select 的字段只能是两种:
    1. group by 使用的字段
    2. 其他字段的聚合函数
  2. select 的字段可以是具体的某一个字段, 也可以是多个字段运算后的结果

题解

SELECT
    order_num
    , sum(item_price * quantity) as total_price
FROM
    OrderItems
GROUP BY
    order_num
HAVING
    total_price >= 1000
ORDER BY
    order_num;

SQL91 返回购买价格为 10 美元或以上产品的顾客列表

题目链接

知识点

子查询语法

题解

SELECT
    cust_id
FROM
    Orders
WHERE
    order_num in
        (SELECT
            order_num
        FROM
            OrderItems
        GROUP BY
            order_num
        HAVING
            sum(item_price) >= 10);