Posted on | Edited on | In |

我理解的回溯法，简单来说，就是遍历，就是DFS！

其它的都是想想都知道的：谁不知道碰到走不下去的就回去，谁不知道碰到走不下去退回到上一步，而不是退到初始的地方。

基本解决思想

记录之前的操作，这样可以退回到上一步的操作，进而进行下一个candidate的试探。

考虑要点

1. 非法结束

当进入非法的状态的时候，执行怎样的操作，通常在递归的过程中，直接return结束即可，如果有特殊的操作，需要进行特殊的处理。

2. 满足条件

满足条件的情况下，需要进行怎样的操作，比如将正确的值记录下来，返回成功的状态等。

3. 遍历试探

这一步是最重要的一步，也是最繁琐的一步。

需要遍历所有可能的选择，往前“走一步”，在“走了一步”的状态下进行新的一轮操作。操作完成之后，需要“回退一步“到原来的状态。

这个遍历可能出现的情况有：二维地图的上下左右遍历，找数组满足条件的值得遍历数组等。

相关问题

以下问题都能够或多或少体现上述的三个要点。

subset problem

LeetCode 78. Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<int>& nums, int start_idx) {
        res.push_back(curr);
        for (int i = start_idx; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            backtrack(res, curr, nums, i + 1);
            curr.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> curr;
        backtrack(res, curr, nums, 0);
        return res;
    }
};

LeetCode 90. Subsets II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<int>& nums, int start_idx) {
        res.push_back(curr);
        for (int i = start_idx; i < nums.size(); i++) {
            if (i > start_idx && nums[i] == nums[i - 1]) // 注意如何跳过重复！！！
                continue;
            curr.push_back(nums[i]);
            backtrack(res, curr, nums, i + 1);
            curr.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> curr;
        sort(nums.begin(), nums.end());
        backtrack(res, curr, nums, 0);
        return res;
    }
};

N-Queen

LeetCode 51. N-Queens

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 {
private:
    bool check(vector<string>& curr, int r, int c, int n) {
        for (int i = 1; i <= r; i++) {
            if (c - i >= 0 && curr[r - i][c - i] == 'Q' ||
               curr[r - i][c] == 'Q' ||
               c + i < n && curr[r - i][c + i] == 'Q')
                return false;
        }
        return true;
    }
    void fill(vector<vector<string>>& res, vector<string>& curr, int row, int n) {
        if (row >= n) {
            res.push_back(curr);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check(curr, row, i, n)) {
                curr[row][i] = 'Q';
                fill(res, curr, row + 1, n);
                curr[row][i] = '.';
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> curr;
        for (int i = 0; i < n; i++) {
            string s(n, '.');
            curr.push_back(s);
        }
        fill(res, curr, 0, n);
        return res;
    }
};

Sudoku

LeetCode 37. Sudoku Solver

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
class Solution {
private:
    bool check(vector<vector<char>>& board, int r, int c) {
        for (int i = 0; i < 9; i++) {
            if (i != r && board[i][c] == board[r][c])
                return false;
        }
        for (int j = 0; j < 9; j++) {
            if (j != c && board[r][j] == board[r][c])
                return false;
        }
        int r_div = r / 3;
        int c_div = c / 3;
        for (int i = r_div * 3; i < (r_div + 1) * 3; i++) {
            for (int j = c_div * 3; j < (c_div + 1) * 3; j++) {
                if ((i != r || j != c) && board[i][j] == board[r][c])
                    return false;
            }
        }
        return true;
    }
    bool fill(vector<vector<char>>& board, int r, int c) {
        int i, j;
        bool found_next = false;
        for (i = r; i < 9; i++) {
            for (j = c; j < 9; j++) {
                if (board[i][j] == '.') {                    
                    found_next = true;
                    break;
                }
            }
            if (found_next)
                break;
            j = 0;
        }
        if (i >= 9)
            return true;
        for (char k = '1'; k <= '9'; k++) {
            board[i][j] = k;
            if (check(board, i, j)) {
                if (fill(board, r, c))
                    return true;
            }
            board[i][j] = '.';
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        fill(board, 0, 0);
    }
};

参考

https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

Posted on | Edited on | In |

在基础数据结构课程中学到的知识，时隔一年之后，真的是忘得一干二净，这些东西，不用，真的就会忘掉。 在思索图像四联通分量标记时等价表的实现时，不知道怎样高效的实现，经人提醒，才发现这就是不相交集/并查集，惭愧。

做一整理，供日后回顾复习。

定义、性质与操作

A disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

操作

Init初始化

给定一些元素，在初始状态，每个都属于不同的集合，初始化的过程就是要体现这一点，这根据实现的不同，会有不同的操作。

Union合并

将两个集合进行合并成为一个集合，即集合中所有的元素有相同的根。

Find查找

找到某个元素的根，目的是确定该元素所属的集合，常用于判断两个元素是否属于一个集合。

实现

数据结构

由于要找到它的根，属于一个集合的元素有相同的根，所以可以想到属于一个集合的元素形成一个树，而整个所有集合就是一个森林。

每一棵树不同于查找树，不会要求从根节点出发找到子节点的元素，只需要给定子节点，找到根，所以每个节点最基本的只需要记录两个值：

  1. 自己所表示的元素
  2. 自己的父元素

这样的信息用数组就可以实现：

数组的下标本身就可以表示自己，数组中存的值可以记录父节点。

关于根节点存储的值

这真的是一个很有趣的问题，子节点存储父节点无疑，但根节点存什么呢？根据自己的需求，可以存相应的值。

1. 0

根节点存0值，表示其是根节点。

2. 本元素

存本元素的值，这样，如果是根节点，则自己与自己所存的值相同，否则为非根节点。

在后续的查找与合并的优化过程中，会用到树的size或height/rank. 所以跟节点会根据需要记录这些值，所以，根节点还可以记录：

3. -size

运用负值，可以区分根节点和非根节点，同时又可以表示树的size，初始化的时候，给每个元素都赋值为-1.

4. -rank/height

类似-size.

操作

实现方式多样，不同的优化方式也有不同的效果。

Naive Solution

没有路径压缩，Naive Union，根节点存0值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void setInit(int size) {
    for (int i = 0; i <= size; ++i) {
        set[i] = 0;
    }
}
void setUnion(int a, int b) {
    set[a] = b;
}
int setFind(int a) {
    if (set[a] == 0)
        return a;
    return setFind(set[a]);
}

Union by size + path compression

根节点初始值为-1，存储-size。
每次查找的时候，都执行路径压缩。
在union的时候，也先进行查找。

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
void setInit(int size) {
    for (int i = 0; i <= size; ++i) {
        set[i] = -1;
    }
}
int setFind(int a) {
    if (set[a] < 0)
        return a;
    return set[a] = setFind(set[a]);
}
void setUnion(int a, int b) {
    int root1 = setFind(a);
    int root2 = setFind(b);
    if (root1 == root2)
        return;
    if (set[root1] <= set[root2]) {
        set[root1] += set[root2];
        set[root2] = root1;
    } else {
        set[root2] += set[root1];
        set[root1] = root2;
    }
}

时间复杂度

结论：带路径压缩，amortized time: O(1)

TODO…看完算法导论有关的那一章再写…

题目

求连通分量，再合适不过了…

LeetCode上有一道四连通分量的题：LeetCode 200. Number of Islands

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
class Solution {
    int setFind(int x, vector<int> &set) {
        if (set[x] < 0)
            return x;
        return set[x] = setFind(set[x], set);
    }
    void setUnion(int x, int y, vector<int> &set) {
        int root1 = setFind(x, set);
        int root2 = setFind(y, set);
        if (root1 == root2)
            return;
        if (set[root1] < set[root2]) {
            set[root1] += set[root2];
            set[root2] = root1;
        } else {
            set[root2] += set[root1];
            set[root1] = root2;
        }
    }
    vector<int> setInit(int size) {
        return vector<int>(size, -1);
    }
    int countSet(vector<int> &set) {
        return count_if(set.begin(), set.end(), [](int x) { return x < 0; });
    }
public:
    int numIslands(vector<vector<char>> &grid) {
        if (grid.empty())
            return 0;
        int tagNum = -1;
        vector<vector<int>> tags(grid.size(), vector<int>(grid[0].size(), -1));
        vector<pair<int, int>> equals;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '0')
                    continue;
                if (i - 1 >= 0 && grid[i - 1][j] == '1' && j - 1 >= 0 && grid[i][j - 1] == '1') {
                    tags[i][j] = tags[i][j - 1];
                    if (tags[i][j - 1] != tags[i - 1][j])
                        equals.emplace_back(tags[i][j - 1], tags[i - 1][j]);
                } else if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                    tags[i][j] = tags[i - 1][j];
                } else if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                    tags[i][j] = tags[i][j - 1];
                } else {
                    tagNum++;
                    tags[i][j] = tagNum;
                }
            }
        }
        if (tagNum == -1)
            return 0;
        if (tagNum == 0)
            return 1;
        vector<int> set = setInit(tagNum + 1);
        for (pair<int, int> p : equals) {
            setUnion(p.first, p.second, set);
        }
        return countSet(set);
    }
};

参考

数据结构与算法分析（C语言描述）第二版
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
https://www.jianshu.com/p/def7767982ac
http://blog.csdn.net/dm_vincent/article/details/7655764

Posted on | Edited on | In |

这些基础总是学了，长时间不看又忘了，这次写一篇文章记录下来，供日后回顾复习。

基本性质

首先是一个二叉树，数据结构：

1
2
3
4
5
struct Node {
    int val;
    Node *left;
    Node *right;
};

作为搜索树的性质：左子树节点的值 <= 根节点的值 <= 右子树节点的值

遍历

中序遍历

对于二叉搜索树来说，中序遍历输出的就是从小到大的顺序。

1
2
3
4
5
inorder_walk(node):
    if node != nil
        inorder_walk(node.left)
        print node.val
        inorder_walk(node.right)

CPP实现：

1
2
3
4
5
6
7
void inorder_walk(Node * node) {
    if (node) {
        inorder_walk(node->left);
        cout << node->val << endl;
        inorder_walk(node->right);
    }
}

遍历的话，用递归的方式都很直观，但如果用迭代的方式，就稍微有些麻烦，借助栈可以记录之前遍历的状态，进而实现中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
inorder_walk(node):
    stack s
    root = node
    while !(s.empty() and root == nil) # 结束的状态需要两个条件！！！
        while root != nil
            s.push(root) # 先把所有的左节点进栈
            root = root.left
        
        root = s.top()
        print root.val
        s.pop()
        root = root.right

CPP的实现，这里LeetCode上的题94. Binary Tree Inorder Traversal正好可以用以验证，就直接复制自己的答案了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode *> s;
    vector<int> res;
    while (!(root == NULL && s.empty())) {
        while (root != NULL) {
            s.push(root);
            root = root->left;
        }
        root = s.top();
        res.push_back(root->val);
        s.pop();
        root = root->right;
    }
    return res;
}

前序遍历

先输出根的值，再输出左右的值。

1
2
3
4
5
preorder_walk(node):
    if node != nil
        print node.val
        preorder_walk(node.left)
        preorder_walk(node.right)

非递归可以用中序同样的方式来遍历，但是输出的时机不同应该就可以了。
144. Binary Tree Preorder Traversal 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode *> s;
    while (!(root == NULL && s.empty())) {
        while (root != NULL) {
            res.push_back(root->val);
            s.push(root);
            root = root->left;
        }
        
        root = s.top();
        root = root->right;
        s.pop();
    }
    return res;
}

其实在遍历过程中时使用迭代时，同样有递归的思想在里边，将root调整到右节点上，便相当于把右子树当做一个新的二叉树来进行处理，这种思想在构造迭代的时候还是很有用的。

后序遍历

先输出孩子的值，再输出根的值。

1
2
3
4
5
postorder_walk(node):
    if node != nil
        postorder_walk(node.left)
        postorder_walk(node.right)
        print node.val

非递归的算法自己还的确没有想出来，不过看了LeetCode上的Discussion：Preorder, Inorder, and Postorder Iteratively Summarization. 哇，的确没有注意到这一个性质。

前序遍历的时候，最先输出的是从根节点一直到最左叶节点的一列；而后序遍历的时候，最后输出的，就是从最右叶节点到根节点的最后一列！如图所示：

左为前序遍历，右为后序遍历，可以清楚的看到这个遍历顺序的性质！！

这样在实现的时候，便可以参照前序遍历，相反对称操作下，可以得到后序遍历的结果！

CPP的实现：LeetCode 145. Binary Tree Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode *> s;
    while (!(root == NULL && s.empty())) {
        while (root != NULL) {
            res.push_back(root->val);
            s.push(root);
            root = root->right;
        }
        
        root = s.top();
        root = root->left;
        s.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}

层级遍历

层级遍历的话，用一个队列来存储每个节点，当出队列时，把它的两个孩子入队列，直到队列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
levelorder_walk(root):
    if root == nil
        return
    queue q
    q.push(root)
    while q not empty
        node = q.front()
        print node.val
        q.pop()
        if node.left != nil
            q.push(node.left)
        if node.right != nil
            q.push(node.right)

CPP实现，LeetCode 102. Binary Tree Level Order Traversal
由于这道题要求区分每一层，所以用了两个不同的queue来记录每一层的节点，不过思想大致相同。

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
/**
 * 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) {
        queue<TreeNode*> q1, q2;
        vector<vector<int>> res;
        if (root == NULL)
            return res;
        q1.push(root);
        vector<int> vals;
        while (!q1.empty()) {
            TreeNode* node = q1.front();
            q1.pop();
            vals.push_back(node->val);
            if (node->left)
                q2.push(node->left);
            if (node->right)
                q2.push(node->right);
            if (q1.empty()) {
                res.push_back(vals);
                if (!q2.empty()) {
                    vals.clear();
                    while(!q2.empty()) {
                        q1.push(q2.front());
                        q2.pop();
                    }
                }
            }
        }
        return res;
    }
};

深度遍历

深度遍历是最普通最直观的二叉树遍历，其一般都结合具体的需求使用，比如查找，确定高度等等。

查找

利用搜索树的性质，查找很直观：

1
2
3
4
5
6
7
search(root, key):
    if root == nil or key == root.val
        return root
    if key < root.val
        return search(root.left, key)
    else
        return search(root.right, key)

非递归的方式也很直观，因为上述的递归是尾递归：

1
2
3
4
5
6
7
search(root, key):
    while root != nil and key != root.val
        if key < root.val
            root = root.left
        else
            root = root.right
    return root

插入

二叉搜索树的插入只是在查找的基础上做一点微小的改动。因为查找已经找到了对应的位置，只要在找到的位置上放上新的值即可。

删除

BST的删除需要考虑几个情况：

  1. 叶节点：直接删掉
  2. 只有一个子节点：删掉，子节点顶替删除的节点的位置
  3. 有两个孩子：删掉，用左子树的最大节点或右子树的最小节点顶替

描述起来很清楚，但是真正写起来，需要考虑具体的一些细节，比如根节点的情况，比如如何去做“顶替”这一操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
delete(root, key):
    if root == nil
        return nil
    if key < root.val
        root = delete(root.left, key)
    else if key > root.val
        root = delete(root.right, key)
    else # find node to delete
        # 以下的两种情况涵盖了都是nil的情况，这是实践中的一点小小的hack吧
        if root.left == nil
            return root.right
        if root.right == nil
            return root.left
        right_min = find_min(root.right)
        root.val = right_min.val
        root.right = delete(root.right, root.val) # 注意，更新的这一点，要考虑各种情况，而不能只是将它变为nil
    return root
find_min(root):
    while root != nil and root.left != nil
        root = root.left
    return root

CPP实现，LeetCode 450. Delete Node in a 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
/**
 * 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 {
private:
    TreeNode* findMin(TreeNode* root) {
        while (root != NULL && root->left != NULL)
            root = root->left;
        return root;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL)
            return root;
        if (key < root->val)
            root->left = deleteNode(root->left, key);
        else if (key > root->val)
            root->right = deleteNode(root->right, key);
        else {
            if (root->left == NULL)
                return root->right;
            if (root->right == NULL)
                return root->left;
            TreeNode* rightMin = findMin(root->right);
            root->val = rightMin->val;
            root->right = deleteNode(root->right, root->val);
        }
        
        return root;
    }
};

关于迭代的方式去实现删除的话，可能要比递归考虑更多的东西，但是想法的话还是很直观的，遍历查找要删除的节点时，始终记得记录其父节点。具体的删除过程与上述的大同小异，可能会有好多边界需要考虑。

建立

从数组

给定结构

确定一个二叉树，有两个要素，一个是二叉树的结构，另一个是各个节点的值，给定的数组确定了BST的值，但结构是未定的，根据给定的结构，可以构建一个确定的BST。

PAT 1099. Build A Binary Search 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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Node {
    int val;
    Node *left;
    Node *right;
    Node() : val(0), left(NULL), right(NULL) {}
    explicit Node(int val) : val(val), left(NULL), right(NULL) {}
};
void printTree(Node *root, int level) {
    if (root != NULL) {
        cout << root->val << endl;
        if (!(root->left == NULL && root->right == NULL)) {
            for (int i = 0; i < level + 1; ++i) {
                cout << "   ";
            }
            cout << "L->";
            printTree(root->left, level + 1);
            for (int i = 0; i < level + 1; ++i) {
                cout << "   ";
            }
            cout << "R->";
            printTree(root->right, level + 1);
        }
    } else {
        cout << "NULL" << endl;
    }
}
void levelOrderTravel(Node *root) {
    if (!root)
        return;
    cout << root->val;
    queue<Node *> q;
    if (root->left)
        q.push(root->left);
    if (root->right)
        q.push(root->right);
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        cout << " " << node->val;
        if (node->left)
            q.push(node->left);
        if (node->right)
            q.push(node->right);
    }
}
int main() {
    Node *root = new Node(0);
    int nodeNum;
    cin >> nodeNum;
    if (nodeNum == 0)
        return 0;
    stack<Node *> s;
    s.push(root);
    for (int i = 0; i < nodeNum; ++i) {
        int l, r;
        cin >> l >> r;
        Node *node = s.top();
        s.pop();
        if (r != -1) {
            node->right = new Node(r);
            s.push(node->right);
        }
        if (l != -1) {
            node->left = new Node(l);
            s.push(node->left);
        }
    }
    vector<int> vals;
    for (int i = 0; i < nodeNum; ++i) {
        int v;
        cin >> v;
        vals.push_back(v);
    }
    sort(vals.begin(), vals.end());
//    printTree(root, 0);
    vector<Node *> nodes;
    stack<Node *> s1;
    Node *curr = root;
    while (!s1.empty() || curr != NULL) {
        while (curr != NULL) {
            s1.push(curr);
            curr = curr->left;
        }
        curr = s1.top();
        s1.pop();
        nodes.push_back(curr);
        curr = curr->right;
    }
    for (int i = 0; i < nodes.size(); ++i) {
        nodes[i]->val = vals[i];
    }
    levelOrderTravel(root);
    return 0;
}

平衡二叉树

如果限定是生成一个平衡二叉树的话，需要保证两边的相对均衡，将数组排序之后，每次取中点就可以做到：

LeetCode 108. Convert Sorted Array to Binary Search Tree

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:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty())
            return NULL;
        int midIdx = nums.size() / 2;
        TreeNode *node = new TreeNode(nums[midIdx]);
        if (midIdx == 0) {
            node->left = NULL;
        } else {
            vector<int> left(nums.begin(), nums.begin() + midIdx);
            node->left = sortedArrayToBST(left);
        }
        
        if (midIdx == nums.size() - 1) {
            node->right = NULL;
        } else {
            vector<int> right(nums.begin() + midIdx + 1, nums.end());
            node->right = sortedArrayToBST(right);            
        }
        return node;
    }
};

完全二叉树

完全二叉树的结构是确定的，所以仍然可以采用从给定结构构建二叉树的方法：

PAT 1064. Complete Binary Search Tree

我在PAT上的解答，部分正确！！有内存超限的错误！！！唔，怎么在PAT上做的这两道题，都有各种各样奇怪的错误，唉，有时间再看吧。

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
100
//
// Created by Zhao Xiaodong on 2018/2/1.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
struct Node {
    int val;
    Node *left;
    Node *right;
    Node() : val(0), left(NULL), right(NULL) {}
};
void levelOrderTravel(Node *root) {
    if (!root)
        return;
    cout << root->val;
    queue<Node *> q;
    if (root->left)
        q.push(root->left);
    if (root->right)
        q.push(root->right);
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        cout << " " << node->val;
        if (node->left)
            q.push(node->left);
        if (node->right)
            q.push(node->right);
    }
}
int main() {
    int size;
    cin >> size;
    if (size == 0)
        return 0;
    vector<int> vals;
    for (int i = 0; i < size; ++i) {
        int v;
        cin >> v;
        vals.push_back(v);
    }
    sort(vals.begin(), vals.end());
    Node *root = new Node();
    queue<Node *> q;
    q.push(root);
    int nodeNum = 1;
    while (true) {
        Node *node = q.front();
        q.pop();
        node->left = new Node();
        nodeNum++;
        if (nodeNum == size)
            break;
        node->right = new Node();
        nodeNum++;
        if (nodeNum == size)
            break;
        q.push(node->left);
        q.push(node->right);
    }
    vector<Node *> nodes;
    stack<Node *> s1;
    Node *curr = root;
    while (!s1.empty() || curr != NULL) {
        while (curr != NULL) {
            s1.push(curr);
            curr = curr->left;
        }
        curr = s1.top();
        s1.pop();
        nodes.push_back(curr);
        curr = curr->right;
    }
    for (int i = 0; i < nodes.size(); ++i) {
        nodes[i]->val = vals[i];
    }
    levelOrderTravel(root);
    return 0;
}

参考了网上某篇博文的这道题的答案，发现自己这样写有点傻，利用性质完全二叉树的相关性质，可以更加简便和巧妙的完成这道题。

因为最后要求层级遍历，而完全二叉树的层级遍历有个性质可以利用：
按层遍历的输出顺序，就是用表示完全二叉树的数组中的顺序

这看起来并没有什么，但和我们知道的一个完全二叉树非常熟悉的性质：
leftIndex = 2 x rootIndex, rightIndex = 2 x rootIndex + 1

这样一来，便可以用下表来定位某个元素，而用数组的数据结构存储二叉树，其实遍历的行为更加简单，比如本题中用到的中序遍历：

1
2
3
4
5
6
7
void inorderTravel(int root) {
    if (root > size)
        return;
    inorderTravel(root * 2);
    inorderNodes.push_back(root);
    inorderTravel(root * 2 + 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
44
45
46
47
48
//
// Created by Zhao Xiaodong on 2018/2/2.
//
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1000;
int size;
vector<int> inorderNodes;
void inorderTravel(int root) {
    if (root > size)
        return;
    inorderTravel(root * 2);
    inorderNodes.push_back(root);
    inorderTravel(root * 2 + 1);
}
int main() {
    cin >> size;
    vector<int> vals;
    for (int i = 0; i < size; ++i) {
        int v;
        cin >> v;
        vals.push_back(v);
    }
    sort(vals.begin(), vals.end());
    inorderTravel(1);
    vector<int> tree(MAX + 1);
    for (int i = 0; i < size; ++i) {
        tree[inorderNodes[i]] = vals[i];
    }
    for (int i = 1; i < size; ++i) {
        cout << tree[i] << " ";
    }
    cout << tree[size];
    return 0;
}

从序列

从前序中序构建

前序中找到第一个节点，即为根节点，在中序中找到，中序的左侧就是左子树，右侧为右子树；得到左右子树的节点数量之后，可以将前序数组剩下的元素分成左右子树，进而递归的做下去。

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

（发现自己之前CPP和Python都AC过，python似乎看起来更简洁，要不以后做OJ都用PY？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return
        root_val = preorder.pop(0)
        root_idx = inorder.index(root_val)
        root = TreeNode(root_val)
        root.left = self.buildTree(preorder, inorder[0:root_idx])
        root.right = self.buildTree(preorder, inorder[root_idx + 1:])
        return root

从后序中序构建

与从前中构建很类似，做一个镜像即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return
        val = postorder.pop()
        idx = inorder.index(val)
        root = TreeNode(val)
        root.right = self.buildTree(inorder[idx + 1:], postorder)
        root.left = self.buildTree(inorder[:idx], postorder)
        return root

前中转后与后中转前

有的时候，只要求通过前中序列写出后序，或者后中序列，写出前序，而不要求构建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
def pre_in_to_post(preorder, inorder):
    postorder = []
    if not preorder or not inorder:
        return postorder
    val = preorder[0]
    idx = inorder.index(val)
    postorder += pre_in_to_post(preorder[1:1 + idx], inorder[:idx])
    postorder += pre_in_to_post(preorder[1 + idx:], inorder[idx + 1:])
    postorder += [val]
    return postorder
def post_in_to_pre(postorder, inorder):
    preorder = []
    if not postorder or not inorder:
        return preorder
    val = postorder[-1]
    idx = inorder.index(val)
    preorder += [val]
    preorder += post_in_to_pre(postorder[:idx], inorder[:idx])
    preorder += post_in_to_pre(postorder[idx:-1], inorder[idx + 1:])
    return preorder
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
print(pre_in_to_post(preorder, inorder))
print(post_in_to_pre(postorder, inorder))

output:

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

参考：

http://blog.csdn.net/simple_the_best/article/details/52713491
http://www.cnblogs.com/jackwang822/p/4749965.html

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/coin-change/description/

想法

贪心？

要考虑一些情况，比如：[1, 3, 4], amount = 6:
3 + 3是最优的

DP?

对amount吗？dp[n] = ?
dp[n] = min(dp[n-coins[i]]) + 1

写了一个dp的，但是有测试点没过，没耐心调了：

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
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0)
            return 0;
        coins.erase(remove_if(coins.begin(), coins.end(), [amount](int coin){return coin > amount;}), coins.end());
        if (coins.empty())
            return -1;
        vector<int> dp(amount + 1, INT_MAX - 100);
        for (int c : coins) {
            dp[c] = 1;
        }
        for (int i = *std::max_element(coins.begin(), coins.end()) + 1; i <= amount; i++) {
            int min = INT_MAX - 100 + 1;
            for (int j = 0; j < coins.size(); j++) {
                if (dp[i - coins[j]] + 1 < min) {
                    min = dp[i - coins[j]] + 1;
                }
            }
            dp[i] = min;
        }
        if (dp[amount] == INT_MAX - 100 + 1)
            return -1;
        return dp[amount];
    }
};

看了discussion，思路是一样的，就是一点也不清晰！！！

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

想法

为什么自己这么菜呢？？？

思路不清晰！！！
算法不熟练！！！

多练哇！！！
太菜啦！！！
菜到自己都看不下去啦！！！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/trapping-rain-water/description/

想法

每个块，直到遇到下一个>=它的块，则存储确定…

每个块都假定能盛满，直到最后遇不到>=自己的块

从左往右扫一遍，记录valid和如果valid所装的容量：

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
class Solution {
public:
    struct Bar {
        int s;
        bool v;
        Bar() : s(0), v(false) {}
    };
    int trap(vector<int>& height) {
        vector<Bar> content(height.size());
        int s = 0;
        for (int i = 1; i < height.size(); i++) {
            for (int j = s; j < i && content[j].v == false; j++) {
                if (height[j] <= height[i]) {
                    content[j].v = true;
                    if (j == s)
                        s = i;
                } else {
                    content[j].s += height[j] - height[i];
                }
            }
        }
        int res = 0;
        int maxHeight = 0;
        for (int i = 0; i < content.size(); i++) {
            if (height[i] >= maxHeight && content[i].v) {
                maxHeight = height[i];
                res += content[i].s;
            }
        }
        return res;
    }
};

错误！！！
都没有考虑最基础的情况： [4, 2, 3]
自己的答案在这个情况下，认为4没有找到>=它的，所以invalid，也就没有后边的容量了

看了discussion，发现自己还是没有想到简单解决问题的关键：

Here is my idea: instead of calculating area by height*width, we can think it in a cumulative way. In other words, sum water amount of each bin(width=1).
Search from left to right and maintain a max height of left and right separately, which is like a one-side wall of partial container. Fix the higher one and flow water from the lower part. For example, if current height of left is lower, we fill water in the left bin. Until left meets right, we filled the whole container.

答案

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
class Solution {
public:
    int trap(vector<int>& height) {
        int maxLeft = 0;
        int maxRight = 0;
        int res = 0;
        int l = 0, r = height.size() - 1;
        while (l <= r) {
            if (height[l] <= height[r]) {
                if (height[l] >= maxLeft)
                    maxLeft = height[l];
                else
                    res += maxLeft - height[l];
                l++;
            } else {
                if (height[r] >= maxRight) {
                    maxRight = height[r];
                } else {
                    res += maxRight - height[r];
                }
                r--;
            }
        }
        return res;
    }
};

回顾

记录左右的最高值，只要比本侧的最高值低且比另一侧低，就肯定会被填满…

抓住问题的管家哇，分析关系！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/

想法

一开始没有明确的想法，看了别人的思路之后明白…
用堆来实现，找最小值！
关键在于如何确定下一个可能的最小值！

  1. 先把(0,0), (1,0), …, (n,0)放进去
  2. 从heap中不断pop最小
  3. 最小(i,j)的下一个候选是(i, j+1), 关键
  4. 把下一个候选push进去就可以了

答案

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<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> res;
        if (nums1.empty() || nums2.empty() || k == 0)
            return res;
        auto comp = [nums1, nums2](pair<int, int> x, pair<int, int> y) {return nums1[x.first] + nums2[x.second] > nums1[y.first] + nums2[y.second];};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> q(comp);
        for (int i = 0; i < nums1.size(); i++) {
            q.push(pair<int, int>(i, 0));
        }
        for (int i = 0; i < k; i++) {
            pair<int, int> p = q.top();
            q.pop();
            res.push_back(pair<int, int>(nums1[p.first], nums2[p.second]));
            if (p.first == nums1.size() - 1 && p.second == nums2.size() - 1)
                break;
            if (p.second < nums2.size() - 1)
                q.push(pair<int, int>(p.first, p.second+1));
        }
        return res;
    }
};

回顾

  1. 找准关系，如何能确定下一个和当前最小值的比较
  2. C++ priority_queue的使用

Posted on | Edited on | In |

Q1

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
a. Draw four Gantt charts illustrating the execution of these processes . using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.
b. What is the turnaround time of each process for each of the scheduling algorithms in part a?
c. What is the waiting time of each process for each of the scheduling algorithms in part a?
d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

a.

b.

Turnaround time:
FCFS: 10, 11, 13, 14, 19
SJF: 19, 1, 4, 2, 9
nonpreemptive priority: 16, 1, 18, 19, 6
RR: 19, 2, 7, 4, 14

c.

Waiting time:
FCFS: 0, 10, 11, 13, 14
SJF: 9, 0, 2, 1, 4
nonpreemptive priority: 6, 0, 16, 18, 1
RR: 9, 1, 5, 3, 9

d.

Average waiting time:
FCFS: 9.6
SJF: 3.2
nonpreemptive priority: 8.2
RR: 5.4

SJF has minimal average waiting time.

Q2

Assume three processes P1, P2, and P3:
P1 consists of one thread T11
P2 consists of three threads T21, T22, and T23
P3 consists of two threads T31 and T32.
The following are the CPU bursts for these processes and their threads:

process thread cpu burst
P1 T11 7
P2 T21 4
T22 2
T23 4
P3 T31 6
T32 3

Assume that all threads arrive at the same time 0.
Show in gantt charts the execution of these processes using Round-Robin scheduler and Tq=5 time units:
(1) If the threads are user-level threads
(2) If the threads are kernel (OS) supported threads.
Calculate the waiting times (Tw) and turnaround times (Ttr) for each process and their average values for both cases (1) and (2).

Gantt charts:

Waiting time:

(1):
P1: 15 - 5 = 10
P2: 5 + 17 - 10 = 12
P3: 10 + 22 - 15 = 17
average: 13
(2):
P1: 23 - 5 = 18
P2: 5
P3: 15 + 25 - 23 = 17
average: 13.3

Turnaround time:

(1):
P1: 17
P2: 22
P3: 26
average: 65 / 3 = 21.7
(2):
P1: 25
P2: 15
P3: 25
average: 65 / 3 = 21.7

Posted on | Edited on | In |

接触前端一年多点，有了些自己的理解，记下自己的心路历程，用以自勉。

理解

前端很有趣

…

前端是个大坑

…

基础还是最根本最真的东西

最近真正开始做实际的东西，做一个小外包，简单的需求，页面要求也不复杂，但是发现，自己玩和做出来能看的东西之间的差距还是太大了。
总是想着用最新的东西，总是想用最爽的特性，总是想写优雅的结构，但是，一些基础的要求却不知道满足：完美还原设计稿了吗？浏览器兼容性够好吗？不同屏幕适配做好了吗？

发现，最基础的HTML，CSS，自己还只是入门。

HTML主要是H5中的一些新特性，自己还需要了解一下，不是只有div和a。

CSS自己还相当的不熟悉，不说一些”新特性“，动画之类的完全不了解，就基础的布局都需要搜半天才能找到best practice。

HTML与CSS，虽然发展不是很快，但恰恰证明这是很成熟，很基础的东西，这些搞懂，才能自如写界面。虽说过去部分人认为前端就是调布局，写页面这种想法在现在看来是错误的，但是不得不说，这些也是前端的根本，失去了根本，稿各种花里胡哨的框架结构，组织多么合理，结构多么优雅，都只是花瓶。

回顾学习历程

  1. 去年暑假开始看一些HTML、CSS之类的东西，没打算做什么，所以很低效。
  2. 完成一个报名表的页面，边学边写，学到了不少东西，初步了解了HTML，CSS，第一次使用CSS/JS外部库：BootStrap。
  3. 接触Vue，惊奇于这样精巧的组织方式以及一些绑定的理念，但只是专注于器，而不是道，同时缺乏实践，所以只是大致了解了其大致思想和样子吧。
  4. 再看JavaScript的一些基础语法与使用，熟练了一些，了解了一点ES6的东西，但只是皮毛的语法糖。
  5. 开始学习React并至今。弃Vue的原因是当时Vue比较新，一些IDE，文档，生态没有React那么好。思想很好，比较喜欢，在组织方式上很清晰，Component的划分与相应的行为设置很合理，但是感觉对初期的规划要求较高，不能乱糊，设计，分component还以有些讲究的。
  6. 进一步通过项目使用React，接触Redux与React Router，初步具备了用React生态写前端的能力。
  7. 接触了下React Native，因为思想完全相同，很亲切，由于这玩意不是很成熟，Bug比较多，写的体验很不好，毕竟没有安卓IOS数年的积淀，不过如果稳一些的话，依靠其跨平台的优势，的确很好，另一个优势在于界面布局上，感觉应该是优于原生开发的。
  8. 第一次做实际的前端，发现自己所学的还是太少，考虑的还是太少，发先自己在近一年的时间没怎么了解过HTML5和CSS，正在回顾这些基础和进一步理解JS的过程中。

再谈前端学习

现在看自己的前端学习路程，还是有些后悔的。

  1. 没有在入门的时候好好学一些HTML，CSS而去搞各种框架，重器而不重道。
  2. 看的太多，写的太少，没怎么写实际的东西，现在才发现真正写起来和自己想象的还是很有差距的。

额，可能这就是一个咸鱼者的心态，而不是一个踏踏实实的学习者的心态吧。

学前端，真的一定要去写，没有什么高深理论的东西，最好的学习方式就是直接去做！

下一步规划

  1. H5, CSS学习 看相关文档以及一些例子
  2. 网页布局与效果研究 注意搜集好的网页布局或效果，尝试实现
  3. JS基础学习 看完JS高程，ES6知识
  4. 阅读微型JS库的源码 lodash之类的，一到两个
  5. MVVM思想学习 弄明白MVVM原理，比如看个backboneJS源码
  6. 学习并掌握一个CSS拓展语言 选一个自己喜欢的，但要能够使用