算法演练1:钻石与石头

原创
02/07 11:20
阅读数 0

小程介绍一个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代码提交,主因在于用了更多的空间): 

// 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,得到反馈如下: 


总结一下,本文介绍了算法设计的一个常规套路,即为了解决问题而先设计一个数据结构。读者在遇到一个问题时,应该先给自己留一点时间,进行一定的设计,而在设计算法时,应该先问问自己:是不是先设计一个数据结构呢?


本文分享自微信公众号 - 广州小程(gzxc2018)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部