leetcode常用算法:打基础之LeetCode算法题第30日
leetcode常用算法:打基础之LeetCode算法题第30日注:您可以按任何顺序返回列表。我们给出两个句子A和B。(句子是一串空格分隔的单词。每个单词只包含小写字母。)如果一个单词在其中一个句子中只显示一次,并且不出现在另一个句子中,则该单词不常用。返回所有不常见单词的列表。
一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧,一开始就弄些重量级的,什么人工智能,机器学习的算法,还要有大量的数学以及优化的知识,小白们估计会很郁闷,当然我也不一定能做出来对吧。
我计划每题给出两种语言的解决方案,一种静态语言,一种动态语言。
我选择C语言和Python,本来考虑Java,但是篇幅有限,有兴趣的朋友自己试试
LeetCode 884. 找出两个句子中最不常用的词(Uncommon Words from Two Sentences)
问题描述:我们给出两个句子A和B。(句子是一串空格分隔的单词。每个单词只包含小写字母。)
如果一个单词在其中一个句子中只显示一次,并且不出现在另一个句子中,则该单词不常用。
返回所有不常见单词的列表。
您可以按任何顺序返回列表。
注:
- 0 <= A.length <= 200
- 0 <= B.length <= 200
- A并且B都只包含空格和小写字母。
首先我们必须要将两个字符串拆分成一个个的单词,存放到一个数组中。注意数组存放的是两个字符串拆分的结果,所以要注意它的长度。
然后对数组进行遍历,找到那些只出现一次的单词。
代码如下:
10~13行,分别复制A和B为_A和_B,因为原则上我是不想改变输入字符串的。
14~18行,定义一个长度是400的字符串数组words用来存放_A和_B拆分后的单词,然后调用自定义的split()函数拆分_A和_B,split()用库函数strtok()来完成拆分,注意strtok()的使用发方法,第一次调用的时候第一个参数应该是一个字符串地址,后面再次调用的时候第一个参数必须为NULL。
23~36行,对数组words的遍历查找,找到那些只出现一次的单词并存放到返回数组list中。
注意32~33行,因为words里面字符串都来自_A和_B,而_A和_B是位于函数uncommonFromSentences()的栈空间内的,不能返回给调用者,所以这里要重新分配一个堆内存空间来存放要返回的字符串。
python语言的实现:与计数有关,所以用Counter来实现会比较简单。
首先将A和B合并后再分割来创建一个Counter,这就可以统计每个单词出现的次数。
最后返回那些只出现一次的单词。