February 6, 2024
Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.
Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].
Example 1:
Input: [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations.
Example 2:
Input: [2,2,2] Output: 1
Note:
1 <= A.length <= 120 <= A[i] <= 1e9Try all permutations with pruning.
Time complexity: O(n!)
Space complexity: O(n)
|
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 |
// Author: Huahua, running time: 4 ms, 8.8 MB class Solution { public: int numSquarefulPerms(vector<int>& A) { std::sort(begin(A), end(A)); vector<int> cur; vector<int> used(A.size()); int ans = 0; dfs(A, cur, used, ans); return ans; } private: bool squareful(int x, int y) { int s = sqrt(x + y); return s * s == x + y; } void dfs(const vector<int>& A, vector<int>& cur, vector<int>& used, int& ans) { if (cur.size() == A.size()) { ++ans; return; } for (int i = 0; i < A.size(); ++i) { if (used[i]) continue; // Avoid duplications. if (i > 0 && !used[i - 1] && A[i] == A[i - 1]) continue; // Prune invalid solutions. if (!cur.empty() && !squareful(cur.back(), A[i])) continue; cur.push_back(A[i]); used[i] = 1; dfs(A, cur, used, ans); used[i] = 0; cur.pop_back(); } } }; |
dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i
dp[s | (1 << j)][j] += dp[s][i] if g[i][j]
Time complexity: O(n^2*2^n)
Space complexity: O(2^n)
|
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 |
// Author: Huahua, running time: 20 ms, 14.9 MB class Solution { public: int numSquarefulPerms(vector<int>& A) { const int n = A.size(); // For deduplication. std::sort(begin(A), end(A)); // g[i][j] == 1 if A[i], A[j] are squareful. vector<vector<int>> g(n, vector<int>(n)); // dp[s][i] := number of ways to reach state s and ends with node i. vector<vector<int>> dp(1 << n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; int r = sqrt(A[i] + A[j]); if (r * r == A[i] + A[j]) g[i][j] = 1; } } // For the same numbers, only the first one can be the starting point. for (int i = 0; i < n; ++i) if (i == 0 || A[i] != A[i - 1]) dp[(1 << i)][i] = 1; int ans = 0; for (int s = 0; s < (1 << n); ++s) for (int i = 0; i < n; ++i) { if (!dp[s][i]) continue; for (int j = 0; j < n; ++j) { if (!g[i][j]) continue; if (s & (1 << j)) continue; // Only the first one can be used as the dest. if (j > 0 && !(s & (1 << (j - 1))) && A[j - 1] == A[j]) continue; dp[s | (1 << j)][j] += dp[s][i]; } } for (int i = 0; i < n; ++i) ans += dp[(1 << n) - 1][i]; return ans; } }; |
In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
Example 1:
Input: A = [0,1,0], K = 1 Output: 2 Explanation: Flip A[0], then flip A[2].
Example 2:
Input: A = [1,1,0], K = 2 Output: -1 Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].
Example 3:
Input: A = [0,0,0,1,0,1,1,0], K = 3 Output: 3 Explanation: Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0] Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0] Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]
Note:
1 <= A.length <= 300001 <= K <= A.lengthFrom left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.
Time complexity: O(nk) -> O(k)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, running time: 5172 ms, 16.4 MB class Solution { public: int minKBitFlips(vector<int>& A, int K) { int ans = 0; for (int i = 0; i <= A.size() - K; ++i) { if (A[i] == 1) continue; ++ans; for (int j = 0; j < K; ++j) A[i + j] ^= 1; } for (int i = A.size() - K + 1; i < A.size(); ++i) if (A[i] == 0) return -1; return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, running time: 100 ms, 19.6 MB class Solution { public: int minKBitFlips(vector<int>& A, int K) { vector<int> flipped(A.size()); int ans = 0; int flip = 0; for (int i = 0; i < A.size(); ++i) { if (i >= K) flip ^= flipped[i - K]; if ((A[i] ^ flip) == 0) { if (i + K > A.size()) return -1; ++ans; flip ^= 1; flipped[i] = 1; } } return ans; } }; |
In a given grid, each cell can have one of three values:
0 representing an empty cell;1 representing a fresh orange;2 representing a rotten orange.Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1instead.
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]] Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
1 <= grid.length <= 101 <= grid[0].length <= 10grid[i][j] is only 0, 1, or 2.Time complexity: O(mn)
Space complexity: O(mn)
|
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 |
// Author: Huahua, Running time: 12 ms, 10.8 MB class Solution { public: int orangesRotting(vector<vector<int>>& grid) { const int m = grid.size(); const int n = grid[0].size(); queue<pair<int,int>> q; int fresh = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == 1) ++fresh; else if (grid[i][j] == 2) q.emplace(j, i); vector<int> dirs = {1, 0, -1, 0, 1}; int days = 0; while (!q.empty() && fresh) { int size = q.size(); while (size--) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; ++i) { int dx = x + dirs[i]; int dy = y + dirs[i + 1]; if (dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dy][dx] != 1) continue; --fresh; grid[dy][dx] = 2; q.emplace(dx, dy); } } ++days; } return fresh ? -1 : days; } }; |
In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.
Example 1:
Input: root = [1,2,3,4], x = 4, y = 3 Output: false
Example 2:
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true
Example 3:
Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false
Note:
2 and 100.1 to 100.Time complexity: O(n)
Space complexity: O(n)
|
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 |
// Author: Huahua, running time 8 ms, 11.5 MB class Solution { public: bool isCousins(TreeNode* root, int x, int y) { preorder(root, x, y, nullptr, 0); return px_ != py_ && dx_ == dy_; } private: TreeNode* px_; TreeNode* py_; int dx_; int dy_; void preorder(TreeNode* root, int x, int y, TreeNode* p, int d) { if (!root) return; if (root->val == x) { px_ = p; dx_ = d; } if (root->val == y) { py_ = p; dy_ = d; } preorder(root->left, x, y, root, d + 1); preorder(root->right, x, y, root, d + 1); } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua, running time: 40 ms, 12.4 MB class Solution: def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool': self.px, self.dx = None, -1 self.py, self.dy = None, -2 def preorder(root, parent, d): if not root: return if root.val == x: self.px, self.dx = parent, d if root.val == y: self.py, self.dy = parent, d preorder(root.left, root, d + 1) preorder(root.right, root, d + 1) preorder(root, None, 0) return self.dx == self.dy and self.px != self.py |