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

系统学习算法:专题十六 字符串

题目一:

算法原理:

其实这道其实就是偏模拟的题,即比较所有字符串,找出相同的字符,最后就是最长公共前缀

其中有两种方法,一种是两两比较,还有一种是统一比较

方法一:两两比较

如上图,两两比较,最后一组比较完就是最长公共前缀

时间复杂度是O(mn),m是字符串长度,n是字符串个数

方法二:统一比较

 

即按照字符串从前往后的顺序,遍历字符,看看该位置的字符是否所有字符串都一样,如果不一样或者有字符串越界了,那么就停止并返回当前位置之前的所有字符,也就是最长公共前缀

代码一(两两比较):

class Solution {public String longestCommonPrefix(String[] strs) {//以第一个字符串作为比较基准String s=strs[0];//两两比较所有字符串for(int i=1;i<strs.length;i++){//更新当前最长公共前缀s=findCommon(s,strs[i]);}//返回最长公共前缀return s;}public String findCommon(String s1,String s2){//最小长度int minLen=Math.min(s1.length(),s2.length());int i=0;//如果没越界且该位置字符相同while(i<minLen&&s1.charAt(i)==s2.charAt(i)){i++;}//返回这两个字符串的最长公共前缀return s1.substring(0,i);}
}

方法二(统一比较):

class Solution {public String longestCommonPrefix(String[] strs) {//以第一个字符串作为基准for(int i=0;i<strs[0].length();i++){//第一个字符串的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];}
}

题目二:

算法原理:

一开始还是暴力解法,那就是枚举出所有的子串,然后判断一下是否是最长回文子串,所以时间复杂度为枚举出所有子串为O(N^2),判断一下是否是最长回文子串O(N),所以综上时间复杂度为O(N^3)

这里采用中心扩展算法,刚好利用了回文字符串的特性,即以当前位置为中心,向左右扩展,此时就可以判断是否为回文字符串,如果不为回文字符串了,就看看需不需要更新结果

细节就是奇数和偶数长度的回文字符串,左右扩展的起始位置不一样

奇数情况很好想

 偶数情况也不难想

 因此需要判断两次,第一次判断以当前位置为中心的奇数长度的回文串,第二次判断以当前位置为中心的偶数长度的回文串

剩下的判断回文串的操作那就很简单了,两两比较,然后移动指针,直到有一方越界

代码:

class Solution {public String longestPalindrome(String s) {//最长回文子串的长度int maxLen=0;//最长回文String ret=new String();//遍历字符串确定中心点for(int i=0;i<s.length();i++){//奇数情况int left=i-1;int right=i+1;while(left>=0&&right<s.length()){if(s.charAt(left)==s.charAt(right)){left--;right++;}else{break;}}if(right-left-1>maxLen){maxLen=right-left-1;ret=s.substring(left+1,right);}//偶数情况left=i;right=i+1;while(left>=0&&right<s.length()){if(s.charAt(left)==s.charAt(right)){left--;right++;}else{break;}}if(right-left-1>maxLen){maxLen=right-left-1;ret=s.substring(left+1,right);}}return ret;}
}

题目三:

算法原理:

其实就是模拟加法,运算方法就是列竖式运算

 

用一个变量t表示两数之和,两数相加后,根据进制来决定除和模的多少,比如二进制, 那么进完位后,剩下的值就是t%2,要进的位就是t/2

如果出现某一位一个有数,一个没数,那么默认没数的为0计算就行

然后这道题又是字符串形式,所以需要采用一些字符串转整数等一系列方法

需要注意的是,计算过程是先算低位再算高位,对应的字符串上,字符串后面的是低位,前面的是高位,所以要从字符串后面往前面遍历

代码:

class Solution {public String addBinary(String a, String b) {//从后往前遍历int cur1=a.length()-1,cur2=b.length()-1;//某一位的两数之和int t=0;//结果StringBuffer ret=new StringBuffer();//当某一个数还没计算完,或者还有进位没有用上while(cur1>=0||cur2>=0||t!=0){//加上aif(cur1>=0){t+=a.charAt(cur1)-'0';cur1--;}//加上bif(cur2>=0){t+=b.charAt(cur2)-'0';cur2--;}//头插ret.insert(0,String.valueOf(t%2));//进位t/=2;}//返回return ret.toString();}
}

题目四:

算法原理:

 第一种方法那就是模拟乘法运算,用列竖式去运算两数乘法

思路很简单,就是代码写起来比较复杂,第一步就是固定其中一个字符串的一个数,然后去遍历另一个字符串的所有数挨个去乘,得到一个数

但是在这里需要注意,比如上图615可不是真的就615,而是6150,492也是49200,要进行补零的,解决办法就是将两数的字符串逆序,这样下标就反过来了

这时6在下标为0的位置,所以6乘完得到的738要补0个零

5在下标为1的位置,所以5乘完得到的615要补1个零

4在下标为2的位置,所以4乘完得到的492要补2个零

最后再将得到的这些数又进行相加的操作

相加完还要处理一下前导零的情况,总之细节很多,难度比较大

解法二:

是对解法一的优化,解法一是每算完一步都进位,也就是我们现实用的方法

解法二是无进位相乘然后相加,最后处理进位

 然后还需要知道的是,m位数*n位数=(m+n-1)位数

因此我们就可以用int数组来接收每一位的未进位的数,至于如何一一对应存放顺序,则还是先将两个字符串逆序,将下标反过来

则6*3=18时,3在下标0位,6在下标0位,0+0=0,所以18放在数组下标0位

6*2=12时,2在下标1位,6在下标0位,1+0=0,所以12放在数组下标1位

6*1=6时,1在下标2位,6在下标0位,2+0=0,所以6放在数组下标2位

如此类推,全部加到数组后,数组里存的就是:4  13  28  27  18

然后再处理进位,那就模拟与0相加即可

最后再处理一下前导零的问题

思路基本是想不出来的,就看知不知道了,知道这种思路的话,那代码就很好写了

解法二这种就属于思路难,代码简单,解法一则是思路简单,代码难

代码(解法二):

class Solution {public String multiply(String num1, String num2) {//初始化,将两个字符串翻转int l1=num1.length(),l2=num2.length();char[] n1=new StringBuffer(num1).reverse().toString().toCharArray();char[] n2=new StringBuffer(num2).reverse().toString().toCharArray();//m位数*n位数=(m+n-1)位数int[] tmp=new int[l1+l2-1];//固定其中一个字符串的一个数,与另一个字符串的所有数相乘,放在数组i+j位上for(int i=0;i<l1;i++){for(int j=0;j<l2;j++){tmp[i+j]+=(n1[i]-'0')*(n2[j]-'0');}}//加法进位int cur=0,t=0;StringBuffer ret=new StringBuffer();while(cur<tmp.length||t!=0){if(cur<tmp.length){t+=tmp[cur];cur++;}ret.insert(0,String.valueOf(t%10));t/=10;       }//处理前导零问题cur=0;while(ret.length()>1&&ret.charAt(cur)=='0'){ret.deleteCharAt(cur);}//返回return ret.toString();}
}

总结:

 字符串的题也基本就是模拟以及各种算法的杂糅,主要要掌握一些常见的Java自带的字符串封装好的方法

http://www.lryc.cn/news/608773.html

相关文章:

  • 第三章-提示词-高级:开启智能交互新境界(13/36)
  • 日常--详细介绍qt Designer常用快捷键(详细图文)
  • 【QT】概述
  • 高质量数据集|建设三大难点
  • 01.MySQL 安装
  • 服务器中切换盘的操作指南
  • Android 之 MVVM架构
  • 使用 Docker 部署 Golang 程序
  • 第四章:OSPF 协议
  • Dify中自定义工具类的类型
  • WebMvc自动配置流程讲解
  • MySQL 索引失效的场景与原因
  • 嵌入式开发学习———Linux环境下IO进程线程学习(二)
  • 04.Redis 的多实例
  • 笔试——Day27
  • 前端面试手撕题目全解析
  • 【数据迁移】Windows11 下将 Ubuntu 从 C 盘迁移到 D 盘
  • Redis——常用指令汇总指南(三)(哈希类型)
  • Odoo OWL前端框架全面学习指南 (后端开发者视角)
  • 三角洲行动ACE反作弊VT-d报错?CPU虚拟化如何开启!
  • GitOps:云原生时代的革命性基础设施管理范式
  • Ubuntu20.04 Carla安装与和Ros联合仿真
  • Ubuntu22.4部署大模型前置安装
  • AI + 云原生:正在引爆下一代应用的技术革命
  • LabVIEW小波变换检测信号断点
  • HCIP笔记(第四章)
  • 悬挂的绳子,它的函数方程是什么样子的?
  • Python Dash 全面讲解
  • 大屏项目展示
  • 基于Springboot+UniApp+Ai实现模拟面试小工具八:管理端基础功能实现