LeetCode 1084, 135, 21

1084. 销售分析III

题目链接

1084. 销售分析III

表

• 表Product的字段为product_id，product_name和unit_price。
• 表Sales的字段为seller_id，product_id，buyer_id，sale_date，quantity和price。

要求

• 编写解决方案，报告2019年春季才售出的产品。即 仅在2019-01-01至2019-03-31（含）之间出售的商品 。
• 以 任意顺序 返回结果表。

知识点

1. min()：求某个字段最小值的函数。
2. max()：求某个字段最大值的函数。
3. group by：按照某些字段进行分组。
4. between and：将字段的值限制在闭区间内。
5. 子查询：将查询结果作为表进行查询。

思路

既然要求 仅在2019-01-01至2019-03-31（含）之间出售的商品 ，那就先求出每件商品售卖的最早日期和最晚日期，如果最早和最晚日期都在 2019-01-01~2019-03-31 以内，则说明这就是题目要求的商品，将其product_id和product_name返回即可。

代码

select
    p.product_id product_id,
    product_name
from
    Product p,
    (
        select
            min(sale_date) min_date,
            max(sale_date) max_date,
            product_id
        from
            Sales
        group byj
            product_id
    ) s
where
    p.product_id = s.product_id
and
    s.min_date between '2019-01-01' and '2019-03-31'
and
    s.max_date between '2019-01-01' and '2019-03-31'

135. 分发糖果

题目链接

135. 分发糖果

标签

贪心 数组

普通版

思路

首先思考一个问题，就是如何才能准备最少的糖果，答案不是分数越低，获得的糖果数越少，而是由这个孩子旁边的人决定，他旁边的人分数高，而他的分数低，则尽量给他最少的糖果，也就是1个糖果。但是旁边分为左边和右边，要是简简单单地根据一边而决定他的糖果数，就很难保证 相邻两个孩子评分更高的孩子会获得更多的糖果。

也就是说两边都需要判断：先从左到右遍历分数的数组，（条件一）保证对于两个相邻孩子，右边孩子的分数越高，他的糖果数越多，当右边孩子的分数比左边少时，就给右边的孩子给1个糖果；再从右到左遍历分数的数组，（条件二）保证对于两个相邻孩子，左边孩子的分数越高，他的糖果数越多，当左边孩子的分数比右边少时，就给左边的孩子给1个糖果。最后遍历两个糖果数的数组，取较大值作为这个孩子的糖果数（因为较大值同时满足两个条件），将其加到结果数中。

代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;

        // 1. 先从左到右循环一遍，保证：对于两个相邻孩子，右边孩子的分数越高，他的糖果数越多
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else { // 若右边的分数低，则给他一个糖果
                left[i] = 1;
            }
        }

        // 2. 再从右到左循环一遍，保证：对于两个相邻孩子，左边孩子的分数越高，他的糖果数越多
        int[] right = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else { // 若左边的分数低，则给他一个糖果
                right[i] = 1;
            }
        }

        // 3. 计算结果
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 值越大，能保证满足两个条件，所以给结果加上更大值
            res += Math.max(left[i], right[i]);
        }
        return res;
    }
}

优化版

思路

本题可以省去从右到左遍历的数组（按理来说少一个数组会降低空间复杂度，但反而是普通版消耗的内存更少），因为对于左边的孩子，他的糖果数只与右边孩子有关系，所以只用一个变量记录右边孩子的糖果数就行。（当然与之类似，也可以省去从左到右遍历的数组，只不过有些反直觉罢了）

代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;

        // 1. 先从左到右循环一遍，保证：对于两个相邻孩子，右边孩子的分数越高，他的糖果数越多
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else { // 若右边的分数低，则给他一个糖果
                left[i] = 1;
            }
        }

        // 2. 再从右到左循环一遍，保证：对于两个相邻孩子，左边孩子的分数越高，他的糖果数越多
        int right = 0, res = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else { // 若左边的分数低，则给他一个糖果
                right = 1;
            }
            // 值越大，能保证满足两个条件，所以给结果加上更大值
            res += Math.max(left[i], right);
        }
        
        return res;
    }
}

21. 合并两个有序链表

题目链接

21. 合并两个有序链表

标签

递归 链表

思路

合并链表，首先就能想到使用一个指针head作为结果链表的头指针，再用一个指针curr作为当前节点，从两个链表中选取较小值min让这个指针指向它，然后更新这个指针和选取较小值的链表。

这里提出一个比较“高级”的做法：用一个 哨兵节点指向链表的头部，返回结果时直接返回它的next 。这样做可以避免（先判断head是否为空，再决定将min赋值给head，还是将min赋值给curr.next）这个复杂的操作。

当任意一个链表为空时退出循环，再判断链表1是否为空，若不为空，则说明退出循环是因为链表2为空，这时只需要让curr指向链表1即可（这样做就把链表1的剩余节点全部加到结果链表尾部了，对于接下来的链表2也是同理）；否则退出循环的原因就是链表1为空，此时让curr指向链表2（就算链表2也为空，只不过是让curr指向null，对结果不影响）。

代码

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode sentinel = new ListNode(-1, null); // 定义一个哨兵节点，返回它的next
        ListNode curr = sentinel;

        // 1. 先把小的节点加到哨兵节点上，直到两个链表任意一个为空
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        
        // 2. 如果链表1不为空，则加上它剩余的部分
        if (list1 != null) {
            curr.next = list1;
        } else { // 否则链表2不为空，加上它剩余的部分
            curr.next = list2;
        }

        // 3. 返回哨兵节点的next，因为它指向结果链表
        return sentinel.next;
    }
}