leetcode_OJ WC120 解題心得
- 總算忙完一切，畢業專題、研究所、四上課業、活動等等，已經快三個月沒寫題目啦，雖然有點生疏，但久久回歸感覺真好
- 題意以及想法：平方後排序
- 分析：Time complexity O(NlogN), Space complexity O(N)
class Solution
{
public:
vector<int> sortedSquares(vector<int>& A)
{
int n = A.size();
vector<int> res;
for(int i = 0; i < n; ++i)
{
A[i] = A[i] * A[i];
res.push_back(A[i]);
}
sort(res.begin(), res.end());
return res;
}
};
- 題意：滿足
a1 < a2 > a3 < a4... 或 a1 > a2 < a3 > a4...之最長子陣列
- 想法：水題直接做
- 分析：Time complexity O(N^2) (會小於許多), Space complexity O(N)
class Solution
{
public:
int maxTurbulenceSize(vector<int>& A)
{
int n = A.size();
if(n == 1)
{
return 1;
}
int cnt = 0, tmp = 0, res = 0;
for(int i = 0; i < n - 1; i++)
{
tmp = 0;
if(A[i] < A[i + 1])
{
cnt = 1;
}
else if(A[i] > A[i + 1])
{
cnt = 0;
}
for(int j = i; j < n - 1; j++)
{
if(cnt) // <
{
if(A[j] < A[j +1])
{
tmp++;
cnt ^= 1;
}
else
{
break;
}
}
else // >
{
if(A[j] > A[j +1])
{
tmp++;
cnt ^= 1;
}
else
{
break;
}
}
}
res = max(res, tmp);
}
return res + 1;
}
};
- 題意：給定一個二元樹，節點的數值val 加總為節點數，一次可以將1移出節點或是移入（亦即：增加一，或是減少一），謂之一步，問要多少步驟才能將整棵樹的各個節點數值平衡為1
- 想法：這題想法有點特別，有兩個概念，考慮一個子樹，有 left subtree, right subtree 和 root
- 流量 = abs(node_val - 1)，數值比1多的subtree可以flow出（要絕對值的原因是，比一多要供給，比一少要他人提供），不需要在意是誰提供也不用在意給誰，只要太多就給出（至於root要怎麼分配那是root自己的事情），太少需求，僅此而已，終將平衡。
- 整棵樹的平衡值（整棵樹和完全平衡 1 1 1的樹差多少） 會是 left_subtree平衡值 + right_subtree平衡值 + root_val - 1（因為 root也要是1所以它還差 root_val - 1到達） 不用絕對值的原因是，少的會由多得來補，在加上絕對值會太多
- 例如 [3,0,0] left subtree 0 缺一，所一需要一個人流動給它，right subtree亦同，而上面的三正好能分給左右各一，因此流量（移動步數 = abs(0-1) + abs(0-1)) 而
整棵樹的平衡數值會是： (0 - 1) + (0 - 1) + (3 - 1) = 0 因此整棵樹平衡
- 分析：Time complexity O(N)，走訪過所有節點，Space complexity O(N)
- 額外補充，這裡可以看有名的「花花刷題找工作」有更詳細的影音檔講解，歡迎大家訂閱他
連結
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
int res = 0;
int distributeCoins(TreeNode* root)
{
dfs(root);
return abs(res);
}
int dfs(TreeNode* root)
{
if(root == NULL)
{
return 0;
}
int L = dfs(root -> left); //檢查左邊的流量
int R = dfs(root -> right); //檢查左邊的流量
res += abs(L) + abs(R); //總流量
return L + R + (root -> val - 1); //整棵樹的平衡值
}
};
- 題意：問從起點到終點，有多少
Hamilton path Wikipedia reference
- 想法，因為題目規模不大，(row x col) <= 20 數據規模親民，可以直接用暴力的DFS求解（其實是DP想不太出來 XD)，具體描述請見下面程式碼的註解
- 分析： Time complexity O(4^(row * col))，因為題目規模不大，可以用暴力解出，再大一點可能就 TLE了，Space complexity O(row * col)
class Solution
{
public:
int zcnt = 0, res = 0;
int rt = 0, ct = 0;
int uniquePathsIII(vector<vector<int>>& grid)
{
rt = grid.size(), ct = grid[0].size();
int sr = 0, sc = 0;
for(int r = 0; r < rt; r++)
{
for(int c = 0; c < ct; c++)
{
if(grid[r][c] == 1)
{
sr = r;
sc = c;
}
else if(grid[r][c] == 0)
{
zcnt++;
}
}
}
dfs(grid, sr, sc, 0);
return res;
}
void dfs(vector<vector<int>>& grid, int row , int col, int steps)
{
if(row < 0 || row >= rt || col < 0 || col >= ct || grid[row][col] < 0) //illegal position
{
return;
}
if(grid[row][col] == 2) //reached the target position with steps = zcnt
{
if(steps - 1 == zcnt)
{
res++;
}
return;
}
grid[row][col] = -2; //marked as traversed
// 4 sides
dfs(grid, row - 1, col, steps + 1); //U
dfs(grid, row + 1, col, steps + 1); //D
dfs(grid, row, col - 1, steps + 1); //L
dfs(grid, row, col + 1, steps + 1); //R
grid[row][col] = 0; //marked as untraversed, backtracking again
}
};