字符串系列题目一览：
1.t1是否有与t2树拓扑结构相同的子树
2.判断两个字符串是否互为变形词？
3.判断两个字符串是否为旋转词？
4.字符串str，请在单词间做逆序调整。
5.给字符串str和一个整数i,i代表str中的位置，将str[0...i]移到右侧，str[i+1...N-1]移到左侧
6.将字符串数组strs拼接一个字符串，字典顺序最小
7.将str中空格字符替换成"%20",假设有足够空间
8.判断字符串是不是有效的括号字符串 str="(()" 返回false
9.判断字符串最长无重复子串的长度 str="abcd" 返回3
1.t1是否有与t2树拓扑结构相同的子树
2.判断两个字符串是否互为变形词？
两个字符串出现的字符种类和每个字符种类出现的次数一样，成为互为变形词。
可以声明256的数组，但是在Java中一个char字符类型占用两个字节，16位65535，所以可以声明65536大小的数组。
也可以使用哈希表解决这个问题。key为字符，value存储出现的次数。str1增加，str2减少。遍历结束正确的结果刚好为0，说明字符种类与出现次数相同。
public static boolean distortion_test(String s1,String s2){
if(s1==null||s2==null||s1.length()!=s2.length()){
return false;
}
char[] c1=s1.toCharArray();
char[] c2=s2.toCharArray();
int[] k=new int[256];
for(int i=0;i<c1.length;i++){
k[c1[i]]++;
}
for(int i=0;i<c2.length;i++){
if(k[c2[i]]==0)
return false;
k[c2[i]]--;
}
return true;
}
public static boolean distortion_test2(String s1,String s2){
if(s1==null||s2==null||s1.length()!=s2.length()){
return false;
}
char[] c1=s1.toCharArray();
char[] c2=s2.toCharArray();
Map<Character, Integer> map=new HashMap<Character,Integer>();
for(int i=0;i<c1.length;i++){
if(map.get(c1[i])==null)
map.put(c1[i], 1);
else
map.put(c1[i],map.get(c1[i])+1);
}
for(int i=0;i<c2.length;i++){
if(map.get(c2[i])==null||map.get(c2[i])==0)
return false;
else
map.put(c2[i], map.get(c2[i])-1);
}
return true;
}
3.判断两个字符串是否为旋转词？
把str前面任意部分挪到后面形成的字符串叫做str旋转词
a="abcd" b="cdab" 返回true
4.字符串str，请在单词间做逆序调整。
"pig loves dog"逆序成"dog loves pig"
构造一个字符串全体逆序方法。
先对将整体逆序 --->"god sevol gip"，再循环到空格处，对单词进行逆序--->"dog loves pig"，得到结果。
public static void inverse(char[] ch,int begin,int end){
while(begin<end){
char temp=ch[begin];
ch[begin]=ch[end];
ch[end]=temp;
begin++;
end--;
}
}
public static String swapWord(String s){
char[] a=s.toCharArray();
inverse(a,0,a.length-1);
int blank=-1;
for(int i=0;i<a.length;i++){
if(a[i]==' '){
int nextBlank=i;
inverse(a,blank+1,nextBlank-1);
blank=nextBlank;
}
}
inverse(a,blank+1,a.length-1);
return (new String(a));
}
5.给字符串str和一个整数i,i代表str中的位置，将str[0...i]移到右侧，str[i+1...N-1]移到左侧
str="abcde",i=2 调整后 str="deabc"
同上题，先构造逆序方法。对str逆序--->"edcba"，然后再根据i的位置对两侧分别逆序，--->"deabc"
public static void inverse(char[] ch,int begin,int end){
while(begin<end){
char temp=ch[begin];
ch[begin]=ch[end];
ch[end]=temp;
begin++;
end--;
}
}
public static String shift(String s,int i){
char[] ch=s.toCharArray();
inverse(ch,0,ch.length-1);
inverse(ch,0,ch.length-i-2);
inverse(ch,ch.length-i-1,ch.length-1);
return new String(ch);
}
public static void main(String args[]){
String s="abcde";
System.out.println(shift(s,3));
}
6.将字符串数组strs拼接一个字符串，字典顺序最小
strs=["abc","de"] 拼成"abcde"
strs=["b","ba"]拼成"bab"
比较的内容为o1+o2>o2+o1，是两个字符串连接后的大小，而不是单独字符串的比较。
public static String findSmallest(String[] strs, int n) {
// write code here
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//此方法如果这个字符串是等参数字符串那么返回值0，==
//如果这个字符串是按字典顺序小于字符串参数那么返回小于0的值，<
//如果此字符串是按字典顺序大于字符串参数那么一个大于0的值 >
String s1=o1+o2;
String s2=o2+o1;
return s1.compareTo(s2);
}
});
StringBuilder sb=new StringBuilder();
for(int i=0;i<n;i++){
sb.append(strs[i]);
}
return sb.toString();
}
public static void main(String args[]){
String s[]=new String[]{"ba","b"};
System.out.println(findSmallest(s, s.length));
}
7.将str中空格字符替换成"%20",假设有足够空间
s=s.replace(" ", "%20");
8.判断字符串是不是有效的括号字符串 str="(()" 返回false
设置num，代表‘（’与‘）’出现此时差值，（就++，）就--，最后应该=0
9.判断字符串最长无重复子串的长度 str="abcd" 返回3
求出每个字符结尾的情况下，最长无重复字符子串的长度，并找出最大值返回
哈希表map --> 统计了每种字符之前出现的位置
整型数组preArr-->代表以s[i]结尾的情况下，最长无重复子串的长度
当循环中，遇见字符重复出现，求该字符的最大不重复子串时。需要比较：上一次该字符出现位置+1与 该字符左边字符的最长无重复子串。如上图位置A与位置B。选择A与B中靠右的点，该点到c的距离便是c的最长无重复子串。（A与B之间必然会重复，所以选择靠右的点）
public static int longestSubstring(String A, int n) {
//charPosition统计A中每种字符之前出现的位置
Map<Character, Integer> charPosition = new HashMap<Character, Integer>();
//preArr代表以s[i-1]结尾的情况下，最长无重复子串的长度
int[] preArr = new int[A.length()];
char[] str2charArr = A.toCharArray();
//从头到尾遍历str2charArr，统计出以每个字符为当前位置的向前最长无重复子串的长度
for(int i=0; i<A.length(); i++){
Integer lastPosOfChar = charPosition.get(str2charArr[i]);
if(lastPosOfChar == null){//说明当前字符第一次出现
//更新最长无重复子串的长度
preArr[i] = i == 0 ? 1 : preArr[i-1] + 1;
//记录当前字符出现的位置
charPosition.put(str2charArr[i], i);
}
else{//当前字符不是第一次出现(既然不是第一次出现，那也不是在第一个位置),也就是之前出现过该字符
//获取前一个字符最长无重复子串的长度
int aPos = lastPosOfChar + 1; //上一次出现该字符的位置+1
int unRepeatLen = preArr[i-1];//以该字符左侧一位字符为标准的最长无重复子串的长度
int bPos = i - unRepeatLen;
if(aPos >= bPos){
//当前位置的最长无重复子串长度
preArr[i] = i - aPos + 1;
}
else{
//当前位置的最长无重复子串长度
preArr[i] = unRepeatLen + 1;
}
//更新当前字符出现的位置
charPosition.put(str2charArr[i], i);
}
}
//遍历preArr,最大值即为所求
int max = preArr[0];
for(int i: preArr) if(i > max) max = i;
return max;
}
网友评论