LeetCode 1141, 134, 142

1141. 查询近30天活跃用户数

题目链接

1141. 查询近30天活跃用户数

表

• 表Activity的字段为user_id，session_id，activity_date和activity_type。

要求

• 编写解决方案，统计截至 2019-07-27（包含2019-07-27），近 30 天的每日活跃用户数（当天只要有一条活动记录，即为活跃用户）。
• 以 任意顺序 返回结果表。

知识点

1. date_add()：将日期加上指定时间的函数，第二个参数经常有interval做前缀，表示间隔。
2. count()：统计个数的函数。
3. group by：按某些字段分组。
4. between and：判断某个值是否在这个闭区间内。num between 20 and 30相当于num >= 30 && num <= 30。

思路

本题只是统计在2019-07-27和它的前29天中每天的用户数，一天当中重复的用户算一条记录。思路很明显了，使用分组函数按天数分组，然后对用户的id使用去重统计，注意，判断条件是日期在2019-07-27和它的前29天之内。

代码

selectactivity_date day,count(distinct user_id) active_users
fromActivity
whereactivity_date between date_add('2019-07-27', interval -29 day) and '2019-07-27'
group byactivity_date

134. 加油站

题目链接

134. 加油站

标签

贪心 数组

普通版

思路

暴力的思路是：将整个数组都遍历一次，每次都判断能否以当前下标为起始加油站的下标绕环一周。但是这样会超时，因为有一个样例的gas, cost数组全都是0。

所以得想一个降低时间复杂度的方法，具体的做法就是合理利用之前计算的结果：如果从一个下标i作为起始加油站无法到达另一个下标i + k，则说明以i到i + k作为起始加油站的情况都无法到达i + k。

这是因为如果从i无法到i + k（且k > 0），则说明当下标为i + k时，这次消耗的 比 之前积累的 还多，但是如果i比原来还大，则积累的油量变少了，就更不能到达i + k了。所以可以跳过中间的无效点，从i + k + 1处开始进行下一次的判断。当k == 0时，说明下标为i的加油站的油量比消耗的少，则从i + 1处进行下一次的判断，可以将这个分支与上面的分支并起来，即从i + k + 1处开始进行下一次的判断。

代码

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;int i = 0;while (i < n) { // i是出发时加油站的下标int rest = 0; // rest是目前剩余的总油量int k = 0; // k是经过加油站的个数while (k < n) {int j = (i + k) % n; // j是当前经过加油站的下标rest += gas[j] - cost[j];// 如果剩余的油量比0小，则无法绕环一周，退出循环if (rest < 0) {break;}k++;}// 如果经过的加油站数等于加油站的总数，则返回这个下标if (k == n) {return i;}// 跳过中间无效的点，从i + k + 1处进行下一次的判断i += k + 1;}// 发现无法从任何一个加油站作为起始点绕环一周，返回-1return -1;}
}

简化版

思路

简化版的思想是：如果以start作为起始加油站的下标并且满足三个条件，那么start就是题目所求的答案。第一个是以小于start的值作为起始加油站的下标无法绕环一周，第二个是以start作为起始加油站的下标可以走到数组的最后一个下标，最后一个是全程的总剩余油量大于等于0（若全程的总剩余油量小于0，则无法绕环一周）。

简化版 更新起始加油站下标 的思路和普通版是一样的，但是它少了很多计算（比如取余的计算，因为简化版不需要真正绕环一周，只需要找到一个下标满足上述的三个条件），这就使得它的耗时比普通版小。

代码

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int total = 0; // total是总剩余的油量int rest = 0; // rest是以start作为起始加油站的下标剩余的油量int start = 0; // start是起始加油站的下标for (int i = 0; i < gas.length; i++) {int sub = gas[i] - cost[i];rest += sub;total += sub;// 如果以start作为起始加油站的下标剩余油量小于0，则将start更新到i + 1if (rest < 0) {rest = 0;start = i + 1;}}// 如果总剩余的油量小于0，则说明无法绕环一周；否则唯一解为startreturn total < 0 ? -1 : start;}
}

142. 环形链表 II

题目链接

142. 环形链表 II

标签

哈希表 链表 双指针

思路

这道题可以使用Floyd判圈算法，不知道原理的可以去看这篇文章：算法——Floyd判圈算法。

这里讲一下思路：使用快慢指针fast, slow，快指针每次走两步fast = fast.next.next，慢指针每次走一步slow = slow.next，如果发现fast == null || fast.next == null，则这个链表没有环；否则两个指针就会相遇，相遇后把慢指针slow放到链表头部head处，快指针fast不动，仍在相遇点，此时让两个指针同速，每次都只走一步fast = fast.next, slow = slow.next，直到发生第二次相遇，第二次相遇点就是环的入口。

代码

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {slow = head;while (slow != fast) {fast = fast.next;slow = slow.next;}return slow;}}return null;}
}