2015-05-10
敬叶 初稿

数值计算

位运算习题

  1. 本题实际是个进制转换问题，整数部分的转换规则为： b1 = n, n = n/2; b2 = n; n = n/2; ...整数部分为 \(b_i ... b_2 b_1\) 。小数部分的转换规则为： c1 = int(2f), f = 2f - c1; c2 = int(2f), f = 2f - c2; ... 小数部分为 \(c_1 c_2 ... c_i\) 。

  2. 查找下一个最小的数很好找，找到最右边的1，向左搜索第一个0，将其置1，再将其右边的1置0。这还不够小，还需要将右边所有的1全部移到最右边去。

    同样的方法可以找前一个最大的数，找到最左边的0，注意必须在最高位右边，将其置1，再将其左边的1置0。这还不够大，将右边所有的1全部移到挨着该位的位置。

  3. ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)
  4. 利用n & (n -1)可以消掉最末一位。

  5. 这个题目用到一个二进制表示中的特性，即低位的0和1个数是对称的。这句话的意思是任何一个位，0的个数和1的个数相同。如果缺少的那个数b0为0，那么统计b0就会发现0的个数就会比1少一个，依次类推。

    对于最高位在处理上还有点技巧，比较简单的做法是将n对齐到 \(2^{k} - 1\) ，并假定大于n的数都没有丢失。

顺序数据结构

数组与字符串

  1. 使用位图标记已经出现的字符。
  2. 查询位图删除已经出现的字符。
  3. 使用数组统计每个字符出现的次数。

  4. 只需要挨个检查str1的每个字符是否在str2中剩余部分出现。 

     1: bool is_substr(char str1[], char str2[], int len1, int len2)
 2: {
 3:     if (len1 == 0) return true;
 4:     if (len2 == 0) return false;
 5: 
 6:     if (str1[len1 - 1] == str2[len2 - 1])
 7:         return is_substr(str1, str2, len1 - 1, len2 - 1);
 8: 
 9:     return is_substr(str1, str2, len1, len2 - 1);
10: }

    也可以用非递归实现： 

     1: bool is_substr(char str1[], char str2[], int len1, int len2)
 2: {
 3:     int i = 0, j = 0;
 4: 
 5:     while (j < len1 && j < len2)
 6:         if (str1[i] == str2[j++])
 7:             i++;
 8: 
 9:     return (i == len1);
10: }
  5. is_substring(s1, s2+s2)。

  6. 这个问题看上去还是很复杂的，因为没有排序，所以考虑起来很有难度。关键要注意到如下一个规律，那就是如果一个子数组可以连续排列，那么最大值和最小值之间的元素个数，就是数组长度。 

    int arr_seq_max(int *arr, int len)
{
    int max_len = 1;
    for (int i = 0; i < len-1; i++) {
        int amin = arr[i], amax = arr[i];

        for (int j = i+1; j < n; j++) {
            amin = min(amin, arr[j]);
            amax = max(amax, arr[j]);
            alen = amax - amin + 1;
            if (alen == j - i + 1)
                max_len = max(max_len, alen);
        }
    }
    return max_len;
}
  7. 四个角落的点循环移位。
  8. 用两个数组统计需要置零的行和列，本题的陷阱是置0后会影响后面的判断。

链表习题

  1. 提供两种思路：通过hash表保存已出现元素，通过遍历舍弃已出现元素。
  2. 两个相距n个节点的指针同时前进。
  3. 将后面的元素依次向前复制。
  4. 利用数学公式：假定链长为 \(l\) ，环长为 \(c\) ，p1和p2前进速度分别为1和2。相遇时假定p1走了 \(l+a\) ，并假定 \(a=kc + x\) ，那么有 \(l+x = nc\) ，且 \(x < c\) 。此时置p1为起点，p2不变，p1和p2同步前进，相遇的时候p2相对于入口点正好走 \(l + x\) ，也就是正好回到入口点。

堆栈和队列提示

  1. 维护一个最小值栈，并且修改pop()/push()方法， push()出现小于或等于最小值的时候，就向最小值栈同步push()该值。
  2. 一个栈用于出队，一个栈用于入队，出队为空时，将入队栈全部放到出队栈。
  3. 标准C++库利用一个双端队列即可实现栈。如果是单端队列，我们用一个队列qin来接受用户输入，另外一个队列qout接受qin的输入，不管是pop()还是top()我们都先将qin插入到qout去，直到qin只剩最后一个元素，这时候要pop()只要对qin做pop_front()即可，要top()只要对qin做front()即可。如果qin为空，那么我们只要将qin和qout交换一下即可。
  4. 需要额外一个栈来保存以排序部分，从未排序栈抽出一个元素。如果该值较小，就将已排序栈中的数据逐个压入未排序栈，插入当前值到已排序栈正确位置之后，再从未排序栈逐个压入到已排序栈。
  5. 维护一个堆，插入每个文件的第一个元素，当从堆抽取一个元素时，就将该元素所在文件的后继插入堆中。

网状数据结构

树和图提示

  1. 只需要比较最高和最低深度的差距即可。 

    int max_depth(node root)
{
    return 1 + max(max_depth(root.left), max_depth(root.right));
}
int min_depth(node root)
{
    return 1 + min(min_depth(root.left), min_depth(root.right));
}
  2. 一种方法可以用栈来保存元素。一种方法可以找到最左端元素，然后反复查找后继来完成。

  3. 为了简单，给出算法导论中的示例代码： 

    def tree_insert(root, node):
    x, pos = root, root
    while x:
        pos = x
        x = x.left if node < x else x.right
    node.parent = pos
    if not pos:
        root = node
    elif node < pos:
        pos.left = node
    else:
        pos.right = node

    删除就比较复杂了，要分几种情况：

    • node没有子节点，可以直接删除
    • node只有一个孩子，将孩子替换该节点
    • node有两个孩子，要找到后继，并将node的左子树放到后继的左子树中
    def tree_replace_subtree(T, a, b):
    "replace subtree a by subtree b"
    if not a.parent:
        T = b
    elif a == a.parent.left:
        a.parent.left = b
    else:
        a.parent.right = b
    if b:
        b.parent = a.parent

def tree_remove(T, node):
    if not node.left:
        tree_replace_subtree(T, node, node.right)
    elif not node.right:
        tree_replace_subtree(T, node, node.left)
    else:
        next = tree_min(node.right)
        if next.parent != node:
            tree_replace_subtree(T, next, next.right)
            next.right = node.right
            next.right.parent = next
        tree_replace_subtree(T, node, next)
        next.left = node.left
        next.left.parent = next

  4. 搞清楚二叉搜索树和数组的对应关系，用一个简单的递归式即可完成。 

    node tr_add(int *arr, int start, int end)
{
    int mid;

    if (end < start)
        return NULL;

    mid = (start + end) / 2;
    node n = new node(arr[mid]);
    n.left = tr_add(arr, start, mid - 1);
    n.right = tr_add(arr, mid + 1, end);

    return n;
}
  5. 首先root单属于一个链表，那么第2层链表就是root的子节点，第3层链表就是第2层链表中每个节点的字节点，依次类推即可。
  6. 该题目比较难，需要分如下几种情况分别处理：
    1. X.right存在，那么下一个节点就是left_most(X.right)
    2. X = P.left，那么P就是下一个节点
    3. X = P.right，那么下一个节点就是next(P)

  7. 如果是二叉搜索树，可以根据搜索路径来确定分叉节点。反过来可以找出A和B到根节点的路径，计算路径的相交点，通过链表很容易实现。另外一个比较有意思的解法是：如果A、B在P的一边，那么最小公共祖先一定是P的字节点，否则P就是A和B的最小公共祖先。 

    node min_ancestor(node root, node A, node B)
{
    if (root.left.has_node(A) && root.left.has_node(B))
        return min_ancestor(root.left, A, B);
    if (root.right.has_node(A) && root.right.has_node(B))
        return min_ancestor(root.right, A, B);
    return root;
}

  8. 创建一个前序遍历字符串和中序遍历字符串，如果A的两种字符串均是B的子字符串，那么可以确定A是B的子树。另外可以用一个典型的递归匹配算法来完成。 

    int __is_subtree(node A, node B)
{
    if (!A && !B)
        return 1;
    if (!A || !B)
        return 0;
    if (A.data != B.data)
        return 0;
    return __is_subtree(A.left, B.left) && __is_subtree(A.right, B.right);
}

int is_subtree(node A, node B)
{
    if (!A)
        return 1;
    if (!B)
        return 0;
    if (A.data == B.data) {
        if (__is_subtree(A, B))
            return 1;
    }
    return is_subtree(A, B.left) || is_subtree(A, B.right);
}

  9. 这个题目比较有难度，要对每一个节点作为起始遍历，并记录其所有路径。 

    void sum_path(node root, int sum, vector<int> &arr, int depth)
{
    if (!root)
        return;

    int tmp = sum;
    arr.push_back(root.data);
    for (int i = depth; i > -1; i--) {
        tmp -= arr[i];
        if (!tmp)
            print_msg(arr, i, depth);
    }

    vector<int> a1 = arr;
    vector<int> a2 = arr;
    sum_path(root.left, sum, a1, depth + 1);
    sum_path(root.right, sum, a1, depth + 1);
}
  10. 假定给定两点为A和B，从A开始进行遍历即可。