一、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);
}
}
