1017. Convert to Base -2
Solution: Math / Simulation
Time complexity: O(logn)
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: string baseNeg2(int N) { if (N == 0) return "0"; vector<char> ans; while (N) { ans.push_back((N & 1) + '0'); N = -(N >> 1); } return {rbegin(ans), rend(ans)}; } }; |
base K
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: string baseNeg2(int N) { if (N == 0) return "0"; return baseNegK(N, -2); } private: string baseNegK(int N, int K) { vector<char> ans; while (N) { int r = N % K; N /= K; if (r < 0) { r += -K; N += 1; } ans.push_back(r + '0'); } return {rbegin(ans), rend(ans)}; } }; |
1018. Binary Prefix Divisible By 5
Solution: Math
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: vector<bool> prefixesDivBy5(vector<int>& A) { int num = 0; vector<bool> ans(A.size()); for (int i = 0; i < A.size(); ++i) { num = ((num << 1) | A[i]) % 5; ans[i] = num == 0; } return ans; } }; |
1019. Next Greater Node In Linked List
Solution: Reverse + Monotonic Stack
Process in reverse order and keep a monotonically increasing stack, pop all the elements that are smaller than the current one, then the top of the stack (if exists) will be the next greater node.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: vector<int> nextLargerNodes(ListNode* head) { vector<int> nums; while (head) { nums.push_back(head->val); head = head->next; } stack<int> s; vector<int> ans(nums.size()); for (int i = nums.size() - 1; i >= 0; --i) { while (!s.empty() && s.top() <= nums[i]) s.pop(); ans[i] = s.empty() ? 0 : s.top(); s.push(nums[i]); } return ans; } }; |
1020. Number of Enclaves
Solution: DFS / Connected Components
Time complexity: O(mn)
Space complexity: O(mn)
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 |
// Author: Huahua class Solution { public: int numEnclaves(vector<vector<int>>& A) { int ans = 0; for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) { int count = 0; if (!dfs(A, j, i, count)) ans += count; } return ans; } private: static constexpr int dirs[5]{0, -1, 0, 1, 0}; bool dfs(vector<vector<int>>& A, int x, int y, int& count) { if (x < 0 || x == A[0].size() || y < 0 || y == A.size()) return true; if (A[y][x] == 0) return false; ++count; A[y][x] = 0; bool valid = false; for (int i = 0; i < 4; ++i) valid |= dfs(A, x + dirs[i], y + dirs[i + 1], count); return valid; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment