使用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;
就可以達到循環的效果。
計算出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;
}
移除subarray之後，其他的總合為p的倍數，試問最小的subarray長度，如果沒這個答案則回傳-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的所有內容，新增的東西還會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<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;
// 因為題目的關係，每次跌代都必須把最大值減掉其他值。
// 因為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。
// 找出最右邊的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
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;
}
通常Special case都會比較好解決。所以可以的話把General case轉化成Special case。
給你一個linked list和left, right。只反轉從left到right之間的node。
- special case : left == 1，反轉前N個node
- 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。
其中 k 為slinding window的長度。
vector<int> nums;
multiset<int> s; // value
s.insert(nums[i]);
if(s.size() > k) s.erase(s.find(nums[i - k]));
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裡面的內容是否一樣。會使用以下的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;
}
最大公因數，或是稱為Highest common factor(hcf)。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
其實c++有提供gcd的函數，不用自己寫一個。
constexpr int p {2 * 2 * 3};
constexpr int q {2 * 3 * 3};
static_assert(2 * 3 == std::gcd(p, q));
例如在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
題目中很常出現，例如兩兩組合或是三個的組合。這時候如何避免重複列舉就是很重要的技巧。通常使用如下的方法。
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
}
}
}
unordered_set<string> m[26]; // 使用array來存放unordered_set
for(int i = 0; i < 26; ++i) {
for(int j = i + 1; j < 26; ++j) {
}
}
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
}
leetcode 刷題
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe