首页 > 其他分享 >最大单词长度乘积

最大单词长度乘积

时间:2023-11-07 20:11:07浏览次数:27  
标签:字符 乘积 int 单词 length words 字符串 长度

题目概述:给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0 。
解题思路1:暴力做法+小优化。直接两重循环枚举所有组合,再写一个函数判断两个字符串是否含有相同字符。
时间复杂度:\(O(n^3)\),加了个小优化居然就过了
代码

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int res = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                if(i == j)continue;
                else if(words[i].length() * words[j].length() <= res)continue;//小优化
                else if(check(words[i],words[j])){
                    res = Math.max(res,words[i].length() * words[j].length());
                }
            }
        }

        return res;
    }

    public boolean check(String a,String b){
        for(int i = 0; i < a.length(); i ++){
            if(b.contains(a.charAt(i) + ""))return false;
        }

        return true;
    }
}

正解:上述做法在判断两个字符串是否含有相同字符时,需要O(n)的时间复杂度。那么能不能对其进行优化呢?答案是肯定的,我们可以将每个单词都转化为一个二进制串,在判断两个字符串是否含有相同字符时,只需判断这两个字符串对应的二进制经过与(&)操作后是否为0,如果为0说明无重复字符,否则有重复字符。这样就可以使用O(1)的时间复杂度来判断两个字符串是否含有相同字符了。并且本题限制,只有小写字符,所以,int类型就能够存储。
时间复杂度:\(O(n^2)\)
代码

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int res = 0;
        int masks[] = new int[n];
       for(int i = 0; i < n; i ++){
           int len = words[i].length();
           for(int j = 0; j < len; j ++){
               //将单词转化为二进制,26个字母对应26位二进制,该位为1仅当该单词含有该位对应的单词
               masks[i] |= 1 << (words[i].charAt(j) - 'a');
           }
       }

       for(int i = 0; i < n; i ++){
           for(int j = 0; j < n; j ++){
               if(i == j)continue;
               else if((masks[i] & masks[j]) == 0)res = Math.max(res,words[i].length() * words[j].length()); 
           }
       }

        return res;
    }

}

标签:字符,乘积,int,单词,length,words,字符串,长度
From: https://www.cnblogs.com/dengch/p/17815837.html

相关文章

  • 使用 JSON JavaScriptSerializer 进行序列化或反序列化时出错。字符串的长度超过了为
    一个报表的查询,用ajax调用的Service,查询条件没有问题,后台也能返回数据,就一直返回Error提示,F12看到是因为返回json时出错了 在web.config的configuration加以下代码即可解决<system.web.extensions><scripting><webServices><jsonSerializationmaxJs......
  • 30. 串联所有单词的子串
    给定一个字符串s和一个字符串数组words。words中所有字符串长度相同。s中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。例如,如果words=["ab","cd","ef"],那么"abcdef","abefcd","cdabef","cdefab","efabcd",和......
  • 根据三条边的长度在线生成三角形(generate triangles by edge lengths)
     网址:https://www.geogebra.org/m/JHgTXKrt 方法:鼠标拖放端点可以改变端点的长度和位置。 网址:https://www.mathwarehouse.com/triangle-calculator/online.php 方法:输入三条边的长度,生成三角形。 ......
  • 无限乘积拓扑
      还有关于无限乘积部分,大多数书上直接给出乘积空间中开集的样子。其中有限也不知道如何而来。而且Munkres上的解释与符号过于复杂。  \(\left\{X_i\right\}_{i\inI}\)是一族集合,一个映射\(x:I\rightarrow\bigcup\limits_{i\inI}{X_i}\)称为一个选择函数,若对于每个......
  • HashMap的长度是2的幂次方
    为了能让HashMap存取高效,尽量减少碰撞,也就是要尽量把数据分配均匀。Hash值的范围值-2147483648到2147483647,前后加起来大概40亿的映射长度,只要哈希函数映射的比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。......
  • 算法刷题记录-长度最小的子数组
    算法刷题记录-长度最小的子数组长度最小的子数组给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的连续子数组[numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。示例1:输......
  • 请求筛选模块被配置为拒绝超过请求内容长度的请求。
    转自:https://blog.csdn.net/cplvfx/article/details/126608987一、打开站点根目录的“web.config ”二、找到“system.webServer”节点三、在“security”节点增加“requestFiltering”节点配置1<system.webServer>2<security>3<req......
  • Token vs 单词
    要让LLMs(LargeLanguageModels,大型语言模型)生成文字,首先得让它们“懂”单词。单词首先会被拆分为Tokens(一种能够被编码的基础单元)。在不同的语言模型和分词系统中,Token的定义和分割方法可能会有所不同。绝大多数情况下,一个单词对应一个Token,但是也有很多情况不能一一对应。......
  • 无重复字符的最长子串(给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长
    importjava.util.*;publicclassSolution{/***代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可***@paramarrint整型一维数组thearray*@returnint整型*/publicintmaxLength(int[]arr){......
  • 如何遍历字符串的单词?
    内容来自DOChttps://q.houxu6.top/?s=如何遍历字符串的单词?如何遍历由空格分隔的单词组成的字符串中的单词?请注意,我对C字符串函数或那种字符操作/访问不感兴趣。我更喜欢优雅而不是效率。我目前的解决方法:#include<iostream>#include<sstream>#include<string>using......