leetcode算法题解(Java版)-2-最长回文子串
一、int数字反转
题目描述
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
思路:
- 题目很简单,需要注意的是:int型是32位的。1000000003 反转后就超了!所以需要包装类Integer中的最大值和最小值
- 小技巧:为了实现反转,可以先把符号保存到flag中。
代码:
public class Solution { public int reverse(int x) { int res=0; int flag=x>0?1:-1; x=x*flag; while(x>0){ res=10*res+x%10; x/=10; } res=res*flag; if(res>Integer.MAX_VALUE){ res=Integer.MAX_VALUE; } if(res<Integer.MIN_VALUE){ res=Integer.MIN_VALUE; } return (int)res; } }
二、简单模拟、StringBuffer类
题目描述
The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line:"PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3)should return"PAHNAPLSIIGYIR".
思路:
- 这题考到了StringBuffer类,虽然是将原字符“Z“字型排开,然后按每行输出得到结果。观察发现:从上到下(0~nRows),然后再从下到上(nRows-2~0),依次把字符添加到每行对应的sb后面。最后再按行输出就行。
- 语法点:
sb.append(char c);sb.toString();sb.length;s.charAt(int index);s.length();
代码:
public class Solution { public String convert(String s, int nRows) { if(s==null||s.length()<=0||nRows<=1){ return s; } StringBuffer [] sb=new StringBuffer[nRows]; for(int i=0;i<nRows;i++){ sb[i]=new StringBuffer(); } int len=s.length(); int tot=0; while(tot<len){ for(int i=0;i<nRows&&tot<len;i++){ sb[i].append(s.charAt(tot++)); } for(int j=nRows-2;j>0&&tot<len;j--){ sb[j].append(s.charAt(tot++)); } } for(int i=1;i<nRows;i++){ sb[0].append(sb[i]); } return sb[0].toString(); } }
三、最长回文子串
题目描述
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
思路
- 中间扩散法:因为回文串是中心对称的。不妨找到回文串的中心,往两边扩散来看是否符合回文串定义。奇数:一个中心字符;偶数:两个中心字符
- dp大法:设置一个dp状态数组,dp(i,j)=true如果子串i~j是回文串,那么子串i-1~j+1是不是回文串跟i~j有关,所以可以用dp。状态转移方程:dp(i,j)=(s[i]==s[j]&&dp(i+1,j-1))
代码:
中间扩散:
public class Solution { public String longestPalindrome(String s) { if(s==null||s.length()<=1){ return s; } int len=s.length(); int beg=0; int ans=0; //odd for(int i=1;i<len;i++){ int m=i-1; int n=i+1; while(m>=0&&n<len&&s.charAt(m)==s.charAt(n)){ if(n-m+1>ans){ ans=n-m+1; beg=m; } m--; n++; } } //even for(int i=0;i<len;i++){ int m=i; int n=i+1; while(m>=0&&n<len&&s.charAt(m)==s.charAt(n)){ if(n-m+1>ans){ ans=n-m+1; beg=m; } m--; n++; } } if(beg==0&&ans==1){ return s.charAt(0)+""; } return s.substring(beg,beg+ans); } }
dp大法:
public class Solution { public String longestPalindrome(String s) { int len=s.length(); if(len<2||s==null){ return s; } boolean [][] dp=new boolean [len][len]; int maxlen=0; int beg=0; for(int i=0;i<len;i++){//dp解题,初始化dp状态数组 dp[i][i]=true; } for(int i=0;i<len;i++){ for(int j=0;j<i;j++){ if(s.charAt(i)==s.charAt(j)){ if(j+1<len&&i-1>=0&&(dp[j+1][i-1]==true||i-j==1)){//注意!i-j==1小细节,一开始不过就是因为没有考虑它 dp[j][i]=true; if(maxlen<i-j+1){ maxlen=i-j+1; beg=j; } } } } } if(maxlen==0&&beg==0){ return s.charAt(0)+""; } return s.substring(beg,beg+maxlen); } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
10-51单片机ESP8266学习-AT指令(单片机采集温湿度数据通过8266发送给C#TCP客户端显示)
https://yq.aliyun.com/articles/580125?spm=a2c4e.11155435.0.0.34723312e7QrBf 先写单片机端的程序先把源码和资料链接放到这里 链接:https://pan.baidu.com/s/10MxI8-Q33-M_R2WEHqEi1A 密码:j1sz 等等哈,,,,我自己做一个android版本的TCP调试助手再接着写....发现别人的不好使.......老有问题,我担心让初学者感觉麻烦,所以自己做一个 稳定的调试助手再接着讲 现在接着说, APP可在百度手机助手,安卓市场,91助手,下载安装(搜索"小五物联")今天刚做好,增加了TCP客户端和服务器,其实前天做好了TCP客户端,但是测试出来问题了......在修改的过程中就把TCP客户端和服务器做到 可一个Pager做到了一起,这样以后再添加MQTT,WEB,蓝牙等功能的时候直接做到这里面刚发布出去,如果亲们不是我上面的界面说明还没审核通过,亲们可以用自己的调试助手,我就用自己做的,,因为做的功能 很全,很方便 等一下,,我先看看上一篇写到哪种程度了 咱先用TCP调试助手...
- 下一篇
Python——基本的书写规则
1、输入方法input() 等待用户输入数据,并回车后得到数据(name为输入的字符串) name=input('Please input your name:') print('Hi,',name) 运行代码效果: 2、注释的写法:#开头 以#开头的语句是注释,注释是给人看的,可以是任意内容,解释器会忽略掉注释。 语句以冒号:结尾时,缩进的语句视为代码块,没有规定缩进是几个空格,但是约定俗成为4个空格。 #Note:firse code demo #print absolute value of an integer: a=100 if a >=0: print(a) else: print(-a) 输出为: 3、数据类型 整数,比如20,-100 浮点数,比如1.2323,对于很大的数使用科学计数法,用e代替10,比如1.23x109就是1.23e9 字符串,比如'abc',“hello world”, 转义,使用\来转移单引号和双引号,\\转义\,\n换行,\t制表符, 不转义,r'\xxx\xxx'表示'\xxx\xxx'不用转义 多行,用'''xxxxxxx'''表...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Linux系统CentOS6、CentOS7手动修改IP地址