《剑指 Offer》专项突破版 - 面试题 5 : 单词长度的最大乘积(C++ 实现)
目录
前言
方法一
方法二
前言
题目链接:318. 最大单词长度乘积 - 力扣(LeetCode)
题目:
输入一个字符串数组 words,请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串都包含至少一个相同的字符,那么返回 0。假设字符串中只包含英文小写字母。例如,输入的字符串数组 words 为 ["abcw", "foo", "bar", "fxyz", "abcdef"],数组中的字符串 "foo" 与 "bar" 没有相同的字符,它们的长度的乘积为 9;"abcw" 和 "fxyz" 也没有相同的字符,它们长度的乘积为 16,这是该数组中不包含相同字符的一对字符串的长度乘积的最大值。
分析:
解决这个问题的关键在于如何判断两个字符串 str1 和 str2 中有没有相同的字符。一个直观的想法是基于字符串 str1 中的每个字符 ch,扫描字符串 str2 判断字符串 ch 是否出现在 str2 中。如果两个字符串的长度分别为 p 和 q,那么这种蛮力法的时间复杂度是 O(pq)。
方法一
可以用哈希表来优化时间效率。对于每个字符串,可以用一个哈希表记录出现在该字符串中的所有字符。在判断两个字符串是否有相同的字符时,只需要从 'a' 到 'z' 判断某个字符是否在两个字符串对应的哈希表中都出现了。在哈希表中查找的时间复杂度是 O(1)。这个题目假设所有字符都是英文小写字母,只有 26 个可能的字符,因此最多只需要在每个字符串对应的哈希表中查询 26 次就能判断两个字符串是否包含相同的字符。26 是一个常数,因此可以认为应用哈希表判断两个字符是否具有相同的字符的时间复杂度是 O(1)。
由于这个题目只需要考虑 26 个英文小写字母,因此可以用一个长度为 26 的布尔型数组来模拟哈希表。数组下标为 0 的值表示字符 'a' 是否出现,下标为 1 的值表示字符 'b' 是否出现,其余依次类推。
写法一:
class Solution {
public:int maxProduct(vector<string>& words) {int length = words.size();bool** flags = new bool*[length];for (int i = 0; i < length; ++i){flags[i] = new bool[26];for (int j = 0; j < 26; ++j){flags[i][j] = false;}}
for (int i = 0; i < length; ++i){for (char ch : words[i]){flags[i][ch - 'a'] = true;}}
int result = 0;for (int i = 0; i < length; ++i){for (int j = i + 1; j < length; ++j){int k = 0;for (; k < 26; ++k){if (flags[i][k] && flags[j][k])break;}
if (k == 26){int product = words[i].size() * words[j].size();if (product > result)result = product;}}}
for (int i = 0; i < length; ++i){delete[] flags[i];}delete[] flags;
return result;}
};
写法二:
class Solution {
public:int maxProduct(vector<string>& words) {int length = words.size();vector<vector<bool>> flags(length, vector<bool>(26, false));for (int i = 0; i < length; ++i){for (char ch : words[i]){flags[i][ch - 'a'] = true;}}
int result = 0;for (int i = 0; i < length; ++i){for (int j = i + 1; j < length; ++j){int k = 0;for (; k < 26; ++k){if (flags[i][k] && flags[j][k])break;}
if (k == 26){int product = words[i].size() * words[j].size();if (product > result)result = product;}}}
return result;}
};
方法二
方法一是用一个长度为 26 的布尔型数组记录字符串中出现的字符。布尔值只有两种可能,即 true 或 false。这与二进制有些类似,在二进制中数字的每个数位要么是 0 要么是 1。因此,可以将长度为 26 的布尔型数组用 26 个二进制的数位代替,二进制的 0 对应布尔值 false,而 1 对应 true。
C++ 中 int 型整数的二进制形式有 32 位,但只需要 26 位就能表示一个字符串中出现的字符,因此可以用一个 int 型整数记录某个字符串中出现的字符。如果字符串中包含 'a',那么整数最右边的数位为 1;如果字符串中包含 'b',那么整数的倒数第 2 位为 1,其余依次类推。这样做的好处是能更快地判断两个字符串是否包含相同的字符。如果两个字符串中包含相同的字符,那么它们对应的整数相同的某个数位都为 1,两个整数的与运算(&)将不会为 0;如果两个字符串没有相同的字符,那么它们对应的整数的与运算的结果等于 0。
class Solution {
public:int maxProduct(vector<string>& words) {int length = words.size();vector<int> flags(length, 0);for (int i = 0; i < length; ++i){for (char ch : words[i]){flags[i] |= 1 << (ch - 'a');}}
int result = 0;for (int i = 0; i < length; ++i){for (int j = i + 1; j < length; ++j){if ((flags[i] & flags[j]) == 0){int product = words[i].size() * words[j].size();if (product > result)result = product;}}}return result;}
};
注意:方法一和方法二的时间复杂度是同一个量级的,但是方法一在判断两个字符串是否包含相同的字符时,可能需要 26 次布尔运算,而方法二只需要 1 次位运算,因此方法二的时间效率更高。
相关文章:
《剑指 Offer》专项突破版 - 面试题 5 : 单词长度的最大乘积(C++ 实现)
目录 前言 方法一 方法二 前言 题目链接:318. 最大单词长度乘积 - 力扣(LeetCode) 题目: 输入一个字符串数组 words,请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串…...
【Java集合篇】HashMap的get方法是如何实现的?
HashMap的get方法是如何实现的 ✔️典型解析✔️拓展知识仓✔️如何避免HashMap get方法的哈希重✔️HashMap get方法的优缺点有哪些✔️HashMap get方法的是线程安全的吗✔️什么是ConcurrentHashMap✔️ConcurrentHashMap有哪些应用场景✔️ConcurrentHashMap的优缺点 ✔️源…...
Java学习苦旅(二十二)——MapSet
本篇博客将详细讲解Map和Set。 文章目录 搜索概念模型 MapMap.Entry<K, V>Map的常用方法说明TreeMap和HashMap的区别 Set常用方法说明TreeSet和HashSet的区别 结尾 搜索 概念 Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例…...
【Linux Shell】12. 文件包含
和其他语言一样,Shell 也可以包含外部脚本,这样可以很方便的封装一些公用的代码作为一个独立的文件。可以理解为在第2个文件中包含第1个文件,执行第1个文件的代码。 被包含的文件 不需要可执行权限 。Shell 文件包含的语法格式如下࿱…...
前端-基础 常用标签-超链接标签( 锚点链接 )
锚点链接 : 点击链接,可以快速定位到 页面中的某个位置 如果不好理解,讲一个例子,您就马上明白了 >>> 这个是 刘德华的百度百科 ,可以看到,页面里面有很多内容,那就得有个目录了 …...
2024--Django平台开发-基础信息(一)
一、前置知识点 - Python环境搭建 (Python解释器、Pycharm、环境变量等) - 基础语法(条件、循环、输入输出、编码等) - 数据类型(整型、布尔型、字符串、列表、字典、元组、集合等) - 函数(文件操作、返回值、参数、作用域等) - 面向对象 (类、对象、封装、继承、多态等)包和模…...
C++力扣题目--94,144,145二叉树递归遍历
思路 这次我们要好好谈一谈递归,为什么很多同学看递归算法都是“一看就会,一写就废”。 主要是对递归不成体系,没有方法论,每次写递归算法 ,都是靠玄学来写代码,代码能不能编过都靠运气。 本篇将介绍前后…...
开源游戏引擎:创造无限可能 | 开源专题 No.56
godotengine/godot Stars: 62.6k License: MIT Godot Engine 是一个功能强大的跨平台游戏引擎,可用于创建 2D 和 3D 游戏。它提供了一套全面的常见工具,让用户可以专注于制作游戏而不必重复造轮子。该引擎支持将游戏一键导出到多个平台上,包…...
MyBatisPlus学习一:快速入门
前言 前面快速学习了Mybatis,现在开始快速学习MyBatisPlus 学习教程: 黑马mybatis教程全套视频教程,2天Mybatis框架从入门到精通 黑马程序员最新MybatisPlus全套视频教程,4小时快速精通mybatis-plus框架 简介 MyBatisPlus 是…...
2024最新外贸建站:ChemiCloud主机购买使用及自建外贸独立站教程
随着电商平台竞争的加剧,许多外贸从业者意识到减少对平台依赖的重要性,并选择搭建自己的外贸独立站来获得更多的控制权和灵活性。即使是没有建站基础的新手,也可以通过学习建站来实现这一目标。下面是一个适用于新手的外贸建站教程࿰…...
校招社招,认知能力测验,③如何破解语言常识类测试题?
作为认知能力测评中的一个环节,语言常识类,是大概率的出现,不同的用人单位可能略有不同,语言是一切的基础,而常识则意味着我们的知识面的宽度。 语言常识类的测试,如果要说技巧?难说....更多的…...
了解一下InternLM2
大模型的出现和发展得益于增长的数据量、计算能力的提升以及算法优化等因素。这些模型在各种任务中展现出惊人的性能,比如自然语言处理、计算机视觉、语音识别等。这种模型通常采用深度神经网络结构,如 Transformer、BERT、GPT( Generative P…...
关于使用统一服务器,vscode和网页版jupyter notebook的交互问题
autodl 查看虚拟环境 在antodl上租借了一个服务器,通过在网页上运行jupyter notebook和在vscode中运行,发现环境都默认的是miniconda3。 conda info --envs 当然环境中所有的包都是一样的。 要查看当前虚拟环境中安装的所有包,可以使用以…...
Linux22.04系统安装显卡驱动,cuda,cudnn流程
1. 安装显卡驱动 ubuntu-drivers deices显示所有适配显卡的驱动型号,recommended为推荐安装 安装 sudo apt install nvidia-driver-440重启 sudo reboot验证 nvidia-smi2. 安装cuda 在 CUDA Toolkit 的下载页面选择系统版本和安装方式,下载并运行…...
【常考简答题】操作系统
目录 1、什么是进程 2、创建进程步骤 3、什么是死锁 4、死锁四个必要条件 5、什么是内存管理 6、内存管理功能 7、进程的三个基本状态转化图 8、操作系统为什么引入线程 9、什么是对换技术,好处是什么 10、DMA直接存取控制工作方式流程图 11、什么是假脱…...
Large Language Models Paper 分享
论文1: ChatGPTs One-year Anniversary: Are Open-Source Large Language Models Catching up? 简介 2022年11月,OpenAI发布了ChatGPT,这一事件在AI社区甚至全世界引起了轰动。首次,一个基于应用的AI聊天机器人能够提供有帮助、…...
微信小程序实战-01翻页时钟-1
文章目录 前言需求分析功能设计界面设计界面结构设计界面样式设计 逻辑设计 单页功能实现运行结果 前言 我经常在手机上用的一款app有一个功能是翻页时钟,基于之前学习的小程序相关的基础内容,我打算在微信小程序中也设计一个翻页时钟功能,J…...
BigDecimal的性能问题
BigDecimal 是 Java 中用于精确计算的数字类,它可以处理任意精度的小数运算。由于其精确性和灵活性,BigDecimal 在某些场景下可能会带来性能问题。 BigDecimal的性能问题 BigDecimal的性能问题主要源于以下几点: 内存占用:BigDec…...
Defi安全-Monox攻击事件Foundry复现
其它相关内容可见个人主页 Mono攻击事件的介绍见:Defi安全–Monox攻击事件分析–phalconetherscan 1. 前情提要和思路介绍 Monox使用单边池模型,创建的是代币-vCash交易对,添加流动性时,只需添加代币,即可进行任意代…...
大二上总结和寒假计划
👂 Start Again - Connor Price/Chloe Sagum - 单曲 - 网易云音乐 👂 年年 - 徐秉龙 - 单曲 - 网易云音乐 目录 🌼前言 👊成长 (1)情感 (2)运动 (3)穿搭…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
