常用技巧

技巧、常识、策略、原则。

哨兵位

设置哨兵位是程序设计中常用的技巧之一，常用在线性表的处理过程中，比如查找和移动数据操作。

哨兵位通常起到两个作用，一个是作为一个临时存储空间使用，另一个是减少不必要的越界判断，简化算法代码复杂度。比如环形链表通常会设置一个表头节点，无论向前或向后遍历，均以这个表头节点为遍历越界（重复）的依据，这样维护链表的时候就不需要专门存储一个表头指针，这个表头节点可以理解为哨兵位。
插入排序算法中也会利用表中的 0 号位置作为哨兵位使用，这个位置不仅起到一个临时存储空间的作用，还可以简化插入后移动数据的判断条件。
在一些查找操作中，有时候也会用到哨兵位，比如要查找某个值，可以在表中适当的位置预置一个等于这个值的哨兵位，这样在查找过程中就不用考虑边界越界，也不用考虑找不到的情况，查找遍历的算法实现就可以很简洁，只需在查找结束的时候，判断一下结果是否是哨兵位，如果是哨兵位，则说明没有找到。

巧用数组下标

巧用数组下标可用于统计元素出现次数，在某些情况下，问题域内的一些特殊数据元素，比如 ID、类型等标识性属性，如果能定义成从 0 开始的连续整数，也可以利用数组和数组下标的特殊关系，简化数据模型，优化代码结构。

type_house = 0,
type_nation = 1,
type_drink = 2,
type_pet = 3,
type_cigaret = 4

然后将这五种类型属性定义成数组：

1	int itemValue[GROUPS_ITEMS];

现在要查看一个 GROUP 绑定组中房子的颜色是否是蓝色，就可以这样编写代码：

1	if(group.itemValue[type_house] == COLOR_BLUE)

这样的例子应用得非常广泛，只要控制好数组越界问题，巧妙地设计数据结构，定义有意义的常量名称，可以在不影响代码可读性的基础上极大地简化算法实现。

取余的用法

取余运算最常用的方法就是判断一个数能否被另一个数整除：

if ((number % 5) == 0)
   {
       //能被5整除
   }
   else
   {
       //不能被5整除
   }

如果仅仅是判断奇偶数，判断（number & 1）是否等于 0 是更好的方法。更一般的情况，当取余运算的除数是 2 的 n 次方的时候，用 & 运算符代替取余会更高效。比如当 x=2n 的时候，a % x 的结果与 a & (x - 1) 的结果是等价的。

一重循环遍历二维数组

重循环遍历二维表关键是对下标的处理，对于一个 M × N 的二维表，可用以下方法解出对应的二维下标

1 2	int row = i / M int col = i % N

反过来，也可以用以下公式将二维坐标还原为一维坐标：

1	int i = row * N + col

很多九宫格类型的游戏棋盘的初始化就是用的这种方法。

for(int i = 0; i < 9; i++)
{
    int row = i / 3;
    int col = i % 3;
    game->cells[row][col].fixed = false;
}

棋盘（迷宫）类算法方向遍历

棋盘或迷宫类游戏常常需要配合各种搜索算法，二维棋盘和迷宫的搜索常常是沿着与某个位置相临的 4 个或 8 个方向展开，对这些方向的遍历就是搜索算法的主要结构。我常常看到一些朋友给出的算法用了长长的 if-else 或 switch-case 语句，无非是这样的结构：

switch(direction)
{
case UP:
……
case DOWN:
……
case LEFT:
……
case RIGHT:
……
}

以二维数组定义的棋盘为例，如果从 i 行 j 列开始向上、下、左、右四个方向搜索，则这四个方向可转换为以下行、列坐标关系：

向左搜索：行坐标 i 不变，列坐标 j-1
向上搜索：行坐标 i-1，列坐标不变
向右搜索：行坐标 i 不变，列坐标 j+1
向下搜索：行坐标 i+1，列坐标不变

根据以上关系，首先定义二维数组下标偏移量，然后定义一个偏移量数组，分别表示向四个方向的数组下标偏移量：

typedef struct
{
   int x_off;
   int y_off;
}OFFSET;

OFFSET dir_offset[] = {{0,-1},{-1,0},{0,1},{1,0}};

假设当前位置的二维数组下标是 x、y，则对此位置开始向四个方向搜索的代码可以如此实现：

for(int i = 0; i < count_of(dir_offset); i++)
{
    int new_x = x + dir_offset[i].x_off;
    int new_y = y + dir_offset[i].y_off;
    ……
}

单链表

“判断单链表是否有环”:
如何一次遍历就找到链表中间位置节点”
“单链表中倒数第 k 个节点”

如第一个问题，设置一个“慢指针”和一个“快指针”，从链表头开始遍历，慢指针一次向后移动一个节点，快指针一次移动两个节点。如果链表没有环，则快指针会先到达最后一个节点（NULL），否则的话，快指针会追上慢指针（相遇）。

第二个问题同样设置一快一慢两个指针，慢指针一次移动一个节点，快指针一次移动两个节点，当快指针移动到结尾时，慢指针指向的就是中间节点。

第三个问题也是双指针，其中一个先移动 k 个节点，然后两个指针以相同的速度一起移动，当先移动的指针移动到结尾的时候，后移动的指针指向的就是倒数第 k 个节点。

单链表倒序

LINK_NODE *reverse_link(LINK_NODE *head)
{
    LINK_NODE *newHead;

    if ((head == nullptr) || (head->next == nullptr))
        return head;

    newHead = reverse_link(head->next); /*递归逆转子链表部分*/
    head->next->next = head; /*回朔部分*/
    head->next = nullptr;

    return newHead;
}

这段代码的关键点是头节点 head 的下一个节点 head→next 将是逆序后的新链表的尾节点，也就是说，被摘除的头接点 head 需要被链接到 head→next 才能完成整个链表的逆序。

利用英文字母的 ASCII 编码特点

ASCII 表中 26 个英文字母是连续的，小写字母 a-z 对应的 ASCII 码值是 0x61-0x7A，大写字母 A-Z 对应的 ASCII 码值是 0x41-0x5A。如果将字母’A’以整数看待，它就是 0x41，同样，将整数 0x41 当作字符看待，它就是字母’A’。判断一个 char 是大写英文字母还是小写英文字母，就可以利用这种连续的特点，直接做范围判断：

if ((c >= 'a') && (c <= 'z'))
   {
       //c是小写字母
   }

对于题目中用 a、b、c、d 字母标识的事物，数据模型通常可用 0、1、2、3 这样连续的数字来对应，输出结果时，也可以利用这种连续性直接将数字编号转成字母标识：

for (int i = 0; i < 5; i++)
    {
        char object = 'a' + i;
        std::cout << "object: " << object << " is good!" << std::endl; //输出object：a(/b/c/d） is good！
    }

ASCII 码表中小写字母和对应的大写字母之间的 ASCII 码值相差 0x20，可以利用这个特点进行大小写的转换，小写字母减 0x20 可以得到对应的大写字母，大写字母加上 0x20 可以得到对应的小写字母：

1 2	char A = 'a' - 0x20; char a = A + 0x20;

常见问题

topN 问题和最小堆

从大量的数据中找出符合条件的 n 个数据就是所谓的 topN 问题，常见的问题比如：从 N 个无序的数中找出最小的前 k 个数（或最大的前 k 个数）。对这种问题，如果 N 的规模不大，可以考虑先对 N 个数进行升序排序（或降序排序），然后输出前 k 个数。排序算法的时间复杂度最好就是 O(nlg(n))，这个方法基本上也是 O(nlg(n)) 的时间复杂度。但是当 N 的规模大到一定程度时，完整的对 N 个数进行排序仍然是个很大的开销，在这种情况下，通常采用的方法是用一个小的有序数据结构维护前 k 个被选出来的最小数，依次遍历 N 个数，如果某个数比选出来的前 K 个数中最大的那个数小，则将这个数插入到这个小的有序数据结构中，同时淘汰掉最大的那个数。当 N 个数都处理完，这个有序数据结构中的 k 个数就是最小的前 k 个数。这个方法的主要处理就是维护前 k 个有序的数需要的比较操作，有序表的比较操作次数是 lg(k) 次，因此这个方法的时间复杂度是 O(nlg(k))。一般情况下，k 都是远远小于 N 的，因此这种方法大大优于直接排序的方法。

有很多种方法维护这前 k 个有序的数，比如数组，但是每次插入操作需要移动数据，k 稍微大一点开销也不少。大多数有追求的人会选择用最小堆来组织这 k 个数，堆是一棵完全二叉树，树的深度小，维护效率高。如果用前面介绍的数组方法存储树，则其子节点的数组索引可以直接用父节点的索引计算出来，还可以进一步提高数据访问的效率。

使用最大最小堆来维护有序数据，在很多情况下可以提高某些操作的效率，在很多算法的改进算法中经常可以看到它们的“身影”。比如 Dijkstra 算法中每次需要从 dist 数组中寻找最小值 dist[Vi]，并将 Vi 加入到 T 集合中。如果用一个最小堆存放当前的各个 dist[Vi] 值，则每次不需要再做查找比较操作，直接从最小堆中 extract 出最小的那个值即可（当然，需要维护最小堆）。

常用的 hash 算法（字符串比较）

在很多算法问题中，字符串常常作为关键字（key）属性存在，比如人名、地名和物品名称等。字符串的存储和处理也是 C 语言比较头疼的问题，字符串的直接比较更是效率不高，如果能将字符串的处理转化成整数的处理，则存储就变得简单，而且关键字的比较也更高效，排序和查找的处理算法也可以简化。将长度不一的字符串一一映射到各不相同的整数，通常需要进行 hash 计算，这一节我们就介绍几种常用的字符串 hash 算法。

unsigned int bkdr_hash(const char *str)
{
    unsigned int hash = 0;
    while (*str != 0)
    {
        int ch = (int)*str++;
        hash = hash * 31 + ch;   // 乘法因子还可以是 131、1313、13131、131313...
    }

    return hash;
}

算法的乐趣之常用技巧