ARTS-week14

Algorithms

Merge Sorted Array
思路: 合并之后的数组是m+n，从后往前赋值，比较A、B中最后一个元素的大小，将较大的值插入到m+n-1的位置上，再依次向前。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i, j, k;
        
        i = m - 1;
        j = n - 1;
        k = m + n - 1;
        while (i >= 0 && j >= 0) 
        {
            if (nums1[i] > nums2[j])
            {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) 
        {
            nums1[k--] = nums2[j--];
        }
    }
};

Same Tree
思路: 使用DFS递归。

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

Review

本周阅读英文文章 Layer 3 Is for Interoperability

Technique

本周在项目中遇到了基数树: Radix tree

在Linux内核中有具体的实现：
radix-tree.h
radix-tree.c

Linux内核中的Radix树的root节点的结构体:

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

其中

height: 从叶节点向上计算的树高度
gfp_mask: 内存分配标识
rnode: 子节点指针

Radix树在IP路由中十分有用，在《TCP/IP详解卷２：实现》中专门有两章提到了Radix树的应用：第18章Radix树路由表，第19章选路请求和选路消息。

由IP完成的路由选择是一种选路机制，它通过搜索路由表来确定从哪个接口把分组发送出去，它与选路策略不一样，选路策略是一组规则的集合，这些规则用来确定哪些路由可以编入到路由表中，Net/3内核实现选路机制，而选路守护进程，典型地如routed或gated，实现选路策略。

Net/3路由表采用Patricia树结构来表示主机地址和网络地址。待查找的地址和树中的地址都被看成比特序列。这样可以用相同的函数的来查找和维护不同类型的树，如：含有32bit定长IP地址的树、含有48bit定长XNS地址的树以及一颗含有变长OSI地址的树。

书中给出了一个主机bsdi的路由表：

分别以127.0.0.1和127.0.0.2为查找键，并给出了他们的16进制：

bsdi的Net/3路由表对应的内部表示：

方框被称为内部结点，圆角框被称为叶子。每一个内部节点对应于测试查找键的一个比特位，其左右各有一个分支。每一个叶子对应于一个主机地址或者对应于一个网络地址。如果在叶子节点下面有一个16进制数，那么这个叶子就对应于一个网络地址，该16进制数就是叶子的网络掩码。如果在叶子节点下面没有十六进制的掩码，那么这个叶子就是一个主机地址，其隐含的掩码是0xffffffff。

本周分享《计算机安全-原理与实践》随机与伪随机

密码应用大多使用算法来生成随机数。这些算法是确定的，所以产生的序列并非是统计随机的。不过如果算法好的话，产生的序列可以接受随机性检测。这样的数一般称为伪随机数。

一个真随机数发生器(True Random Number Generator, TRNG)是利用不确定的源来生成随机数。大部分是通过不可预测的自然过程(如电离辐射效应的脉冲检测器、气体放电管和漏电电容器)来实现的。Intel公司开发了一个商用芯片，其通过增大无驱动电阻器的电压来对热噪声进行采样。第一个作为商用的且具有一定产量的TRNG是于2012年5月上市的Intel数字随机发生器(Digital Random Number Generator， DRNG)，它载于新的多核芯片上。

Algorithms

Review

Technique

Share