LeetCode Weekly Contest 23

1. 541. Reverse String II

按照题目要求的做就行，没有特殊考虑的边界条件。

 1 class Solution {
 2 public:
 3 string reverseStr(string s, int k) {
 4     int n = s.size();
 5     if(k == 1) {
 6         return s;
 7     }
 8     if(n <= k) {
 9         reverse(s.begin(), s.end());
10         return s;
11     }
12     int i = 0;
13     while(i < n) {
14         if(i + k >= n) {
15             reverse(s.begin() + i, s.end());
16         } else {
17             reverse(s.begin() + i, s.begin() + i + k);
18         }
19         i += 2 * k;
20     }
21     return s;
22 }
23 };

View Code

2. 539. Minimum Time Difference

把字符串转化为数字，都转化为以分钟为单位，然后排序，结果一定在相邻的2个之间产生，注意第一个和最后一个。以及每个差值的补数。

 1 class Solution {
 2 public:
 3 int findMinDifference(vector<string>& ti) {
 4     vector<int> v;
 5     for(string s : ti) {
 6         int t = 0;
 7         t = ((s[0] - '0') * 10 + s[1] - '0') * 60 + (s[3] - '0') * 10 + s[4] - '0';
 8         v.push_back(t);
 9     }
10     sort(v.begin(), v.end());
11     int res = INT_MAX;
12     int n = v.size();
13     for(int i = 0; i < n; i++) {
14         int t = abs(v[(i + 1) % n] - v[i]);
15         res = min(res, min(t, 1440 - t));
16     }
17     return res;
18 }
19 };

View Code

3. 536. Construct Binary Tree from String

显然是要递归调用，每个数字后面可能有0,1,2对匹配的括号，对应相应的儿子。考虑有无限对括号的情况（当然这个题目是二叉树），这跟前面的一些题目，parser类的题目很相似，解析类的题目，都是要递归调用，考虑不同的结构。

 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 TreeNode* work(string &s, int& p) {
13     int n = s.size();
14     if(p >= n) return NULL;
15     if(!(s[p] == '-' || (s[p] >= '0' || s[p] <= '9'))) return NULL;
16     int f = 1;
17     if(s[p] == '-') {
18         f = -1;
19         p++;
20     }
21     int t = 0;
22     while(p < n && s[p] >= '0' && s[p] <= '9') {
23         t = t * 10 + s[p] - '0'; p++;
24     }
25     t *= f;
26     TreeNode*tr = new TreeNode(t);
27     if(p < n && s[p] == '(') {
28         p++;
29         tr->left = work(s, p);
30         p++;
31     }
32     if(p < n && s[p] =='(') {
33         p++;
34         tr->right = work(s, p);
35         p++;
36     }
37     return tr;
38 }
39 TreeNode* str2tree(string s) {
40     int n = s.size();
41     int t = 0;
42     return work(s, t);
43 }
44 };

View Code

4. 527. Word Abbreviation

看的前面大神的代码，基本上都是暴力，可能400*400（个数和单词长度）的数据范围太小了吧！维护一下压缩后的长度，长度为1的就是最终结果，大于1的需要扩展压缩长度，重复这个过程，直到结果。

分析：字符串长度小于等于3的，结果是原字符串，然后考虑其他的，考虑产生冲突的情况，肯定是长度相同的，长度不同的一定不会产生冲突（这个应该是肯定的）。然后对长度相同的进行处理，找出不同的字符表示，当这个字符只有一个字符串包含的时候，这个字符串的压缩方式就确定了，然后就是用trie树，维护一下个数，插入所有，然后对每一个字符串，找到只出现一次的字符，输出压缩结果。由于初始压缩方式只有头尾字符以及中间个数，所以，插入trie树的时候，先插入末尾字符，再插入其他字符。

  1 struct node {
  2     int c;
  3     int nxt[26];
  4     void clear() {
  5         c = 0;
  6         memset(nxt, 0, sizeof nxt);
  7     }
  8 } e[160010];
  9 int cnt;
 10 class Solution {
 11 public:
 12 
 13 vector<string> di;
 14 vector<string> res;
 15 void add(string& s) {
 16     int u = 0;
 17     for (char ch : s) {
 18         int cur = ch - 'a';
 19         if(e[u].nxt[cur] == 0) {
 20             e[u].nxt[cur] = ++cnt;
 21             e[cnt].clear();
 22         }
 23         u = e[u].nxt[cur];
 24         e[u].c++;
 25     }
 26 }
 27 void work(vector<int> &v) {
 28     //cout << v.size() << endl;
 29     //cout << "asd " << v[0] << endl;
 30     cnt = 0;
 31     e[0].clear();
 32     int n = v.size();
 33     int len = di[v[0] ].size();
 34     if(n == 1) {
 35         stringstream ss;
 36         ss << di[v[0] ][0];
 37         ss << len - 2;
 38         ss << di[v[0] ][len - 1];
 39         res[v[0] ] = ss.str();
 40         return;
 41     }
 42     for (int x : v) {
 43         string t = di[x];
 44         string td = t[len - 1] + t.substr(0, len - 1);
 45         add(td);
 46     }
 47     for (int x : v) {
 48         string t = di[x];
 49         string td = t[len - 1] + t.substr(0, len - 1);
 50         int u = 0;
 51         bool f = 1;
 52         for (int i = 0; i < len; i++) {
 53             int cur = td[i] - 'a';
 54             u = e[u].nxt[cur];
 55             if(e[u].c == 1) {
 56                 stringstream ss;
 57                 if(i == 0)
 58                     ss << t[0];
 59                 else
 60                     ss << td.substr(1, i);
 61                 if(len - i - 1 > 0)
 62                     if(i > 0)
 63                         ss << (len - i - 1);
 64                     else
 65                         ss << (len - 2);
 66                 ss << td[0];
 67                 res[x] = ss.str();
 68                 if(res[x].size() >= di[x].size())
 69                     res[x] = di[x];
 70                 //cout << "res " << res[x] << endl;
 71                 f = 0;
 72                 break;
 73             }
 74         }
 75         if(f) cout << "err" << endl;
 76     }
 77 }
 78 vector<string> wordsAbbreviation(vector<string>& dict) {
 79     di = dict;
 80     int n = dict.size();
 81     map<int, vector<int>> ma;
 82     res.clear();
 83     res.resize(n);
 84     for (int i = 0; i < n; i++) {
 85         string s = dict[i];
 86         if(s.size() <= 3) {
 87             res[i] = s;
 88         } else {
 89             int t = s.size();
 90             ma[t].push_back(i);
 91         }
 92     }
 93     //cout << "asd" << endl;
 94     for (auto it : ma) {
 95         auto& x = it.second;
 96         //for (int t : x)
 97         //    cout << t << " ";
 98         //cout << endl;
 99         work(x);
100     }
101     return res;
102 }
103 };

View Code