LeetCode 481. Magical String

Jan 10, 2017

题目描述：

A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules:

The string S is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string S itself.

The first few elements of string S is the following: S = “1221121221221121122……”

If we group the consecutive '1’s and '2’s in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 …

and the occurrences of '1’s or '2’s in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 …

You can see that the occurrence sequence above is the S itself.

Given an integer N as input, return the number of '1’s in the first N number in the magical string S.

Note: N will not exceed 100,000.

Example 1:

1
2
3
Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

按照一个序列中的数值往这个序列的末尾增加元素，要求1与2是间隔的，不能超过两个相同的值在一起。按照题目给出的规律生成这个序列就可以了。

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:
    int magicalString(int n) {
        if(n == 0) return 0;
        vector<int> s(n + 1);
        s[0] = 1, s[1] = 2, s[2] = 2;
        int index1 = 3, index2 = 2;
        int ans = 1;
        while(index1 < n){
            int t = s[index1 - 1] == 1 ? 2 : 1;
            for(int i = 0; i < s[index2]; i++){
                s[index1 + i] = t;
            }
            if(t == 1){
                ans += s[index2];
            }
            index1 += s[index2];
            index2++;
        }
        if(index1 > n && s[index1 - 1] == 1) ans--; 
        return ans;
    }
};

LeetCode 449. Serialize and Deserialize BST

Jan 10, 2017

题目描述：

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

序列化一个二叉搜索树，有两个问题：

  1. 如何序列化一个二叉搜索树的节点
  2. 如何序列化节点里的值

因为二叉搜索树本身的有序性，所以按照先序遍历的顺序来保存节点就足够恢复BST的结构了。而对于节点里的值，最简单的方法是变为字符串，可是节点值的长度各不相同，这给区分不同的节点带来了麻烦，所以我用四个字节（char）来保存一个int，实际上就是计算机中的小端法存储。

对于节点的序列化与反序列化使用递归来实现。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    int decodeInt(string &s, int begin){
        int v = 0;
        for(int i = 0; i < 4; i++){
            int t = s[i + begin];
            v |= ((t & 0xff) << (i << 3));
        }
        return v;
    }
    
    string encodeInt(int v){
        string s;
        for(int i = 0; i < 4; i++){
            s.push_back(v & 0xff);
            v >>= 8;
        }
        return s;
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return encodeDFS(root);
    }
    
    string encodeDFS(TreeNode *node){
        if(!node) return string();
        return encodeInt(node->val) + encodeDFS(node->left) + encodeDFS(node->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //cout<<data<<endl;
        return deserializeHelper(data, 0, data.length());
    }
    
    TreeNode* deserializeHelper(string &data, int left, int right){
        if(left == right) return nullptr;
        int v = decodeInt(data, left);
        //cout<<v<<endl;
        TreeNode *node = new TreeNode(v);
        int mid = right;
        for(int i = left + 4; i < right; i += 4){
            int t = decodeInt(data, i);
            if(t > v) {
                mid = i;
                break;
            }
        }
        node->left = deserializeHelper(data, left + 4, mid);
        node->right = deserializeHelper(data, mid, right);
        return node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

LeetCode 445. Add Two Numbers II

Jan 10, 2017

题目描述：

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

翻转链表后相加再翻转回来。至于Follow up，关键的问题在于加法要求最低位对齐，而单向链表又不能回溯，所以最直接的办法就是用两个数组或者栈保存每个节点的前一个节点……虽然我觉得这实在是有点多此一举，不过没有想到什么更好的办法。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode ret(0);
        ListNode *p = &ret, *p1 = l1, *p2 = l2;
        int carry = 0;
        while(p1 || p2 || carry > 0){
            int s;
            if(p1 && p2){
                s = p1->val + p2->val + carry;
                p1 = p1->next;
                p2 = p2->next;
            }
            else if(p1){
                s = p1->val + carry;
                p1 = p1->next;
            }
            else if(p2){
                s = p2->val + carry;
                p2 = p2->next;
            }
            else{
                s = carry;
            }
            p->next = new ListNode(s % 10);
            carry = s / 10;
            p = p->next;
        }
        ret.next = reverseList(ret.next);
        return ret.next;
    }
    
    ListNode* reverseList(ListNode *l){
        ListNode *p1, *p2;
        p1 = l; p2 = l->next;
        while(p2){
            ListNode *tmp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = tmp;
        }
        l->next = nullptr;
        return p1;
    }
};

LeetCode 442. Find All Duplicates in an Array

Jan 9, 2017

题目描述：

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

跟LeetCode 448. Find All Numbers Disappeared in an Array类似，只不过这次是寻找出现过两次的数。我用0（输入数据中不会出现）来表示该数已经记录过来防止重复计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            if(nums[nums[i] - 1] == 0 || nums[i] == i + 1){
                continue;
            }
            else if(nums[nums[i] - 1] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
                i--;
            }
            else{
                ans.push_back(nums[i]);
                nums[nums[i] - 1] = 0;
            }
        }
        return ans;
    }
};

LeetCode 434. Number of Segments in a String

Jan 9, 2017

题目描述：

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

1
2
Input: "Hello, my name is John"
Output: 5

比较简单，注意处理连续的空格和结尾。还有有符号数与无符号数的隐式转换问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countSegments(string s) {
        int prevIndex = -1, ans = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == ' '){
                if(prevIndex != i - 1){
                    ans++;
                }
                prevIndex = i;
            }
        }
        if(prevIndex < (int)s.length() - 1) ans++;
        return ans;
    }
};

LeetCode 448. Find All Numbers Disappeared in an Array

Jan 9, 2017

题目描述：

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

寻找没有出现过的数字，因为数组中的元素满足1 ≤ a[i] ≤ n，所以可以利用下标来保存一个数是否出现过，把一个数放到它对应的下标处，然后再找出哪些下标与元素不对应就是没有出现过的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            if(nums[nums[i] - 1] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
                i--;
            }
        }
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] - 1 != i) ans.push_back(i + 1);
        }
        return ans;
    }
};

阳光之下依然是罪恶——扯扯《GTA5》

Jan 8, 2017

GTA5已经是好几年前发售的游戏了，奈何我电脑配置太低，再加上80G的大小让我望而却步。上个月Steam特价94软妹币，没忍住剁了手。54个小时通了主线剧情和大部分的支线，还有在游戏里瞎搞花了一些时间，所以主线剧情所需的时间大概在30~40小时左右。

要说我第一次玩GTA5还是一年半前，用老逼的电脑玩了一丁点。很多年以前……大概是初中的时候玩过《罪恶都市》还是《圣安地列斯》，不过那时什么都不懂，属于真正的瞎玩一通，甚至都没有剧情的概念，现在只记得卡在一个开遥控飞机的任务上再也没有过去过。这次通关GTA5之后想写点东西，就当是这几十个小时人生的总结吧。

本文涉及剧透！

背景

GTA5的故事主要发生在洛圣都，NETA洛杉矶。游戏里的洛圣都真是不折不扣的罪恶都市，到处都散发着荒诞的气息。健忘症的警察、泛滥的枪支毒品、比黑帮还像黑帮的FIB和IAA、发生在电视直播上的爆炸和枪杀、大街上一言不合便拔枪开干……一切都构筑在赤裸裸的金钱、暴力与性的基础上。剧情中出现的人物似乎没有一个有正常的三观，这座城市似乎也不存在秩序，自私、贪婪、恃强凌弱也不像现实中那样遮遮掩掩，从这个角度来说，我觉得GTA中的暴力与罪恶恰恰是对现实中掩饰暴力与罪恶的讽刺。

从玩家，也就是三位主角的角度来看，这座城市的中上层简直是面目可憎。本来是秩序维护者的FIB和IAA都不是什么好东西，IAA为了拨款人为制造恐怖袭击，FIB出场的几个探员个个都不干净。有钱人想尽办法赚钱而毫无底线。同时下层则是黑帮火并，毒品交易，各种坑蒙拐骗。

游戏中的洛圣都绝大部时间都是阳光普照，然而在这阳光下的城市却弥漫着浓浓的罪恶气息。

人物

GTA5的主角有三人，崔佛、麦克和富兰克林，我还是分开来说说吧。

崔佛：老实说我还是挺喜欢这种真性情的人的，但可惜他是个疯子。也许说疯子不太准确，也有的人说他有时候控制不住自己的行为。在崔佛刚出场的时候就开始杀人，在后来的行动中又干出各种杀光别人帮派所有人的事情，麦克也总是说老崔只是喜欢杀人而已。但是如果仅仅这样我也并不讨厌他，因为他都是在你死我活的环境下杀人（除了第一个被打死的强尼），而且老崔莫名的有一些童真（当然更有可能是精神缺陷，他也说自己有童年阴影），比如他的个人载具保险杠那里的一只玩具熊，还有大结局（第三条路那个结局）之后遇到他妈妈痛哭流涕；而且他对朋友重情重义（后来我知道前提是他把你当朋友）。但是当我看到他杀了弗洛伊德（貌似没有死）和他女友黛伯拉的时候我就觉得老崔实在是太危害社会了，当老崔浑身是血的走出公寓以及特写给到窗户上的大量血迹时，我就觉得他们两个实在是遭了无妄之灾，一个被表弟的狐朋狗友把生活搞得一团糟（也有可能本来就一团糟），另一个只不过是想把一个看起来就不正常的人从自己家里赶出去而已结果不知道被装了几个袋子。当时我就知道结局要选择杀老崔还是杀麦克，所以我决定不能留老崔，他就像一个坏掉的定时炸弹一样，可能拿在手里就炸了。但是到最后真的选择的时候还是心软了，毕竟是一起抢过银行，怼过坦克，挨过枪子的交情，而且转念一想，三位主角在大街上碾死的围观群众个个都成百上千（都是我的锅，我不好好开车），老崔那次杀人让我印象深刻只不过是剧情中杀人而已，三位主角手上都沾满鲜血，没有理由单独除掉老崔。

麦克：三位主角中我最同情麦克了。从一开始富兰克林潜入麦克的房子然后看到他老婆出轨，儿子废柴，女儿胸大无脑只想出名我就开始同情他了，这情况要是换我早就用人生重来枪了。麦克是最像一个文明人的人，换一句话说他是最虚伪的人。他一直想要的就是稳定的生活，可是当需要钱的时候他首先想到的还是抢劫。其实从GTA5的剧情中我看不出麦克为什么对这个从各方面都是bull shit的家庭有那么强的执念，大概我还是没法理解那种年龄的想法吧。

富兰克林：我一直觉得富兰克林是一个推动剧情的人物，最终选择线路的时候也是富兰克林来做决定。他一开始只是个偷车的黑帮小混混，不太能看得出他做事的动机，大概是想做一番大事（THE BIG ONE！），感觉富兰克林这个人物塑造的不是很丰满。在救拉玛，救麦克的行动中可以看出他很重义气。

剧情

GTA5的剧情总的来说就是抢枪抢，杀杀杀……我在最后的选择中选了“第三条路”，一个HE，这个结局太好了，好的不真实。仿佛不费吹灰之力就干掉了所有的对头，一切的麻烦都烟消云散，基友冰释前嫌重归于好，抢来的黄金足够大家挥霍。然而理智告诉我这实在是不合逻辑，不是说选择既不杀麦克也不杀崔佛不合逻辑，而是选择“第三条路”之后这个“不费吹灰之力就干掉了所有的对头”不合逻辑，感觉与前面的剧情落差太大。我也看了另外两个结局，首先我觉得富兰克林不可能去杀麦克，感觉毫无理由，杀崔佛至少还有拆除定时炸弹目的。我觉得要是在现实中我大概会选杀崔佛，要不然指不定他又会搞什么麻烦，这种随机出现BUG的组件还是尽早清除掉为好。

支线任务我还没有做完，不过我对那两个追星的老年夫妇印象挺深的。病态的追寻名人，搜集名人的生活垃圾等等的Hentai行为甚至不惜进行绑架，没有追星经历的我还真是叹为观止。还有那个拿自己老婆当酬劳的房地产中介……一个大写的服，连老崔都表示佩服。

LeetCode 209. Minimum Size Subarray Sum

Jan 2, 2017

题目描述：

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

使用双指针。因为都是正数，所以子串的长度越长和越大。先增大右指针直到[left,right]中的元素的和>=s，然后从中依次去掉开头的数，也就是left增大，直到和不再>=s，更新最短长度。然后再次增大右指针进入下一个循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.empty()) return 0;
        int left = 0, minSum = 0, minLen = INT_MAX, curSum = 0;
        for(int i = 0; i < nums.size(); i++){
            if(i - left + 1 > minLen){
                curSum -= nums[left++];
            }
            curSum += nums[i];
            if(curSum >= s){
                for(; left <= i && curSum >= s; left++){
                    curSum -= nums[left];
                }
                minLen = i - left + 2;
            }
        }
        return minLen == INT_MAX ? 0 : minLen;
    }
};

LeetCode 208. Implement Trie (Prefix Tree)

Jan 2, 2017

题目描述：

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

实现前缀树。因为输入只有小写字母，所以直接使用26叉树，使用vector来实现支持任意分支数也可以。

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
class TrieNode {
public:
    char val;
    vector<TrieNode*> children;
    bool wordEnd = false;
    // Initialize your data structure here.
    TrieNode(char v = 0) : val(v){
        children = vector<TrieNode*>(26, nullptr);
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        insertToNode(word, root);
    }
    
    void insertToNode(string word, TrieNode* node){
        if(word.empty()){
            node->wordEnd = true;
            return;
        }
        
        int pos;
        for(pos = 0; pos < word.size(); pos++){
            if(node->children[word[pos] - 'a'] != nullptr){
                node = node->children[word[pos] - 'a'];
            }
            else{
                break;
            }
        }
        
        if(pos == word.size()) {
            node->wordEnd = true;
            return;
        }

        for(int i = pos; i < word.size(); i++){
            TrieNode *tmp = new TrieNode(word[i]);
            node->children[word[i] - 'a'] = tmp;
            node = tmp;
        }
        node->wordEnd = true;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        int pos = 0;
        TrieNode *p = root;
        for(; pos < word.size(); pos++){
            if(p->children[word[pos] - 'a'] != nullptr){
                p = p->children[word[pos] - 'a'];
            }
            else{
                break;
            }
        }
        if(pos == word.size() && p->wordEnd) return true;
        else return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        int pos = 0;
        TrieNode *p = root;
        for(; pos < prefix.size(); pos++){
            if(p->children[prefix[pos] - 'a'] != nullptr){
                p = p->children[prefix[pos] - 'a'];
            }
            else{
                break;
            }
        }
        if(pos == prefix.size()) return true;
        else return false;
    }

private:
    TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

LeetCode 207. Course Schedule

Jan 2, 2017

题目描述：

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Hints:

  • This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  • Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  • Topological sort could also be done via BFS.

Hint中已经说的很明确了，就是判断一个图中有没有环。我用DFS来遍历每个节点，有两个出现环的情况：

  1. 出现了路径中已经出现的节点
  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
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:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<vector<int>> gg(numCourses);
		vector<int> prerequested(numCourses, false), allVisited(numCourses, false);
		for (int i = 0; i < prerequisites.size(); i++) {
			gg[prerequisites[i].first].push_back(prerequisites[i].second);
			prerequested[prerequisites[i].second] = true;
		}
		int prerequestedNum = 0;
		for (int i = 0; i < numCourses; i++) {
			if (!prerequested[i]) {
				vector<int> thisTimeVisited(numCourses, false);
				thisTimeVisited[i] = true;
				allVisited[i] = true;
				if (!DFS(gg, i, allVisited, thisTimeVisited)){
					return false;
				}
				thisTimeVisited[i] = false;
			}
			else {
				prerequestedNum++;
			}
		}
		if (prerequestedNum == numCourses) {
			//no start node
			return false;
		}
		for (int i = 0; i < numCourses; i++) {
			if (!allVisited[i]) {
				//some nodes cannot be visited
				return false;
			}
		}
		return true;
	}

	bool DFS(vector<vector<int>> &gg, int node, vector<int> &allVisited, vector<int> &thisTimeVisited) {
		vector<int> nextNodes = gg[node];
		for (int i = 0; i < nextNodes.size(); i++) {
			if (thisTimeVisited[nextNodes[i]]) {
				//find cycle
				return false;
			}
			allVisited[nextNodes[i]] = true;
			thisTimeVisited[nextNodes[i]] = true;
			if (!DFS(gg, nextNodes[i], allVisited, thisTimeVisited))
				return false;
			thisTimeVisited[nextNodes[i]] = false;
		}
		return true;
	}
};