ARTS-week32

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

Algorithms

Lowest Common Ancestor of 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
/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || !p || !q ) {
            return NULL;
        }
        if (root->val > max(p->val, q->val)) {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (root->val < min(p->val, q->val)) {
            return lowestCommonAncestor(root->right, p, q);
        }
        else {
            return root;
        }
    }
};

Lowest Common Ancestor of a Binary Tree
思路: 递归，题目中提到了p and q are different and both values will exist in the binary tree.，如果当前结点不等于p或q，p和q要么分别位于左右子树中，要么同时位于左子树或右子树。 

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
/**
 * 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 * lowestCommonAncestor(TreeNode * root, TreeNode * p, TreeNode * q) {
        if (!root)
            return NULL;
        if (root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right)
            return root;
        if (left != NULL )
            return left;
        if (right != NULL)
            return right;
        return NULL;
    }
};

Review

本周阅读英文文章 Basic C++ for DATA STRUCTURES

Technique

阅读Tanenbaum的《计算机网络》一书中，关于服务原语
一个服务由一组原语(primitive)正式说明，用户进程通过这些原语来访问该服务。原语告诉服务要执行某个动作，或者将对等实体所执行的动作报告给用户。如果协议栈位于操作系统中(大多数情况是这样)，则这些服务原语通常是一些系统调用。这些系统调用会陷入内核模式，然后在内核模式中取代操作系统来控制机器发送必要的数据包。可用的原语取决于底层所提供的服务。面向连接服务的原语与无连接服务的原语是不同的。

比如Berkeley的套接字接口: 

1
2
3
4
5
6
7
  原语                含义    
LISTEN      阻塞操作，等待入境连接请求
CONNECT     与等待中的对等实体建立连接
ACCEPT      接受来自对等实体的入境连接请求
RECEIVE     阻塞操作，等待入境报文
SEND        给对等实体发送一个报文
DISCONNECT  终止一个连接

服务和协议是两个截然不同的概念，服务是指某一层向它上一层提供的一组原语，定了该层准备代表其用户执行哪些操作，但是它并不涉及如何实现这些操作。而协议是一组规则，规定了同一层上对等实体之间所交换的数据包或报文的格式和含义。

Share

朋友安利了我很久《明朝那些事儿》，说写的很好，豆瓣评分超高，之前入手了一套，刚看到第一本《洪武大帝》朱元璋和陈友谅决战PK的地方。