Contest 121 （题号981～984）（2019年1月27日）

链接：

 

 

 

Contest 122（题号985～988）（2019年2月3日）

链接：https://leetcode.com/contest/weekly-contest-122

总结：这周题目非常简单，四题都过了。

【985】Sum of Even Numbers After Queries（第一题 4分）

给了一个数组，以及一个修改的序列。序列中的一个 pair 代表 p[0] 代表在原来数字上加上的值 val , p[1] 代表数组中需要修改元素的下标。求每次修改之后整个数组的偶数的和。

数据规模：

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. 1 <= queries.length <= 10000
4. -10000 <= queries[i][0] <= 10000
5. 0 <= queries[i][1] < A.length

题解： 用一个变量curSum存储当前数组偶数的和，然后每次执行一个query之后，看当前元素是奇数变成偶数，还是偶数变成奇数，还是偶数变成偶数。来做不同的处理。

 1 class Solution {
 2 public:
 3     vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
 4         const int n = A.size(), m = queries.size();
 5         vector<int> ret;
 6         int curSum = 0;
 7         for (auto num : A) {
 8             if ((num & 1) == 0) {
 9                 curSum += num;
10             }
11         }
12         for (auto q : queries) {
13             int val = q[0], idx = q[1];
14             int oriVal = A[idx];
15             int newVal = oriVal + val;
16             if ((oriVal & 1) == 0) {
17                 if (newVal & 1) {
18                     curSum -= oriVal;
19                 } else {
20                     curSum += val;
21                 }
22             } else {
23                 if ((newVal & 1) == 0) {
24                     curSum += newVal;
25                 }
26             }
27             ret.push_back(curSum);
28             A[idx] = newVal;
29         }
30         return ret;
31     }
32 };

View Code

 

【988】Smallest String Starting From Leaf（第二题 5分）

给了一棵二叉树，树上的每个结点代表一个字母（0-25），问从叶子结点开始到根节点的字典序最小的单词是哪个？

题解：dfs 这颗树，把所有单词找出来。然后排序。注意这个题要求是从叶子结点开始，如果一个结点只有一个儿子，那么它本身不能算叶子结点，从它开始的单词要忽略掉。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     string smallestFromLeaf(TreeNode* root) {
13         vector<string> words;
14         string str;
15         if (!root) {
16             return "";
17         }
18         dfs(root, words, str);
19         sort(words.begin(), words.end());
20         return words[0];
21     }
22     void dfs(TreeNode* root, vector<string>& words, string& str) {
23         if (!root) { return; }
24         char c = root->val + 'a';
25         str += string(1, c);
26         if (!root->left && !root->right) {
27             reverse(str.begin(), str.end());
28             words.push_back(str);
29             reverse(str.begin(), str.end());
30             str.pop_back();
31             return;
32         }
33         if (root->left) {
34             dfs(root->left, words, str);
35         }
36         if (root->right) {
37             dfs(root->right, words, str);
38         }
39         str.pop_back();
40         return;
41     }
42 };

View Code

 

【986】Interval List Intersections（第三题 5分）

给了两组左闭右闭的线段，返回这两组线段的交集。

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

题解：2 pointers 扫描一遍。

 1 /**
 2  * Definition for an interval.
 3  * struct Interval {
 4  *     int start;
 5  *     int end;
 6  *     Interval() : start(0), end(0) {}
 7  *     Interval(int s, int e) : start(s), end(e) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {
13         const int size1 = A.size(), size2 = B.size();
14         int p1 = 0, p2 = 0;
15         vector<Interval> ret;
16         while (p1 < size1 && p2 < size2) {
17             Interval seg1 = A[p1], seg2 = B[p2];
18             int s = max(seg1.start, seg2.start), e = min(seg1.end, seg2.end);
19             if (s > e) {
20                 if (seg1.end > seg2.end) { p2++; }
21                 else { p1++; }
22                 continue;
23             }
24             Interval seg(s, e);
25             ret.push_back(seg);
26             if (seg1.end > seg2.end) {
27                 p2++;
28             } else if (seg2.end > seg1.end) {
29                 p1++;
30             } else {
31                 p1++, p2++;
32             }
33         }
34         return ret;
35     }
36 };

View Code

 

【987】Vertical Order Traversal of a Binary Tree（第四题 5分）

给了一棵二叉树，给了树的结点上坐标的定义。根结点是 (0, 0)， For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1). 按照 X 轴升序， Y 轴降序， 然后 value 升序的条件，返回这颗树的值。 

 题解：dfs一遍树，用map存起来。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> verticalTraversal(TreeNode* root) {
13         vector<vector<int>> ret;
14         if (!root) {return ret;}
15         dfs(root, 0, 0);
16         for (auto& pp : memo) {
17             int x = pp.first; map<int, vector<int>, greater<int>> mp = pp.second;
18             vector<int> temp;
19             for (auto& ele : mp) {
20                 sort(ele.second.begin(), ele.second.end());
21                 for (auto& num : ele.second) {
22                     temp.push_back(num);
23                 }
24             }
25             ret.push_back(temp);
26         }
27         return ret;
28     }
29     map<int, map<int, vector<int>, greater<int>>> memo; // x-idx, list of values, and height
30     void dfs(TreeNode* root, int x, int y) {
31         if (!root) {return;}
32         memo[x][y].push_back(root->val);
33         dfs(root->left, x-1, y-1);
34         dfs(root->right, x+1, y-1);
35     }
36     
37 };

View Code

 

 

Contest 123（题号985～988）（2019年2月10日）

 

Contest 124（题号993～996）（2019年2月17日）