算法初步——其他高效技巧与算法

1. 打表

  打表是一种典型的用空间换时间的技巧,一般将所有可能需要用到的结果事先计算出来,这样后面需要用到时就可以直接查表获得。打表常见的用法有如下几种:

    • 在程序中一次性计算出所有需要用到的结果,之后的查询直接取这些结果。例如在一个需要大量查询 Fibonacci 数的问题中,则可以把所有 Fibonacci 数预先计算并存在数组中,那么每次查询就只需要 O(1) 的时间复杂度。
    • 在程序 B 中分一次或多次计算出所有需要用到的结果,手工把结果写在程序 A 的数组,然后在程序 A 中就可以直接使用这些结果。这种用法一般是当程序的一部分过程消耗的事件过多,因此在另一个程序中使用暴力算法求出结果,这样就能直接在源程序中使用这些结果,例如对 n 皇后问题来说,如果使用的算法不够好,就容易超时,而可以在本地用程序计算出对所有 n 来说 n 皇后问题的方案数,然后把算出的结果直接写在数组中,就可以根据题目输入的 n 来直接输出结果。
    • 对一些感觉不会做的题目,先用暴力程序计算小范围数据的结果,然后找规律,或许就能发现一些 “蛛丝马迹”。    

 

 

2. 活用递推

  有很多题目需要细心考虑过程中是否存在递推关系,如果能找到这样的递推关系,就能使时间复杂度下降不少。

  2.1 【PAT B1040/A1093】 有几个 PAT

  题目:字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)。现给定字符串,问一共可以形成多少个PAT?

  思路:对一个确定的位置 A 来说,以它形成的 PAT 个数等于它左边 P 的个数乘以它右边 T 的个数。于是问题就转换为,对字符串中的每个 A ,计算它左边 P 的个数与它右边 T 的个数的乘积,然后把所有 A 的这个乘积相加就是答案。那么如何较快的获得每一位左边 P 的个数呢?只需要设定一个数组 leftNumP,记录每一位左边 P 的个数(含当前位)。接着从左向右遍历字符串,如果当前位 i 是P,那么 leftNumP[i] = leftNumP[i-1]+1;如果当前为不是 P ,那么 leftNumP[i] = leftNumP[i-1]。以同样的方法可以计算每一位右边 T 的个数。

  主要代码如下:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstdlib>
 6 using namespace std;
 7 
 8 const int MAXN = 100010;
 9 const int MOD = 1000000007;
10 char str[MAXN];        // 字符串
11 int leftNumP[MAXN] = {0};    // 每一位左边(含)P 的个数 
12 
13 int main() {
14     gets(str);                // 读取字符串 
15     int len = strlen(str);    // 字符串长度
16     for(int i=0; i<len; ++i) {    // 计算每一位左边(含)P 的个数 
17         if(i > 0) {
18             leftNumP[i] = leftNumP[i-1];    // 继承上一位    
19         }
20         if(str[i] == 'P') {    // 当前位是 P  
21             leftNumP[i]++;
22         } 
23     }
24     
25     int ans=0, rightNumT=0;    // ans 为答案,rightNumT 为右边 T 的个数
26     for(int i=len-1; i>=0; --i) {    // 从右向左遍历 
27         if(str[i] == 'T') {            // 当前位为 T 
28             rightNumT++;
29         } else if(str[i] == 'A') {    // 当前位为 A  
30             ans = (ans + leftNumP[i]*rightNumT) % MOD;
31         }
32     }
33     printf("%d
", ans); 
34 
35     return 0;
36 }

3. 随机选择算法

  本节要讨论这样一个问题:如何从一个无序的数组中求出第 K 大的数。例如,对数组{5,12,7,2,9,3}来说,第三大的数是 5,第五大的数是 9。

  思路:随机选择算法的原理类似于之前介绍的随机快速排序算法。当对 A[left,right] 执行一次 randPartition 函数之后,主元左侧的元素个数就是确定的,且它们都小于主元。假设此时主元是 A[p],那么 A[p] 就是 A[left,right] 中的第 p-left+1 大的数。不妨令 M 表示 p-left+1,那么

    • 若 K==M ,说明第 K 大的数就是主元 A[p]
    • 若 K < M ,说明第 K 大的数在主元 A[p] 左侧,即 A[left...(p-1)] 中的第 K 大
    • 若 K > M ,说明第 K 大的数在主元 A[p] 右侧,即 A[(p+1)...right] 中的第 K-M 大  

  算法以 left==right 作为递归边界,返回 A[left] 。主要代码如下:

 1 // 随机选择算法
 2 // 从 A[left...right] 中返回第 K 大的数 
 3 int randSelect(int A[], int left, int right, int K) {
 4     if(left == right) {    // 边界 
 5         return A[left];
 6     }
 7     // randPartition 函数在 快速排序 随笔中有实现 
 8     int p = randPartition(A, left, right);    // 划分后主元的位置为 p 
 9     int M = p-left+1;    // A[p] 为第 M 大
10     if(K == M)    return A[p];    // 找到第 K 大
11     else if(K < M) {    // 第 K 大的数在主元 A[p] 左侧  
12         return randSelect(A, left, p-1, K); 
13     } else {    // 第 K 大的数在主元 A[p] 右侧
14         return randSelect(A, p+1, right, K-M);
15     }
16 }

  下面的问题是一个应用:给定一个整数组成的集合,集合中的整数各不相同,现在要将它分为两个子集合,使得这两个子集合的并为原集合,交为空集,同时在两个子集合的元素 n1 与 n2 只差的绝对值尽可能小的前提下,要求他们各自元素之和 S1 与 S2 之差的绝对值尽可能大。求这个 |S1-S2| 等于多少。

  思路:根据对问题的分析:这个问题实际上就是求原集合中元素的第 n/2 大,同时根据这个数把集合分为两部分。因此只需要使用 randSelect 函数求出第 n/2 大的数即可。代码如下:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstdlib>
 6 #include <ctime> 
 7 using namespace std;
 8 
 9 const int maxn = 100010;
10 int A[maxn], n;        // A[] 存放所有整数,n为其个数 
11 
12 // 对区间 [left,right]进行划分 
13 // 1. 先将 A[1] 存至某个临时变量 temp,并令两个下标 left、right 分别指向序列首尾。
14 // 2. 只要 right 指向的元素 A[right] 大于 temp ,就将 right 不断左移;当某个时候 A[right] 小于等于 temp 时,将元素 A[right] 挪到 left 指向的元素 A[left] 处。
15 // 3. 只要 left 指向的元素 A[right] 小于等于 temp ,就将 left 不断右移;当某个时候 A[right] 大于 temp 时,将元素 A[left] 挪到 right指向的元素 A[right] 处。
16 // 4. 重复 2.3 ,直到 left 与 right 相遇,把 temp(也即原 A[1])放到相遇的地方。 
17 int Partition(int A[], int left, int right) {
18     int temp = A[left];                                // 1.
19     while(left < right) {
20         while(left<right && A[right]>temp) right--;    // 2.
21         A[left] = A[right];
22         while(left<right && A[left]<=temp) left++;    // 3.
23         A[right] = A[left]; 
24     }
25     A[left] = temp;                                    // 4.
26     return left;
27 } 
28 
29 // 随机选择主元,然后进行划分 
30 int randPartition(int A[], int left, int right) {
31     // 生成 [left,right] 内的随机数 p 
32     int p = (int)(round(1.0*rand()/RAND_MAX*(right-left) +left));
33     swap(A[p], A[left]);    // 交换 A[p] 和 A[left] 
34     
35     // 以下跟 Partition 完全相同 
36     return Partition(A, left, right); 
37 } 
38 
39 // 随机选择算法
40 // 从 A[left...right] 中返回第 K 大的数 
41 int randSelect(int A[], int left, int right, int K) {
42     if(left == right) {    // 边界 
43         return A[left];
44     }
45     // randPartition 函数在 快速排序 随笔中有实现 
46     int p = randPartition(A, left, right);    // 划分后主元的位置为 p 
47     int M = p-left+1;    // A[p] 为第 M 大
48     if(K == M)    return A[p];    // 找到第 K 大
49     else if(K < M) {    // 第 K 大的数在主元 A[p] 左侧  
50         return randSelect(A, left, p-1, K); 
51     } else {    // 第 K 大的数在主元 A[p] 右侧
52         return randSelect(A, p+1, right, K-M);
53     }
54 } 
55 
56 int main() {
57     srand((unsigned)time(NULL));    // 初始化随机种子 
58     int sum=0, sum1=0;    // sum 为总和,sum1 为前半部分和
59     scanf("%d", &n);
60     for(int i=0; i<n; ++i) {    // 输出 n 个整数 
61         scanf("%d", &A[i]);
62         sum += A[i];
63     } 
64     randSelect(A, 0, n-1, n/2);    // 寻找第 n/2 大的数,并进行切分
65     for(int i=0; i<n/2; ++i) {    // 求前半部分和 
66         sum1 += A[i];
67     }
68     printf("%d
", (sum-sum1)-sum1);    // 输出结果 
69 
70     return 0;
71 }
随机选择算法应用
原文地址:https://www.cnblogs.com/coderJiebao/p/Algorithmofnotes09.html