当前位置: 首页 > news >正文

华为OD机考算法题:字符串划分

题目部分

题目字符串划分
难度
题目说明给定一个小写字母组成的字符串s,请找出字符串中两个不同位置的字符作为分割点,使得字符串分成的三个连续子串且子串权重相等,注意子串不包含分割点。
若能找到满足条件的两个分割点,请输出这两个分割点在字符串中的位置下标,若不能找到满足条件的分割点请返回0,0。
子串权重计算方式为:子串所有字符的ASCII码数值之和。
输入描述输入为一个字符串,字符串由 a ~ z,26 个小写字符组成,5 ≤ 字符串长度 ≤ 200。
输出描述输出为两个分割点在字符串中的位置下标,以逗号分隔。
补充说明补充说明只考虑唯一解,不存在一个输入多种输出解的情况。
------------------------------------------------------
示例
示例1
输入acdbbbca
输出2,5
说明以位置 2 和 5 作为分割点,将字符串分割为 ac、bb、ca 三个子串,每一个的子串权重都为 196,输出为 2,5。
示例2
输入abcabc
输出0,0
说明找不到符合条件的分割点,输出为0,0。


解读与分析

题目解读

给定一个字符串,以字符串中的 2 个字符为分隔符,把它分成 3 个子字符串(不包含 2 个分隔符),使字符串中所有字符的 ASCII 码之和相等。输出这 2 个分隔符的下标,用 “,” 隔开,如果不存在,输出 “0,0”。

此题要么存在唯一解,要么不存在解。

分析与思路

此题字符串的长度不超过 200 个,比较简单的思路是尝试这 2 个分隔符是所有下标的情况,判断每种情况下所分隔出 3 个字符串的 ASCII 码之和是否相等。

这种方法的时间复杂度为 O(n^{2}),空间复杂度为 O(n^{2})。

以上方法可行,不过我们还有性能更好的方法。

先计算字符串中所有字符的 ASCII 码之和(设为 asciiSum),与此同时,找出可以作为分隔符的字母的最大和最小 ASCII 码值(分别设为 minAscii 和 maxAscii)。

分隔后设三个字符串的 ASCII 码之和的最大值为 maxAsciiSum,则 maxAsciiSum 值为 asciiSum - minAscii * 2;设ASCII 码之和的最小值为 minAsciiSum,则 minAsciiSum 值为 asciiSum - maxAscii * 2。

分隔后,每个字符串ASCII 码之和的取值范围为 [ minAsciiSum / 3,  maxAsciiSum / 3 ]。

顺序遍历字符串,找到第一个子字符串 ASCII 码之和在取值范围内时,第一个分隔符的所有可能下标。
倒序遍历字符串,找到第三个子字符串 ASCII 码之和在取值范围内时,第二个分隔符的所有可能下标。

根据第一个分隔符和第二个分隔符的所有下标组合,判断是否三个字符串 ASCII 码之和是否相等。如果相等,则输出这两个分隔符的下标;否则,输出 “0,0”。

此方法的时间复杂度为 O(n),空间复杂度为 O(n)。


代码实现

Java代码

import java.util.Scanner;/*** 字符串划分* @since 2023.10.10* @version 0.1* @author Frank**/
public class StringDivision {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();processStringDivision( input );}}private static void processStringDivision( String input ){int asciiSum = 0;int minAscii = 'z'; // min初始化成最大值int maxAscii = 'a'; // max初始化成最小值for( int i = 0; i < input.length(); i ++ ){char curChar = input.charAt( i );asciiSum += curChar;if( i > 0 && i < input.length() -1 ){if( curChar < minAscii ){minAscii = curChar;}if( curChar > maxAscii ){maxAscii = curChar;}}}int eachMinSum = ( asciiSum - maxAscii * 2 ) / 3;int eachMaxSum =  ( asciiSum - minAscii * 2 ) / 3 + 1; // 向上取整,避免漏掉一些情况int leftIndex = 0;		int leftSum = 0;for( int i = 0; i < input.length() - 2; i ++ ){int curChar = input.charAt( i );leftSum += curChar;leftIndex ++;if( leftSum >= eachMinSum ){break;}}			int rightIndex = input.length() - 1;int rightSum = 0;for( int i = input.length() - 1; i > 2; i -- ){int curChar = input.charAt( i );rightSum += curChar;rightIndex --;if( rightSum >= eachMinSum ){break;}}while( leftSum <= eachMaxSum && rightSum <= eachMaxSum && leftIndex < rightIndex ){if( leftSum < rightSum ){int curChar = input.charAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;}if( leftSum > rightSum ){int curChar = input.charAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;}if( leftIndex >= rightIndex ){break;}// 相等的情况int theOtherSum = asciiSum - leftSum - rightSum - input.charAt( leftIndex ) - input.charAt( rightIndex );if( theOtherSum == leftSum ){System.out.println( leftIndex + "," + rightIndex);return;}// 如果 theOtherSum 不相等,继续int curChar = input.charAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;curChar = input.charAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;			}System.out.println( "0,0" );}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {processStringDivision(line);}
}();function processStringDivision( input ) {var asciiSum = 0;var minAscii = 'z'.charCodeAt(); // min初始化成最大值var maxAscii = 'a'.charCodeAt(); // max初始化成最小值for( var i = 0; i < input.length; i ++ ){var curChar = input.charCodeAt( i );asciiSum += curChar;if( i > 0 && i < input.length -1 ){if( curChar < minAscii ){minAscii = curChar;}if( curChar > maxAscii ){maxAscii = curChar;}}}var eachMinSum = ( asciiSum - maxAscii * 2 ) / 3;var eachMaxSum =  ( asciiSum - minAscii * 2 ) / 3 + 1; // 向上取整,避免漏掉一些情况var leftIndex = 0;      var leftSum = 0;for( var i = 0; i < input.length - 2; i ++ ){var curChar = input.charCodeAt( i );leftSum += curChar;leftIndex ++;if( leftSum >= eachMinSum ){break;}}           var rightIndex = input.length - 1;var rightSum = 0;for( var i = input.length - 1; i > 2; i -- ){var curChar = input.charCodeAt( i );rightSum += curChar;rightIndex --;if( rightSum >= eachMinSum ){break;}}while( leftSum <= eachMaxSum && rightSum <= eachMaxSum && leftIndex < rightIndex ){if( leftSum < rightSum ){var curChar = input.charCodeAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;}if( leftSum > rightSum ){var curChar = input.charCodeAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;}if( leftIndex >= rightIndex ){break;}// 相等的情况var theOtherSum = asciiSum - leftSum - rightSum - input.charCodeAt( leftIndex ) - input.charCodeAt( rightIndex );if( theOtherSum == leftSum ){console.log( leftIndex + "," + rightIndex);return;}// 如果 theOtherSum 不相等,继续var curChar = input.charCodeAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;curChar = input.charCodeAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;          }console.log( "0,0" );
}

(完)

相关文章:

华为OD机考算法题:字符串划分

题目部分 题目字符串划分难度难题目说明给定一个小写字母组成的字符串s&#xff0c;请找出字符串中两个不同位置的字符作为分割点&#xff0c;使得字符串分成的三个连续子串且子串权重相等&#xff0c;注意子串不包含分割点。 若能找到满足条件的两个分割点&#xff0c;请输出…...

AF_UNIX和127.0.0.1(AF_INET)回环地址写数据速度对比(二)

之前写了篇博客&#xff1a;AF_UNIX和127.0.0.1(AF_INET)回环地址写数据速度对比 然后利用的是发送端读取大文件&#xff0c;接收方接收并保存为文件的方式进行测试&#xff0c;结果发现&#xff0c;AF_UNIX并未比127.0.0.1(AF_INET)回环地址优秀&#xff0c;若单次发送的字节数…...

“Python+”集成技术高光谱遥感数据处理与机器学习教程

详情点击公众号链接&#xff1a;“Python”集成技术高光谱遥感数据处理与机器学习教程 第一&#xff1a;高光谱基础 一&#xff1a;高光谱遥感基本概念 01)高光谱遥感 02)光的波长 03)光谱分辨率 04)高光谱遥感的历史和发展 二&#xff1a;高光谱传感器与数据获取 01)高…...

centos7 快速搭建自测mysql环境 docker + mysql

环境准备 centos7快速搭建docker mysql docker镜像源配置 一般都是要配的不然太慢了&#xff0c;docker 1.12以上创建或修改 /etc/docker/daemon.json 文件&#xff0c;修改为如下形式: 地址替换国内源 {"registry-mirrors" : ["https://docker.mirrors.u…...

c++视觉检测-----Canny边缘算子

Canny边缘算子 cv::Canny()是OpenCV库中用于执行Canny边缘检测的函数。Canny边缘检测是一种广泛使用的图像处理技术&#xff0c;用于检测图像中的边缘。 以下是cv::Canny()函数的一般用法和参数&#xff1a; void cv::Canny(cv::InputArray image, // 输入图像&#x…...

机器学习笔记 - 用于动作识别的网络TSN/TSM/SlowFast/R(2+1)D/3D MobileNetV2

一、简述 动作识别是在视频序列中检测和分类人类动作的过程。 近年来,由于其广泛的应用,它已成为一项越来越重要的技术,例如监控、人机交互以及视频索引和检索。 特别是,动作识别对于无人驾驶飞行器 (UAV) 或无人机来说变得至关重要,因为它们越来越多地用于各种应用,例如…...

mybatis批量插入

一、定义DBExec import java.util.List;public abstract class DBExec<T> {public abstract void operate(List<T> list); }二、定义BatchDBService public interface BatchDBService<T> {void exec(int batchSize, List<T> list, DBExec<T> d…...

软件‘小程序‘前台开发软件定制的知识|app网站搭建

软件&#xff0c;小程序&#xff0c;前台开发软件定制的知识 随着互联网的快速发展&#xff0c;软件&#xff0c;小程序&#xff0c;前台开发软件定制已经成为了企业必备的工具。它可以帮助企业更好地管理业务&#xff0c;提高效率&#xff0c;增强用户体验。那么&#xff0c;什…...

HTML-注册页面

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>注册页面</title> </head> <body><from action"#" method"get"><table border"1" align&q…...

17.(开发工具篇Gitlab)如何在Gitlab配置ssh key

前言: Git是分布式的代码管理工具,远程的代码管理是基于SSH的,所以要使用远程的Git则需要SSH的配置 一、git 配置 (1)打开 git 命令窗口 (2)配置用户名(填自己的姓名) git config --global user.name “chenbc” (3)配置用户邮箱(填自己的邮箱) git config …...

ArcGIS/GeoScene脚本:基于粒子群优化的支持向量机分类模型

参数输入 输出 栅格 预测为负类的概率 预测为正类的概率 二值化结果 评估结果 ROC曲线...

Python+Tkinter 图形化界面基础篇:添加图形和图像

PythonTkinter 图形化界面基础篇&#xff1a;添加图形和图像 引言添加图形元素步骤1&#xff1a;导入 Tkinter 步骤2&#xff1a;创建主窗口步骤3&#xff1a;创建 Canvas 步骤4&#xff1a;绘制图形 绘制线条 绘制矩形 绘制椭圆 绘制多边形 步骤5&#xff1a;启动主事件循环 显…...

前端js八股文大全

一、js的数据类型 值类型(基本类型)&#xff1a;数字(Number)、字符串&#xff08;String&#xff09;、布尔(Boolean)、对空&#xff08;Null&#xff09;、未定义&#xff08;Undefined&#xff09;、Symbol,大数值类型(BigInt) 引用数据类型&#xff1a;对象(Object)、数组…...

[环境]Ubuntu20.04安装Ceres

安装这么顺利我有点不适应&#xff0c;记录一下 注意安装的位置与层级关系 参考链接 知乎方案...

ruoyi 若依 前端vue npm install 运行vue前端

首次导入&#xff0c;需要先执行 npm install #进入到前端模块目录下 cd ruoyi-ui # 安装 npm install 启动后端项目 运行前端项目&#xff1a;运行成功后&#xff0c;会浏览器自动加载到前端首页&#xff08;或者 浏览器访问打印的两个地址&#xff09; # 运行 npm run dev 部…...

各大搜索引擎的User-Agent

各大搜索引擎的User-Agent baidu&#xff1a;Mozilla/5.0 (compatible; Baiduspider/2.0; http://www.baidu.com/search/spider.html) Google&#xff1a;Mozilla/5.0 (compatible; Googlebot/2.1; http://www.google.com/bot.html) Sogou&#xff1a;Sogou web spider/4.0(h…...

codesys【按钮】

1用于控制bool信号。 1声明全局变量 2绑定该变量 运行后&#xff0c;按钮就能控制这个bool变量了。 2按钮【自复位】 3按钮【锁位】...

SSH在桌面会话启动应用程序

通过远程SSH会话在实体机&#xff08;物理机&#xff09;的当前登录用户的桌面会话上启动应用程序 1. 找到用户的桌面会话的DISPLAY变量 在大多数情况下&#xff0c;主桌面会话的DISPLAY变量设置为:0&#xff0c;但为了确定&#xff0c;你可以运行以下命令查找活跃的DISPLAY&…...

React的类式组件和函数式组件之间有什么区别?

React 中的类组件和函数组件是两种不同的组件编写方式&#xff0c;它们之间有一些区别。 语法和写法&#xff1a;类组件是使用类的语法进行定义的&#xff0c;它继承自 React.Component 类&#xff0c;并且需要实现 render() 方法来返回组件的 JSX。函数组件是使用函数的语法进…...

codesys【读写轴参数】

在SM3_Basic库内。 作用&#xff1a;读写实轴寄存器参数。【一般用于修改2000h段的值】 或者获取6041h的状态值。 ecat主站操作&#xff1a; 补偿间隙&#xff1a; 追剪&#xff1a; 凸轮&#xff1a; 读写轴参数&#xff1a;...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...