算法的乐趣之常用技巧

发布 : 2019-03-24 浏览 :

常用技巧

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

哨兵位

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

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

巧用数组下标

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

1
2
3
4
5
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)

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

取余的用法

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

1
2
3
4
5
6
7
8
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

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

1
2
3
4
5
6
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 语句,无非是这样的结构:

1
2
3
4
5
6
7
8
9
10
11
switch(direction)
{
case UP:
……
case DOWN:
……
case LEFT:
……
case RIGHT:
……
}


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

  • 向左搜索:行坐标 i 不变,列坐标 j-1
  • 向上搜索:行坐标 i-1,列坐标不变
  • 向右搜索:行坐标 i 不变,列坐标 j+1
  • 向下搜索:行坐标 i+1,列坐标不变

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

1
2
3
4
5
6
7
typedef struct 
{
int x_off;
int y_off;
}OFFSET;

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

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

1
2
3
4
5
6
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 个节点。

单链表倒序

1
2
3
4
5
6
7
8
9
10
11
12
13
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 是大写英文字母还是小写英文字母,就可以利用这种连续的特点,直接做范围判断:

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

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

1
2
3
4
5
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 算法。

1
2
3
4
5
6
7
8
9
10
11
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;
}

本文作者 : HeoLis
原文链接 : http://ishero.net/算法的乐趣之常用技巧.html
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

学习、记录、分享、获得

微信扫一扫, 向我投食

微信扫一扫, 向我投食