经过设计的东西就是算法，学习算法就是学习设计。跟熟手技工一样，算法强的有效手段，就是训练啦，日常或工作中遇到的问题，是一个训练，而主动去刷题，是另一个训练。
这里就刷leetcode的题目，leecode是一个可以进行算法答题的网站，地址是：https://leetcode.com/，前不久还出了中文版，地址是：https://leetcode-cn.com/
这一次，先来一个题目：
钻石与石头
对于这个题目，自然的想法，就是顺着题意来，也就是判断J中的字母在S中出现的次数。如果能判断J中一个字母出现的次数，那所有字母都可以这样判断--重用的套路就出来了。
所以，按自然的想法，把J中一个字母出现次数的判断作为一个标准作业，使用之前小程多次提到的“重用”的基础套路，把各个字母出现的次数累加起来，就可以把问题解决掉。
但是，一般自然的想法，并不是高效的算法。
这个题目，不应该简单地套用“重用”的套路去解决问题，你要思考更高效的设计。
为了设计一个好的算法，你可能要先设计或选择一个合适的数据结构。小刀砍树，或大炮打蚊子，都是不合适的，但如果没有武器裸手拆炸弹也是不合适的。这里有一个套路，就是为了解决一个问题，先弄一个武器出来。
本文介绍一个基本的算法设计套路，就是为了解决问题而设计一个特别的数据结构。 这个套路，到处可见。为了设计一个算法，先设计一个数据结构。 数据结构，就是数据的组织结构，一定会有自己的组织特点。
对于这个题目，使用这个套路，那就是，要设计一个怎么样的数据结构，才能让J中的字母快速地知道自己出现的次数呢（而不是跟S中的字母一个一个地配对）？
根据S的特点（只能是字母，区分大小写），可以设计一个这样的数据结构：一个数组，数组的长度能覆盖所有的字母的值，也就是以字母的值作为索引一定能找到一个位置，而这个位置上的值，就是这个字母出现的次数。
如果有这样的数组，那要找出J中字母出现的次数就很简单，以字母的值为索引，对应值就是出现的次数。
这样的数组，怎么构建起来呢？
以'z'+1的值，作为数组的长度，加1是因为数组的索引从0开始，要让'z'为索引时也能找到一个位置。
数组初始时，每个元素的值都是0。
然后，开始遍历S，以字母值为索引，直接找到位置，再把位置值+1。
遍历完S后，这个数据结构就建立起来了，而且，数据结构的状态也建立起来了，就好像经过了机器学习一样，已经是一个可用的状态，比如下面的截图所示：
构建一个数据结构
最后，使用这个构建好的数据结构，遍历J中的字母，直接查到这个字母出现的次数，问题即可解决。
这里设计了一个数组来构建出一个数据结构，但这只是一个示例，只是想说明“先设计一个数据结构”的套路，至于是什么样的数据结构，是有得选择的，比如对于这个问题，也可以设计出一个hash表，用key表示S中的字母，而value为字母出现的次数，一样可以优雅地解决问题。
所以，重要的是套路，而不是具体的表现，除非具体的表现已经成了一个关键的问题。
以上，介绍了怎么根据特定的问题，构建一个合适的数据结构，重点是要有构建数据结构的意识。
最后，小程给出两个实现代码以及leecode的反馈，并结束本文的主要内容：
// c code
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int numJewelsInStones(char* J, char* S) {
int arrlen = 'z'+1;
char* arr = (char*)malloc(arrlen);
memset(arr, 0, arrlen);
for (int i = 0; i < strlen(S); i ++) {
arr[S[i]] += 1;
}
int cnt = 0;
for (int j = 0; j < strlen(J); j ++) {
cnt += arr[J[j]];
}
free(arr);
return cnt;
}
int main(int argc, char *argv[])
{
char *S = "aAAbbbb", *J = "aA";
int cnt = numJewelsInStones(J, S);
printf("cnt=%d\n", cnt);
return 0;
}
把以上实现代码提交到leecode，可以看到这样的反馈（执行速度很快，战胜了100%的c代码提交，主因在于用了更多的空间）：
leecode反馈1
// c# code
public int NumJewelsInStones(string J, string S)
{
int result = 0;
if (string.IsNullOrEmpty(J) || string.IsNullOrEmpty(S)) return result;
var kv = new Dictionary<string, int>();
var sArr = S.ToArray();
var jArr = J.ToArray();
//S去重，统计字母出现次数
int i = 0, v = 1;
while (i < sArr.Count())
{
if (kv.ContainsKey(sArr[i].ToString()))
{
kv[sArr[i].ToString()] += v;
i++;
continue;
}
kv.Add(sArr[i].ToString(), v);
i++;
}
//统计宝石数
foreach (var kvp in kv)
{
if (!J.Contains(kvp.Key)) continue;
result += kvp.Value;
}
return result;
}
把以上的实现提交到leecode，得到反馈如下：
leetcode反馈2
总结一下，本文介绍了算法设计的一个常规套路，即为了解决问题而先设计一个数据结构。你在遇到一个问题时，应该先给自己留一点时间，进行一定的设计，而在设计算法时，应该先问问自己：是不是先设计一个数据结构呢？
haha
网友评论