LeetCode Weekly Contest 27

1. 557. Reverse Words in a String III

分割字符串，翻转。

 1 class Solution {
 2 public:
 3 string reverseWords(string s) {
 4     int n = s.size();
 5     if(n < 2) return s;
 6     string res;
 7     int i = 0;
 8     n += 1;
 9     s += " ";
10     int last = 0;
11     while(i < n) {
12         last = i;
13         while(i < n && s[i] != ' ') i++;
14         string t = s.substr(last, i - last);
15         reverse(t.begin(), t.end());
16         res += t + " ";
17         i++;
18     }
19     return res.substr(0, n - 1);
20 }
21 };

View Code

2. 554. Brick Wall

这刚好是以前做的hihocode的一道题目：https://hihocoder.com/problemset/problem/1494

就是统计边界的最大次数，然后n- max求出最小的穿过次数。

 1 class Solution {
 2 public:
 3 int leastBricks(vector<vector<int>>& wall) {
 4     int n = wall.size();
 5     if(n == 0) return 0;
 6     map<int, int> ma;
 7     int res = 0;
 8     for (vector<int> &it:wall) {
 9         int m = it.size();
10         int s = 0;
11         for (int i = 0; i < m - 1; i++) {
12             s += it[i];
13             ma[s]++;
14             res = max(res, ma[s]);
15         }
16     }
17     return n - res;
18 }
19 };

View Code

3. 556. Next Greater Element III

要求下一个比较大的，可以采用next_permutation来做，然后判断下是不是真的比n大，然后还要check是否超过int的表示范围。

 1 class Solution {
 2 public:
 3 int nextGreaterElement(int n) {
 4     if(n < 10) return -1;
 5     vector<int> v;
 6     int t = n;
 7     while(t > 0) {
 8         v.push_back(t % 10);
 9         t /= 10;
10     }
11     int sz = v.size();
12     //cout << sz << endl;
13     if(sz == 1) return -1;
14     reverse(v.begin(), v.end());
15     if(next_permutation(v.begin(), v.end())) {
16         long long res = 0;
17         for (int t : v) {
18             res = res * 10 + t;
19         }
20         if(res > INT_MAX)
21             return -1;
22         return res;
23     } else
24     return -1;
25 }
26 };

View Code

4. 549. Binary Tree Longest Consecutive Sequence II

这个题跟求二叉树的最长路径的方法是一致的，维护信息，以及更新结果。

我当时写的有点复杂，只需要维护每个点的最长上升和下降长度就行。注意：题目要求必须连续。

 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 int res;
13 typedef pair<pair<int, int>, pair<int, int>> pp;
14 typedef pair<int, int> pii;
15 pair<pair<int, int>, pair<int, int>> work(TreeNode* root) {
16     if(!root) {
17         return {{0,0}, {0, 0} };
18     }
19     if(!root->left && !root->right) {
20         int v = root->val;
21         res = max(res, 1);
22         return {{1, v}, {1, v} };
23     }
24     int v = root->val;
25     pp m1 = work(root->left), m2 = work(root->right);
26     int a1 = m1.first.first, a2 = m1.first.second, b1 = m1.second.first, b2 = m1.second.second;
27     int ta1 = m2.first.first, ta2 = m2.first.second, tb1 = m2.second.first, tb2 = m2.second.second;
28     int ra1 = 1, ra2 = v, rb1 = 1, rb2 = v;
29     if(v == a2 + 1) {
30         ra1  = a1 + 1;
31     }
32     if(v == ta2 + 1) {
33         ra1 = max(ra1, ta1 + 1);
34     }
35     if(v == b2 - 1) {
36         rb1 = b1 + 1;
37     }
38     if(v == tb2 - 1) {
39         rb1 = max(rb1, tb1 + 1);
40     }
41     if(v == a2 + 1 && v == tb2 - 1) {
42         res = max(res, 1 + a1 + tb1);
43     }
44     if(v == ta2 + 1 && v == b2 - 1) {
45         res = max(res, 1 + ta1 + b1);
46     }
47     res = max(res, max(ra1, rb1));
48     return {{ra1, ra2}, {rb1, rb2} };
49 
50 }
51 int longestConsecutive(TreeNode* root) {
52     if(!root) return 0;
53     res = 0;
54     work(root);
55     return res;
56 }
57 };

View Code