数据结构笔记总结(6.4)Leetcode中的集合问题和更多集合相关问题

804. 唯一摩尔斯密码词

国际摩尔斯密码定义一种标准编码方式,将每个字母对应于一个由一系列点和短线组成的字符串, 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
为了方便,所有26个英文字母对应摩尔斯密码表如下:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

给定一个单词列表,每个单词可以写成每个字母对应摩尔斯密码的组合。例如,”cab” 可以写成 “-.-.-….-“,(即 “-.-.” + “-…” + “.-“字符串的结合)。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有词不同单词翻译的数量。

注意:

单词列表words 的长度不会超过 100
每个单词 words[i]的长度范围为 [1, 12]
每个单词 words[i]只包含小写字母。

解题思路

首先对于这个words列表中相应的每一个单词使用这样的规则,逐个字母的把相应的摩斯密码是什么计算出来,计算完成之后把他们扔进一个集合中就好了。

在扔进集合过程中如果两个摩斯码是相同的就不会重复计算,最终我们看集合中相应的有多少个元素就是有多少个不同的摩斯密码。

代码演示

import java.util.TreeSet;

public class Solution {

    public int uniqueMorseRepresentations(String[] words) {

        String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        TreeSet set = new TreeSet<>();
        for(String word: words){
            StringBuilder res = new StringBuilder();
            for(int i = 0 ; i < word.length() ; i ++)
                res.append(codes[word.charAt(i) - 'a']);

            set.add(res.toString());
        }

        return set.size();
    }
}

集合拓展

有序集合与无序集合

之前我们实现的基于二分搜索树的集合,包括java中基于红黑树的集合本质都是有序集合。所谓的有序是指:

  • 有序集合中的元素具有顺序性<--基于搜索树来实现
  • 无序集合中的元素没有顺序性<--基于哈希表来实现

多重集合

对于集合来说,大多数情况下是不希望有重复元素的,但是在有些情况下,我们也希望有集合能容纳重复的元素,这种情况下就称为多重集合。实现其实也非常简单,我们只需要在允许重复元素的二分搜素树这样的结构基础上包装一层就是多重集合了。简单了解一下就可以了。

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(6.4)Leetcode中的集合问题和更多集合相关问题

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多