字符串
最经典的就是寻找最长回文子串的问题
解题思想:回文子串的详细思路 在上面的链接中,对该问题做了很详细的思路讲解 下面自己实现采用 Manacher 算法,被中国程序员戏称为“马拉车”算法。它专门用于解决“最长回文子串”问题,时间复杂度为O(N) 。
public int getLongestPalindrome(String A, int n) {
// 做字符串的预处理
String str = changeStr(A,'#');
// 定义左跳跃的指针和右跳跃的指针以及最长回文串的返回值
int left=0,right=0,max=0;
for(int i = 1;i<str.length();i++) {
//判断每一步扩散的步数
right = i + 1;
left = i - 1;
int count = 0;
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
count++;
left--;
right++;
}
max = max > count ? max : count;
}
return max;
}
// 对字符串做预处理,保证处理后的字符串为奇数
private String changeStr(String str,char ch){
char[] chars = str.toCharArray();
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i<chars.length;i++){
stringBuilder.append(ch);
stringBuilder.append(chars[i]);
}
stringBuilder.append(ch);
return stringBuilder.toString();
}
题目描述:给定一个十进制数M,以及需要转换的进制数N。将十进制数M转化为N进制数
备注:M是32位整数,2<=N<=16.
public class Solution {
/**
* 进制转换
* @param M int整型 给定整数
* @param N int整型 转换到的进制
* @return string字符串
*/
public String solve (int M, int N) {
// write code here
if(M==0)return "0";
String s = "0123456789ABCDEF";
//判断是整数还是负数
StringBuilder str = new StringBuilder();
// 判断是否是负数
boolean flag = false;
if(M<0) {
flag = true;
M = -M;
}
while(M !=0 ){
str.append(s.charAt(M%N));
M /= N;
}
if(flag) str.append("-");
return str.reverse().toString();
}
}
题目描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串,如果最长公共子串为空,输出-1。
输入:”1AB2345CD”,“12345EF”
输出:”2345”
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// write code here
if(str1==null || str1.equals("") ||str2==null || str2.equals(""))return "-1";
StringBuilder str = new StringBuilder();
int left=0,right=1;
while(right<str1.length()+1){
if(str2.contains(str1.substring(left,right))){
if(str.length()<right-left){
str.delete(0,str.length());
str.append(str1,left,right);
}
right++;
}else left++;
}
if(str.length()==0)return "-1";
return str.toString();
}
题目描述: 以字符串的形式读入两个数字,编写一个函数计算它们的和,以字符串形式返回。 (字符串长度不大于100000,保证字符串仅由’0’~‘9’这10种字符组成)
输入:”1”,“99”
输出:”100”
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
StringBuilder stringBuilder = new StringBuilder();
int i = s.length() - 1, j = t.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int x = i < 0 ? 0 : s.charAt(i--) - '0';
int y = j < 0 ? 0 : t.charAt(j--) - '0';
int sum = x + y + carry;
stringBuilder.append(sum % 10);//添加到字符串尾部
carry = sum / 10;
}
return stringBuilder.reverse().toString();//对字符串反转
}
- 上一篇: 对数组中寄偶数据的处理
- 下一篇: 基于Arrays.binarySearch解决最长递增子序列