LeetCode解析------1178.猜字谜-位运算

标签: leetcode

题目:

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出,如果一个单词 word 符合下面两个条件,那么它就可以算作谜底:

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如,如果字谜的谜面是 “abcdefg”,那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”;而 “beefed”(不含字母 “a”)以及 “based”(其中的 “s” 没有出现在谜面中)。
返回一个答案数组 answer,数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例:

输入:
words = [“aaaa”,“asas”,“able”,“ability”,“actt”,“actor”,“access”],
puzzles = [“aboveyz”,“abrodyz”,“abslute”,“absoryz”,“actresz”,“gaswxyz”]
输出:
[1,1,3,2,4,0]

解释:
1 个单词可以作为 “aboveyz” 的谜底 : “aaaa”
1 个单词可以作为 “abrodyz” 的谜底 : “aaaa”
3 个单词可以作为 “abslute” 的谜底 : “aaaa”, “asas”, “able”
2 个单词可以作为 “absoryz” 的谜底 : “aaaa”, “asas”
4 个单词可以作为 “actresz” 的谜底 : “aaaa”, “asas”, “actt”, “access”
没有单词可以作为 “gaswxyz” 的谜底,因为列表中的单词都不含字母 ‘g’。

提示:
1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] 都是小写英文字母。
每个 puzzles[i] 所包含的字符都不重复。

简单介绍:
题目:猜字谜
题目难度:困难
使用语言:JAVA。
这道题来自leetcode题库的位运算标签。

解题思路:
首先看题、分析题意,我们可以明确1个关键点:
1.如何去简化计算量(遍历的方式会超时)
既然,我们已经分析出来题目的关键任务了,下面我们就可以开始思考实现了。
我们采用算法与数据结构的思路来剖析一下这题,

数据结构:
要实现对数据的操作,我们要先明确存储数据的数据结构。
该题的数据结构的作用:
1.动态列表res保存结果
2.哈希键值对统计单词词频

算法:
既然明确了我们的数据结构,我们就可以开始我们的算法分析了。
1.统计words单词的词频,用位运算将单词转化为一个数。
2.搜索puzzles的模式子集,判断首字母是否在word中出现,若出现,则将wordcount中的单词词频(0或其他)添加为该字谜的谜底数。

代码部分:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> res = new ArrayList<>();   //结果
        HashMap<Integer, Integer> wordCount = new HashMap<>();    //单词模式出现的次数。如aaa与aaaaa是同一类单词模式

        //统计同一单词模式出现的次数
        for (int i = 0; i < words.length; i++) {
            int k = 0;
            for (char c : words[i].toCharArray()) {
                k |= (1 << (c - 'a'));     //位运算 |:与运算,赋值各位    <<:移位也相当于乘2的n次方
            }
            wordCount.put(k, wordCount.getOrDefault(k, 0) + 1);//次数加1
        }

        //搜索模式子集
        for (int i = 0; i < puzzles.length; i++) {
            int k = 0;
            for (char c : puzzles[i].toCharArray()) {
                k |= (1 << (c - 'a'));     //位运算 |:与运算,提取1    <<:移位也相当于乘2的n次方
            }
            int count=0;
            for (int j=k;j>0;j=(j-1)&k){ //模式子集
                 if(((1<<(puzzles[i].charAt(0)-'a'))&j)>0){ //取位
                    count+=wordCount.getOrDefault(j,0);
                }
            }
            res.add(count);
        }
        return res;
    }
}

在这里插入图片描述

结语:
晚安!晚安!晚安!晚安!晚安!晚安!晚安!晚安!晚安!晚安!

版权声明:本文为weixin_44337475原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44337475/article/details/107082186

智能推荐

Go语言gin框架的安装

尝试安装了一下gin,把遇到的一些小问题来记录一下 安装步骤 首先来看看官方文档,链接点这里 可以看到安装步骤很简单,就一句话 在命令行中输入这句话运行等待就好。 问题来了,因为墙的问题,go get会很慢,所以命令行里面半天什么反应也没有,不要急,慢慢等着就会看到gin-gonic/gin这个目录出现 这个时候命令行还是没有结束,表示还在下一些东西。有的时候可能心急的人就停了(比如我),然后写个...

uni-app表单组件二

input(输入框) 属性名 类型 说明 平台差异 value String 输入框的初始内容 type String input 的类型 password Boolean(默认false) 是否是密码类型 placeholder String 输入框为空时占位符 placeholder-style String 指定 placeholder 的样式 placeholder-class Strin...

深入理解 JavaScript 代码执行机制

深入理解 JavaScript 代码执行机制 前言 本文仅为个人见解,如有错误的地方欢迎留言区探讨和指正。 1、餐前甜品 如下是一段 JavaScript 代码,如果你毫不犹豫的说出代码执行顺序。那么请直接滚动到底部,留下你的足迹,接受膜拜。如果还不是很确定,那么请往下继续查看。 2、磨刀不误砍柴工(了解浏览器原理) (1) 进程和线程 进程是cpu资源分配的最小单位(是能拥有资源和独立运行的最小...

Centos7下配置DRBD Cluster扩展节点

操作环境 CentOS Linux release 7.4.1708 (Core) DRBDADM_BUILDTAG=GIT-hash:\ ee126652638328b55dc6bff47d07d6161ab768db\ build\ by\ [email protected]\,\ 2018-07-30\ 22:23:07 DRBDADM_API_VERSION=2 DRBD_KERNEL_VER...

选择排序了解一下

选择排序是一种简单直观的排序算法,它的主要思想:初始时在序列中找到最小(大)的元素,放到序列的起始位置作为已排序序列;然后再从剩余未排序元素中继续寻找最小(大)的元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。 即每遍历一次就记住了最大(小)的元素的位置,最后仅需要一次交换操作就可以放到其适合的位置。 如下图所示: 实现代码如下: 选择排序是不稳定排序,时间复杂度在最优、最坏情况下都...

猜你喜欢

ssh免密登录、操作另一个服务器

目录 一、SSH简介 scp 传输文件 二、SSH免密登陆原理  三、SSH免密登陆 1、生成** 2、将客户端公钥 配置到服务器端 方法一:  方法二: 3、known_hosts 一、SSH简介 SSH(Secure Shell)是一种通信加密的网络传输协议,可在不安全的网络中为网络服务提供安全的传输环境。 SSH通过在网络中创建安全隧道来实现SSH客户...

如何把OpenCV v3.1.0整合到 Android Studio v1.4.1

本文翻译自: https://stackoverflow.com/questions/27406303/opencv-in-android-studio   点击打开链接 有经验的Android studio 开发大牛们可能觉得这篇文章写得太啰嗦,可是本文主要针对刚刚迈入进来的小妞们~~现在开始啦: 第一步 创建一个新工程(File/New Project) 命名为 "...

mysql主从库配置

1.场景描述 废话不多说了,简单记录下mysql主从库配置,实现读写分离,还可以设置延迟同步,防止误操作,起到备库作用。。 2.解决方案 简单记录下如何快速对现有mysql库实现读写分离,至于可能遇到的数据不一致等问题,后续再解释,本次只介绍如何快速对现有mysql做主从库配置/读写分离。 2.1 原理 MySQL主从库或者读写分离配置,其实依靠的mysql自带二进制日志。 简单说就是在主库上做的...

Java多线程编程-(8)-多图深入分析ThreadLocal原理

前几篇: Java多线程编程-(1)-线程安全和锁Synchronized概念 Java多线程编程-(2)-可重入锁以及Synchronized的其他基本特性 Java多线程编程-(3)-线程本地ThreadLocal的介绍与使用 Java多线程编程-(4)-线程间通信机制的介绍与使用 Java多线程编程-(5)-使用Lock对象实现同步以及线程间通信 Java多线程编程-(6)-两种常用的线程计...