550. 游戲玩法分析 IV

題目鏈接

550. 游戲玩法分析 IV

表

• 表Activity的字段為player_id，device_id，event_date和games_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, 5，count(distinct num)的結果為4。
6. 子查詢：將查詢的結果作為表進行查詢。

思路

要求中明確提出了要先查找連續兩天登錄的玩家，然后再獲取這些玩家的數量，最后獲取玩家的總數，再用前者除以后者即可。要注意的是表中玩家的id可能重復，所以在統計數量時需要使用distinct來去重。

代碼

對于獲取連續兩天登錄的玩家數量，有以下的sql語句，其中num就是連續兩天登錄的玩家數量：

selectcount(distinct ss.player_id) num
fromActivity a,(selectplayer_id,date_add(min(event_date), interval 1 day) second_datefromActivitygroup byplayer_id) ss
wherea.player_id = ss.player_id
anda.event_date = ss.second_date

總體的sql語句如下：

selectround(s.num / count(distinct a.player_id), 2) fraction
fromActivity a,(selectcount(distinct ss.player_id) numfromActivity a,(selectplayer_id,date_add(min(event_date), interval 1 day) second_datefromActivitygroup byplayer_id) sswherea.player_id = ss.player_idanda.event_date = ss.second_date) s

380. O(1) 時間插入、刪除和獲取隨機元素

題目鏈接

380. O(1) 時間插入、刪除和獲取隨機元素

標簽

設計 數組 哈希表 數學 隨機化

思路

對于$O(1)$時間復雜度的插入、刪除元素，一般都能想到使用哈希表的方法，不熟悉哈希表的可以去看我寫的這篇博客——數據結構——哈希表。本題只需要使用一個鏈表用來存儲元素，再使用哈希表HashMap來映射元素和它的下標，最后使用隨機類Random來獲取隨機下標。

• 對于插入，先檢查待插入元素是否在數組中存在，如果存在，就不添加，并且返回false；否則將其放在鏈表末尾，并建立它的值與下標的映射。
• 對于刪除，先檢查待插入元素是否在數組中存在，如果不存在，就不刪除，并且返回false；否則讓鏈表的最后一個元素覆蓋待刪除元素，修改最后一個元素的值與下標的映射，并移除 待刪除元素 和 它的值與下標的映射。
• 對于隨機訪問，可以使用java.util.Random類的random()方法來生成，給random()方法傳入鏈表的長度即可返回一個范圍為[0, 鏈表長度)的隨機下標。

代碼

class RandomizedSet {public RandomizedSet() {}public boolean insert(int val) {// 1. 如果存在這個元素，則返回fasleif (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. 如果不存在這個元素，則返回falseif (!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) {// 如果有一個值不一樣，則返回falseif (new1.val != slow.val) {return false;}slow = slow.next;new1 = new1.next;}// 4. 所有值都一樣了，返回truereturn true;}
}