【刷题15】字符串专题

目录

  • 一、字符串相加
  • 二、最长公共前缀
  • 三、最长回文子串
  • 四、二进制求和
  • 五、字符串相乘

一、字符串相加

题目:
在这里插入图片描述

思路:

  • 字符串中的每一位的字符转换为数字后要相加,相加的必须是同一位的,即个位加个位,十位加十位。所以要倒着来实现。这里end1和end2直接就是最后一个字符的下标了
  • 两个数相加要考虑进位,用一个变量next来表示进位,进位是给下一位相加时用的,比如个位加个位有进位(0就算了),就给十位加十位用,所以next变量不能写在循环里面
  • 循环条件和字符转换数字。while循环是end1和end2大于等于0,满足一个即可在循环里面。这里我们要结合具体的代码,如果是&&,不是||,那么肯定有一个越界(字符串个数相同另说),这时又要写while循环去处理剩余那个还没越界的有点麻烦且冗余,所以都在一个循环里面处理。问题来了,假如end1越界了,end2没有,根据前面的循环条件还是能进入循环的,但是取字符转化为数字不就可能越界了吗?所以这里有一个平衡的方法,先表示当前位的数字val1和val2等于0,记住,此时它们是0,后面不管有没有参与都不影响。然后重点是:接下来用if语句判断end1是否越界,end2也要判断,没有越界val1 才等于 当前位字符转换为数字,val2同理。到后面用时,不管是val1和val2都有值,还是一个有一个没有,都不影响后面的操作,因为没有值的那个是0
  • 变量sum,同位的两个数相加(val1+val2),同时还要加上上一次的进位next,第一次进来next是0,到下一次加时,next可能有进位,就按照sum=val1+val2+next的操作就行了。sum得到前面变量相加的结果后,要给下一次的相加准备进位的数,next = sum/10(其实next要么为0要么为1,后面再看),然后sum %= 10,保证当前的位是个位的那个数(sum是12,取的是2,1给next进位了),返回值字符串ret += sum 转换字符
  • next的处理。end1和end2都结束了,进位变量next可能没有处理干净,这里说的处理干净指的是next可能是1,如果是1,说明有进位,但是下一位没有元素了怎么办,根据竖加法图,要进行的操作是给下一位补1,那么next有没有可能是其他数字呢?(0就算了,说明整个过程已经处理干净,没有多余的数)不会有其他的数字,只能等于0或者1,因为ret最大的结果是19,同位相加9+9加上上一次的进位next=1,得到19,所以next那么为1那么为0,0就不处理了,1就进入该判断,然后补1
  • 逆置,返回字符串

在这里插入图片描述

代码:

class Solution {
public:string addStrings(string num1, string num2) {string ret;int next = 0;// 进位int end1 = num1.size()-1, end2 = num2.size()-1;while(end1 >= 0 || end2 >= 0){int val1 = 0;int val2 = 0;if(end1 >= 0) val1 = num1[end1--]-'0';if(end2 >= 0) val2 = num2[end2--]-'0';int sum = val1 + val2 + next;next = sum / 10;sum %= 10;ret += sum + '0';}if(next == 1){ret += "1";}reverse(ret.begin(), ret.end());return ret;}
};

二、最长公共前缀

题目:
在这里插入图片描述
思路:

  • set去重,数量大于1说明有不同,跳出结束
  • 数组中每个字符串的同一个位置的字符都要遍历一遍,有一个为空跳出循环结束

在这里插入图片描述

代码:

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.size() == 0) return "";string ret;int n = strs.size();for(int i=0; ; i++){string tmp;int flag = 0;for(int j=0; j<n; j++){char k = strs[j][i];if(!k) {flag = 1;break;}tmp += k;}if(flag == 1) break;set<char> se(tmp.begin(), tmp.end()); if(se.size() > 1) break;auto it = se.begin();ret += (*it);}return ret;}
};

三、最长回文子串

题目:
在这里插入图片描述
思路:中心扩展法
在这里插入图片描述
相同就+=2,不相同就跳出循环。返回两个函数,得到返回值的较大值

代码:

class Solution {
public:// 奇数 string func1(const string& str, int pos){int p1 = pos-1, p2 = pos+1, len = 1;while(p1 >= 0 && p2 < str.size()){if(str[p1] == str[p2]) len += 2;else break;p1--;p2++;}string ret = str.substr(p1+1, len);return ret;}// 偶数string func2(const string& str, int pos){int p1 = pos, p2 = pos+1, len = 0;while(p1 >= 0 && p2 < str.size()){if(str[p1] == str[p2]) len += 2;else break;p1--;p2++;}string ret = str.substr(p1+1, len);return ret;}string longestPalindrome(string s) {string ret;for(int i=0; i<s.size(); i++){string s1 = func1(s, i);string s2 = func2(s, i);string tmp = s1.size()>s2.size() ? s1 : s2;if(tmp.size() > ret.size()) ret = tmp;}return ret;}
};

四、二进制求和

题目:
在这里插入图片描述
思路:模拟二进制相加的过程(注意考虑进位)

代码:

class Solution {
public:string addBinary(string a, string b) {int end1 = a.size()-1, end2 = b.size()-1;int next = 0;string ret;while(end1 >= 0 || end2 >= 0){int val1 = 0, val2 = 0;if(end1 >= 0) val1 = a[end1--]-'0';if(end2 >= 0) val2 = b[end2--]-'0';int sum = val1+val2+next;if(sum > 2){ret += "1";next = 1;}else if(sum == 2){ret += "0";next = 1;}else if(sum == 1) {ret += "1";next = 0;}else {ret += "0";next = 0;}}if(next == 1) ret += "1";reverse(ret.begin(), ret.end());return ret;}
};

五、字符串相乘

题目:
在这里插入图片描述
思路:

  • 两个字符串转化为数字后相乘,先定义一个返回值字符串ret,给它开的大小是两个字符串的长度之和,并且每个位置初始化为字符0;为什么要开空间大小?因为要给每个位置初始化为字符0,这是重点之一,后面要用到这些字符0。为什么开的空间大小是两个字符串的长度之和?直接上栗子,两位数X两位数,数字分别是是11和22时,得到的结果是242,长度是3;数字分别是是99X99时,得到的结果是9801,长度是4;也就是说,两位数乘以两位数,结果的最大的长度是两个字符串的和,即使是长度为3的,前面先占一个字符0,后面再讨论怎么处理。
  • 用两层for循环。为什么是两层for循环?因为与加法不同,乘法:一个的数某位遍历乘完另一个数的每一位后,它的下一位还要进行同样的操作,所以要用两层for。for循环也是倒着实现的,即从最后一位数字开始累乘起来
  • 变量sum,当前位取模操作、进位操作。sum是当前两个数的某位相乘的结果,但确定就是这样吗?不是的,还要加上进位。但是注意注意,这里的进位与加法那里不同,加法那里是用一个变量来表示进位的值的,而乘法这里是根据字符串数组的位置的元素来表示进位的多少。sum的公式代码:int sum = (s[i]-‘0’) * (t[j]-‘0’) + (ret[i+j+1]-‘0’); 这里的 ret[i+j+1]-'0’的值就是进位的数字。为什么是方括号里面的下标表示是i+j+1?因为刚开始时,i等于n-1,表示在第一个字符串的最后一个位置,j等于m-1,表示在第二个字符串的最后一个位置,前面说过,ret的长度是两个字符串的长度之和,那么ret的最后一个位置是n+m-1,i+j=n+m-2,所以i+j+1就得到ret的最后一个位置(刚开始时),随着j–和i–,位置就会发生变化,取的位置的值也就不一样了。当前位是要取模的,因为只能填sum的个位数字,取模公式:ret[i+j+1] = sum%10 + ‘0’; ret[i+j+1]就是当前要填的位置。进位操作:重!! 进位公式:ret[i+j] += sum/10; 当前位是i+j+1,进位到下一位是i+j,随着j–和i–是一样的(倒着)。有没有发现与取模不同,进位是+=,取模是赋值,因为取模最终就是要模后的结果,而进位的+=代表前面已经有元素,还要加上它才行,具体看下图的分析过程(ret的某个位置的类型是字符类型,数字+字符0=该数字字符;+=的话,字符0的用处来了(其一)因为前面初始化时已经给字符0了,假如之前的操作或者说是刚开始,那么i+j的位置是字符0,字符0加上除等后的数字得到该数字字符,如果已经是数字字符的话,加上除等后的数字,得到的是数字字符的数字加上该数字的和———【字符0+数字=数字字符】+数字 = 数字字符)。【还有字符0的用处(其二),在sum的公式里刚开始i+j+1就是字符0,所以减去字符0得到数字0,如果前面没有初始化为字符0的话,可能会是乱码】
  • 图——进位理解——模拟下整个过程!
    在这里插入图片描述
    最后用循环的方式截取字符串返回。字符0用处(其三),字符串ret可能被占满,也可能前面的位置有字符0没有被覆盖,但不管是哪种情况,用for遍历,只要遇到不是字符0的元素,说明在这个位置及其后面的位置都是要返回的字符串(前面的字符0是多余,要的就是后面不是字符0开头的)只要遇到不是字符0,就截取后面全部的字符串,然后返回;即使只有一个也返回;如果连一个都没有,说明都是字符0,返回字符串0。(中间有字符0呢?中间有就有呗,2乘5=10,要返回10,难道后面的0不要了?)

代码:

class Solution {
public:string multiply(string num1, string num2) {int n = num1.size();int m = num2.size();string ret(n+m, '0');for(int i = n-1; i>=0; i--){for(int j=m-1; j>=0; j--){int sum = (num1[i]-'0') * (num2[j]-'0') + (ret[i+j+1]-'0');ret[i+j+1] = sum % 10 + '0';ret[i+j] += sum / 10; }}for(int i=0; i<m+n; i++){if(ret[i] != '0'){return ret.substr(i);}}return "0";}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/2098.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

企业数据安全举报投诉如何有效处理?

相关制度、流程图等获取请联系作者&#xff01;&#xff01; 在当今数字化和信息化的浪潮中&#xff0c;企业数据安全问题越来越受到重视&#xff0c;而对于数据安全的举报和投诉处理是保障企业数据安全、提升用户信任度的重要手段之一。一个完善的举报投诉处理机制能够有效应对…

[综述笔记]Deep learning for brain disorder diagnosis based on fMRI images

论文网址&#xff1a;Deep learning for brain disorder diagnosis based on fMRI images - ScienceDirect 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向…

论文提交步骤 | 2024年第五届MathorCup大数据竞赛

2024年第五届MathorCup数学应用挑战赛—大数据竞赛于2024年10月25日下午6点正式开赛。 论文和承诺书、支撑材料&#xff08;可选&#xff09;及计算结果文档由各参赛队队长电脑登录下方报名主页提交&#xff1a; https://www.saikr.com/vse/bigdata2024 初赛作品提交截止时间为…

[sa-token]StpUtil.getLoginId

闲聊 一般情况下&#xff0c;我们想用uid&#xff0c;可能需要前端将uid传过来&#xff0c;或者将token传来&#xff0c;然后我们进行识别。 用了sa-token之后&#xff0c;可以使用StpUtil.getLoginId()方法获取当前会话的用户id 代码展示 例如以下代码&#xff1a; public Res…

双向 Type-C 转 DP 线:高清视频输出的灵活解决方案

在当今数字化生活中&#xff0c;人们对高效能和高清晰度的需求日益增长。双向 Type-C 转 DP 线应运而生&#xff0c;它以其灵活便捷的特点&#xff0c;为用户提供了一种高清视频输出的解决方案。本文将详细介绍双向 Type-C 转 DP 线的技术原理、适用设备、性能参数以及市场选择…

一键式配置适合 Web 开发的Ubuntu系统

大家好&#xff0c;今天给大家分享一个专为Ubuntu设计的Web开发者配置方案Omakub。 项目介绍 Omakub是一个为开发者打造的、经过精心配置的 Ubuntu 环境项目&#xff0c;由 Ruby on Rails 的创造者 David Heinemeier Hansson&#xff08;DHH&#xff09;发起。目的是为了简化他…

使用WebStorm开发Vue3项目

记录一下使用WebStorm开发Vu3项目时的配置 现在WebStorm可以个人免费使用啦&#xff01;&#x1f929; 基本配置 打包工具&#xff1a;Vite 前端框架&#xff1a;ElementPlus 开发语言&#xff1a;Vue3、TypeScript、Sass 代码检查&#xff1a;ESLint、Prettier IDE&#xf…

【OpenGL】vs中glsl高亮显示插件

vs中glsl高亮显示插件 扩展搜索glsl安装

谷歌CEO劈柴吹了个牛,被自家员工“反诈”

Google的CEO Sundar Pichai&#xff0c;可以说是渲染“AI取代人类”的恐慌氛围的帮凶之一了。 谷歌大部分部门都启用了“AI人力”的策略&#xff0c;进行大规模裁员。与一年前相比&#xff0c;现在谷歌的员工整体数量减少了1112人。 甚至&#xff0c;在最新的公司财报电话会议…

一文了解什么是NLP(自然语言处理)

文章目录 简介NLP 的应用NLP 的工作原理步骤1&#xff1a;文本预处理步骤2&#xff1a;文本表示步骤3&#xff1a;分析和建模 结语主要参考 简介 自然语言处理&#xff08;NLP&#xff09;是一种专业分析人类语言的人工智能。&#xff08;下文皆简称为“NLP”&#xff09;&…

一个基于Zookeeper+Dubbo3+SpringBoot3的完整微服务调用程序示例代码

一、关于 Dubbo3 的一些优化改进介绍 Dubbo3 的官方文档地址&#xff1a; https://cn.dubbo.apache.org/zh-cn/overview/what/overview/ 其针对一些问题进行了优化和改变。个人整理3个小的方面&#xff1a; 1. 在服务注册方面使用 DubboService 注解&#xff0c;不再使用 Servi…

群控系统服务端开发模式-应用开发-上传配置功能开发

下面直接进入上传配置功能开发&#xff0c;废话不多说。 一、创建表 1、语句 CREATE TABLE cluster_control.nc_param_upload (id int(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 编号,upload_type tinyint(1) UNSIGNED NOT NULL COMMENT 上传类型 1&#xff1a;本站 2&a…

一:时序数据库-Influx应用

目录 0、版本号 1、登录页面 2、账号基本信息 3、数据库案例 4、可视化 5、java案例 0、版本号 InfluxDB v2.4.0 1、登录页面 http://127.0.0.1:8086/signin 账号&#xff1a;自己账号 密码&#xff1a;自己密码 2、账号基本信息 查看用户id和组织id&#xff01;&…

Linux高阶——1027—进程间关系相关

本章节介绍&#xff0c;进程间的各种关系&#xff1a;亲缘关系&#xff0c;终端进程&#xff0c;进程组&#xff0c;会话&#xff0c;孤儿进程&#xff0c;守护进程 1、亲缘关系 Linux或unix操作系统&#xff0c;进程间具备亲缘关系&#xff0c;分为强亲缘与弱亲缘 强亲缘&a…

leetcode动态规划(二十三)-打家劫舍III

题目 337.打家劫舍III 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口&#xff0c;我们称之为 root 。 除了 root 之外&#xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后&#xff0c;聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树…

(七)Python运算符和优先级

一、算数运算符 算数运算符&#xff0c;如下表所示&#xff1a; x1 y2 z3 # 加法运算 axy print(a,a) # 减法运算 by-x print(b,b) # 乘法运算 cy*z print(c,c) # 除法运算 dz/y print(d,d) # 取模运算 ez%y print(e,e) # 幂运算 fy**z print(f,f) 输出结果&#xff1a; 二…

echarts地图,柱状图,折线图实战

1.地图 <template><div style"height: 100%;" class"cantainerBox"><div class"top"><div class"leftTop"><span class"firstSpan">推广进度</span><div>省份选择&#xff1a;&l…

JAVA语言多态和动态语言实现原理

JAVA语言多态和动态语言实现原理 前言invoke指令invokestaticinvokespecialinvokevirtualinvokeintefaceinvokedynamicLambda 总结 前言 我们编码java文件&#xff0c;javac编译class文件&#xff0c;java运行class&#xff0c;JVM执行main方法&#xff0c;加载链接初始化对应…

技术星河中的璀璨灯塔 —— 青云交的非凡成长之路

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

Chromium127编译指南 Linux篇 - 额外环境配置(五)

引言 在成功获取 Chromium 源代码后&#xff0c;接下来我们需要配置适当的编译环境&#xff0c;以便顺利完成开发工作。本文将详细介绍如何设置 Python 和相关的开发工具&#xff0c;以确保编译过程无碍进行。这些配置步骤是开发 Chromium 的必要准备&#xff0c;确保环境设置…