[not completed]leetcode contest biweekly 17

OneCodeMonkey · OneCodeMonkey · commit a923592abbe5 · 2020-01-11T23:00:33.000+08:00
diff --git a/contest/leetcode_biweek_17_problems/leetcode_5143_Decompress_Run-Length_Encoded_List.cpp b/contest/leetcode_biweek_17_problems/leetcode_5143_Decompress_Run-Length_Encoded_List.cpp
@@ -0,0 +1,15 @@
+/**
+ * AC：
+ * 思路：较易，略
+ */
+class Solution {
+public:
+    vector<int> decompressRLElist(vector<int>& nums) {
+     	vector<int> ret;
+     	for(int i = 0; i < nums.size() / 2; i++)
+     		for(int j = 0; j < nums[2 * i]; j++)
+     			ret.push_back(nums[2 * i + 1]);
+
+     	return ret;
+    }
+};
diff --git a/contest/leetcode_biweek_17_problems/leetcode_5144_Matrix_Block_Sum.cpp b/contest/leetcode_biweek_17_problems/leetcode_5144_Matrix_Block_Sum.cpp
@@ -0,0 +1,36 @@
+/**
+ * AC：
+ * 思路：先按行预先计算出行的累加和，用一个 a[row + 2 * K][col + 2 * K] 的数组记录，
+ *      然后在对 a 遍历，每个 [i][j] 位置累加 a[i][j] 到 a[i + 2 * K][j + 2 * K] 的K^2 个元素和
+ *      这样总体复杂度是 O(m)(n)
+ * T: O(m * n * K), 由于 K 是常数，所以接近 m * n 的复杂度
+ */
+class Solution {
+public:
+    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
+        int row = mat.size(), col = mat[0].size();
+        vector<vector<int>> ret(row, vector<int>(col, 0));
+       	vector<vector<int>> record(row + 2 * K, vector<int>(row + 2 * K, 0));
+       	for(int i = 0; i < row; i++) {
+       		for(int j = 0; j < col; j++) {
+       			for(int k = -K; k <= K; k++) {
+       				if(j + k < 0 || j + k > col - 1)	// 左右越界的部分不计算行的累加和
+       					continue;
+       				record[i + K][j + K] += mat[i][j + k];
+       			}
+       		}
+       	}
+
+       	for(int i = 0; i < row; i++) {
+       		for(int j = 0; j < col; j++) {
+       			int temp = 0;
+       			for(int k = -K; k <= K; k++) {
+       				temp += record[i + K - k][j + K];
+       			}
+       			ret[i][j] = temp;
+       		}
+       	}
+
+       	return ret;
+    }
+};
diff --git a/contest/leetcode_biweek_17_problems/leetcode_5145_Sum_of_Nodes_with_Even-Valued_Grandparent.cpp b/contest/leetcode_biweek_17_problems/leetcode_5145_Sum_of_Nodes_with_Even-Valued_Grandparent.cpp
@@ -0,0 +1,15 @@
+/**
+ * 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 sumEvenGrandparent(TreeNode* root) {
+        
+    }
+};
