550. 游戏玩法分析 IV

题目链接

550. 游戏玩法分析 IV

  • Activity的字段为player_iddevice_idevent_dategames_played

要求

  • 编写解决方案,报告在首次登录的第二天再次登录的玩家的 比率,四舍五入到小数点后两位。换句话说,你需要计算从首次登录日期开始至少连续两天登录的玩家的数量,然后除以玩家总数。

知识点

  1. round():四舍五入函数。
  2. count():统计数量函数。
  3. min():取最小值函数。
  4. date_add():将一个日期加上指定时间的函数,它的第二个参数通常有interval作为前缀,表示间隔。例如date_add('2020-1-20', interval 1 day)表示2020-1-21
  5. distinct:将某个字段的重复值去除(去重)。例如num的取值有1, 1, 2, 4, 5,则distinct num的结果为1, 2, 4, 5count(distinct num)的结果为4
  6. 子查询:将查询的结果作为表进行查询。

思路

要求中明确提出了要先查找连续两天登录的玩家,然后再获取这些玩家的数量,最后获取玩家的总数,再用前者除以后者即可。要注意的是表中玩家的id可能重复,所以在统计数量时需要使用distinct来去重。

代码

对于获取连续两天登录的玩家数量,有以下的sql语句,其中num就是连续两天登录的玩家数量:

select
    count(distinct ss.player_id) num
from
    Activity a,
    (
        select
            player_id,
            date_add(min(event_date), interval 1 day) second_date
        from
            Activity
        group by
            player_id
    ) ss
where
    a.player_id = ss.player_id
and
    a.event_date = ss.second_date

总体的sql语句如下:

select
    round(s.num / count(distinct a.player_id), 2) fraction
from
    Activity a,
    (
        select
            count(distinct ss.player_id) num
        from
            Activity a,
            (
                select
                    player_id,
                    date_add(min(event_date), interval 1 day) second_date
                from
                    Activity
                group by
                    player_id
            ) ss
        where
            a.player_id = ss.player_id
        and
            a.event_date = ss.second_date
    ) s

380. O(1) 时间插入、删除和获取随机元素

题目链接

380. O(1) 时间插入、删除和获取随机元素

标签

设计 数组 哈希表 数学 随机化

思路

对于 O ( 1 ) O(1) O(1)时间复杂度的插入、删除元素,一般都能想到使用哈希表的方法,不熟悉哈希表的可以去看我写的这篇博客——数据结构——哈希表。本题只需要使用一个链表用来存储元素,再使用哈希表HashMap来映射元素和它的下标,最后使用随机类Random来获取随机下标。

  • 对于插入,先检查待插入元素是否在数组中存在,如果存在,就不添加,并且返回false;否则将其放在链表末尾,并建立它的值与下标的映射。
  • 对于删除,先检查待插入元素是否在数组中存在,如果不存在,就不删除,并且返回false;否则让链表的最后一个元素覆盖待删除元素,修改最后一个元素的值与下标的映射,并移除 待删除元素 和 它的值与下标的映射。
  • 对于随机访问,可以使用java.util.Random类的random()方法来生成,给random()方法传入链表的长度即可返回一个范围为[0, 链表长度)的随机下标。

代码

class RandomizedSet {

    public RandomizedSet() {}
    
    public boolean insert(int val) {
        // 1. 如果存在这个元素,则返回fasle
        if (exist(val)) {
            return false;
        }

        // 2. 将每个元素都存放在链表的末尾,它的下标就是此时链表的长度
        int index = data.size();
        data.add(val);

        // 3. 建立元素的值与下标的映射
        indices.put(val, index);

        return true;
    }
    
    public boolean remove(int val) {
        // 1. 如果不存在这个元素,则返回false
        if (!exist(val)) {
            return false;
        }

        // 2. 通过映射获取这个元素在链表的下标
        int index = indices.get(val);

        // 3. 获取链表最后一个元素的下标和它的值
        int lastIndex = data.size() - 1;
        int last = data.get(lastIndex);

        // 4. 用最后一个元素覆盖待删除元素
        data.set(index, last);

        // 5. 修改最后一个元素的下标为待删除元素的下标
        indices.put(last, index);

        // 6. 移除此时的最后一个元素,也就是待删除元素
        data.remove(lastIndex);
        
        // 7. 移除待删除元素的值与下标的映射
        indices.remove(val);

        return true;
    }
    
    public int getRandom() {
        return data.get(random.nextInt(data.size()));
    }

    // 判断元素是否在data中存在,即判断这个元素是否有下标
    private boolean exist(int val) {
        return indices.containsKey(val);
    }

    /**
     * 存储元素
     */
    private final List<Integer> data = new ArrayList<>();

    /**
     * 映射元素和它的下标,key为元素的值,value为元素的下标
     */
    private final Map<Integer, Integer> indices = new HashMap<>();

    /**
     * 用来生成随机的下标
     */
    private final Random random = new Random();

}

234. 回文链表

题目链接

234. 回文链表

标签

栈 递归 链表 双指针

思路

把链表分成两部分,然后反转前半部分,对比这两部分是否完全相同,如果有一个值不相同,则返回false。

如何把链表分为两部分?很简单,用两个指针,慢指针每次走一格slow = slow.next,快指针每次走两格fast = fast.next.next,直到fast == null || fast.next == null为止,最后的慢指针可能指向链表后半部分的头部。当fast == null作为结束条件时,说明链表的节点数为偶数,慢指针指向链表后半部分的头部;当fast.next == null作为结束条件时,说明链表的节点数为奇数,此时需要将慢指针向后移一格,之后的慢指针才指向链表后半部分的头部。

如何反转链表?很简单,用三个指针new1, old1, old2,它们分别代表新链表的头节点旧链表的前一个节点旧链表的后一个节点,用old1从待反转链表的头部开始一直向后遍历,直到指向null,每次都先用old2保存old1的下一个节点,然后再让old1指向new1(这步就是反转链表的关键,新链表是从尾部向头部建的,每次都往新链表的头部添加一个节点),接着将old1赋值给new1,最后将old2赋值给old1。代码如下:

public ListNode reverseList(ListNode head) {
	ListNode new1 = null, old1 = head;
	while (old1 != null) {
		ListNode old2 = old1.next;
		old1.next = new1;
		new1 = old1;
		old1 = old2;
	}
	return old1;
}

注意:本题的题解并没有明确写出用来反转链表的方法,而是将反转链表的操作与划分链表的操作合二为一。

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head; // 慢指针,反转完之后指向链表后半部分的头节点
        ListNode fast = head; // 快指针
        ListNode old1 = head; // 用于反转的指向旧值的指针
        ListNode new1 = null; // 用于反转的指向新值的指针,反转完之后指向前半部分的头节点

        // 1. 将链表的前半部分反转
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针每次走两格
            slow = slow.next; // 慢指针每次走一格

            // 反转链表前半部分的某个节点,此处利用了反转链表的思想
            old1.next = new1;
            new1 = old1;

            // 更新old1的值
            old1 = slow;
        }

        // 2. 如果是奇数个节点,则少比较一次,让slow指向下一个节点
        if (fast != null) {
            slow = slow.next;
        }

        // 3. 比较 前半部分的反向链表 和 后半部分的链表 是否一模一样
        while (new1 != null) {
            // 如果有一个值不一样,则返回false
            if (new1.val != slow.val) {
                return false;
            }
            slow = slow.next;
            new1 = new1.next;
        }

        // 4. 所有值都一样了,返回true
        return true;
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部