• 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 如果有任何体验不佳的地方,欢迎向客服反馈!

数据结构笔记总结(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<String> 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 中基于红黑树的集合本质都是有序集合。所谓的有序是指:

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

多重集合

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

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(6.4)Leetcode 中的集合问题和更多集合相关问题
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00