Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) ans[i] = nums[nums[i]];
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), prev = 0;
        vector<int> ans(2);
        for (int num : nums) {
            if (num == prev) {
                ans[0] = num;
            } else if (num - prev > 1) {
                ans[1] = prev + 1;
            }
            prev = num;
        }
        if (nums.back() != n) ans[1] = n;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 10001;
int c[N];
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        memset(c, 0, (n + 1) * 4);
        vector<int> ans(2);
        for (int num : nums)
            if (++c[num] == 2)
                ans[0] = num;
        for (int i = 1; i <= n; ++i)
            if (c[i] == 0) {
                ans[1] = i;
                break;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(), mask = 0, i = 0;
        while (++i <= n) mask ^= i;
        for (int num : nums) mask ^= num;
        i = 0, mask = mask & (-mask); // lowbit.
        int num1 = 0, num2 = 0;
        while (++i <= n) {
            if ((i & mask) == 0) num1 ^= i;
            else num2 ^= i;
        }
        for (int num : nums) {
            if ((num & mask) == 0) num1 ^= num;
            else num2 ^= num;
        }
        for (int num : nums) {
            if (num == num1)
                return {num1, num2};
            if (num == num2)
                return {num2, num1};
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(), idx;
        for (int i = 0; i < n; ++i) {
            idx = (nums[i] - 1) % n;
            nums[idx] += n;
        }
        vector<int> ans(2);
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 2 * n)
                ans[0] = i + 1;
            else if (nums[i] <= n)
                ans[1] = i + 1;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL l, r, ans;
vector<LL> s;
void dfs(int c, LL x) {
    s.emplace_back(x);
    if (c == 10) return;
    dfs(c + 1, 10 * x + 4);
    dfs(c + 1, 10 * x + 7);
}
int main() {
    s.clear();
    dfs(0, 0);
    sort(s.begin(), s.end());
    scanf("%lld%lld", &l, &r);
    ans = 0;
    for (int i = 1; i < s.size(); ++i) {
        LL a = s[i - 1] + 1, b = s[i];
        ans += s[i] * max(0ll, min(r, b) - max(l, a) + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int N = 100;
int n;
int a[N];
int main() {
    cin >> n;
    int p = 0, o = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] & 1) ++o;
        else ++p;
    }
    cout << (o & 1 ? o : p) << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        for (auto &c : s) ++m[c];
        vector<pair<int, int>> v;
        for (auto &it : m) v.emplace_back(it);
        sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ans;
        for (auto &[c, n] : v)
            for (int i = 0; i < n; ++i)
                ans.push_back(c);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        int maxFreq = 0;
        for (auto &c : s) maxFreq = max(maxFreq, ++m[c]);
        vector<string> buckets(maxFreq + 1);
        for (auto &[c, n] : m) buckets[n].push_back(c);
        string ans;
        for (int i = maxFreq; i; --i)
            for (auto &c : buckets[i])
                for (int k = 0; k < i; ++k)
                    ans.push_back(c);
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(begin(costs), end(costs));
        int ans = 0;
        for (int cost : costs) {
            if ((coins -= cost) >= 0)
                ++ans;
            else
                break;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 100001;
int c[N];
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        memset(c, 0, sizeof c);
        for (int cost : costs) ++c[cost];
        int ans = 0;
        for (int i = 1; i < N && i <= coins; ++i) {
            if (c[i]) {
                int x = min(c[i], coins / i);
                coins -= i * x;
                ans += x;
            }
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const numWays = (n, relation, k) => {
    const t = n - 1,
        g = new Array(n).fill(0).map(() => new Array());
    let ans = 0;
    for (const [u, v] of relation)
        g[u].push(v);
    const dfs = (u, steps) => {
        if (steps == k) {
            if (u == t) ++ans;
            return;
        }
        for (const v of g[u])
            dfs(v, steps + 1);
    }
    dfs(0, 0);
    return ans;
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Codec {
public:
    string serialize(TreeNode* root) {
        string ans;
        dfs(root, ans);
        return ans;
    }
    void dfs(TreeNode* root, string& curr) {
        if (!root)  {
            curr += "null,";
            return;
        }
        curr += to_string(root->val) + ",";
        dfs(root->left, curr);
        dfs(root->right, curr);
    }
    TreeNode* deserialize(string data) {
        istringstream ss(data);
        string s;
        function<TreeNode*(void)> dfs = [&]() {
            TreeNode* ans;
            if (getline(ss, s, ',')) {
                ans = parse(s);
                if (ans) {
                    ans->left = dfs();
                    ans->right = dfs();
                }
            }
            return ans;
        };
        return dfs();
    }
    TreeNode* parse(string& s) {
        if (s == "null") return nullptr;
        return new TreeNode(stoi(s));
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int N = 10001;
struct Node {
    int shop, movie, price;
    bool operator < (const Node t) const {
        if (price != t.price) return price < t.price;
        if (shop != t.shop) return shop < t.shop;
        return movie < t.movie;
    }
};
set<Node> in[N]; // available.
set<Node> out; // rent.
map<pair<int, int>, int> pr; // <shop, movie> => price.
class MovieRentingSystem {
public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (int i = 0; i < N; ++i) in[i].clear();
        out.clear();
        pr.clear();
        for (auto& e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            in[movie].insert({shop, movie, price});
            pr[{shop, movie}] = price;
        }
    }
    
    vector<int> search(int movie) {
        vector<int> ans;
        for (auto& m : in[movie]) {
            ans.emplace_back(m.shop);
            if (ans.size() == 5) break;
        }
        return ans;
    }
    
    void rent(int shop, int movie) {
        auto it = in[movie].find({shop, movie, pr[{shop, movie}]});
        out.insert(*it);
        in[movie].erase(it);
    }
    
    void drop(int shop, int movie) {
        auto it = out.find({shop, movie, pr[{shop, movie}]});
        in[movie].insert(*it);
        out.erase(it);
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        for (auto& e : out) {
            ans.push_back({e.shop, e.movie});
            if (ans.size() == 5) break;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import defaultdict
from sortedcontainers import SortedList

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self._prices = dict()
        self._available = defaultdict(SortedList)
        self._rent = SortedList()
        for shop, movie, price in entries:
            self._available[movie].add((price, shop))
            self._prices[(shop, movie)] = price

    def search(self, movie: int) -> List[int]:
        a = self._available
        if movie not in a: return []
        return [shop for (price, shop) in a[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = self._prices[(shop, movie)]
        self._available[movie].discard((price, shop))
        self._rent.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self._prices[(shop, movie)]
        self._rent.discard((price, shop, movie))
        self._available[movie].add((price, shop))

    def report(self) -> List[List[int]]:
        return [(shop, movie) for price, shop, movie in self._rent[:5]]

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:
        MOD = 10**9 + 7
        g = collections.defaultdict(list)
        for curr, prev in enumerate(prevRoom): g[prev].append(curr)
    
        def dfs(curr):
            if not g[curr]: return 1, 1
            ans, l = 1, 0
            for next in g[curr]:
                tmp, r = dfs(next)
                ans = (ans * tmp * math.comb(l + r, r)) % MOD
                l += r
            return ans, l + 1

        return dfs(0)[0]

Reference: [Python/C++] clean DFS solution with explanation

0%