Problems
LeetCode : 493. Reverse Pairs
[動態開點][區間修改][區間和查詢][Segment Tree][BIT]
LeetCode : 2219. Maximum Sum Score of Array
[Prefix Sum][Array]
LeetCode : 1991. Find the Middle Index in Array
[Prefix Sum]
LeetCode : 2171. Removing Minimum Number of Magic Beans
[Prefix Sum][Array][Sorting]
LeetCode : 2483. Minimum Penalty for a Shop
[Prefix Sum]
LeetCode : 2256. Minimum Average Difference
[Prefix Sum]
LeetCode : 2102. Sequentially Ordinal Rank Tracker
[Binary Indexed Tree][Binary Search][Heap (Priority Queue)][Ordered Map]
[Hard]
— — — — — — -
LeetCode : 715. Range Module
[動態開點][懶人標記][區間修改][區間和查詢][Segment Tree][BIT]
LeetCode 673. Number of Longest Increasing Subsequence
LeetCode : 850. Rectangle Area II
LeetCode : 732. My Calendar III
LeetCode : 2158. Amount of New Area Painted Each Day
LeetCode : 327. Count of Range Sum
LeetCode : 218. The Skyline Problem
LeetCode : 315. Count of Smaller Numbers After Self
LeetCode : 1649. Create Sorted Array through Instructions
LeetCode : 307. Range Sum Query — Mutable
LeetCode : 493. Reverse Pairs
BIT 動態開點 + 單點修改。
每一次遍尋一個數字，就將該數字存入 BIT，並查詢目標的範圍。
TODO : 效能很差，想辦法提升效能。
#define LL long long
#define BASE 2147483649LL
#define MAXVAL (BASE * 2)
#define LOWBIT(x) ((x) & (-x))class Solution {
private:
unordered_map<LL, int> bit;
void modify(LL pos, LL val) {
for(LL i = pos;i <= MAXVAL;i += LOWBIT(i)) {
bit[i] += val;
}
}
LL query(LL pos) {
LL tmp = 0;
for(LL i = pos;i > 0;i -= LOWBIT(i)) {
tmp += bit[i];
}
return tmp;
}
public:
int reversePairs(vector<int>& nums) {
int res = 0;
for(LL i = 0;i < nums.size();i++) {
res += (query(MAXVAL) - query(((LL)nums[i] * 2 + BASE)));
modify(nums[i] + BASE, 1);
}
return res;
}
};
LeetCode : 2219. Maximum Sum Score of Array
先取前綴和，就可以 O(1) 得區間和。
#define LL long long
class Solution {
public:
long long maximumSumScore(vector<int>& nums) {
vector<LL> preSum = vector<LL>(nums.size(), 0);
preSum[0] = nums[0];
for(int i = 1;i < nums.size();i++) {
preSum[i] = preSum[i - 1] + nums[i];
}
LL maxVal = INT_MIN;
for(int i = 0;i < nums.size();i++) {
LL tmp = 0;
if(0 == i) {
tmp += preSum.back();
} else {
tmp += preSum.back() - preSum[i - 1];
}
maxVal = max(maxVal, max(preSum[i], tmp));
}
return maxVal;
}
};LeetCode : 1991. Find the Middle Index in Array
class Solution {
public:
int findMiddleIndex(vector<int>& nums) {
// prefix sum
vector<int> pres = vector<int>(nums.size());
pres[0] = nums[0];
for(int i = 1;i < nums.size();i++) {
pres[i] = pres[i - 1] + nums[i];
}
for(int i = 0;i < pres.size();i++) {
int left = (0 == i ? 0 : pres[i - 1]);
int right = pres.back() - pres[i];
if(left == right) {
return i;
}
}
return -1;
}
};LeetCode : 2171. Removing Minimum Number of Magic Beans
// TODO : 效能太差
// 比自己大的要變成自己
// 比自己小的要變成 0
#define LL long longtypedef struct Node Node;
struct Node {
int val;
int num;
};
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
map<int, int> m;
for(int i = 0;i < beans.size();i++) {
m[beans[i]]++;
}
vector<vector<LL>> v;
for(auto it = m.begin();it != m.end();it++) {
v.push_back({it->first, it->second});
}
// 整理由左到右的陣列，以及由右到左的陣列
// 就可以在 O(1) 求得每個元素的解
// O(N) 可找到最小解
vector<LL> l2r = vector<LL>(v.size(), 0);
vector<LL> r2l = vector<LL>(v.size(), 0);
LL nown = v.back()[1];
for(int i = v.size() - 2;i >= 0;i--) {
LL diff = v[i + 1][0] - v[i][0];
r2l[i] = diff * nown + r2l[i + 1];
nown += v[i][1];
}
nown = v[0][1];
LL nowv = v[0][0] * v[0][1];
for(int i = 1;i < v.size();i++) {
l2r[i] = nowv;
nowv += v[i][0] * v[i][1];
}
LL minVal = INT64_MAX;
for(int i = 0;i < v.size();i++) {
minVal = min(minVal, l2r[i] + r2l[i]);
}
return minVal;
}
};
LeetCode : 2483. Minimum Penalty for a Shop
// TODO : 效能太差
// prefixSum
class Solution {
public:
int bestClosingTime(string customers) {
vector<int> n = vector<int>(customers.size(), 0);
vector<int> y = vector<int>(customers.size(), 0);
for(int i = 0;i < customers.size();i++) {
if(i != 0) {
n[i] = n[i - 1];
}
if(customers[i] == 'N') {
n[i]++;
}
}
for(int i = customers.size() - 1;i >= 0;i--) {
if(i != customers.size() - 1) {
y[i] = y[i + 1];
}
if(customers[i] == 'Y') {
y[i]++;
}
}
if(n.back() == 0) {
return n.size();
}
int minVal = INT_MAX;
int ans = -1;
for(int i = 0;i < n.size();i++) {
int p = 0;
p += y[i];
if(i != 0) {
p += n[i - 1];
}
if(p < minVal) {
minVal = p;
ans = i;
}
}
if(n.back() < minVal) {
return n.size();
}
return ans;
}
};LeetCode : 2256. Minimum Average Difference
#define LL long long
class Solution {
public:
int minimumAverageDifference(vector<int>& nums) {
LL nowsum = 0;
LL allsum = 0;
for(int i = 0;i < nums.size();i++) {
allsum += nums[i];
}
LL minVal = INT64_MAX;
LL ans = -1;
for(int i = 0;i < nums.size();i++) {
nowsum += nums[i];
LL lefth = i + 1 == 0 ? 0 : nowsum / (i + 1);
LL righth = nums.size() - i - 1 == 0 ? 0 : (allsum - nowsum) / (nums.size() - i - 1);
if(abs(lefth - righth) < minVal) {
minVal = abs(lefth - righth);
ans = i;
}
}
return ans;
}
};LeetCode : 2102. Sequentially Ordinal Rank Tracker
// TODO : 效能太差了，瀕臨 TLE 邊緣
/*
每個 name 是獨特的
多個 name 會有同個分數
--> 以 [分數 : 個數] 建 segment tree
--> 動態求取前綴和
取得分數區間後，再從 [分數 : name] 中找出是哪個 name
--> 應該是 Binary Indexed Tree
*/
#define LOWBIT(x) (x & (-x))
class SORTracker {
private:
unordered_map<int, map<string, bool>> score2name;
vector<int> score2num;
vector<int> bit;
int totalN = 0;
int nown = 0;
public:
SORTracker() {
score2num = vector<int>(100001, 0);
bit = vector<int>(100001, 0);
}
void modify(int score) {
for(;score < bit.size();score += LOWBIT(score)) {
bit[score] += 1;
}
}
int query(int score) {
int sum = 0;
for(;score >= 1;score -= LOWBIT(score)) {
sum += bit[score];
}
return sum;
}
void add(string name, int score) {
score2name[score][name] = true;
score2num[score]++;
modify(score);
totalN++;
}
string get() {
// do binary search here
nown++;
// 我們的 BIT 是由小記錄到大
// 但這邊要求的順序是相反
// e.g. 總共有 1 ~ 10 個景點
// 題目要求第一好的景點時，我們在這邊要求的是第 10 個景點
int goal = totalN + 1 - nown;
string ans;
int left = 1;
int right = 100000;
int minVal = INT_MAX;
while(left <= right) {
int mid = (left + right) / 2;
int midn = query(mid);
if(midn < goal) {
left = mid + 1;
} else if(midn >= goal) {
right = mid - 1;
minVal = min(minVal, mid);
}
}
int q = query(minVal);
if(q == goal) {
ans = score2name[minVal].begin()->first;
} else {
int index = q - goal;
auto it = score2name[minVal].begin();
/* TODO : 這一步太慢了，理論上這一步也是能二分搜 */
for(int i = 0;i < index;i++) {
if(it != score2name[minVal - 1].end()) {
it++;
}
}
ans = it->first;
}
return ans;
}
};
/**
* Your SORTracker object will be instantiated and called as such:
* SORTracker* obj = new SORTracker();
* obj->add(name,score);
* string param_2 = obj->get();
*/// https://leetcode.com/problems/sequentially-ordinal-rank-tracker/solutions/1623288/decrement-iterator-4-lines/
// 來自 votrubac 的天才解法，實在是太厲害了！
class SORTracker {
private:
set<pair<int, string>> s;
set<pair<int, string>>::iterator it = s.end();
public:
SORTracker() {
}
void add(string name, int score) {
/*
s.insert() returns {iterator,bool}.
it1 會指向當前插入的元素
it 則不會變動
*/
auto it1 = s.insert({-score, name}).first;
if (it == s.end() || *it1 < *it) {
it--;
}
}
string get() {
return (it++)->second;
}
};
/**
* Your SORTracker object will be instantiated and called as such:
* SORTracker* obj = new SORTracker();
* obj->add(name,score);
* string param_2 = obj->get();
*/
