LeetCode 1633, 122, 239

1633. 各赛事的用户注册率

题目链接

1633. 各赛事的用户注册率

表

• 表Users有字段user_id和user_name。
• 表Register有字段contest_id和user_id。

要求

• 编写解决方案统计出各赛事的用户注册百分率，保留两位小数。
• 返回的结果表按 percentage 的 降序 排序，若相同则按 contest_id 的 升序 排序。

知识点

1. rount()：四舍五入函数。
2. count()：统计个数函数。
3. 多表查询：from后跟多张表，然后使用where限制笛卡尔积的部分数据（多表查询的结果是两张表排列组合的结果，这个结果被称为笛卡尔积）。
4. 子表查询：子表查询就是将从表查询到的结果作为另一个表放在from后边。
5. order by + desc/asc：排序，比如order by num表示按num进行（默认）升序排序，效果等价于order by num asc；order by num desc表示按num进行降序排序。

思路

要求各赛事的用户注册百分率，首先要求出参加各赛事的用户数和用户的总数（求用户的总数可以键一张子表），然后用前者除以后者就可以得出各赛事的用户注册百分率，但要注意的是求出来的百分率要乘100；然后再根据题目中的两个条件进行排序。

代码

selectcontest_id,round(count(*) * 100 / cnt.num, 2) percentage
fromUsers s,Register r,(selectcount(*) numfromUsers) cnt
wheres.user_id = r.user_id
group bycontest_id
order bypercentage desc,contest_id

122. 买卖股票的最佳时机 II

题目链接

122. 买卖股票的最佳时机 II

标签

贪心 数组 动态规划

思路

本题的股票可以随时卖和买，所以不需要计划的很长远，只要一天的价格比前一天的高，就在前一天买，然后在这天卖，使用了一种贪心的思想：只顾当前（局部）的最优解，局部最优解的总和就是全局最优解。

代码

class Solution {public int maxProfit(int[] prices) {int i = 1, res = 0;while (i < prices.length) {int profit = prices[i] - prices[i - 1];if (profit > 0) {res += profit;}i++;}return res;}
}

239. 滑动窗口最大值

题目链接

239. 滑动窗口最大值

标签

队列 数组 滑动窗口 单调队列 堆（优先队列）

思路

本题建议使用优先队列来解答，优先队列指的是插入队列的所有元素都有一个优先级，按照优先级的大小进行排序，优先级越大（或越小），越靠近队列头部（或尾部），其中，优先级可以是数字的大小，也可以是字符串的长度等可以量化的数量。
优先队列的实现也很简单，在这个类中内置一个双端队列，从头部执行获取和删除的操作，从尾部执行添加的操作，每次添加时从尾部向前扫描，直到扫描到优先级比待添加元素的优先级高的元素，将这些优先级低于待添加元素优先级的元素从队列中删除。
了解优先队列的实现后，就可以开始做题了。把滑动窗口想象成一个优先队列，每次滑动时都往队列中添加一个值，按理来说也应该从队列中删除一个值，但其实不然，在这个优先队列中只有最大值会被使用到，所以只要那个该删除的值不是最大值，就不需要删除它。

代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int index = 0;int[] res = new int[nums.length - k + 1];PriorityQueue queue = new PriorityQueue();for (int i = 0; i < nums.length; i++) {// 队列中已经有k个元素了，并且该队列的最大值还等于窗口前面的元素，对于这种队列，取出这个最大值if (i >= k && nums[i - k] == queue.peek()) {queue.poll();}queue.offer(nums[i]);// 从第k - 1个数开始if (i >= (k - 1)) {res[index++] = queue.peek();}}return res;}private static class PriorityQueue {LinkedList<Integer> deque = new LinkedList<>();int peek() {return deque.peekFirst();}void poll() {deque.pollFirst();}void offer(int n) {while (!deque.isEmpty() && deque.peekLast() < n) {deque.pollLast();}deque.offerLast(n);}}
}