LeetCode 392. Is Subsequence

Sep 5, 2016

题目描述:

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1: s = "abc", t = "ahbgdc"

Return true.

Example 2: s = "axc", t = "ahbgdc"

Return false.

双指针, O(n)时间复杂度.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int sLen = s.length(), tLen = t.length();
        if(sLen == 0 && tLen == 0) return true;
        int sp = 0;
        for(int i = 0; i < tLen; i++){
            if(s[sp] == t[i]) sp++;
            if(sp == sLen) return true;
        }
        return false;
    }
};

LeetCode 109. Convert Sorted List to Binary Search Tree

Sep 4, 2016

题目描述:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

最简单的方法就是遍历一次链表, 把每个节点的值放入一个数组中, 然后就变成了上一题.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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 {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        deque<int> nums;
        ListNode *p = head;
        while(p){
            nums.push_back(p->val);
            p = p->next;
        }
        return buildBST(nums, 0, nums.size());
    }
    
    TreeNode* buildBST(deque<int> &nums, int left, int right){
        if(left >= right) return nullptr;
        
        int mid = (left + right) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = buildBST(nums, left, mid);
        node->right = buildBST(nums, mid + 1, right);
        return node;
    }
};

如果不使用辅助空间, 就要实现一个根据节点距头结点的距离来获取节点的函数. 这样的话每次访问节点都要遍历一部分链表.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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 {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int len = 0;
        ListNode *p = head;
        while(p){
            len++;
            p = p->next;
        }
        return buildBST(head, len);
    }
    
    TreeNode* buildBST(ListNode *head, int len){
        if(len <= 0) return nullptr;
        
        int mid = len / 2;
        ListNode *n = getNode(head, mid);
        
        TreeNode* node = new TreeNode(n->val);
        node->left = buildBST(head, mid);
        node->right = buildBST(n->next, len - mid - 1);
        return node;
    }
    
    ListNode* getNode(ListNode *head, int index){
        int i = index;
        while(head && index > 0){
            head = head->next;
            index--;
        }
        return head;
    }
};

LeetCode 108. Convert Sorted Array to Binary Search Tree

Sep 4, 2016

题目描述;

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

根据有序数组来构建一颗平衡二叉搜索树. 比较直观的方法就是选择给定数组的中间位置的元素作为根节点的值, 然后把左边和右边的元素分别递归地生成左右子树, 这样可以保证高度平衡.

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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if(num.size() == 0)return NULL;
        
        return sortedArrayToBSTImpl(num, 0, num.size());
    }
    
    TreeNode* sortedArrayToBSTImpl(vector<int> &num, int start, int end){
        if(end <= start)return NULL;
        int mid = (start + end) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        
        root->left = sortedArrayToBSTImpl(num, start, mid);
        root->right = sortedArrayToBSTImpl(num, mid + 1, end);
        
        return root;
    }
};

LeetCode 107. Binary Tree Level Order Traversal II

Sep 1, 2016

题目描述:

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

先层次遍历, 然后将得到的二维数组颠倒顺序.

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
/**
 * 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 {
    vector<vector<int>> ret;
public:
	vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root) return ret;
        BFS(root);
        reverse(ret.begin(), ret.end());
		return ret;
	}
	
	void BFS(TreeNode *root){
	    queue<TreeNode*> nodeQueue;
	    queue<int> levelQueue;
	    
	    nodeQueue.push(root);
	    levelQueue.push(0);
	    
	    while(!nodeQueue.empty()){
	        TreeNode *node = nodeQueue.front();
	        int nodeLevel = levelQueue.front();
	        nodeQueue.pop();
	        levelQueue.pop();
	        
	        if(nodeLevel >= ret.size()){
	            ret.resize(nodeLevel + 1);
	        }
	        ret[nodeLevel].push_back(node->val);
	        
	        if(node->left){
	            nodeQueue.push(node->left);
	            levelQueue.push(nodeLevel + 1);
	        }
	        if(node->right){
	            nodeQueue.push(node->right);
	            levelQueue.push(nodeLevel + 1);
	        }
	    }
	}
};

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Sep 1, 2016

题目描述:

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

与上一题LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal非常相似, 只不过先序序列变成了后序序列, 实质上并没有什么变化, 仍然使用相同的方法.

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
/**
 * 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 {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeImpl(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
    
    TreeNode* buildTreeImpl(vector<int> &inorder, int inStart, int inEnd, vector<int> &postorder, int postStart, int postEnd){
        if(inStart == inEnd || postStart == postEnd) return nullptr;
        int rootVal = postorder[postEnd - 1];
        TreeNode *root = new TreeNode(rootVal);
        int leftLen, rightLen;
        for(int i = inStart; i < inEnd; i++){
            if(inorder[i] == rootVal){
                leftLen = i - inStart;
                break;
            }
        }
        rightLen = (inEnd - inStart - leftLen - 1);
        root->left = buildTreeImpl(inorder, inStart, inStart + leftLen, postorder, postStart, postStart + leftLen);
        root->right = buildTreeImpl(inorder, inStart + leftLen + 1, inEnd, postorder, postStart + leftLen, postEnd - 1);
        return root;
    }
};

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Sep 1, 2016

题目描述:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

通过中序遍历序列和先序遍历序列来还原一颗二叉树. 由于题目指出可以假设树中不存在重复元素, 所以在先序序列的第一个元素就是根节点的值, 然后再中序序列中找到这个值就可以把中序序列划分为左子树的中序序列和右子树的中序序列, 并且得到左右子树的节点数量, 根据节点数量就可以把先序序列划分开来. 然后就可以通过递归来分别构建左右子树.

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
/**
 * 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 {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        return buildBinaryTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
    
    TreeNode* buildBinaryTree(vector<int> &preorder, int preLeft, int preRight, vector<int> &inorder, int inLeft, int inRight){
        if(preLeft >= preRight || inLeft >= inRight) return nullptr;
        TreeNode *node = new TreeNode(preorder[preLeft]);
        int rootPosInOrder;
        for(int i = inLeft; i < inRight; i++){
            if(inorder[i] == node->val){
                rootPosInOrder = i;
                break;
            }
        }
        int leftNum = rootPosInOrder - inLeft, rightNum = inRight - rootPosInOrder - 1;
        node->left = buildBinaryTree(preorder, preLeft + 1, preLeft + 1 + leftNum, inorder, inLeft, inLeft + leftNum);
        node->right = buildBinaryTree(preorder, preLeft + 1 + leftNum, preRight, inorder, inLeft + leftNum + 1, inRight);
        return node;
    }
};

在Hyper-V为Linux扩大分区

Sep 1, 2016

问题来源

我在Hyper-V里安装的虚拟机一开始只分配了10G的虚拟硬盘, 今天编译RISC-V Toolchain的时候硬盘空间耗尽了(顺带吐槽一下编译的时候下载源代码再次被网速折磨), 所以就要扩大虚拟磁盘的空间.

Hyper-V中的设置

首先就是在Hyper-V中的磁盘编辑中修改虚拟磁盘的大小. 这一步没有任何问题, 下一步是修改分区表.

修改分区表

在Linux中要修改一个分区的大小, 必须要把它umount, 但是我要扩展的是整个系统分区, 所以需要用Linux的系统安装光盘启动. 然后运行gparted程序来修改分区大小.

回到Linux中的设置

到了上一步还是不行, 因为我要扩展的是一个逻辑分区 logical volume, 需要在原来的系统中扩展逻辑分区和启用新的分区空间才可以.

1
$ lvresize -l 100%VG [your device]

100%VG的意思是使用全部空闲空间. 然后启用空间.

1
$ resize2fs [your device]

LeetCode 104. Maximum Depth of Binary Tree

Aug 31, 2016

题目描述:

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归递归递.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;
        int left_depth = 1, right_depth = 1;
        if(root->left != NULL)
            left_depth = maxDepth(root->left) + 1;
        if(root->right != NULL)
            right_depth = maxDepth(root->right) + 1;
            
        return left_depth > right_depth ? left_depth : right_depth;
    }
};

LeetCode 103. Binary Tree Zigzag Level Order Traversal

Aug 31, 2016

题目描述:

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

这道题与上一题Binary Tree Level Order Traversal非常相似, 只需要在BFS之后汇总的时候以正反方向间隔的形式放入level中即可. 我是全部正向放入之后再对偶数行颠倒来完成的.

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
/**
 * 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 {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return vector<vector<int>>();
        vector<int> vals, level;
        generateMap(root, vals, level);
        int maxLevel = 0;
        for(int i = 0; i < level.size(); i++) if(maxLevel < level[i]) maxLevel = level[i];
        vector<vector<int>> re(maxLevel + 1);
        for(int i = 0; i < vals.size(); i++){
            re[level[i]].push_back(vals[i]);
        }
        
        for(int i = 1; i <= maxLevel; i += 2){
            reverse(re[i].begin(), re[i].end());
        }
        return re;
    }
    
    void generateMap(TreeNode* root, vector<int> &vals, vector<int> &level){
        queue<TreeNode*> nodes;
        queue<int> levels;
        nodes.push(root);
        levels.push(0);
        while(!nodes.empty()){
            TreeNode* p = nodes.front();
            int l = levels.front();
            vals.push_back(p->val);
            level.push_back(l);
            if(p->left){
                nodes.push(p->left);
                levels.push(l + 1);
            }
            if(p->right){
                nodes.push(p->right);
                levels.push(l + 1);
            }
            nodes.pop();
            levels.pop();
        }
    }
};

LeetCode 102. Binary Tree Level Order Traversal

Aug 31, 2016

题目描述:

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

我的方法是使用广度优先搜索遍历每一个节点并计算出每一个节点的level值, 然后再遍历一次节点把节点放到相应的level中去. 时间和空间复杂度都是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
/**
 * 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 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root){
            return vector<vector<int>>();
        }
        // 用于BFS的队列, qLevel用于保存BFS中相应节点的level
        queue<TreeNode*> BFS;
        queue<int> qLevel;
        // 把遍历到的每一个节点都放到vector中保存, 用于最后汇总
        vector<int> level;
        vector<TreeNode*> nodes;
        
        BFS.push(root);
        qLevel.push(0);
        int maxLevel = 0;
        nodes.push_back(root);
        level.push_back(0);
        while(!BFS.empty()){
            TreeNode* node = BFS.front();
            int currentLevel = qLevel.front();
            if(node->left){
                BFS.push(node->left);
                qLevel.push(currentLevel + 1);
                nodes.push_back(node->left);
                level.push_back(currentLevel + 1);
            }
            if(node->right){
                BFS.push(node->right);
                qLevel.push(currentLevel + 1);
                nodes.push_back(node->right);
                level.push_back(currentLevel + 1);
            }
            if(currentLevel + 1 > maxLevel) maxLevel = currentLevel + 1;
            BFS.pop();
            qLevel.pop();
        }
        // 再次遍历节点并放到相应的level中去
        vector<vector<int>> re(maxLevel);
        for(int i = 0; i < nodes.size(); i++){
            re[level[i]].push_back(nodes[i]->val);
        }
        return re;
    }
};