leetcode_OJ WC79 解題心得
- Contest time: Apr 1, 2018
PA. 812. Largest Triangle Area 暴力解+海龍公式
- 思路：暴力解+海龍公式即可，程式碼中的 a b c 分別為三角形的三邊，s為週長的一半
class Solution { public: double largestTriangleArea(vector<vector<int>>& points) { //points = 50, butr force OK double a = 0.0f, b = 0.0f,c = 0.0f ,s = 0.0f, area = 0.0f, max_area = 0.0f; for(int i = 0; i < points.size() - 2; i++) { for(int j = i + 1; j < points.size() - 1; j++) { for(int k = j + 1; k < points.size(); k++) { a = dist(points[i],points[j]); b = dist(points[j],points[k]); c = dist(points[i],points[k]); s = (a + b + c) / 2.0f; area = sqrt(s * (s - a) * (s - b) * (s - c)); max_area = max(max_area, area); } } } return max_area; } double dist(vector<int> p1, vector<int> p2) { return sqrt(abs(p1[0] - p2[0]) * abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]) * abs(p1[1] - p2[1])); } };
PB. 814. Binary Tree Pruning 二元樹修剪
- 題意：對於一個只有數值為0 or 1的二元樹，倘若此節點以下所有的節點均為0，則刪除此節點以及以下所有的節點，算是漸漸弄懂遞迴的執行原則了，也比較看得懂對於處理樹的題目。 當不知道遞迴怎麼跑時，可以先用小的例子來輔助驗證
- 思路：使用遞迴，往下走訪，『唯一有需要刪除的節點便是，自己為零，並且該底下所有子樹都只有數值為0的節點（包含0作為leaf也應該刪除，因此可以切出數個狀況）』
1.對於null節點，返回0即可，因為已經沒有必要操作，先以 if 左子樹右子樹均true必須刪除且自己也是0 來判斷刪除，亦即2.但由於 null<-0->null的節點 兩個null返回0會使得這種節點刪不掉，因此特判一個(if pruneit(left) && pruneit(right) && val == 0) <br /><br />
if(cur->left == NULL && cur->right == NULL && cur->val == 0) { return 1; }
3.對於 true<-0->null 或是 null<-0->true 實際上也都必須刪除，但由於(if pruneit(left) && pruneit(right) && val == 0)and串接邏輯的關係，也會刪不掉，故增加兩個特判
if(cur->left == NULL && cur->right && pruneit(cur->right) && cur->val == 0) { return 1; }
if(cur->left && cur->right == NULL && pruneit(cur->left) && cur->val == 0) { return 1; }
4. 對於 數值為1的node，無須處理，因此返回 left_check & right_check & (cur->val == 0); 例如
1
/
0
/ |
true true
則最後0返回 true & true & val == 0 遞迴結束後返回給1，1的 left_check = pruneit(cur->left);便會街收到true，將其剪掉，完成prune。
5.特別處理連根拔起的情形if(pruneit(root)) //last one for root { root = NULL; }
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ /** * 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: TreeNode* pruneTree(TreeNode* root) { if(pruneit(root)) //last one for root { root = NULL; } return root; } bool pruneit(TreeNode* cur) //1 for need prune { if(cur == NULL) { return 0; } //due to left_check & right_check & (cur->val == 0); null<-0->null should also be deleted if(cur->left == NULL && cur->right == NULL && cur->val == 0) { return 1; } //due to left_check & right_check & (cur->val == 0); null<-0->true should also be deleted if(cur->left == NULL && cur->right && pruneit(cur->right) && cur->val == 0) { return 1; } //due to left_check & right_check & (cur->val == 0); true<-0->null should also be deleted if(cur->left && cur->right == NULL && pruneit(cur->left) && cur->val == 0) { return 1; } bool left_check = pruneit(cur->left); bool right_check = pruneit(cur->right); if(left_check) //if left subtree needs to be pruned { cur->left = NULL; } if(right_check) //if right subtree needs to be pruned { cur->right = NULL; } return left_check & right_check & (cur->val == 0); //subtree only delete for this one } };
PC. 813. Largest Sum of Averages略嫌麻煩的動態規劃題目
- 思路：動態規劃，切割不同長度平均所對應的子問題，在由對應的子問題將以前算過得子問題數值取出，最後加總，而在這不同長度平均所對應的加總數值，再選取最大的，作為當前動態規劃的數值。
- 詳細流程推導，請見
內附註解
class Solution { public: double largestSumOfAverages(vector<int>& arr, int kin) { double dp[105][105] = {0.0f}; for(int i = 0; i < arr.size(); i++) { double sum = 0.0f; for(int j = 0; j <= i; j++) { sum += arr[j]; } dp[0][i] = sum / (double) (i + 1); } double cur_val = 0.0f, max_val = 0.0f, segment_avg = 0.0, segment_avg2 = 0.0f; for(int i = 1; i < kin; i++) { for(int j = i; j < arr.size(); j++) { cur_val = 0.0f, max_val = 0.0f; if(j < i) { continue; } else if(j == i) { segment_avg = 0.0f; for(int k = 0; k <= j; k++) { segment_avg += arr[k]; } dp[i][j] = segment_avg; } else if(i == 1) { for(int k = 1; k <= j; k++) { segment_avg = 0.0f; segment_avg2 = 0.0f; for(int l = 0; l < k; l++) { segment_avg += arr[l]; } for(int m = k; m <= j; m++) { segment_avg2 += arr[m]; } max_val = max(max_val, segment_avg / k + segment_avg2 / double(j - k + 1)); } dp[i][j] = max_val; } else { for(int n = j; n >= i; n--) //let's say the slice is zero based, for the i th slice, the smallest group //should contain at least i element ex: 1 2 3 4 for 3 slice then at least in DP 12 [3 4](grouped for current slice) is OK //but for 1 [2 3 4](grouped for current slice) is not right { segment_avg = 0.0f; for(int k = j; k >= n; k--) //forward to accumulate and the average /* let's say the slice is zero based, for the n th slice. ex: for 1 2 3 4 5 and slice for 3 ()as the slice group need to search for the 2-slice of best line(row) we will then check (1 2 3 4)(search for i = slice - 1 for the SUBPROBLEM OF SIZE - 1 and j = 3 (since 1 2 3 4 till 4th element)) [5] which is value = dp[2][3] + avg(5) = 8.5 + 5 = 13.5 the same is true for (1 2 3) [4 5] value = dp[2][2] + avg(4 5) = 6 + 4.5 = 10.5 (1 2) [3 4 5] value = dp[2][1] + avg(3,4,5) = (1) [2 3 4 5] //unable to do since the smallest group is less then i - 1 = 3 - 1 = 2 then we take the max value of these calculation for dp[i][j] */ { segment_avg += arr[k]; } //the other part of from 0 to i - 1 there are i elements to search for the previous saved (best value) dp grid cur_val = dp[i - 1][n - 1] + segment_avg / (double)(j - n + 1); max_val = max(max_val, cur_val); } dp[i][j] = max_val; //after choosing the max_val of the dp } } } return dp[kin - 1][arr.size() - 1]; } };