LeetCode 101. Symmetric Tree

Aug 30, 2016

题目描述:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
6
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
6
  1
 / \
2   2
 \   \
 3    3

Note: Bonus points if you could solve it both recursively and iteratively.

最直观的方法就是先把二叉树翻转, 然后再判断两棵二叉树是否相同.

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
/**
 * 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:
    void copyTree(TreeNode* root, TreeNode *copy){
        if(!root){
            return;
        }
        if(root->left)
            copy->left = new TreeNode(root->left->val);
        else
            copy->left = NULL;
        copyTree(root->left, copy->left);
        if(root->right)
            copy->right = new TreeNode(root->right->val);
        else
            copy->right = NULL;
        copyTree(root->right, copy->right);
    }
    void reverseTree(TreeNode *root){
        if(!root)
            return;
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        reverseTree(root->left);
        reverseTree(root->right);
    }
    bool sameTree(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 == NULL)
            return true;
        if(root1 == NULL || root2 == NULL)
            return false;
        if(root1->val != root2->val)
            return false;
        return sameTree(root1->left, root2->left) && sameTree(root1->right, root2->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        TreeNode *mirrorRoot = new TreeNode(root->val);
        copyTree(root, mirrorRoot);
        reverseTree(mirrorRoot);
        return sameTree(root, mirrorRoot);
    }
};

非递归的方法就是使用迭代而不是递归来分别从不同的方向遍历左右子树, 注意, 不能用先序遍历或者后序遍历, 比如这组数据[1,2,2,null,3,null,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
49
50
/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isMirror(root->left, root->right);
    }
    
    bool isMirror(TreeNode* left, TreeNode *right){
        stack<TreeNode*> leftPath, rightPath;
        while((!leftPath.empty() || left != nullptr) && (!rightPath.empty() || right != nullptr)){
            TreeNode *curLeftNode = nullptr, *curRightNode = nullptr;
            if(left != nullptr){
                leftPath.push(left);
                left = left->left;
            }
            else{
                left = leftPath.top();
                curLeftNode = left;
                leftPath.pop();
                left = left->right;
            }
            if(right != nullptr){
                rightPath.push(right);
                right = right->right;
            }
            else{
                right = rightPath.top();
                curRightNode = right;
                rightPath.pop();
                right = right->left;
            }
            if((curLeftNode && curRightNode && curLeftNode->val != curRightNode->val) || (!(curLeftNode && curRightNode) && !(curLeftNode == nullptr && curRightNode == nullptr))) {
                // 这个布尔表达式的意思是当前的左右节点都不为null并且值不等, 或者其中有且只有
                // 一个null
                return false;
            }
        }
        if(leftPath.empty() && left == nullptr && rightPath.empty() && right == nullptr) return true;
        else return false;
    }
};

附上标准的非递归遍历方法:

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
// 先序遍历
void preOrderIter(struct node *root)  
{  
    stack<struct node *> s;  
    while (root != NULL || !s.empty()) {  
        if (root != NULL) {  
            cout << root->data << " "; //访问结点并入栈  
            s.push(root);                
            root = root->left;         //访问左子树  
        } else {  
            root = s.top();            //回溯至父亲结点  
            s.pop();  
            root = root->right;        //访问右子树  
        }  
    }  
    cout << endl;  
}

// 中序遍历
void inOrderIter(struct node *root)  
{  
    stack<struct node *> s;  
    while (root != NULL || !s.empty()) {  
        if (root != NULL) {  
            s.push(root);  
            root = root->left;  
        }  
        else {  
            root = s.top();  
            cout << root->data << " ";  //访问完左子树后才访问根结点  
            s.pop();  
            root = root->right;        //访问右子树  
        }  
    }  
    cout << endl;  
}

// 后序遍历
void postOrderIter(struct node *root)  
{  
    if (!root) return;  
    stack<struct node*> s, output;  
    s.push(root);  
    while (!s.empty()) {  
        struct node *curr = s.top();  
        output.push(curr);  
        s.pop();  
        if (curr->left)  
            s.push(curr->left);  
        if (curr->right)  
            s.push(curr->right);  
    }  
      
    while (!output.empty()) {  
        cout << output.top()->data << " ";  
        output.pop();  
    }  
    cout << endl;  
}

LeetCode 391. Perfect Rectangle

Aug 30, 2016

题目描述:

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

img

Example 1:

1
2
3
4
5
6
7
8
9
10
rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

img

Example 2:

1
2
3
4
5
6
7
8
9
rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

img

Example 3:

1
2
3
4
5
6
7
8
9
rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

img

Example 4:

1
2
3
4
5
6
7
8
rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

一开始我对于这道题的思路是这样的:

  • 第一步, 遍历所有小的矩形计算它们的面积之和并且计算出最终应该拼成的大矩形的端点位置(左下角和右上角), 如果面积之和与大矩形的面积不相等, 那么就肯定不可能拼成.
  • 第二步, 判断小矩形之间是不是有重叠.

问题在于第二步, 判断矩形是否有重叠比较容易, 但是两两比较要求O(n2)的时间复杂度, 超时了.

如果不对小矩形两两判断是否有重叠而使用累积的办法看某个小矩形与之前所有小矩形拼成的多边形是否有重合的话, 实现起来相当复杂, 所以应该有更好的方法.

在Discuss中看到了一个相当妙的办法https://discuss.leetcode.com/topic/56081/easy-understanding-o-n-python-solution, 基本思想就是如果最终能拼成大矩形, 那么除了大矩形的四个顶点只出现一次外, 其他的每个小矩形的顶点只能出现两次或者四次. 所以就可以用一个map来记录小矩形的每个顶点出现的次数, 然后再遍历这个map判断其中的顶点是不是都满足条件. 时间复杂度(O(nlogn + 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
class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int n = rectangles.size(), areaSum = 0;
        vector<int> finalRect(4);
        map<pair<int, int>, int> corners;
        finalRect[0] = finalRect[1] = INT_MAX, finalRect[2] = finalRect[3] = INT_MIN;
        vector<int> areas(n, 0);
        for(int i = 0; i < n; i++){
            areas[i] = (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
            vector<pair<int, int>> corner = {{rectangles[i][0], rectangles[i][1]}, {rectangles[i][2], rectangles[i][3]}, {rectangles[i][0], rectangles[i][3]}, {rectangles[i][2], rectangles[i][1]}};
            for(int j = 0; j < 4; j++){
                if(corners.count(corner[j])){
                    corners[corner[j]]++;
                }
                else{
                    corners[corner[j]] = 1;
                }
            }
            finalRect[0] = min(finalRect[0], rectangles[i][0]);
            finalRect[1] = min(finalRect[1], rectangles[i][1]);
            finalRect[2] = max(finalRect[2], rectangles[i][2]);
            finalRect[3] = max(finalRect[3], rectangles[i][3]);
            areaSum += areas[i];
        }
        int finalArea = (finalRect[2] - finalRect[0]) * (finalRect[3] - finalRect[1]);
        if(areaSum != finalArea) return false;
        
        for(auto i = corners.begin(); i != corners.end(); i++){
            if(((i->first.first == finalRect[0] && i->first.second == finalRect[1]) || (i->first.first == finalRect[2] && i->first.second == finalRect[3]) || (i->first.first == finalRect[0] && i->first.second == finalRect[3]) || (i->first.first == finalRect[2] && i->first.second == finalRect[1]))){
                if(i->second != 1){
                    return false;
                }
            }
            else if(i->second == 2 || i->second == 4){
                continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

LeetCode 389. Find the Difference

Aug 29, 2016

题目描述:

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

使用哈希表来记录每个字母出现的次数, 多出现的字符就是增加的字符.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> nums(26, 0);
        for(int i = 0; i < s.length(); i++){
            nums[s[i] - 'a']++;
        }
        for(int i = 0; i < t.length(); i++){
            if(--nums[t[i] - 'a'] < 0) return t[i];
        }
        return 0;
    }
};

还可以使用异或. 由于s与t除了一个元素以外其他都相同, 所以使用0分别于s与t的每个元素异或, 得到的就是多余的那一个字符.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        char ch = 0;
        for(int i = 0; i < s.length(); i++){
            ch ^= s[i];
        }
        for(int i = 0; i < t.length(); i++){
            ch ^= t[i];
        }
        return ch;
    }
};

LeetCode 100. Same Tree

Aug 28, 2016

题目描述:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

很简单, 使用递归来判断每个节点是否相等.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == NULL && q == NULL) return true;
        if((p == NULL && q != NULL) || (p != NULL && q == NULL))return false;
        if(p->val != q->val)return false;
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

LeetCode 99. Recover Binary Search Tree

Aug 28, 2016

题目描述:

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

使用O(n)辅助空间的方法就是使用中序遍历从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
/**
 * 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 {
    deque<TreeNode*> seq;
public:
    void recoverTree(TreeNode* root) {
        inOrder(root);
        vector<int> mistakeNodes;
        for(int i = 0; i < seq.size() - 1; i++){
            if(seq[i]->val > seq[i + 1]->val){
                mistakeNodes.push_back(i);
            }
        }
        if(mistakeNodes.size() == 1){
            swap(seq[mistakeNodes[0]]->val, seq[mistakeNodes[0] + 1]->val);
        }
        else{
            swap(seq[mistakeNodes[0]]->val, seq[mistakeNodes[1] + 1]->val);
        }
    }
    
    void inOrder(TreeNode *root){
        if(root == nullptr) return;
        inOrder(root->left);
        seq.push_back(root);
        inOrder(root->right);
    }
};

而把这一思路推广到不使用辅助空间, 很容易就可以发现我们并不需要一个完整的序列, 只需要相邻两个值的大小关系, 所以我们只要在遍历过程中维持两个节点值即可. 另外由于我们没有完整的序列, 所以在mistakeNodes中要同时保存前一个元素比后一个元素大的这两个元素, 因为对于被交换的较小值来说, 它在后一个元素的位置, 而对于较大值来说, 它位于前一个元素的位置. 当然也可以通过判断mistakeNodes中是否已经有元素来避免同时保存.

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
/**
 * 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<TreeNode*> mistakeNodes;
    vector<TreeNode*> tmpNodes;
public:
    void recoverTree(TreeNode* root) {
        tmpNodes.resize(2);
        inOrder(root);
        if(mistakeNodes.size() == 2){
            swap(mistakeNodes[0]->val, mistakeNodes[1]->val);
        }
        else{
            swap(mistakeNodes[0]->val, mistakeNodes[3]->val);
        }
    }
    
    void inOrder(TreeNode *root){
        if(root == nullptr || mistakeNodes.size() == 4) return ;
        inOrder(root->left);
        tmpNodes[0] = tmpNodes[1];
        tmpNodes[1] = root;
        if(tmpNodes[0] && tmpNodes[0]->val > tmpNodes[1]->val){
            mistakeNodes.push_back(tmpNodes[0]);
            mistakeNodes.push_back(tmpNodes[1]);
        }
        inOrder(root->right);
    }
};

LeetCode 98. Validate Binary Search Tree

Aug 28, 2016

题目描述:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
4
  2
 / \
1   3

Binary tree

1
[2,1,3]

, return true.

Example 2:

1
2
3
4
  1
 / \
2   3

Binary tree

1
[1,2,3]

, return false.

验证一个二叉搜索树是否合法, 使用递归的方法来依次遍历左右子树.

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
/**
 * 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:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        if(root->left && BSTMax(root->left) >= root->val){
            return false;
        }
        if(root->right && BSTMin(root->right) <= root->val){
            return false;
        }
        return isValidBST(root->left) && isValidBST(root->right);
    }
    
    int BSTMax(TreeNode* root){
        if(!root->right){
            return root->val;
        }
        return BSTMax(root->right);
    }
    
    int BSTMin(TreeNode* root){
        if(!root->left){
            return root->val;
        }
        return BSTMin(root->left);
    }
};

LeetCode 97. Interleaving String

Aug 24, 2016

题目描述:

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.

使用动态规划, dp[i][j]代表s1的前i个字符与s2的前j个字符是否能组成s3的前i+j个字符.

显然dp[0][0]能组成空字符串, 所以dp[0][0]为真. 而对于i=0和j=0的情况来说, 直接比较s1的前i个字符或s2的前j个字符与s3是否相同就可以了.

接下来的dp[i][j]分为两种情况:

  1. s3[i+j-1]的字符与s1[i-1]相同, 代表s3[i+j-1]的字符可以从s1中取得. 此时dp[i][j]为真则要求dp[i-1][j]为真.
  2. s3[i+j-1]的字符与s2[j-1]相同, 代表s3[i+j-1]的字符可以从s2中取得. 此时dp[i][j]为真则要求dp[i][j-1]为真.

递推方程为

1
dp[i][j] = (dp[i - 1][j] && s3[i + j - 1] == s1[i - 1]) || (dp[i][j - 1] && s3[i + j - 1] == s2[j - 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length() + s2.length() != s3.length()) return false;
        vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= s1.size(); i++){
            if(!dp[i - 1][0]) break;
            if(s1[i - 1] == s3[i - 1]) dp[i][0] = 1;
        }
        for(int i = 1; i <= s2.size(); i++){
            if(!dp[0][i - 1]) break;
            if(s2[i - 1] == s3[i - 1]) dp[0][i] = 1;
        }
        for(int i = 1; i <= s1.size(); i++){
            for(int j = 1; j <= s2.size(); j++){
                if((dp[i - 1][j] && s3[i + j - 1] == s1[i - 1]) || (dp[i][j - 1] && s3[i + j - 1] == s2[j - 1])) dp[i][j] = 1;
            }
        }
        return dp[s1.size()][s2.size()];
    }
};

LeetCode 96. Unique Binary Search Trees

Aug 24, 2016

题目描述:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example, Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

采用递归+动态规划来解决.

首先一颗n个节点的BST, 假设它的根节点值为r(1<=r<=n), 那么它的不同形态数量等于所有左子树的形态数量(r-1个节点)×所有右子树的形态数量(n-r个节点), 而因为一颗BST的形态数量只与节点数量有关而与节点的具体值无关, 所以可以用一个数组来记录已经计算过数量的n来减少计算.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numTrees(int n) {
        vector<int> nums(n + 1, -1);
        return numsTrees(n, nums);
    }
    
    int numsTrees(int n, vector<int> &nums){
        int num = 0;
        if(n == 0 || n == 1){
            return 1;
        }
        for(int i = 1; i <= n; i++){
            num += ((nums[i - 1] == -1 ? numsTrees(i - 1, nums) : nums[i - 1]) * (nums[n - i] == -1 ? numsTrees(n - i, nums) : nums[n - i]));
        }
        nums[n] = num;
        return num;
    }
};

LeetCode 95. Unique Binary Search Trees II

Aug 24, 2016

题目描述:

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example, Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

返回由1-n组成的所有可能的二叉搜索树. 先来复习一下二叉搜索树BST的定义:

  1. 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

根据定义, 很容易想到通过递归的方法来产生所有可能的BST, 对于[1,n]n个节点, 从中取一个值1<=r<=n, 则属于[1, r)的值在左子树, 属于(r,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
/**
 * 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<TreeNode*> generateTrees(int n) {
        return buildBST(1, n + 1);
    }
    
    vector<TreeNode*> buildBST(int left, int right){
        vector<TreeNode*> re;
        if(left >= right){
            return re;
        }
        for(int i = left; i < right; i++){
            auto leftVector = buildBST(left, i);
            auto rightVector = buildBST(i + 1, right);
            for(int j = 0; j < leftVector.size(); j++){
                if(rightVector.empty()){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftVector[j];
                    node->right = nullptr;
                    re.push_back(node);
                }
                else{
                    for(int k = 0; k < rightVector.size(); k++){
                        TreeNode* node = new TreeNode(i);
                        node->left = leftVector[j];
                        node->right = rightVector[k];
                        re.push_back(node);
                    }
                }
            }
            if(leftVector.empty()){
                if(rightVector.empty()){
                    TreeNode* node = new TreeNode(i);
                    node->left = nullptr;
                    node->right = nullptr;
                    re.push_back(node);
                }
                else{
                    for(int k = 0; k < rightVector.size(); k++){
                        TreeNode* node = new TreeNode(i);
                        node->left = nullptr;
                        node->right = rightVector[k];
                        re.push_back(node);
                    }
                }
            }
        }
        return re;
    }
};

LeetCode 388. Longest Absolute File Path

Aug 23, 2016

题目描述:

Suppose we abstract our file system by a string in the following manner:

The string “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext” represents:

dir subdir1 subdir2 file.ext The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” represents:

dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is “dir/subdir2/subsubdir2/file2.ext”, and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note: The name of a file contains at least a . and an extension. The name of a directory or sub-directory will not contain a … Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

虽然题目描述非常的长, 但是实际的难度并不大. 目录结构是一个树形结构, 使用栈可以模拟深度优先搜索, 遍历根目录到每一个叶子节点的路径, 从中找出总长度最长的一条路径. 每个节点通过\n分割, 而每个节点前的\t的个数就是该节点所的层次.

要注意输入字符串中\n和\t都只是一个字符而不是两个字符.

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
class Solution {
public:
    int lengthLongestPath(string input) {
        vector<int> pathLevel; // 记录path中节点的层次
        vector<string> path; // 记录路径
        int pos = 0, nextPos = 0, maxLen = 0;
        while(true){
            nextPos = input.find("\n", pos);
            string node = input.substr(pos, nextPos - pos); // 获取当前节点的字符串
            
            int level = getLevel(node);

            while(!pathLevel.empty() && pathLevel.back() >= level){ // 路径退回到当前节点的上一层
                pathLevel.pop_back();
                path.pop_back();
            }
            
            path.push_back(node);
            pathLevel.push_back(level);
            
            if(isFile(node)){
                maxLen = max(maxLen, getTotalLen(path) - 1);
            }
            
            if(nextPos == string::npos) break;
            pos = nextPos + 1;
        }
        return maxLen;
    }
    
    bool isFile(string &s){ // 判断是不是file
        int index = s.find('.');
        if(index == string::npos || index == s.length() - 1) return false;
        else return true;
    }
    
    int getTotalLen(vector<string> &v){ // 根据path计算总长度
        int len = 0;
        for(auto s : v){
            len += s.length();
            len++;
        }
        return len;
    }
    
    int getLevel(string &s){ // 计算字符串头部\t的个数
        if(s.length() < 2) return 0;
        int level = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '\t' ){
                level++;
            }
        }
        s = s.substr(level); // 清除头部的\t
        return level;
    }
};