安裝 Unity Recorder

 新版本的 Unity 無法直接安裝 Unity Recorder。

方法：

1. Open Project Manager

2.  clicking  "+" > "Add package by name..."

3.  type "com.unity.recorder"

等待一段時間後即可。

ref

https://forum.unity.com/threads/cant-find-unity-recorder.908690/

在 VirtualBox 上安裝 Ubuntu 與共享資料夾、調整螢幕大小、雙向剪貼簿

簡易步驟：

1. 裝 VirtualBox

2. 下載 Ubuntu iso 檔

3. 新增虛擬機與設定

共享資料夾：

1.  把資料夾加入共用 (記得選取「自動掛載」)

2.  試試看打開資料夾

https://ubuntu.com/tutorials/how-to-run-ubuntu-desktop-on-a-virtual-machine-using-virtualbox#2-create-a-new-virtual-machine

設定與在 virtualbox 的 ubuntu 共享資料夾所遇問題 " You do not have the permissions necessary to view the contents of "

打開 terminal，輸入

sudo adduser $USER vboxsf

後重啟即可解決。

ref

https://askubuntu.com/questions/890729/this-location-could-not-be-displayed-you-do-not-have-the-permissions-necessary

1351. Count Negative Numbers in a Sorted Matrix

解題思路

先以單一個 row 來看，要怎麼找有幾個負數？

根據題目說明的特性，只要找到從哪裡開始都是負數的位置就好。那可以用 binary search。

譬如：[4,3,2,-1]，最後 left 會停在 -1 的位置，那就可以算有幾個負數。

另外，因為下面的 row 肯定負數/正數的邊界只會越靠左，所以可以先存這邊以加快速度。

程式碼

class Solution {
public:
    int helper(vector<vector<int>>& grid, int& right, int row)
    {
        int left = 0;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(grid[row][mid] >= 0)
                left++;
            else
                right--;
        }
        right = min(right, left);
        return grid[row].size() - left;
    }
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0, right = grid[0].size() - 1;
        for(int i=0; i<grid.size(); i++)
        {
            ans += helper(grid, right, i);
        }
        return ans;
    }
};

1318. Minimum Flips to Make a OR b Equal to c

解題思路

每次都把 a, b, c 的LSB 抓出來看，如果 a, b 的 bit OR 不等於 c，就要進一步檢查。

如果 c 是 0，代表 a,b 一定要都是0，所以算 a, b是1的數量。

如果 c 是 1，那就只需要改一個bit，直接加一就好。

程式碼

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        while(a != 0 || b!= 0 || c != 0)
        {
            int m1 = a % 2, m2 = b % 2, m3 = c % 2;
            if((m1 | m2) != m3)
            {
                if(m3 == 0)
                    ans += (m1 == 1) + (m2 == 1);
                else
                    ans += 1;
            }
            a /= 2;
            b /= 2;
            c /= 2;
        }
        return ans;
    }
};

705. Design HashSet

解題思路

昨天的 leetcode daily 也是 hash map ，但已經偷懶用 single array 來解了，今天不能再偷懶下去，不然就失去解題意義(其實是看到discussion裡面有人說：「你確定你會在面試時用這種解法嗎？」)。

hash 通常會搭配 linked-list，而 list 這個 stl 容器就是用 double-linked list 實現的。

另外 vector 的 resize 可以用來動態改變大小。

至於 prime 數字大小怎麼選擇暫時沒想到，這裡的數字是抄別人的。

程式碼

class MyHashSet {
public:
    int size;
    vector<list<int>> table;
    MyHashSet() {
        size = 10007;
        table.resize(size);
    }
    
    void add(int key) {
        int hash = key % size;
        table[hash].push_back(key);
    }
    
    void remove(int key) {
        int hash = key % size;
        table[hash].remove(key);
    }
    
    bool contains(int key) {
        int hash = key % size;
        return find(table[hash].begin(), table[hash].end(), key) != table[hash].end();
    }
};

2542. Maximum Subsequence Score

解題思路

解法參考其他大神，沒指望自己能想出來，只是順手紀錄幾個部分。

pair sorting 是預設 sort first element。

以及

sort(rbegin(), rend()) 是由大排序到小。

程式碼

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> v;
        for(int i=0; i<nums1.size(); i++)
            v.push_back({nums2[i], nums1[i]});
        sort(rbegin(v), rend(v));

        long long ans = 0, currentSum = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto [second, first] : v)
        {
            pq.emplace(first);
            currentSum += first;

            if(pq.size() > k)
            {
                currentSum -= pq.top();
                pq.pop();
            }
            if(pq.size() == k)
                ans = max(ans, currentSum * second);
        }
        return ans;
    }
};

2563. Count the Number of Fair Pairs

解題思路

先假設 sort 好的 input = [0, 1, 4, 4, 5, 7]。很明顯不可能把 array  中任兩個數字的 pair 都檢查一次，這樣時間複雜度太高。

要簡化，直覺想到要調整 boundary，至少某些數字超過 upper 想也知道要排除掉。

用這個邏輯往下繼續想，其實可以用兩個 pointer 構成的boundary，找出當下有幾個符合的 pair。

譬如說當 left = 0, right = 4 時，代表數字 0 跟 1、4、4、5 都是可以選擇的組合，共有四個。

用這個方法找出所有 < upper 的 pair，在減掉其中 < lower 的組合即可。

程式碼

class Solution {
public:
    long long helper(vector<int>& nums, int bound)
    {
        long long ans = 0;
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            while(left < right && nums[left] + nums[right] > bound)
                right--;
            ans += right - left;
            left++;
        }
        return ans;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return helper(nums, upper) - helper(nums, lower - 1);
    }
};

2130. Maximum Twin Sum of a Linked List

解題思路

題目要求兩兩對應點和的最大值。要能找到一個點的對應點，就要能找到中間在哪。

在 linked list 中找中間，可以用 two pointer。

再來觀察 two pointer，當 linked list 是偶數長度時，slow pointer 會一一走訪左半部的 node，停在中間靠右的 node。

所以可以在找中間點的同時，用 stack 紀錄點的數值。當找到中間點時，一個個 pop 出來跟當前的 node value 相加，看看是不是最大值。

程式碼

class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow, *fast;
        fast = slow = head;

        stack<int> st;
        int maxSum = 0;
        while(fast && fast->next)
        {
            st.push(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }
        while(slow)
        {     
            maxSum = max(maxSum, slow->val + st.top());
            st.pop();
            slow = slow->next;
        }
        return maxSum;
    }
};

2095. Delete the Middle Node of a Linked List

解題思路

看到找 linked list 中間節點，就知道是使用 fast-slow pointer。

程式碼

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if(head->next == nullptr)
            return nullptr;
        ListNode *fast, *slow, *prev;
        fast = slow = head;

        while(fast && fast->next)
        {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = slow->next;
        return head;
    }
};

2466. Count Ways To Build Good Strings

解題心得

推導後會發現這是爬樓梯問題的變化版。

程式碼

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;

        int count = 0, mod = 1e9 + 7;
        for(int i=1; i<=high; i++)
        {
            dp[i] = (i >= zero ? dp[i-zero] : 0) + (i >= one ? dp[i-one] : 0);
            dp[i] %= mod;
            if(low <= i && i <= high)
                count = (count + dp[i]) % mod;
        }
        return count;
    }
};