很久没有好好看书做笔记了

血缘与地缘的联系

乡土社会稳定的社会结构是以血缘为基础的，以子继父业的形式形成稳定的社会分工，也就是所谓“农人之子恒为农，商人之子恒为商”。血缘以不由分说、无可争辩地形式分配传统社会中各人的职业、身份和财产。

在稳定的乡土社会中，地缘不过是血缘的投影，地域的远近一定程度反映着血缘的亲疏，因此地理区位也就成为了社会化了的空间。我们现在仍然可以见到这样对区位的划分：左尊于右，南尊于北；更明显的例子是，我们现在仍然用“地位”一词表示一个人的社会阶层，这便是来自血缘的地域投影。在原始社会中血缘和地域是合一的，而现代社会仍然延续了部分的传统。

但人，特别是现代人，终究是要流动的。传统社会的人口流动主要源自于繁殖引起的土地资源不足，首先会引起向内的精耕以提升土地的单位报酬，但随着人口的继续增加，社群便会分裂，形成新的村落，寻找新的耕地。而现代人流动的理由就更多了，就业、教育，亦或是单纯对某一地的喜爱，这在发达的现代社会已成为可能。

但人口在流动时，仍然会以另外的形式保有血缘的空间投影。比如移民社会中的“新英伦新约克New York”云云。再者还有我们的籍贯，即使我们一生都可能不会去往我们籍贯所在的地方，但我们还是会在介绍自己以及填写资料的时候诚实地写上。但事实上，现在随着社会的进一步变迁、城市化的发展，籍贯的概念可能会越来越模糊并最终消失。但在它消失之前，我们仍可以说，籍贯是血缘的一种表现形式。

血缘关系的局限和新地域概念

血缘关系对社会活动有许多限制，最大的体现莫过于商业活动。亲戚间的交易往往是基于人情和相互拖欠，也就是俗话说的“亲戚间不用计较那么细”。反而明算账意味着人情的减弱甚至有点绝交的意味。这样一来，一宗“人情交易”可以被长期甚至永久地搁置，因此对于不亲的关系人们反而会减少这样的往来，避免太多的人情债，无论是别人欠自己的还是自己欠别人的。

随着社会生活的逐渐发达，牵扯的社会活动越来越多，就越来越不能靠人情来维系权利和义务的平衡，这时候就需要一定程度的“当场清算”，也就是商业。但这种形式是有悖于传统的亲密血缘关系的，因此就衍生出集市的概念，乡村社会划分出一个特定的地点让大家都到这里来，暂时撇开社会联系，进行纯粹的商业交易与结算，不用讲人情。

因为有集市的存在，“外村人”也可以参与本村的商业活动并生活于此，这是由商业衍生出的新的地缘概念，有别于传统的附加在血缘上的地缘关系，是契约关系的基础，也是现代社会的基础。从学院结合转变到地缘结合是社会性质的转变，也是社会史上的大转变。

有不少概念也是在自己的理解上添油加醋，也不保证能准确传达费孝通先生原文的意思，比如关于籍贯、新地缘关系的产生部分。

使用 Go 并发比较两棵二叉查找树。

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1
2

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

我的解法

一开始我有一个错误的解法，这个解法是通过有穷自动机分析出来的；虽然这这种解法最终无法实现，但我发现有穷自动机真的是个逻辑分析的好工具，也算增长了经验

• 先遍历一遍找出最大值，并假设一开始每一列都有着max高度的水；这个是个 O(N)的操作；
• 而后从上至下，逐行地减去头和尾溢出的部分，这是个kO(N)的操作，k取决于最大的高度能有多大
• 总结来说这是一个O(kN)的操作

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

func trap(height []int) int {
    
    if len(height) == 0{
        return 0;
    }
    
    // fill with the max;
    max := height[0]
    for _, val := range height {
        if max < val {
            max = val
        }
    }
    result := max * len(height)
    
    // delete the first 0 cols
    sp := 0
    for ; sp < len(height) && height[sp] == 0; sp++ {
        result -= max;
    }
    
    // delete the existing places
    for e:=sp; e<len(height); e++{
        result -= height[e];
    }
    
    // delete row by row
    for curH := max; curH >= 1; curH-- {
        
        // delete the head
        for e := sp;; e++ {
            if height[e] < curH {
                result--;
            } else{
                break;
            }
        }
        // delete the tail
        for e := len(height)-1;;e--{
            if height[e] < curH{
                result--;
            } else{
                break;
            }
        }
    }
    return result;
}

更巧妙的

讨论区里利用双指针，可以有 O(N)（只遍历一遍）的算法。具体看这里，这里不说详细的解析，简单来说就是左右同步扫描，并将水从低处往高处逐列填。这里只贴一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int trap(int A[], int n) {
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }
};

更多的解法

Solution有更多的解法，还有一种动态规划的解法很有意思，将左边加起来，右边加起来，重叠部分就是所求。

LeetCode 99. Recover Binary Search Tree：题目、思路与代码实现。

LeetCode Regular Expression Matching：题目、思路与代码实现。

LeetCode 931. Minimum Falling Path Sum：题目、思路与代码实现。

有向图边的类型

有向图边有如下几个类型：

• tree edge 树边
• foward edge 前向边
• back edge 回边
• cross edge 横跨边

一张图即可解释：

定义

Definition: A strongly connected component (SCC) of a directed graph G = (V, E) is a maximal set of vertices C ⊆ V such that every pair of vertices u and v in C are reachable from each other.

翻译过来就是，把一个有向图划分成尽可能大的几个集合，集合内的结点两两互相都可达，这样的每一个“集合”就是一个强连通分量

昨天下午尝试了第一次视频面试，面试的岗位是字节跳动的[后台开发-基础架构]实习岗，由于我本身的技术的确是远远没有达到岗位的要求，所以这一次的面试也只是抱着试一试的态度，了解一下面试的流程，积累一些经验，同时通过面试进一步了解自己应该努力的方向。

建议在开始之前，先在这里学习分区和开机的知识，然后按照这个步骤把CentOS单系统安装成功之后，再来看这里。

参考资料

• 鸟哥Linux私房菜 - 多重开机安装流程与管理
• Grub2配置文件详解