LeetCode 第47場雙周賽題解
【GiantPandaCV導語】這是LeetCode的第47場雙周賽的題解，本期考察的知識點有暴力，貪心，STL，樹狀數(shù)組等等。
比賽鏈接
https://leetcode-cn.com/contest/biweekly-contest-47/
題目一：找到最近的有相同 X 或 Y 坐標的點
題解思路：直接枚舉每一個點，如果這個點的x坐標或者y坐標與目標點的對應坐標相等，則與答案取最小值，并記錄下最小值的下標。時間復雜度：解題代碼如下：
class Solution {
public:
int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
pair<int, int> ans(INT_MAX, -1);
for (int i = 0; i < points.size(); i++)
if (points[i][0] == x || points[i][1] == y)
ans = min(ans, make_pair(abs(points[i][0] - x) + abs(points[i][1] - y), i));
return ans.second;
}
};
題目二：判斷一個數(shù)字是否可以表示成三的冪的和
題解思路：首先，任何正整數(shù)，都可以表示為\sum_{i=0}^{\infty}3^ik_i，即三進制表示。題意即需要驗證n的三進制表示中，是否每一位都是0或者1，直接模擬短除法即可。時間復雜度：解題代碼如下：
class Solution {
public:
bool checkPowersOfThree(int n) {
while (n) {
if (n % 3 > 1)
return false;
n /= 3;
}
return true;
}
};
題目三：所有子字符串美麗值之和
題解思路：暴力枚舉每一個子串并求其美麗值，但是需要注意枚舉的順序。外層枚舉子串的起始坐標，內(nèi)層枚舉子串的長度，記錄當前子串每個字母出現(xiàn)的次數(shù)，并計算出現(xiàn)次數(shù)的最大值減去出現(xiàn)次數(shù)最小值的差的和。時間復雜度：解題代碼如下：
class Solution {
public:
int beautySum(string s) {
int ans = 0;
for (int st = 0; st < s.size(); st++) {
int cnt[26];
memset(cnt, 0, sizeof(cnt));
for (int len = 1; st + len <= s.size(); len++) {
int idx = s[st + len - 1] - 'a';
cnt[idx]++;
int mx = 0;
int mi = INT_MAX;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0) {
mx = max(mx, cnt[i]);
mi = min(mi, cnt[i]);
}
}
ans += mx - mi;
}
}
return ans;
}
};
題目四：統(tǒng)計點對的數(shù)目
題解思路：
題意比較晦澀，需要仔細閱讀。
首先，需要記錄每個點的度du，然后記錄每個點和他相鄰的點的邊的個數(shù)ecnt，為了方便，這里使用ecnt[u][v]表示點u和點v之間邊的條數(shù)。
對于每一個點對(u,v)，存在兩種情況：
u和v相鄰，則此時連載u或v點上的邊的條數(shù)為du[u]+du[v]-ecnt[u][v]; u和v不相鄰，則此時連載u或v點上的邊的條數(shù)為du[u]+du[v]。
對這兩類情況分開討論即可。具體做法：
建立一個數(shù)組數(shù)組，將每個點u在樹狀數(shù)組下標為du[u]的地方+1; 枚舉每一個點，再枚舉每一個與之相鄰的點，統(tǒng)計每個詢問對于情況1的答案 在樹狀數(shù)組對應位置減去u以及和u相鄰的點的度。 對于每一個詢問queries[j]，需要知道有多少個與u不相鄰，且du[v]>queries[j]-du[u]的v點的個數(shù)，即當前樹狀數(shù)組下標從queries[j]-du[u]+1到結(jié)束的這段區(qū)間的和。 還原步驟3的操作，枚舉下一個u點。
求出的答案還需要進行/2的操作。
時間復雜度**：
解題代碼如下：
class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<unordered_map <int, int> > ecnt(n + 1);
vector<int> du(n + 1);
for (auto& e : edges) {
du[e[0]]++;
du[e[1]]++;
ecnt[e[0]][e[1]]++;
ecnt[e[1]][e[0]]++;
}
int m = edges.size();
int qSize = queries.size();
vector<int> ans(qSize, 0);
m_c = vector<int>(edges.size() + 1);
for (int u = 1; u <= n; u++) {
add(du[u], 1, m);
}
for (int u = 1; u <= n; u++) {
add(du[u], -1, m);
for (auto& p : ecnt[u]) {
int v = p.first;
add(du[v], -1, m);
for (int i = 0; i < qSize; i++) {
int cnt = queries[i];
if (du[u] + du[v] - p.second > cnt) {
ans[i]++;
}
}
}
for (int i = 0; i < qSize; i++) {
int cnt = queries[i];
ans[i] += sum(m) - sum(cnt - du[u]);
}
for (auto& p : ecnt[u]) {
int v = p.first;
add(du[v], 1, m);
}
add(du[u], 1, m);
}
for (auto& a : ans) a /= 2;
return ans;
}
private:
inline int lowbit(int x) {
return x & -x;
}
inline void add(int pos, int val, int m) {
if (pos == 0) {
m_c[0] += val;
return;
}
for (int i = pos; i <= m; i += lowbit(i)) {
m_c[i] += val;
}
}
inline int sum(int pos) {
if (pos < 0) {
return 0;
}
int ans = 0;
for (int i = pos; i > 0; i -= lowbit(i)) {
ans += m_c[i];
}
return ans + m_c[0];
}
vector<int> m_c;
};
題解思路2：其實本題統(tǒng)計du[u]+du[v]-ecnt[u][v]>queries[j]的點的數(shù)目，可以先統(tǒng)計du[u]+du[v]>queries[j]的數(shù)目，這個可以將du數(shù)組排序后使用二指針的方法求得。然后在遍歷ecnt，從總數(shù)中減去du[u]+du[v]-ecnt[u][v]<=queries[j]的數(shù)目即可。
class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<int> du(n);
unordered_map<int, int> cnt;
vector<pair<int, int>> uedge;
for (auto& e : edges) {
e[0]--;
e[1]--;
du[e[0]]++;
du[e[1]]++;
int code = _getCode(e[0], e[1]);
if (!cnt.count(code)) {
uedge.emplace_back(e[0], e[1]);
}
cnt[code]++;
}
vector<int> sortDu = du;
sort(sortDu.begin(), sortDu.end());
vector<int> ans;
for (int q : queries) {
int sum = 0;
int r = n - 1;
for (int l = 0; l < n; l++) {
while (r > l && sortDu[l] + sortDu[r] > q) r--;
sum += n - max(l, r) - 1;
}
for (auto& e : uedge) {
if (du[e.first] + du[e.second] > q &&
du[e.first] + du[e.second] - cnt[_getCode(e.first, e.second)] <= q) {
sum--;
}
}
ans.emplace_back(sum);
}
return ans;
}
private:
int _getCode(int x, int y) {
if (x > y)
swap(x, y);
return x << 16 | y;
}
};
歡迎關(guān)注GiantPandaCV, 在這里你將看到獨家的深度學習分享，堅持原創(chuàng)，每天分享我們學習到的新鮮知識。( ? ?ω?? )?
有對文章相關(guān)的問題，或者想要加入交流群，歡迎添加BBuf微信：
為了方便讀者獲取資料以及我們公眾號的作者發(fā)布一些Github工程的更新，我們成立了一個QQ群，二維碼如下，感興趣可以加入。