算法——字符串

在这里插入图片描述

T04BF

👋热门专栏: 算法|JAVA|MySQL|C语言

🫵 小比特 大梦想

此篇文章与大家分享字符串相关算法
如果有不足的或者错误的请您指出!

目录

  • 1.最长公共前缀
    • 1.1解析
    • 1.2题解
  • 2.最长回文子串
    • 2.1解析
    • 2.2题解
  • 3.二级制求和
    • 3.1解析
    • 3.2题解
  • 4.字符串相乘
    • 4.1解析
    • 4.2题解

1.最长公共前缀

题目:最长公共前缀

1.1解析

有两种比较方式,一种是两个两个比较,比较得出的最长公共前缀再和另一个比较;另一种就是统一比较,每次都比较所有字符串相同下标的字符,直到遇到不相同的字符或者某一串字符串已经遍历完了
本文采用的是第二种方法

1.2题解

class Solution {
    public static String longestCommonPrefix(String[] strs) {
        for(int i = 0; i < strs[0].length(); i++){
            char ch = strs[0].charAt(i);//以第一串字符串为标准
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length() || ch != strs[j].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];//说明此时第一串字符就是最长公共前缀
    }
}

2.最长回文子串

题目:最长回文子串

2.1解析

我们最容易想到的就是暴力解法,即对每一个子串都进行判断,但是时间复杂度来到了O(n^3)
但是实际上我们可以通过"回文字符串"的特点来进行判断
在这里插入图片描述
如图所示,我们用i来遍历字符串,同时定义left和right变量,left往左走,right变量往后走,每次都判断left下标的字符和right下标的字符是否相等,如果不相等或者left/right超过边界条件,那么此时left 和 right 就是以i下标字符为中心的最长回文字符串
但是实际上这只是考虑奇数个数字符的字符串,因此我们找完奇数情况后还要找偶数情况
在这里插入图片描述
如图所示,我们可以让left = i,right = i+1,按照上面的方法去寻找即可

此时时间复杂度降为O(n^2)

2.2题解

class Solution {
    public String longestPalindrome(String s) {
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int l = i;
            int r = i;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }
            if(right - left < r - l){
                right = r;
                left = l;
            }
            l = i;
            r = i+1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }
            if(right - left < r - l){
                right = r;
                left = l;
            }
        }
        return s.substring(left+1,right);
    }
}

3.二级制求和

题目:二级制求和

3.1解析

实际上无论是二进制、十进制还是其他进制相加,我们只要模拟出来我们常用的两数相加的过程就好了
在这里插入图片描述
对于二进制就是满2就进位,我们只需要在下一次计算的时候将上一次的进位加上就好了
思路比较简单,我们直接通过代码体现

3.2题解

class Solution {
    public String addBinary(String a, String b) {
        int len1 = a.length();
        int len2 = b.length();
        int cur1 = len1-1;
        int cur2 = len2-1;
        int tmp = 0;
        StringBuilder ret = new StringBuilder();
        while(cur1 >= 0 || cur2 >= 0 || tmp != 0){
            if(cur1 >= 0){
                tmp += a.charAt(cur1) - '0';
                cur1--;
            }
            if(cur2 >= 0){
                tmp += b.charAt(cur2) - '0';
                cur2--;
            }
            ret.append(tmp % 2);
            tmp /= 2;
        }
        return ret.reverse().toString();
    }
}

4.字符串相乘

题目:字符串相乘

4.1解析

我们还是模拟我们现实中来两数相乘的计算方式
在这里插入图片描述
思路比较简单,但是这种解法细节还是很多的
(1)高位相乘的时候要补上0
即我们最后进行相加的时候,不是738和615相加,而是738和6150相加
(2)处理前导0
假设题目给我们是
在这里插入图片描述
但是我们只要的是一个0即可,我们就要处理前面的0
(3)字符串的顺序
对于这种大数的四则运算题目,我们最好都是将字符串先逆置过来,即将个位数放在下标为0的位置,这样我们每次进行计算的时候就直接从下标为1的位置开始计算,最后再将答案逆置即可

而第二种解法实际上是对第一种解法的优化
我们的处理策略是先不考虑进位,直接"无进位相乘"后,得到的结果再考虑进位
在这里插入图片描述
此时得到的答案和我们上面是完全一样的
但是这种方法给我们带来的很大的便利
首先我们每次相乘得到数应该存放到以一个数组里,即上面的6 12 18这些数字,假设我们的数组是tmp
而tmp数组的长度最大也就是m+n-1
在这里插入图片描述
那么我们会发现,实际上当下标为i的字符和下标为j的字符相乘后,得到的数字是放在 tmp 数组的 [i+j]下标位置的
这样一来我们就不再需要进行什么高位补0的操作了
同时,我们最后将每次相乘得到的数字进行相加的操作,无非就是tmp数组每次累加即可

4.2题解

class Solution {
    public String multiply(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        int[] tmp = new int[n1+n2-1];
        num1 = new StringBuilder(num1).reverse().toString();//原字符串逆置
        num2 = new StringBuilder(num2).reverse().toString();
        for(int i = 0; i < n1; i++){
            for(int j = 0; j < n2; j++){
                tmp[i+j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        int k = 0;
        int t = 0;
        StringBuilder ret = new StringBuilder();
        //进位
        while(k < tmp.length || t != 0){
            if(k < tmp.length){
                t += tmp[k++];
            }
            ret.append(t % 10);
            t /= 10;
        }
        
        ret.reverse();
        //处理前导0
        k = 0;
        while(k < ret.length()-1 && ret.charAt(k) == '0'){
            k++;
        }
        return ret.substring(k);
    }
}
感谢您的访问!!期待您的关注!!!

在这里插入图片描述

T04BF

🫵 小比特 大梦想

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【环境变量】常见的环境变量 | 相关指令 | 环境变量系统程序的结合理解 | 环境变量表 | 本地变量环境变量 | 外部命令内建命令

目录 常见的环境变量 HOME PWD SHELL HISTSIZE 环境变量相关的指令 echo&env export unset 本地变量 环境变量整体理解 程序现象_代码查看环境变量 ​整体理解 环境变量表 环境变量表的传递 环境变量表的查看 内建命令 少说废话&#x1f197; 每个用…

大型网站系统架构演化

大型网站质量属性优先级&#xff1a;高性能 高可用 可维护 应变 安全 一、单体架构 应用程序&#xff0c;数据库&#xff0c;文件等所有资源都在一台服务器上。 二、垂直架构 应用和数据分离&#xff0c;使用三台服务器&#xff1a;应用服务器、文件服务器、数据服务器 应用服…

JavaEE 初阶篇-深入了解 CAS 机制与12种锁的特征(如乐观锁和悲观锁、轻量级锁与重量级锁、自旋锁与挂起等待锁、可重入锁与不可重入锁等等)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 乐观锁与悲观锁概述 1.1 悲观锁&#xff08;Pessimistic Locking&#xff09; 1.2 乐观锁&#xff08;Optimistic Locking&#xff09; 1.3 区别与适用场景 2.0 轻…

我企业的业务需要制作企业网站吗?11个支持的理由以及5个反对的理由!

如果你的企业经营得还不错&#xff0c;你可能会找出很多理由&#xff0c;说明为什么一个高效的网站对你来说并不那么重要。确实&#xff0c;你明白企业需要在互联网上有一定的存在感&#xff0c;但你可能并不认为一个高效的网站会对你的特定业务产生太大的影响——尤其是当你已…

实战纪实 | 编辑器漏洞之Ueditor-任意文件上传漏洞 (老洞新谈)

UEditor 任意文件上传漏洞 前言 前段时间在做某政府单位的项目的时候发现存在该漏洞&#xff0c;虽然是一个老洞&#xff0c;但这也是容易被忽视&#xff0c;且能快速拿到shell的漏洞&#xff0c;在利用方式上有一些不一样的心得&#xff0c;希望能帮助到一些还不太了解的小伙…

PCIe总线-存储器域和PCIe总线域访问流程(二)

1.概述 PCIe总线的最大特点是像CPU访问DDR一样&#xff0c;可以直接使用地址访问PCIe设备&#xff08;桥&#xff09;&#xff0c;但不同的是DDR和CPU同属于存储器域&#xff0c;而CPU和PCIe设备属于两个不同的域&#xff0c;PCIe设备&#xff08;桥&#xff09;的地址空间属于…

[RK3399 Linux] 使用busybox 1.36.1制作rootfs

一、 编译、安装、配置 busybox 1.1 下载源码 根文件系统是根据busybox来制作的。 下载地址:https://busybox.net/downloads/。 这里就以1.36.1版本为例进行编译安装介绍: 注意:编译linux内核与文件系统中的所有程序要使用相同的交叉编译器。 下载完成后解压: mkdir …

03 SQL基础 -- 查询与运算符

一、SELECT 语句基础 1.1 从表中选取数据 SELECT 语句 从表中选取数据时需要使用SELECT语句,也就是只从表中选出(SELECT)必要数据的意思。通过SELECT语句查询并选取出必要数据的过程称为匹配查询或查询(query) 基本SELECT语句包含了SELECT和FROM两个子句(clause)。示…

NAT实验

要求&#xff1a; 1、AR2为ISP路由器&#xff0c;其上只能配置IP地址&#xff0c;不得再进行其他的任何配置 2、PC1-PC2可以ping通客户平板和DNS服务器&#xff1b; 3、客户端可以通过域名访问http1&#xff0c;通过地址访问http2 4、R1为边界路由器&#xff0c;其上只有一…

计算机视觉工程师

为进一步贯彻落实中共中央印发《关于深化人才发展体制机制改革的意见》和国务院印发《关于“十四五”数字经济发展规划》等有关工作的部署要求&#xff0c;深入实施人才强国战略和创新驱动发展战略&#xff0c;加强全国数字化人才队伍建设&#xff0c;持续推进人工智能从业人员…

【深度学习】深度学习md笔记总结第4篇:TensorFlow介绍,学习目标【附代码文档】

深度学习笔记完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;深度学习课程&#xff0c;深度学习介绍要求,目标,学习目标,1.1.1 区别,学习目标,学习目标。TensorFlow介绍&#xff0c;2.4 张量学习目标,2.4.1 张量(Tensor),2.4.2 创建张量的指令,2.4.3 张量…

C语言世界上最详细自定义类型:联合和枚举

前言&#xff1a; hello! 大家好&#xff0c;我是小陈&#xff0c;今天给大家带来一篇联合和枚举的博客&#xff01;&#xff01;&#xff01; 1.联合体类型的声明 像结构体⼀样&#xff0c;联合体也是由⼀个或者多个成员构成&#xff0c;这些成员可以不同的类型。 但是编译…

安装达梦(DM8)数据库(图形化安装)

一、配置DM8数据库系统环境 在CentOS7系统环境安装DM8&#xff08;达梦&#xff09;数据库前的准备。&#xff08;注意&#xff1a;安装前必须创建 dmdba 用户&#xff0c;禁止使用 root 用户安装数据库。&#xff09; 1、新建用户 运行SecureCRT工具&#xff0c;root登录16…

域控软件安全隔离关键技术剖析:MCU域 VS SOC域

安全隔离的需求 功能安全开发中&#xff0c;软件阶段由软件V模型左边的软件安全需求SSR开始。SSR是从技术安全需求TSR中提取出软件的功能安全需求&#xff0c;大多数情况下具有不同的ASIL等级。 图1 功能安全软件开发V模型 随后&#xff0c;软件安全需求会被分配到软件架构中的…

利用SARscape对日本填海造陆和天然气开采进行地表形变监测

日本千叶市&#xff0c;是日本南部重要的工业港市。位于西部的浦安市是一个典型的"填海造田"城市&#xff0c;东南部的东金区有一片天然气开采区域&#xff0c;本文利用SARscape&#xff0c;用干涉叠加的方法&#xff0c;即PS和SBAS&#xff0c;对这两个区域进行地表…

36-代码测试(上):如何编写Go语言单元测试和性能测试用例?

每种语言通常都有自己的测试包/模块&#xff0c;Go语言也不例外。在Go中&#xff0c;我们可以通过testing包对代码进行单元测试和性能测试。 如何测试 Go 代码&#xff1f; Go语言有自带的测试框架testing&#xff0c;可以用来实现单元测试&#xff08;T类型&#xff09;和性…

Point-Nerf复现及解析

Point-Nerf复现及解析 鸣谢&#xff1a;同组的李xx师兄博士(交流思路)、辰昶仪器的狗哥等人&#xff08;帮忙down资源&#xff09; 0.0我自己的复现工程0.1相关库介绍0.1.1 pytorch0.1.2 h5py0.1.3 Scikit-Image0.1.4 imageio0.1.5 scipy0.1.6 Matplotlib0.1.7 fonttools 0.2…

JAVA的学习日记DAY6

文章目录 数组例子数组的使用数组的注意事项和细节练习数组赋值机制数组拷贝数组反转数组添加 排序冒泡排序 查找多维数组 - 二维数组二维数组的使用二维数组的遍历杨辉三角二维数组的使用细节和注意事项练习 开始每日一更&#xff01;得加快速度了&#xff01; 数组 数组可以…

16. 网络编程(1)

Hi,大家好!从本节开始我们学习网络编程相关的知识。基于TCP服务器和客户端实现流程框架。 本节目录: 网络编程在软件开发中具有相当重要的作用,涉及到各方各面: 网络通信: Linux系统作为一个多用户、多任务的操作系统,网络通信是其重要的功能之一。通过网络编程,可以实现…

稀碎从零算法笔记Day46-LeetCode:互质树

这几天有点懈怠了 题型&#xff1a;树、DFS、BSF、数学 链接&#xff1a;1766. 互质树 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 给你一个 n 个节点的树&#xff08;也就是一个无环连通无向图&#xff09;&#xff0c;节点编号从 0 到 …