LeetCode 1029 Two City Scheduling
Solution1: DP
dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, running time: 8 ms class Solution { public: int twoCitySchedCost(vector<vector<int>>& costs) { int n = costs.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { dp[i][0] = dp[i - 1][0] + costs[i - 1][1]; for (int j = 1; j <= i; ++j) dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0], dp[i - 1][j] + costs[i - 1][1]); } return dp[n][n / 2]; } }; |
Solution 2: Greedy
Sort by cost_a – cost_b
Choose the first n/2 people for A, rest for B
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, running time: 8 ms class Solution { public: int twoCitySchedCost(vector<vector<int>>& costs) { int n = costs.size(); sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){ return c1[0] - c1[1] < c2[0] - c2[1]; }); int ans = 0; for (int i = 0; i < n; ++i) ans += i < n/2 ? costs[i][0] : costs[i][1]; return ans; } }; |
1030. Matrix Cells in Distance Order
Solution: Sorting
Time complexity: O(RC*log(RC))
Space complexity: O(RC)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { vector<vector<int>> ans; for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) ans.push_back({i, j}); std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){ return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0)); }); return ans; } }; |
1031. Maximum Sum of Two Non-Overlapping Subarrays
Solution: Prefix sum
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua class Solution { public: int maxSumTwoNoOverlap(vector<int>& A, int L, int M) { const int n = A.size(); vector<int> s(n + 1, 0); for (int i = 0; i < n; ++i) s[i + 1] = s[i] + A[i]; int ans = 0; for (int i = 0; i <= n - L; ++i) { int ls = s[i + L] - s[i]; int ms = max(maxSum(s, 0, i - M - 1, M), maxSum(s, i + L, n - M, M)); ans = max(ans, ls + ms); } return ans; } private: int maxSum(const vector<int>& s, int start, int end, int l) { int ans = INT_MIN; for (int i = start; i <= end; ++i) ans = max(ans, s[i + l] - s[i]); return ans; } }; |
1032. Stream of Characters
Solution: Trie
Time complexity:
- build O(sum(len(w))
- query O(max(len(w))
Space complexity: O(sum(len(w))
C++
|
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 |
// Author: Huahua, 320 ms, 95 MB class TrieNode { public: ~TrieNode() { for (auto node : next_) delete node; } void reverse_build(const string& s, int i) { if (i == -1) { is_word_ = true; return; } const int idx = s[i] - 'a'; if (!next_[idx]) next_[idx] = new TrieNode(); next_[idx]->reverse_build(s, i - 1); } bool reverse_search(const string& s, int i) { if (i == -1 || is_word_) return is_word_; const int idx = s[i] - 'a'; if (!next_[idx]) return false; return next_[idx]->reverse_search(s, i - 1); } private: bool is_word_ = false; TrieNode* next_[26] = {0}; }; class StreamChecker { public: StreamChecker(vector<string>& words) { root_ = std::make_unique<TrieNode>(); for (const string& w : words) root_->reverse_build(w, w.length() - 1); } bool query(char letter) { s_ += letter; return root_->reverse_search(s_, s_.length() - 1); } private: string s_; unique_ptr<TrieNode> root_; }; |
Java
|
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 |
// Author: Huahua, running time: 133 ms class StreamChecker { class TrieNode { public TrieNode() { isWord = false; next = new TrieNode[26]; } public boolean isWord; public TrieNode next[]; } private TrieNode root; private StringBuilder sb; public StreamChecker(String[] words) { root = new TrieNode(); sb = new StringBuilder(); for (String word : words) { TrieNode node = root; char[] w = word.toCharArray(); for (int i = w.length - 1; i >= 0; --i) { int idx = w[i] - 'a'; if (node.next[idx] == null) node.next[idx] = new TrieNode(); node = node.next[idx]; } node.isWord = true; } } public boolean query(char letter) { sb.append(letter); TrieNode node = root; for (int i = sb.length() - 1; i >= 0; --i) { int idx = sb.charAt(i) - 'a'; if (node.next[idx] == null) return false; if (node.next[idx].isWord) return true; node = node.next[idx]; } return false; } } |