头像设计易做图网站,秦皇岛开发区,东营做网站哪家好,wordpress更换默认目录 1141. 查询近30天活跃用户数题目链接表要求知识点思路代码 134. 加油站题目链接标签普通版思路代码 简化版思路代码 142. 环形链表 II题目链接标签思路代码 1141. 查询近30天活跃用户数
题目链接
1141. 查询近30天活跃用户数
表
表Activity的字段为user_id#xff0c… 目录 1141. 查询近30天活跃用户数题目链接表要求知识点思路代码 134. 加油站题目链接标签普通版思路代码 简化版思路代码 142. 环形链表 II题目链接标签思路代码 1141. 查询近30天活跃用户数
题目链接
1141. 查询近30天活跃用户数
表
表Activity的字段为user_idsession_idactivity_date和activity_type。
要求
编写解决方案统计截至 2019-07-27包含2019-07-27近 30 天的每日活跃用户数当天只要有一条活动记录即为活跃用户。以 任意顺序 返回结果表。
知识点
date_add()将日期加上指定时间的函数第二个参数经常有interval做前缀表示间隔。count()统计个数的函数。group by按某些字段分组。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_date134. 加油站
题目链接
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;}
}
