YoungForest's blog

发表于 更新于 分类于 Disqus：

本次比赛不难，但代码实现起来不易。不容易一次写到bug-free。考察的是用编程语言处理复杂的逻辑，和各种意外情况。比如 第3题，当前一个dp为0时，长度应该更新为2，除此之外，dp+1。第四题，在各种情况下寻找分隔符时，没有找到，应该如何处理。

Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (5) Q4 (5)
388 / 4765 YoungForest 24 1:21:20 0:15:54 0:30:16 0:38:05 1:21:20
大概需要1个小时内做完，才能进入前200。

第4题由于一些边界条件，我调试了不少时间。我分析花这么长时间的原因。还是写代码写的少，对变量更新的边界条件不敏感。比如string::find没有找到的时候，其他各个坐标该如何更新。我就是由于没找到的时候，返回了npos(-1), current_find_index此时应该等于end，而不是继续在-1上加分隔符的长度。

1025. Divisor Game

一道找规律的题目。
Intution:
dp。 Solution(N) = true if any Solution(N’s divisor) is false, else false。
时间复杂度: O(N^2),
空间复杂度: 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
class Solution {
public:
    bool divisorGame(int N) {
        // 1, false
        // 2, 1 true
        // 3, false
        // 4, 1 true
        // 5, 1 false
        // 6. 3, true
        // 7, 1, false
        // 8, 1, true
        // 9, false
        vector<bool> dp(1001, false);
        dp[1] = false;
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                if (i % j == 0 && dp[i - j] == false) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }
};

把1～9的结果输出之后发现了了不得的规律。试了一下，一行代码就搞定了。
用数学归纳法可以证明:
前提:
N 为奇数，false;
N 为偶数，true。

  1. 如果N为偶数，取x=1，N-1为false。则N为True.
  2. 如果N为奇数，它所有的因子也必为奇数，即N-x一定为偶数，true. 则N为False。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool divisorGame(int N) {
        // 1, false
        // 2, 1 true
        // 3, false
        // 4, 1 true
        // 5, 1 false
        // 6. 3, true
        // 7, 1, false
        // 8, 1, true
        // 9, false
        return N % 2 != 1;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

本次比赛的题号吓了我一跳. LeetCode也是任性，直接从5000+开始出题了。看来题量上涨的空间已经超乎我的想象了。

言归正传，本次contest也是以简单题拼速度为主。

Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (5) Q4 (5)
323 / 4894 YoungForest 22 0:59:58 0:10:44 0:19:06(2) 0:30:57 0:49:58
也是大概需要50min内完成，才能进入200名内。

1021. Remove Outermost Parentheses

Intution:
括号匹配的问题。利用栈的思维，设置一个flag表示是否是Outermost。利用状态机的思维构造返回的字符串。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string removeOuterParentheses(string S) {
        int flag = 0;
        string ret;
        for (char c : S) {
            if (c == '(') {
                if (flag != 0)
                    ret.push_back(c);
                flag++;
            } else if (c == ')') {
                if (flag != 1)
                    ret.push_back(c);
                flag--;
            }
        }
        
        return ret;
    }
};

1022. Sum of Root To Leaf Binary Numbers

Intution:
recurse, 二进制表示的值用传值的方式进行传递。

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
/**
 * 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 {
    const static int mod = 1e9 + 7;
    int ret = 0;
    void dfs(TreeNode* root, int value) {
        int current_value = (value << 1) % mod + root->val;
        if (root->left) dfs(root->left, current_value);
        if (root->right) dfs(root->right, current_value);
        if (!root->left && !root->right)
            ret = (ret + current_value) % mod;
    }
public:
    int sumRootToLeaf(TreeNode* root) {
        dfs(root, 0);
        return ret;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

今天刷题的时候遇到一个有趣的题目，求一个数字各个位相加的和，知道和小于10。链接.
题目本身并不难，递归或者迭代都可以解决。但如何在O(1)的复杂度内求解，才是真正的考点。

答案很简单: 1 + (num - 1) % 9.
有兴趣的可以看看证明和扩展: wikipedia.

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (5) Q3 (5) Q4 (5)
258 / 5236 YoungForest 19 0:57:19 0:06:23 0:25:41 0:36:25 0:52:19(1)

本次contest比较简单，都是常规题。没有hard来区分水平，就看谁的实现的速度快了。50min内才能前200名。
第二题耽误了些时间，最后一题刚开始思路秀逗了，走了些弯路。

1029. Binary Prefix Divisible By 5

Intution:
Stright forward. 循环移位，判断除5的余数。需要注意current要取模，因为A的长度会很大。
时间复杂度: O(N),
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> ret(A.size(), false);
        uint32_t current = 0;
        for (int i = 0; i < A.size(); i++) {
            current = (current << 1) % 10;
            current += A[i];
            if (current == 0 || current == 5)
                ret[i] = true;
        }
        
        return ret;
    }
};

1028. Convert to Base -2

Intution:
类比2进制的解法。不断整除2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0) return "0";
        string ret_reverse;
        bool flag = true; // 正
        while (N > 0) {
            if (N % 2 == 1) {
                ret_reverse.push_back('1');
                if (flag)
                    N /= 2;
                else
                    N = (N + 1) / 2;    // 此处要加一，因为最后一位的权重此时是-1. N下一步的迭代要把其补上
            } else {
                ret_reverse.push_back('0');
                N /= 2;
            }
            flag = !flag;
        }
        
        reverse(ret_reverse.begin(), ret_reverse.end());
        return ret_reverse;
    }
};

1030. Next Greater Node In Linked List

Intution:
单调栈。
时间复杂度: O(N),
空间复杂度: O(N).

阅读全文 »

发表于 更新于 分类于 Disqus：

上周末由于准备 Google的kick start round A，放弃了一次LeetCode weekly contest。但当天晚上还是把LeetCode的题补完了。4题不简单，但经过思考还是独立做出来了。算是给被kick start难到自闭的我一个安慰吧。

1020. Partition Array Into Three Parts With Equal Sum

Intution:
One pass. Find the pivots which is 1/3 and 2/3.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum_all = accumulate(A.begin(), A.end(), 0);
        if (sum_all %3 != 0) return false;
        int sum_3 = sum_all / 3;
        int sum_prefix = 0;
        for (int i = 0; i < A.size(); i++) {
            if (sum_prefix == sum_3 && sum_3 != sum_all)
                sum_3 += sum_all / 3;
            sum_prefix += A[i];
        }
        return sum_3 == sum_all;
    }
};

1022. Smallest Integer Divisible by K

Intution:
模拟笔算过程。
如果个位数不为1， 3， 7，9的话，直接范围-1. 代表找不到符合条件的N。
之后用笔算的方法，一直凑最后一位为1，知道前面所有的位数也均为1.
因为一定有解，所以循环一定会结束。

时间复杂度: O(result.length),
空间复杂度: 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
class Solution {
    bool all11(int i) {
        while (i > 0) {
            if (i % 10 != 1) return false;
            i /= 10;
        }
        return true;
    }
public:
    int smallestRepunitDivByK(int K) {
        if (K % 10 != 1 && K % 10 != 3 && K % 10 != 7 && K % 10 != 9) return -1;
        vector<int> dictionary(10);
        vector<int> gewei(10);
        for (int i = 0; i < dictionary.size(); i++) {
            dictionary[i] = K * i;
            gewei[K * i % 10] = i;
        }
        int ret = 0;
        int remain = K;
        while (!all11(remain)) {
            int last = remain % 10;
            int new_value = 0;
            new_value = gewei[(11 - last) % 10] * K;
            ret++;
            remain = (new_value + remain) / 10;
        }
        while (remain > 0) {
            if (remain % 10 != 1) return -1;
            remain /= 10;
            ret++;
        }
        
        return ret;
    }
};

1021. Best Sightseeing Pair

阅读全文 »

发表于 更新于 分类于 Disqus：

[题目链接]

这是我首次参加Kick start比赛。之前本科的时候，和舍友tls 参加过它的前身Code Jam。今年才正式准备Kick start的一系列比赛。原因是这是Google选拔软件工程师的途径，而Google是我的Dream Company。
我于5月22日在清华参加了Google的校园宣讲会。在宣讲会上，前辈们也分外强调准备和参加Kick start的重要性。GG作为一家很左的公司，分外强调公平。而Kick start就是实现招聘公平的一个工具。毕竟相比其他公司的过分注重内推，Kick start给了弱势学校的学生一个机会。

由于平台故障，最后25min无法提交。虽然我提前一个小时放弃比赛了，但是晚上收到邮件告知这个bug。如果没有这个Bug的话，我的排名可能还要后退。
最后的排名是 600/3305.
得分分别为

Training Parcels Contention Total
我的 20 15 0 35
总分 20 35 45 100

也就是说，我过了签到题和第二题的small case。
题目的难度总体比LeetCode要难的多，最后只有2个人拿到了满分。

1. Training

从一个N人的队伍中，挑出P人。要求这P个人的训练时长最小，训练时长为 技能点最大的人的技能点 - 每个人的技能点 之和。
Intuition：
先排序。然后用一个长度为P的窗口，不断滑动，求的最小值。

时间复杂度：O(N log 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
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<int> &skills, int N, int P) {
    sort(skills.begin(), skills.end());

    int need_hour = 0;
    for (int i = 0; i < P - 1; i++) {
        need_hour += skills[P - 1] - skills[i];
    }
    int ret = need_hour;
    int left = 0, right = P - 1;
    while (right < N) {
        right++;
        need_hour += (P - 1) * (skills[right] - skills[right - 1]);
        need_hour -= skills[right - 1] - skills[left];
        left++;
        ret = min(ret, need_hour);
    }
    
    return ret;
}

int main() {
    int T;
    cin >> T;
    
    for (int i = 0; i < T; i++) {
        int N, P;
        cin >> N >> P;
        vector<int> skills;
        for (int j = 0; j < N; j++) {
            int s;
            cin >> s;
            skills.push_back(s);
        }
        cout << "Case #" << i + 1 << ": " << solution(skills, N, P) << endl;
    }
}

2. Parcels

阅读全文 »

发表于 更新于 分类于 Disqus：

最近在学习google-test的使用和源码，在make install的时候发现除了向/usr/local/中安装了头文件，/usr/lib/中安装了shared library外，还向/usr/local/lib/pkgconfig/中安装了2个.pc文件。所以说，这个pkg-config是个什么东西呢？

从一份Guide中，我们可以发现pkg-config的所有有用的基本信息。

Overview

现代的计算机系统使用很多层的组件以向用户提供API。一个很大的难点在于如何合适地将这些不同层的组件整合起来。pkg-config这一工具收集了安装在系统上的库的metadata, 用户可以很方便地查看这些metadata。比如，google-test安装的其中一个pc文件gtest.pc的内容是：

包含使用gtest库的所有信息，如头文件安装位置、shared library的位置，编译时需要的编译选项。可以说，使用gtest看这些metadata就够了。

1
2
3
4
5
6
7
8
9
10
prefix=${pcfiledir}/../..
libdir=${prefix}/lib
includedir=${prefix}/include

Name: gtest
Description: GoogleTest (without main() function)
Version: 1.9.0
URL: https://github.com/google/googletest
Libs: -L${libdir} -lgtest 
Cflags: -I${includedir} -DGTEST_HAS_PTHREAD=1

计算机系统上没有一个如pkg-config的metadata系统的话，定位和获得系统提供的服务的细节将会很难。
对于一个开发者，安装你的包的时候同时安装pkg-config将会极大地方便你的API被用户使用。

pkg-config最主要的使用是当程序编译和链接一个库的时候提供必要的细节。这些元信息被存储在pkg-config文件中。这些文件以.pc为后缀，存放在pkg-config工具知道的特定路径里。
一个.pc文件中包含2种信息，metadata keywords和freeform variables。
前者以keyword开头，后接冒号和value，如“Name: gtest"。
后者用=连接变量的值和名字，如"prefix=…"。
keywords是由pkg-config定义和导出的。
variables不是必须的，但是可以被用来表示pkg-config没有涉及的信息 或是 被keywords使用以增加keywords定义的灵活性。

一个pc文件最好对应一个library文件。文件名(除了后缀)也最好相同。

最重要的metadata域是Requires, Requires.private, Cflags, Libs 和 Libs.private。它们可以被外部的工程用来编译和链接到这个library。优先使用private域，以避免暴露不必要的库给用户。如果用户不不直接使用requires library的symbols，就不应该直接链接到该库。

阅读全文 »

发表于 更新于 分类于 Disqus：

前3道题比较顺利，30min内解决。最后一道hard题目，思路比较混乱，1个小时愣是没做出来。
Contest给我的感觉是，还是拼的熟练度。
因为第2、3题之前做过类似的，所以很快就做出来了。第2题甚至只用了2分钟!!!

Rank Name Score Finish Time Q1 (2) Q2 (4) Q3 (6) Q4 (8)
348 / 5164 YoungForest 19 1:24:03 0:11:33(1) 0:13:42(1) 0:27:37 None

1012. Complement of Base 10 Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int bitwiseComplement(int N) {
        if (N == 0) return 1;
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((1 << i) > N) break;
            ret += ((N & (1 << i)) == 0) ? (1 << i) : 0;
        }
        
        return ret;
    }
};

时间复杂度: O(log N)，与数字的长度成正比。
空间复杂度: O(1).

由于没有注意corner case, if (N == 0) return 1;。wrong answer了一次。
我的方法是straight forward的，没有任何技巧和trick。因为是签到题嘛，而且时间复杂度足够了。
也有一些其他的思路：
比如找到最大的X = 1111..11使得X >= N, return X - N或return X^N即可。

1013. Pairs of Songs With Total Durations Divisible by 60

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> hashmap(60, 0);
        int ret = 0;
        for (const int & t : time) {
            ret += hashmap[(60 - t + 60000) % 60];
            hashmap[t % 60]++;
        }
        return ret;
    }
};

与著名的two sum思路一样，考察hashmap的使用。
为了将所有的值，包括负数，映射到60以内，我使用了(60 - t + 60000) % 60，其实更好的做法是(60 - t % 60) % 60。

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

阅读全文 »

发表于 更新于 分类于 Disqus：

本周4道题目分数分别为4 4 5 6, 应该不是很难的，加油， Forest！

因为题目太简单，即使提前15min做完了，排名还是912 / 4712。这次比赛真的是简单，完全比拼的是写码的速度和熟练度。是否可以一次bug-free很重要。因为如果某个corner case错了，再去调试是很花时间的。我1，2题都是错了一次，耽误了很多时间。

Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (5) Q4 (6)
931 / 4059 YoungForest 19 1:24:03 0:24:49(1) 0:44:58(1) 1:05:12 1:14:03

1005. Maximize Sum Of Array After K Negations

常规签到题。

Intution:
有负数，先flip最小的负数;
没负数，有0。 flip 0;
只有正数，K为奇数，flip最小的正数;
…, K为偶数，不flip.

时间复杂度: O(N log N), 因为排序。
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), less<int>());
        int i;
        for (i = 0; i < A.size() && K > 0 && A[i] < 0; ++i) {
            A[i] = -A[i];
            K--;
        }
        if (K > 0 && K % 2 == 1) {
            if (i > 0 && A[i-1] < A[i]) A[i-1] = -A[i-1];
            else A[i] = -A[i];
        }
        return accumulate(A.begin(), A.end(), 0, plus<int>());
    }
};

我Wrong Answer了一次，因为flip最小的正数时，没有考虑原来是负数的更小的正数，也就是需要有if (i > 0 && A[i-1] < A[i]) A[i-1] = -A[i-1];这行代码。

即使是签到题，在Discuss区果然还是发现了一些牛逼的代码。比如，O(N)的解法。

阅读全文 »

发表于 更新于 分类于 Disqus：

今天试着边做题边录视频，由于场地的限制，无法用麦克风进行讲解，效果差强人意。虽然可以用文字注释进行一些弥补，但丧失了视频传播的最大优势。以后还是以博客为主，传播自己的思想吧。
尤其是本次只做出2道题目，后2道题目都有尝试，但均失败了。视频效果太差。本身大家如果在B站上看视频的话，都是为了看up主秀的。这次没秀起来，遭遇了滑铁卢，甚是尴尬。不过最后我还是打算把视频放上去。就是这么脸皮厚，不怕丢人，不怕以后被翻黑历史。

排名也直接飞到1500名开外，这周的ranking怕不是要跌。

结果：

Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (6) Q4 (9)
1684 / 4564 YoungForest 8 0:38:19 0:16:17 0:33:19 WA(1)

1002. Find Common Characters

因为录视频的时候把思路都写在开始部分了。就只分析一下复杂度吧。
Time complexity: O(N), N为A中所有字符串长度之和。
空间复杂度：O(1), 因为字符被限制在26个小写字母里，否则的话，是和字符数成正比的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        // 用一个vector记录出现的字母，因为只有小写，大小为26，还因为要记录出现的最小次数，所以类型为int即可
        vector<int> record(26, numeric_limits<int>::max());
        for (string & s: A) {
            vector<int> record1String(26, 0);
            for (char c : s) {
                record1String[c - 'a']++;
            }
            for (int i = 0; i < 26; ++i) {
                record[i] = min(record[i], record1String[i]);
            }
        }
        
        vector<string> result;
        for (int i = 0; i < 26; i++) {
            result.insert(result.end(), record[i], string(1, char(i + 'a')));
        }
        
        return result;
    }
};

1003. Check If Word Is Valid After Substitutions

Time complexity: O(N ^ 2), 因为find, 构造 nextS的操作是O(N)的，每次while循环S的长度减3, 需要 长度/3 次循环。
Space complexity: O(N), 因为构造了新的nextS。不过这个是可以消除的，反复利用原来的S的空间就可以。但是要写多余的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string S) {
        // 首先理解valid string的定义:
        // 这个定义的递归的
        // 对于任何valid的string，把"abc"插入任何位置的字符串仍为valid
        // 初始的valid string只有"abc"
        // 所以，判断一个string是否是valid的，我们只需要不断地把"abd"抽掉，如果剩下"abc"，则true，否则false
        // 这个过程也可以递归进行
        
        // 递归解法会stack overflow, 换迭代解法
        while (true) {
            if (S == "abc") return true;
            auto index = S.find("abc");
            if (index == string::npos) { // 没找到"abc"字串
                return false;
            } else {
                string nextS(S.begin(), S.begin() + index);
                nextS.insert(nextS.end(), S.begin() + index + 3, S.end());
                S = nextS;
            }
        }
    }
};
阅读全文 »
0%