YoungForest's blog

发表于 更新于 分类于 Disqus：

赛后补的题解。
题目链接

主要参考的是 旷神 直播的解法，和官方 Analysis的解法。

Wiggle Walk

比较容易想到的是暴力解法。模拟整个命令执行过程，标记每个格子是否之前走过。
时间复杂度: O(N ^ 2).

虽然实际上凑巧可以AC，但比较冒险。理论上会在大的测试集上TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <vector>
#include <iostream>
#include <string>

using namespace std;

pair<int, int> solve(const string& instructions, const int R, const int C, const int Sr, const int Sc) {
    int current_x = Sr, current_y = Sc;
    vector<vector<bool>> visited(R + 1, vector<bool> (C + 1, false));
    visited[current_x][current_y] = true;
    for (char c : instructions) {
        int dx, dy;
        switch (c)
        {
        case 'N':
            dx = -1;
            dy = 0;
            break;
        case 'E':
            dx = 0;
            dy = 1;
            break;
        case 'W':
            dx = 0;
            dy = -1;
            break;
        case 'S':
            dx = 1;
            dy = 0;
            break;
        default:
            cerr << "Bad instruction: " << c << endl;
            break;
        }
        do {
            current_x += dx;
            current_y += dy;
        } while (visited[current_x][current_y] == true);
        visited[current_x][current_y] = true;
    }
    return {current_x, current_y};
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        int N, R, C, Sr, Sc;
        cin >> N >> R >> C >> Sr >> Sc;
        string instructions;
        cin >> instructions;
        auto ans = solve(instructions, R, C, Sr, Sc);
        cout << "Case #" << i + 1 << ": " << ans.first << " " << ans.second << endl;
    }
    return 0;
}

需要找到快速跳过已经走过格子的方法。一种是题解里给的，记录interval的方式。时间复杂度: O(N log N). 每次查询interval需要O(log N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

int getNext(set<pair<int, int>> &visited, const int x, int direction) {
  auto it = visited.lower_bound({x + 1, x + 1});
  assert(it != visited.begin());
  --it;
  if (direction > 0)
    return it->second;
  else
    return it->first - 1;
}

void visitRow(set<pair<int, int>> &row, int y) {
  auto it = row.lower_bound({y + 1, y + 1});
  if (it == row.begin()) {
    it = row.insert({y, y + 1}).first;
  } else {
    --it;
    if (it->first <= y && it->second > y) {
      return;
    } else if (it->second == y) {
      auto old = it;
      it = row.insert(it, {it->first, it->second + 1});
      it = row.erase(old);
    } else {
      it = row.insert({y, y + 1}).first;
    }
  }
  // merge interval
  if (next(it) != row.end() && next(it)->first == it->second) {
    int end = next(it)->second;
    int begin = it->first;
    row.erase(next(it));
    row.erase(it);
    row.insert({begin, end});
  }
}

void visit(vector<set<pair<int, int>>> &visitedR,
           vector<set<pair<int, int>>> &visitedC, const int x, int y) {
  auto &row = visitedR[x];
  visitRow(row, y);
  auto &column = visitedC[y];
  visitRow(column, x);
}

pair<int, int> solve(const string &instructions, const int R, const int C,
                     const int Sr, const int Sc) {
  int current_x = Sr, current_y = Sc;
  vector<set<pair<int, int>>> visitedR(R + 1);
  vector<set<pair<int, int>>> visitedC(C + 1);
  visit(visitedR, visitedC, current_x, current_y);
  for (char c : instructions) {
    switch (c) {
    case 'N':
      current_x = getNext(visitedC[current_y], current_x, -1);
      break;
    case 'E':
      current_y = getNext(visitedR[current_x], current_y, 1);
      break;
    case 'W':
      current_y = getNext(visitedR[current_x], current_y, -1);
      break;
    case 'S':
      current_x = getNext(visitedC[current_y], current_x, 1);
      break;
    default:
      cerr << "Bad instruction: " << c << endl;
      break;
    }
    visit(visitedR, visitedC, current_x, current_y);
  }
  return {current_x, current_y};
}

int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; ++i) {
    int N, R, C, Sr, Sc;
    cin >> N >> R >> C >> Sr >> Sc;
    string instructions;
    cin >> instructions;
    auto ans = solve(instructions, R, C, Sr, Sc);
    cout << "Case #" << i + 1 << ": " << ans.first << " " << ans.second << endl;
  }
  return 0;
}

另一种是 邝神 直播中的方法。用并查集，需要注意的是union时，方向是重要的。时间复杂度为 O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

struct UF {
    int F[200010];
    int find(int x) {
        if (F[x] == -1) return x;
        return F[x] = find(F[x]);
    }
    void init() {
        memset(F, -1, sizeof(F));
    }
    void join(int x, int y) {
        int t1 = find(x);
        int t2 = find(y);
        if (t1 != t2) {
            F[t2] = t1;
        }
    }
};

UF N, E, W, S;

map<pair<int, int>, int> p2Id;
int tot;
map<int, pair<int, int>> id2P;
void init() {
    N.init();
    E.init();
    W.init();
    S.init();
    tot = 0;
    p2Id.clear();
    id2P.clear();
}

int getId(int x, int y) {
    pair<int, int> p = make_pair(x, y);
    if (!p2Id.count(p)) {
        p2Id[p] = tot;
        id2P[tot] = p;
        tot++;
    }
    return p2Id[p];
}

void gao(int x, int y) {
    int now = getId(x, y);

    int w = getId(x, y-1);
    int e = getId(x, y+1);
    int n = getId(x-1, y);
    int s = getId(x+1, y);
    W.join(w, now);
    E.join(e, now);
    N.join(n, now);
    S.join(s, now);
}

pair<int, int> getNext(int x, int y, char dir) {
    int now = getId(x, y);
    int nextId;
    if (dir == 'N') {
        nextId = N.find(now);
    } else if (dir == 'E') {
        nextId = E.find(now);
    } else if (dir == 'W') {
        nextId = W.find(now);
    } else if (dir == 'S') {
        nextId = S.find(now);
    }
    return id2P[nextId];
}

char str[50010];

int main() {
    int T;
    int iCase = 0;
    scanf("%d", &T);
    while (T--) {
        iCase++;
        int N, R, C, sx, sy;
        scanf("%d%d%d%d%d", &N, &R, &C, &sx, &sy);
        scanf("%s", str);
        init();
        gao(sx, sy);
        pair<int, int> now = make_pair(sx, sy);
        for (int i = 0; i < N; ++i) {
            now = getNext(now.first, now.second, str[i]);
            gao(now.first, now.second);
        }
        printf("Case #%d: %d %d\n", iCase, now.first, now.second);
    }
    return 0;
}
阅读全文 »

发表于 更新于 分类于 Disqus：

赛后补的题解。
题目链接

Building Palindromes

给定长度为N的一个字符串，和Q个Query。每个query是一个range，可以得到字串。判断子串重新排列后是否回文。因为可以任意重排，所以子串中字符的顺序不重要，重要的是每个字符出现的频数。频数为奇数的字符数目为0或1，即可重排为回文串。
因为N和Q的规模较大，10^5。平方算法会超时。这里借用前缀和的思路，快速计算子串字符频数。
时间复杂度为线性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i) {
        int N, Q;
        cin >> N >> Q;
        string s;
        cin >> s;
        vector<vector<int>> prefix(N+1);
        prefix[0] = vector<int>(26, 0);
        for (int j = 1; j <= N; ++j) {
            prefix[j] = prefix[j-1];
            ++prefix[j][s[j-1] - 'A'];
        }
        int ans = 0;
        for (int j = 0; j < Q; ++j) {
            int L, R;
            cin >> L >> R;
            const auto& l = prefix[L-1], r = prefix[R];
            int odd = 0;
            for (int k = 0; k < 26; ++k) {
                if ((r[k] - l[k]) % 2 == 1)
                    ++odd;
            }
            if (odd <= 1)
                ++ans;
        }
        cout << "Case #" << i << ": " << ans << endl;
    }
    return 0;
}

Energy Stones

本题的思想是 贪心 + 动态规划 (一种0-1背包)。更多背包问题，可以参考背包九讲。
难点在于，背包遍历的顺序需要用贪心的思路去排序的。

对于S相同的小的测试集而言，L大的先去遍历。可以是的损失的能量最少。
对于S不同的大的测试集而言，2个石头i, j的顺序由S_i * L_j决定，如果S_i * L_j < S_j * L_i，则先去i损失的能量更少。

贪心的正确性也很容易去证明。如果我们有一个吃石头的序列，则 必然是按照能量损失较小的顺序去吃的。否则交换一下顺序，可以获得更大的能量。

时间复杂度: O(N * N * S_i).
空间复杂度: O(N * N * S_i), 可以进一步优化到O(N * S_i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

struct Stone {
  int s, e, l;
  bool operator<(const Stone &p) const { return s * p.l < l * p.s; }
};

int main(int argc, char const *argv[]) {
  int T;
  cin >> T;
  for (int iCase = 1; iCase <= T; ++iCase) {
    int N;
    cin >> N;
    vector<Stone> data(N + 1);
    int S_sum = 0;
    for (int i = 1; i <= N; ++i) {
      cin >> data[i].s >> data[i].e >> data[i].l;
      S_sum += data[i].s;
    }
    sort(data.begin() + 1, data.end());
    vector<vector<int>> dp(N + 1, vector<int>(S_sum + 1));
    for (int i = 1; i <= N; ++i) {
      for (int time = 0; time <= S_sum; ++time) {
        if (time < data[i].s) {
          dp[i][time] = dp[i - 1][time];
        } else {
          dp[i][time] =
              max(dp[i - 1][time],
                  dp[i - 1][time - data[i].s] +
                      max(0, data[i].e - data[i].l * (time - data[i].s)));
        }
      }
    }
    int ans = 0;
    for (int time = 0; time <= S_sum; ++time) {
      ans = max(ans, dp[N][time]);
    }
    cout << "Case #" << iCase << ": " << ans << endl;
  }
  return 0;
}
阅读全文 »

发表于 更新于 分类于 Disqus：

今天由于高中同学xl来北京找我聊，和hcq一起吃了午饭和晚饭，并聊了一下午。上午的contest只匆匆做了签到题。第二题因为粗心，写错了red变化的时机，也没有时间调试。后2题干脆没有看。
晚上回来9点才把题目补完，第二题的bug也调出来了。
不过时间上应该是超时了。
排名1800+。

总体来讲，本次题目虽然不难，但是需要花时间思考才能做出来的。这样的题目也是我喜欢的。通过自己的思考，作出一道并不是一眼看上去就知道解答的题目，是很爽的。快感可比超神和三杀。

5130. Number of Equivalent Domino Pairs

既然domino可以通过旋转相等，我们就把他们归一化(将2种domino映射成一种)。
然后计算组合数即可。

时间复杂度: O(N log N), 因为pair默认不是hashable，所以偷懒用了map。
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        const int n = dominoes.size();
        map<pair<int, int>, int> transform;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (dominoes[i][0] < dominoes[i][1]) {
                ++transform[make_pair(dominoes[i][0], dominoes[i][1])];  
            } else {
                ++transform[make_pair(dominoes[i][1], dominoes[i][0])];
            }
        }
        for (const auto& p : transform) {
            ans += p.second * (p.second - 1) / 2;
        }
        return ans;
    }
};

1129. Shortest Path with Alternating Colors

算最短路径，用BFS。由于需要颜色交替，代码略微有些麻烦，需要2套变量。

时间复杂度: O(N), 每个节点最多遍历2次。
空间复杂度: O(max(N, edges)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        unordered_map<int, vector<int>> red_to, blue_to;
        for (const auto& edge : red_edges) {
            red_to[edge[0]].push_back(edge[1]);
        }
        for (const auto& edge : blue_edges) {
            blue_to[edge[0]].push_back(edge[1]);
        }
        vector<int> ret(n, numeric_limits<int>::max());
        ret[0] = 0;
        // bfs
        for (bool red : {true, false}) {
            queue<int> q;
            unordered_set<int> seen_red, seen_blue;
            q.push(0);
            seen_red.insert(0);
            seen_blue.insert(0);
            int level = 0;
            while (!q.empty()) {
                int s = q.size();
                ++level;
                for (int i = 0; i < s; ++i) {
                    int current = q.front();
                    q.pop();
                    vector<int>* edges = nullptr;
                    unordered_set<int>* seen = nullptr;
                    if (red) {
                        edges = &red_to[current];
                        seen = &seen_red;
                    } else {
                        edges = &blue_to[current];
                        seen = &seen_blue;
                    }
                    for (int des : *edges) {
                        if (seen->find(des) == seen->end()) {
                            q.push(des);
                            seen->insert(des);
                            ret[des] = min(ret[des], level);
                        }
                    }
                }            
                red = !red;
            }
        }
        for (auto& item : ret) {
            if (item == numeric_limits<int>::max())
                item = -1;
        }
        return ret;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

与博客不同，一本书相对内容更为完成，更为体系。博客相比之下就零散的多。不过优秀的系列博客也常常被改编成书。
如果你想分享规模更大，成体系的知识的话，写本小书是个很好的选择。
本文介绍一个工具GitBook，可以用Markdown写书，放在GitHub上，生成网页版和PDF版本的书籍。相较传统的Latex，更简单方便。适合当代程序员。

本文参考的资料主要来源于官网，相较之下，重点更突出，可以快速地 初始化、撰写、发布 一本书。

Install gitbook command line tool:

1
npm install gitbook-cli -g

Create a book:

1
gitbook init ./directory

Preview and serve your book:

1
gitbook serve

Or build the static website:

1
gitbook build
阅读全文 »

发表于 更新于 分类于 Disqus：

今年仍然是在学校度过了自己23岁的生日。下午和舍友出去看了电影《狮子王》，晚上去 城南旧事 吃了“北京菜。算是庆祝了自己的生日吧。祝我生日快乐。
自从18岁之后离开家，独自来到帝都读书。过生日就不再像在家里那么热闹和有人情味了。在外地漂泊，虽说还有同学或朋友祝你生日快乐，亲近的还会陪伴我一起过生日，但家人的温暖却再也没有了。大家来来往往，身边的人也基本只能陪伴一段时间。每每此时，都会怀念小时候。

最近北京的天气特别热，不由的心情烦躁。持续性混吃等死，间断性踌躇满志。经常思考些所谓的人生意义，努力的价值，自己的目标。
我本人可以说是胸无大志，从小读过不少书，尤其是历史书。早早地就明白了自己与王侯将相无缘，只是个贩夫走卒。现在想要的也不多，在大城市有立锥之地，有个温暖的家。这样的想法，恐怕也是千千万万北漂一族的目标吧。这也是我努力学习的动力所在呀。
最近在看一部很火的网剧“长安十二时辰”，里面有句台词很引起我的共鸣：有些人生来就是长安人，有些人到死都没成为长安人。剧中无数长安底层人的生活，不正是影射的北漂族的生活嘛。

时间如白驹过隙。匆匆之间，2019年已经过了一半。回望自己半年前写下的新年愿景，有些容易的已经实现，难的只能推迟到后半年，甚至来年了。

  • 健康的身体和良好的生活习惯。这点做的很不够，因为贪睡、怕热、懒等缘由，跑步、健身 并没有坚持下来。我需要做自我批评。
  • 一段大大厂的实习。在ST实习了一学期，并不算大厂。大大厂的实习需要推迟到明年实现了。
  • 一段交换经历。预计下学期执行。
  • 计算机系统 和 算法 的进阶。LeetCode的最初任务已经超额完成了，算法相关的书CTCI也翻过一遍，这点是值得肯定的。事实上，我在此下的功夫不少。除此之外，对C的熟悉也基本完成了，可以在简历上或面试上大胆的说C是自己的主语言了。剩余的 CSAPP、SICP、设计模式，并没有很大的进展，聊胜于无。
  • 实际面试经历。参加了字节跳动广告组的面试，和 字节跳动夏令营的笔试、以及 Google的电话面试。这些面试经历真的很刺激人，让人深入的认识到自己的短处。比如算法上离Kick start的标准还差的远呢！

我认为自己需要牢记的2点：

  • 时间就是金钱！
  • 身体是革命的本钱！
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (5) Q2 (5) Q3 (8) Q4 (8)
451 / 4931 YoungForest 16 1:24:26 0:09:37 0:17:39 1:14:26 2 null

1122. Relative Sort Array

定制排序规则。

时间复杂度: O(N long N),
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> location;
        for (int i = 0; i < arr2.size(); ++i) {
            location[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [location](int lhs, int rhs) -> bool {
            if (location.find(lhs) != location.end() && location.find(rhs) != location.end()) {
                return location.at(lhs) < location.at(rhs);
            } else if (location.find(lhs) == location.end() && location.find(rhs) != location.end()) {
                return false;
            } else if (location.find(lhs) != location.end() && location.find(rhs) == location.end()) {
                return true;
            } else {
                return lhs < rhs;
            }
        });
        return arr1;
    }
};

1123. Lowest Common Ancestor of Deepest Leaves

树的问题递归解决。关注需要返回给父节点的信息和传递给子节点的信息。

时间复杂度: O(N). 每个节点遍历一次。
空间复杂度: O(N). 树的最深深度，即递归的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 {
    pair<int, TreeNode*> recurse(TreeNode* root, int depth) {
        if (root == nullptr) {
            return {depth, nullptr};
        }
        auto l = recurse(root->left, depth + 1);
        auto r = recurse(root->right, depth + 1);
        if (l.first > r.first) {
            return l;
        } else if (l.first == r.first) {
            return {l.first, root};
        } else {
            return r;
        }
    }
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        auto ans = recurse(root, 0);
        return ans.second;
    }
};

1124. Longest Well-Performing Interval

阅读全文 »

发表于 更新于 分类于 Disqus：

今早由于参加托福考试，无法像往常一样参加周赛。赛后补题。

1108. Defanging an IP Address

One pass. 直接替换即可。

时间复杂度: O(N),
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string defangIPaddr(string address) {
        string ret;
        for (char c : address) {
            if (c == '.') {
                ret.push_back('[');
                ret.push_back('.');
                ret.push_back(']');
            } else {
                ret.push_back(c);
            }
        }
        return ret;
    }
};

1109. Corporate Flight Bookings

Brute force. TLE.
时间复杂度: O(N * bookings.length);
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ret(n, 0);
        for (const auto& booking : bookings) {
            for (int i = booking.at(0); i <= booking.at(1); ++i) {
                ret[i - 1] += booking.at(2);
            }
        }
        return ret;
    }
};

One pass. 前些天刚做过类似的题目。站点上下车的问题。
时间复杂度: O(max(booking.length, N)).
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> stops(n + 1, 0);
        vector<int> ret(n, 0);
        for (const auto& booking : bookings) {
            stops[booking[0] - 1] += booking[2];    // begin
            stops[booking[1]] -= booking[2];    // end
        }
        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += stops[i];
            ret[i] = total;
        }
        return ret;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (5) Q2 (5) Q3 (8) Q4 (8)
396 / 4272 YoungForest 14 1:01:14 0:11:38 0:28:38 0:56:14 1 null

1103. Distribute Candies to People

Brute force. 模拟整个分配过程。

时间复杂度: O(sqrt(candies.size())). 因为1 + 2 + ... + n = n * (n + 1) / 2 = candies.size().
空间复杂度: O(num_people).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> ret(num_people, 0);
        int row = 0;
        while (candies > 0) {
            for (int i = 0; i < ret.size() && candies > 0; ++i) {
                ret[i] += min(candies, row * num_people + i + 1);
                candies -= min(candies, row * num_people + i + 1);
            }
            ++row;
        }
        return ret;
    }
};

1104. Path In Zigzag Labelled Binary Tree

利用2个算法

  • 如果是顺序编号的话，父节点编号为 子节点编号 / 2 向下取整。
  • 反序编号，可以转成顺序编号。

时间复杂度: O(log N),
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int getLevel(int label) {
        int level = 0;
        while (label > 0) {
            label >>= 1;
            ++level;
        }
        return level - 1;
    }
    int complete(int label, int level) {
        return (1<<(level + 1)) - 1 - label + (1<<level);
    }
public:
    vector<int> pathInZigZagTree(int label) {
        int n = getLevel(label);
        const int level = n + 1;
        // cout << level << endl;
        vector<int> ret(level);
        int true_label = label;
        if (n % 2 == 1) {
            true_label = complete(label, n);
        }
        ret[n] = true_label;
        for (int i = n - 1; i >= 0; --i) {
            ret[i] = ret[i + 1] / 2;
        }
        // for (int i = 0; i <= n; ++i) {
        //     cout << ret[i] << " ";
        // }
        for (int i = 0; i <= n; ++i) {
            if (i % 2 == 1)
                ret[i] = complete(ret[i], i);
        }
        return ret;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (5) Q2 (5) Q3 (8) Q4 (8)
851 / 4504 YoungForest 13 1:39:38 null 1:00:12 2 1:19:38 2 null

本次比赛的失误主要在于第二题sort中的cmp函数写错了，没有保证 严格有序。一直segment fault。即 a < b, 必有 b !< a.

1093. Statistics from a Large Sample

Intution:
熟悉C++和统计中的这5个统计值的意义即可。
时间复杂度: O(N),
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<double> sampleStats(vector<int>& count) {
        double minimum = 255.0, maximum = 0.0, mean = 0.0, median = 0.0, mode = 0.0;
        auto minimum_it = find_if(count.cbegin(), count.cend(), [](const auto & a) -> bool {
            return a > 0;
        });
        minimum = minimum_it - count.cbegin();
        auto max_it = find_if(count.crbegin(), count.crend(), [](const auto & a) -> bool {
            return a > 0;
        });
        maximum = static_cast<int>(count.size()) - (max_it - count.crbegin()) - 1;
        
        int num = 0;
        for (int i = 0; i < count.size(); ++i) {
            mean += i * count[i];
            num += count[i];
        }
        mean /= num;
        int total = num;
        num = 0;
        for (int i = 0; i < count.size(); ++i) {
            if (count[i] == 0)
                continue;
            num += count[i];
            if (num * 2 > total) {
                if (median > 0) {
                    median = (median + i) / 2;
                } else {
                    median = i;
                }
                break;
            } else if (num * 2 == total) {
                median = i;
            }
        }
        
        auto mode_it = max_element(count.cbegin(), count.cend());
        mode = mode_it - count.cbegin();
        
        return {minimum, maximum, mean, median, mode};
    }
};

1094. Car Pooling

Intuition:
模拟整个上下车的过程。在每个站台判断是否超载。
时间复杂度: O(N log N)
空间复杂度: O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool carPooling(vector<vector<int>> &trips, int capacity) {
       map<int, int> stops;
       for (const auto& trip : trips) {
           stops[trip[1]] += trip[0];
           stops[trip[2]] -= trip[0];
       }
       int passengers = 0;
       for (const auto& stop : stops) {
           passengers += stop.second;
           if (passengers > capacity)
               return false;
       }
       return true;
    }
};

1095. Find in Mountain Array

本题算是一类新题型：交互式问题。
3次 二分搜索搞定。

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (6) Q4 (8)
234 / 4126 YoungForest 22 1:18:45 0:25:23 1 0:36:29 0:51:47 1:13:45

周一自然辩证法考试，周二矩阵考试，还是强行抽出时间参加contest。本身复习就不充分，平时的学习也没有十分扎实，我也是心大。
200名的时间至少要在1:14:23以内。

1089. Duplicate Zeros

Intuition:
因为要求in-place, 一个自然的想法是从后向前更新值。
2次遍历，第一次正向遍历，得到结果数组最后一位的原始坐标。
第二次逆向遍历，更新结果数组。

Time complexity: O(N),
Space complexity: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int zeros = 0;
        int i = 0;
        for (i = 0; i < arr.size() && i + zeros < arr.size(); ++i) {
            if (arr[i] == 0) {
                ++zeros;
            }
        }
        --i;
        for (int j = arr.size() - 1; j >= 0; --j, --i) {
            arr[j] = arr[i];
            if (arr[i] == 0 && (i + zeros < arr.size())) {
                --j;    // 多减一j
                if (j >= 0)
                    arr[j] = 0;
            }
        }
    }
};

因为忽略 最后一个0如果位数不够的话，将不进行扩展。被罚时一次。

测试用例:

1
2
3
4
5
6
[0]
[0,0]
[0,0,0]
[0,0,1]
[8,4,5,0,0,0,0,7]
[8,4,5,0,0,0,0,0,7]

1090. Largest Values From Labels

阅读全文 »
0%