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;
    }
};