ARTS-week30

发表于 分类于 本文字数： 1.9k 阅读时长 ≈ 2 分钟

Algorithms

Implement Stack using Queues 

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 MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
        for (int i = 0; i < q.size() - 1; ++i) {
            q.push(q.front()); 
            q.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x = q.front(); 
        q.pop();
        return x;
    }
    
    /** Get the top element. */
    int top() {
        return q.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
    
private:
    queue<int> q;
};

Invert Binary Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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* invertTree(TreeNode* root) {
        if (!root) {
            return NULL;
        }
        TreeNode *tmp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tmp);
        return root;
    }
};

Review

本周阅读英文文章 What Is Readable Code?

Technique

Python模块bisect实现了二分查找算法和插入算法。对于有序列表，可使用函数bisect来确定将元素插入到什么位置，同时可确保插入后列表依然是有序的。 

1
2
3
4
>>> import bisect
>>> collection = [1, 2, 4, 5, 6]
>>> bisect.bisect(collection, 3)
2

bisect还提供了其他几个函数，可以查看官方文档：https://docs.python.org/3.7/library/bisect.html

使用bisect排序顺序插入： 

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
import bisect

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

print('New  Pos Contents')

aim = []
for i in values:
    position = bisect.bisect(aim, i)
    bisect.insort(aim, i)
    print('{:3}  {:3}'.format(i, position), aim)


Output：
New  Pos Contents
  3    0 [3]
  2    0 [2, 3]
  1    0 [1, 2, 3]
  4    3 [1, 2, 3, 4]
  7    4 [1, 2, 3, 4, 7]
  5    4 [1, 2, 3, 4, 5, 7]
  9    6 [1, 2, 3, 4, 5, 7, 9]
  7    6 [1, 2, 3, 4, 5, 7, 7, 9]
  8    7 [1, 2, 3, 4, 5, 7, 7, 8, 9]
  6    5 [1, 2, 3, 4, 5, 6, 7, 7, 8, 9]

在文档中提到bisect.insort() Similar to insort_left(), but inserting x in a after any existing entries of x.，也就是说insort()等同于insort_right()。因此如果想将新值插入到现有值的左侧时，可以使用insort_left()。

Share

emmm，推荐一本书吧：社会工程 卷2：解读肢体语言