Go Java算法最大单词长度乘积示例详解
作者:黄丫丫 发布时间:2022-09-27 18:16:19
最大单词长度乘积
给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0 。
*示例 1:
输入:words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出:16
解释:这两个单词为 "abcw", "xtfn"。
示例 2:
输入:words = ["a","ab","abc","d","cd","bcd","abcd"]
输出:4
解释:这两个单词为 "ab", "cd"。
示例 3:
输入:words = ["a","aa","aaa","aaaa"]
输出:0
解释:不存在这样的两个单词。
方法一:位运算(java)
为了得到最大单词长度乘积,朴素的做法是,遍历字符串数组 words 中的每一对单词,判断这一对单词是否有公共字母,如果没有公共字母,则用这一对单词的长度乘积更新最大单词长度乘积。
题目约定了每个单词仅包含小写字母,所以,我们可以将单词中的每个字母都映射到一个 int 类型的不同位上,这样,就做到了每个单词都对应一个 int 类型的数值,这样的话,我们对比两个单词是否包含相同的字母,只需要把它们对应的 int 数值做 & 运算,看是不是等于 0 即可,如果等于 0 ,说明没有相同的位是 1,也就不存在相同的字母。
这样,我们在比较两个单词是否没有公共字母的时候只要直接按位与一下即可,没有公共字母应该得到的值是0,其他情况得到的值都不为零。
class Solution {
public int maxProduct(String[] words) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int length = words.length;
for (int i = 0; i < length; i++) {
int mask = 0;
String word = words[i];
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
mask |= 1 << (word.charAt(j) - 'a');
}
if (wordLength > map.getOrDefault(mask, 0)) {
map.put(mask, wordLength);
}
}
int maxProd = 0;
Set<Integer> maskSet = map.keySet();
for (int mask1 : maskSet) {
int wordLength1 = map.get(mask1);
for (int mask2 : maskSet) {
if ((mask1 & mask2) == 0) {
int wordLength2 = map.get(mask2);
maxProd = Math.max(maxProd, wordLength1 * wordLength2);
}
}
}
return maxProd;
}
}
l:数组中所有单词的长度之和
n:数组长度
时间复杂度:o(l+n^2)
空间复杂度:o(n)
方法一:位运算(go)
具体的方法思路已经在上文中表述,详情请看上文内容
func maxProduct(words []string) int {
hash := func(word string) int {
res := 0
for _, r := range word{
res |= 1 << (r - 'a')
}
return res
}
m, ans := map[int]int{}, 0
for _, word := range words {
h := hash(word)
if m[h] < len(word) {
for other, v := range m {
if((other & h) == 0){
if tmp := v * len(word); tmp > ans {
ans = tmp
}
}
}
m[h] = len(word)
}
}
return ans
}
l:数组中所有单词的长度之和
n:数组长度
时间复杂度:o(l+n^2)
空间复杂度:o(n)
来源:https://juejin.cn/post/7134220167310999566
猜你喜欢
- 1,创建存储过程create proc Pro_Login(@UserName nvarchar(10),@PassWord nvarcha
- 一、封装的查询方法/*** solr查询方法* @param client solr客户端* @param query solr查询对象*
- C#实现多态主要有3种方法,虚方法,抽象类,接口1 虚方法在父类的方法前面加关键字virtual, 子类重写该方法时在方法名前面加上over
- 在项目中有一个需求是需要在局域网内跨PC远程调用一个程序,并且要求有界面显示,调查了一些资料,能实现远程调用的.Net技术大概有PsExec
- Feign调用中的两种Header传参方式在Spring Cloud Netflix栈中,各个微服务都是以HTTP接口的形式暴露自身服务的,
- 持久层的那些事什么是 JDBCJDBC(JavaDataBase Connectivity)就是 Java 数据库连接, 说的直白点就是 使
- package cn.liangjintang.httpproxy;import java.io.BufferedReader;import
- 为了让我提供的通用 Mapper 的 boot-starter 同时兼容 Spring Boot 1.x 和 2.x,增加了这么一个工具类。
- 废话不多说了,直接给大家贴java代码了。具体代码如下所示:/*支付流程*//****Controller.java 代码如下:*/@Req
- 若使用 Spring IoC 容器(ApplicationContext或BeanFactory)作为你的业务对象(你也应该这么做!),你会
- 一、什么时候会加载类?使用到类中的内容时加载:有三种情况1.创建对象:new StaticCode();2.使用类中的静态成员:Static
- 选取单个元素直觉来说选取单个元素肯定会比选取多个要简单得多,不过这里也存在一些问题。我们先看下一般的做法的问题是什么,然后再看下如何用lam
- 本文实例讲述了Java获得当前时间前指定几个小时具体时间的方法。分享给大家供大家参考,具体如下:package getBeforeHourD
- 计算机在执行程序时,为了提高性能,编译器和处理器常常会对指令重排,一般分为以下三种:源代码 -> 编译器优化的重排 -> 指令并
- 1. 运算符是什么?1.1 定义:对常量和变量进行运算操作的符号程序对数据进行运算时要用运算符1.2 常见运算符的概述1.3 表达式1.3.
- 结构:安装NuGet包:using SAP.Middleware.Connector;using System.Data;namespace
- 很多时候你新建了Maven 或者SpringBoot 工程,激动的点了主启动类,你就发现了下面的错误这里说的是啥意思呢,你没有数据库相关的链
- 1.概述在本快速教程中,我们将学习如何设置Spring Security LDAP。在我们开始之前,了解一下LDAP是什么? - 它代表轻量
- 提到类型转换,首先要明确C#中的数据类型,主要分为值类型和引用类型:1.常用的值类型有:(struct)整型家族:int,byte,char
- 前言之前在SpringBoot项目中简单使用定时任务,不过由于要借助cron表达式且都提前定义好放在配置文件里,不能在项目运行中动态修改任务