Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int T, M;
int t[101], v[101];
int dp[101][1001];
int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; ++i)
        cin >> t[i] >> v[i];
    for (int i = 1; i <= M; ++i)
        for (int j = 0; j <= T; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= t[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]] + v[i]);
        }
    cout << dp[M][T] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int T, M;
int t[101], v[101];
int dp[1001];
int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; ++i)
        cin >> t[i] >> v[i];
    for (int i = 1; i <= M; ++i)
        for (int j = T; j >= t[i]; --j)
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
    cout << dp[T] << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        int l = 0, ans = 0;
        long sum = 0;
        for (int r = 0; r < n; ++r) {
            sum += nums[r];
            while (l < r && sum + k < static_cast<long>(nums[r]) * (r - l + 1))
                sum -= nums[l++];
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> m;
        for (Employee* e : employees)
            m[e->id] = e;
        function<int(int)> dfs = [&](int id) {
            Employee* e = m[id];
            int ans = e->importance;
            for (int sub : e->subordinates)
                ans += dfs(sub);
            return ans;
        };
        return dfs(id);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> m;
        for (const auto& e : employees)
            m[e->id] = e;
        int ans = 0;
        queue<int> q;
        q.push(id);
        while (!q.empty()) {
            int curr = q.front(); q.pop();
            Employee* e = m[curr];
            ans += e->importance;
            for (int sub : e->subordinates)
                q.push(sub);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (const auto& num: nums)
            ++freq[num];
        int ans = 0;
        for (auto [num, occ]: freq)
            if (occ == 1) {
                ans = num;
                break;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (const auto& num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3)
                ans |= (1 << 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
19
20
21
22
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        vector<unordered_map<int, bool>> m(n);
        function<bool(int, int)> dfs = [&](int i, int lastDist) {
            // `i` is current position, `lastDist` is the distance that frog jump over to get to `i`.
            if (i == n - 1) return true;
            if (m[i].find(lastDist) != m[i].end()) return m[i][lastDist];
            for (int currDist = lastDist - 1; currDist <= lastDist + 1; ++currDist) {
                if (currDist > 0) {
                    int j = lower_bound(stones.begin(), stones.end(), currDist + stones[i]) - stones.begin();
                    if (j != n && stones[j] == stones[i] + currDist && dfs(j, currDist)) {
                        return m[i][lastDist] = true;
                    }
                }
            }
            return m[i][lastDist] = false;
        };
        return dfs(0, 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        for (int i = 1; i < n; ++i)
            if (stones[i] - stones[i - 1] > i)
                return false;
        // dp[i][k] stands for whether frog can jump to `i` from `j` with distance `k`,
        // so dp[i][k] = dp[j][k − 1] || dp[j][k] || dp[j][k + 1].
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        dp[0][0] = true;
        for (int i = 1; i < n; ++i)
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k > j + 1)
                    break;
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k])
                    return true;
            }
        return false;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int) b)
                return true;
        }
        return false;
    }
};

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
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = *max_element(weights.begin(), weights.end()),
            right = accumulate(weights.begin(), weights.end(), 0);
        while (left < right) {
            int mid = (left + right) / 2;
            int dayCnt = 1, curr = 0;
            for (const auto& w : weights) {
                if (curr + w > mid) {
                    ++dayCnt;
                    curr = 0;
                }
                curr += w;
            }
            if (dayCnt <= D) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

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
class Solution {
private:
    int memo[30][30][31]; // -1 as false, 1 as true, 0 as uncalculated.
    string s1, s2;
    bool checkIfSimilar(int i1, int i2, int len) {
        unordered_map<int, int> freq;
        for (int i = i1; i < i1 + len; ++i)
            ++freq[s1[i]];
        for (int i = i2; i < i2 + len; ++i)
            if (--freq[s2[i]] < 0)
                return false;
        return true;
    }
    bool dfs(int i1, int i2, int len) {
        if (memo[i1][i2][len])
            return memo[i1][i2][len] == 1;
        if (s1.substr(i1, len) == s2.substr(i2, len)) {
            memo[i1][i2][len] = 1;
            return true;
        }
        if (!checkIfSimilar(i1, i2, len)) {
            memo[i1][i2][len] = -1;
            return false;
        }
        for (int i = 1; i < len; ++i) {
            if ((dfs(i1, i2, i) && dfs(i1 + i, i2 + i, len - i))
                || (dfs(i1, i2 + len - i, i) && dfs(i1 + i, i2, len - i))) {
                memo[i1][i2][len] = 1;
                return true;
            }
        }
        memo[i1][i2][len] = -1;
        return false;
    }
public:
    bool isScramble(string s1, string s2) {
        memset(memo, 0, sizeof(memo));
        this->s1 = s1;
        this->s2 = s2;
        return dfs(0, 0, s1.size());
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    TreeNode *dummyHead, *curr;
public:
    TreeNode* increasingBST(TreeNode* root) {
        dummyHead = new TreeNode();
        curr = dummyHead;
        dfs(root);
        return dummyHead->right;
    }
    void dfs(TreeNode* root) {
        if (root) {
            dfs(root->left);
            curr->right = root;
            root->left = nullptr;
            curr = root;
            dfs(root->right);
        }
    }
};
0%