# Leetcode刷題學習筆記 -- 小技巧/code snipe
### mod
使用mod如果目標是負數，則mod出來的結果也是負數。
例如:

for(int i = 5; i >= -5; --i)
    cout << i % 5 << endl;

//3 % 3 = 0
//2 % 3 = 2
//1 % 3 = 1
//0 % 3 = 0     0 mod 任何數皆為0
//-1 % 3 = -1
//-2 % 3 = -2
//-3 % 3 = 0    整數倍依然為0

如果不想要有負數，必須使用以下的方法，把原本的結果 + n 再mod一次。 但是注意結果不是原本的結果取abs()。

int floorMod(int x, int n) {
    return ((x % n) + n) % n; 
}

for(int i = 3; i >= -3; --i)
    cout << i << " % 3 = " << ((i % 3) + 3) % 3 << endl;
//3 % 3 = 0
//2 % 3 = 2
//1 % 3 = 1
//0 % 3 = 0
//-1 % 3 = 2    原本是-1
//-2 % 3 = 1    原本是-2
//-3 % 3 = 0

這樣的作法有一種循環的效果，題目如果要求cyclic可以這樣求下一個index。
0->1->2->0->1->2... step = 1
0->2->1->0->2->1... step = -1

例如:我要使用cyclic queue, 其中queue會被重複複寫，我可以用一個index來表示，往前就index + 1，往後index - 1。但是如果這樣做，index會有超出queue size或是小於0的情況。所以就可以使用

idx = ((idx + 1) % sz + sz) % sz;
//或是
idx = ((idx - 1) % sz + sz) % sz;

就可以達到循環的效果。

+ 或是要mod的target會有負數情況，也可以使用此技巧。
#### [974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/description/)
計算出subarray個數，其中subarray sum為k的倍數。

    // pfs + n % k     = -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 index
// pdf + n % k + k % k =  0,  1,  2,  3,  4, 0, 1, 2, 3, 4, 0 cyclic 
// 
// pfs(cur) - pfs(prev) = k * m
// pfs(cur) % k - pfs(prev) % k = 0
// pfs(cur) = pfs(prev)
//
int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> m{{0, 1}}; //prefix sum, count
    int pfs{0}, ans{0};
    for(auto& n : nums) {
        pfs = ((pfs + n) % k + k) % k;
        ans += m[pfs];
        m[pfs]++;
    }

    return ans;
}

#### [1590. Make Sum Divisible by P](https://leetcode.com/problems/make-sum-divisible-by-p/)
移除subarray之後，其他的總合為p的倍數，試問最小的subarray長度，如果沒這個答案則回傳-1。
> 1. 這邊的重點是 pfs - sum會有負數情況，所以使用

int target = ((pfs - sum) % p + p) % p;

class Solution {
    // sum - (pfs(cur) - pfs(prev)) = p * m
    // sum % p = pfs(cur) % p - pfs(prev) % p
    // pfs(prev) % p = pfs(cur) % p - sum % p
public:
    int minSubarray(vector<int>& nums, int p) {
        unordered_map<int, int> m{{0, -1}}; //pfs, latest index
        int sum = accumulate(nums.begin(), nums.end(), 0l) % p;
        if(sum % p == 0) return 0;
        long pfs{0};
        int ans = nums.size();
        for(int i = 0; i < nums.size(); ++i) {
            pfs = (pfs + (long)nums[i]) % p;
            int target = ((pfs - sum) % p + p) % p;
            if(m.count(target))
                ans = min(ans, i - m[target]);
            m[pfs] = i;
        }
        return ans == nums.size() ? -1 : ans;
    }
};

### queue的走訪
走訪queue的所有內容，新增的東西還會push到queue裡面。
避免拿到新增加的資料，所以使用以下的code。
因為變數i只會被initial一次，所以當下的q.size()會被記錄下來。
==不可以使用 i < q.size() 來判斷，因為for loop每次都會讀取q.size()==。

queue<TreeNode *> q;
while(!q.empty()) {
    for(int i = q.size(); i > 0; --i) {
        TreeNode *p = q.front(); q.pop();
        ...
    }
}

或是可以把答案和數值組成pair放到queue裡面，可以少一個for loop

queue<pair<int, int>> q;
q.push({v, ans});
while(!q.empty()) {
    auto [v, ans] = q.fornt(); q.pop();
    if(v == target) return ans;
    // get new value
    ...
    q.push(nv, ans + 1); // 推進去新的點nv, 還要更新ans
}

### 無條件進位
加上要進位的(單位-1)，即可達到無條件進位。
例如:

// 一百以下無條件進位
int newx = (oldx + 99) / 100; // 當oldx的數字為1-99 時，自然會進到百位，只有當數字為0或是100的時候不會進位。 

int newx = (oldx + mid - 1) / mid; // 除完之後無條件進位

### 從沒排序的vector中，每次都可以用binary search找出要的數值。

vector<int> nums; // 沒排列的vector
set<int> s(nums.begin(), nums.end()); // 放入set中，以後方便查詢
auto it = s.lower_bound(v); // 用binary search 找s中是否有大於等於v的數值。

### 將資料結合
有兩個vector有對應的關係。需要對這兩個進行排序。則可以把這兩個vector結合成一個。

vector<int> difficulty, vector<int> profit;
vector<int> jobs;
for(int i = 0; i < profit.size(); ++i)
    jobs.push_back({difficulty[i], profit[i]});
sort(jobs.begin(), jobs.end());

### 刪除重複的資料
把資料推進unordered_set<T>再拿出來，就可以刪除重複資料。

vector<string> words;
unordered_set<string> s(words.begin(), words.end());
for(auto& w : s)
    cout << w << endl;

### 使用mod來優化多次的減法
[Explain how the % works](https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/573511/Explain-how-the-works)

// 因為題目的關係，每次跌代都必須把最大值減掉其他值。
// 因為max很大，所以每次跌代都是max - (a1 + a2)
target = [max, a1, a2];
1st iteration : target = [max-(a1+a2), a1, a2]
2nd iteration : target = [max-2*(a1+a2), a1, a2]
...
nth iteration : target = [max-n*(a1+a2), a1, a2]
// Can we accelerate the process? Yes
max-n*(a1+a2) = max % (a1+a2)
// special case
// 當 max % (a1 + a2) == 0，因為題目只要減到1，所以必須特別處理。
// mod的結果會是[0, a1 + a2 - 1]，但是當結果為0是，我們是要用a1 + a2。

### right most set bit

// 找出最右邊的set bit
x & -x;
// 減少自己 right most set bit
// 使用在binary index tree中 getSum()
x -= x & -x;
// 加上自己 right most set bit
// 使用在binary index tree中 update()
x += x & -x;

### 使用走訪兩次來產生雙倍陣列的效果
常常有的題目會說陣列是cyclic，最有效的方法是把原本的陣列接在後面，但是可以透過走訪兩次來達到同樣的效果。
例如 : [503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/)

vector<int> nextGreaterElements(vector<int>& nums) {
    int sz = nums.size();
    stack<int> s;
    vector<int> rtn(sz);
    for(int i = 2 * sz - 1; i >= 0; --i) {
        while(!s.empty() && nums[i % sz] >= s.top())
            s.pop();
        rtn[i % sz] = s.empty() ? -1 : s.top();
        s.push(nums[i % sz]);
    }
    return rtn;
}

### 把General case化成Special case
通常Special case都會比較好解決。所以可以的話把General case轉化成Special case。
#### [92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/)
給你一個linked list和left, right。只反轉從left到right之間的node。

> 1. special case : left == 1，反轉前N個node
> 2. general case : left != 1，把下一個node當成新的head，並且修正left和right。

class Solution {
    ListNode *succesor;
    ListNode *reverseN(ListNode *head, int n) {
        if(n == 1) {
            succesor = head->next;
            return head;
        }
        ListNode *last = reverseN(head->next, n - 1);
        head->next->next  = head;
        head->next = succesor;
        return last;
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == 1) return reverseN(head, right);
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }
};

### Slinding Window Maximum/Minimum
在一個slinding window 中有效的取得maximum或是minimum。
其中 k 為slinding window的長度。
1. 使用multiset

vector<int> nums;
multiset<int> s; // value
s.insert(nums[i]);
if(s.size() > k) s.erase(s.find(nums[i - k]));

2. 使用deque

vector<int> nums;
deque<int> deq; // index
// insert
while(!deq.empty() && nums[idx] >= nums[deq.back()]) 
    deq.pop_back();
deq.push_back(idx);
// get 
while(!deq.empty() && idx - deq.front() > k) 
    deq.pop_front();
return nums[deq.front()];

### 快速比較兩個同長度的vector
通常有時候需要比較兩個同樣長度的vector裡面的內容是否一樣。會使用以下的code。c++ 會自動比較兩個vector相同index是否一樣。但是time complexity : O(N)，space complexity 也是O(N)。

int len = 10;
vector<int> target(len);
vector<int> nums(len);
if(target == nums) ...

如果數字小於10，也就是0~9，且vector的長度沒很長，則可以轉成數字比較。

long getNum(vector<int>& vec) {
    long res = 0;
    for(int i = 0; i < vec.size(); ++i)
        res += pow(10, i) * vec[i];
    return res;
}

### GCD(Greatest common divisor)
最大公因數，或是稱為Highest common factor(hcf)。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);                                  
}

其實c++有提供[gcd](https://en.cppreference.com/w/cpp/numeric/gcd)的函數，不用自己寫一個。

constexpr int p {2 * 2 * 3};
constexpr int q {2 * 3 * 3};
static_assert(2 * 3 == std::gcd(p, q));

### 計算child node個數
例如在binary tree中計算每個node的child個數。分別計算left和right的個數，最後再加上root(1)，就是全部的個數。

int count(TreeNode* root) {
    if(!root) return 0;
    int l = count(root->left);
    int r = count(root->right);
    return l + r + 1;
}

因為這是從root開始計算，如果只要知道每個node的child個數，就必須先找到target node然後再呼叫count()，這樣有點浪費時間，其實在計算root的時候就會得到target node的答案，我們只要把結果存起來就好。

int left, right, target;
int count(TreeNode* root) {
    if(!root) return 0;
    int l = count(root->left);
    int r = count(root->right);
    if(root->val == target) {
        left = l;
        right = r;
    }
    return l + r + 1;
}

例如:[1145. Binary Tree Coloring Game](https://leetcode.com/problems/binary-tree-coloring-game/description/)
### 列舉所有的組合
題目中很常出現，例如兩兩組合或是三個的組合。這時候如何避免重複列舉就是很重要的技巧。通常使用如下的方法。

vector<char> list; //a, b, c, d, e
for(int i = 0; i < list.size(); ++i) {
    for(int j = i + 1; j < list.size(); ++j) {
        cout << list[i] << list[j] << endl;
        // ab, ac, ad, ae
        // bc, bd, be
        // cd, ce
        // de
    }                               
}

三個的組合

vector<char> list; //a, b, c, d, e
for(int i = 0; i < list.size(); ++i) {
    for(int j = i + 1; j < list.size(); ++j) {
        for(int k = j + 1; k < list.size(); ++k) {
            cout << list[i] << list[j] << list[k] << endl;
            // abc, abd, abe, acd, ace, ade
            // bcd, bce, bde
            // cde
        }
    }                               
}

+ 這是組合不是排列，所以ab == ba
+ 就是因為是組合，所以只要考慮拿比自己還後面的element來拚
+ 因為使用了for loop，所以==容器必須使用可以依序訪問的==，如: vector, array。unordered_set, unordered_map就不太適合。

unordered_set<string> m[26]; // 使用array來存放unordered_set                                       
for(int i = 0; i < 26; ++i) {
    for(int j = i + 1; j < 26; ++j) {
        
    }    
}      

+ 如果是求排列數 = 組合數 * N!

例如:[2306. Naming a Company](https://leetcode.com/problems/naming-a-company/)

long long distinctNames(vector<string>& ideas) {
    unordered_set<string> m[26];
    for(auto& idea : ideas)
        m[idea[0] - 'a'].insert(idea.substr(1));
    long long ans{0L};
    for(int i = 0; i < 26; ++i) {
        for(int j = i + 1; j < 26; ++j) {
            long long cnt1{0L}, cnt2{0L};
            for(auto& suffix : m[i])
                if(!m[j].count(suffix)) cnt1++;
            for(auto& suffix : m[j])
                if(!m[i].count(suffix)) cnt2++;
            ans += cnt1 * cnt2;
        }
    }
    return ans * 2; // 因為是排列，所以組合數*2
}

###### tags: `leetcode` `刷題`