算法演练1：钻石与石头

作者: 广州小程 | 来源:发表于2019-05-29 19:06 被阅读0次

算法演练1：钻石与石头
你，不是我
石头跟钻石
钻石
iOS开发集锦之 2017.04.07(Swift 算法实战之路
你知道吗
光源的后面更适合修行
十个故事，教你如何理财
回溯算法演练
我的世界，幸运的一刻。

经过设计的东西就是算法，学习算法就是学习设计。跟熟手技工一样，算法强的有效手段，就是训练啦，日常或工作中遇到的问题，是一个训练，而主动去刷题，是另一个训练。

这里就刷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，得到反馈如下：