判断字符串有无重复字符
public class Different{public boolean checkDifferent(String iniString){if(StringUtils.isEmpty(iniString)){//判断是否为空return true;}int[] flag=new int[128];//ASCII码128个字符//扫描字符串for(int i=0;i<iniString.length();i++){int c=(int)(iniString.charAt(i));if(flag[c]>0)return flase;else flag[c]++;}return true;}public static void main(String[] args){String iniString = "Barack0bama";iniString="abcdefg";System.out.println(Different.checkDiffent(iniString));}}
请实现一个算法,翻转一个给定的字符串
public String reverseString(String iniString){int len=iniString.length();char[] charArr=new char[len];for(int i=0;i<len;i++){charArr[i]=iniString.charAt(len-1-i);//从左保存,右边的字符}return new String(charArr);//String类,String(int[] A);生成字符串对象
}//一个递增的变量,i,length-1-i对称保存两边的值public class Reverse{public String reverseString(String iniString){StringBuffer sb=new StringBuffer(iniString);return sb.reverse().toString();//直接API求解//StringBuffer类 构建长度可变的字符串对象;//reverse()反转字符串//toString转为字符串}
}
变形词:两个串由相同的字符及数量组成
两个串由相同的字符及数量组成,abc,bac,acb,cba,aabcd,bcdaa
给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串,
这里规定大小写为不同字符,且考虑字符串中的空格
给定一个string stringA和一个string stringB,请返回一个bool,代表两串是否重新排列后可相同
保证两串的长度都小于等于5000
测试样例:
"Here you are","Are you here"
//返回false//复杂度较高
public boolean checkam(String stringA,String stringB){//write code hereint len1=stringA.length();int len2=stringB.length();if(len1!=len2){return false;}char[] arr1=stringA.toCharArray();char[] arr2=stringB.toCharArray();//字符串转字符数组Arrays.sort(arr1);//给字符排序Arrays.sort(arr2);return Arrays.equals(arr1,arr2);//排完序后是否一样}
请编写一个方法,将字符串中的空格全部替换为"%20"
请编写一个方法,将字符串中的空格全部替换为"%20"。假定该字符串有足够的空间存放新增的字符
并且直到字符串的真实长度(小于等于100),同时保证字符串大小写的英文字母组合
给定一个string iniString为原始的串,以及串的长度int len,返回替换后的string
测试样例:
"Mr John Smith",13
返回:"Mr%20John%20Smith"public String replaceSpace(String iniString,int lengt){return iniString.replaceAll(" ","%20");//API直接求,不过复杂度高一些
}//replaceAll(String str1,STring str2),将字符串中的str1全部替换为str2public static String replaceSpace(char[] iniString,int length){int count=length;for(int i=0;i<length;i++){if(iniString[i]==' '){count+=2;}}//先行指针//923898938p100938983294p2int p1=length-1;int p2=count-1;while(p1>=0){if(iniString[p1]==' '){iniString[p2--]='0';iniString[p2--]='2';iniString[p2--]='%';}else{iniString[p2--]=iniString[p1];}p1--;}}
利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能
利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能
比如,字符串"aabcccccaaa"经压缩会变成"a2b1c5a3".
若压缩后的字符串没有变短,则返回原先的字符串
给定一个string iniString为待压缩的串(长度小于等于10000),
保证串内字符军由大小写英文字母组成,返回一个string,为所求的压缩后或为变化的串
测试样例
“aabcccccaaa”
返回:a2b1c5a3public static String zipString(String src){int count=0;//记录的一个字符的重复次数char last=0;//上一个字符StringBuilder sb=new StringBuilder();for(int i=0;i<src.length;i++){char charAt=src.charAt(i);if(sb.length){//处理第一个字符sb.append(charAt);count++;}else{if(last==charAt){//和上一个字符相同count++;}else{//和上一个字符不同sb.append(count).append(charAt);//若是不同,则将上一个字符的数字放入,并将不同的下一个字符放入count=1;//重复置为1}}last=charAt;//一个字符结束,更新last上一个字符}考虑最后一个字符的重复次数if(count>=1){sb.append(count);}//比较新字符串和原字符串if(sb.length()>scr.length()){retunr src;}//压缩后没有变短,返回原字符串return sb.toString();
}
两个串是否由相同的字符组成
两个串是否由相同的字符组成
两串的字符集相同
static boolean check(String s1,String s2){//int[] help=new int[256];Map<Character,Integer> map=new HashMap<>();//HashMap减少空间复杂度//扫描s1for(int i=0;i<s1.length();i++){char c=s2.charAt(i);if(map.get(c)==null)//help[c]==0map.put(c,1);//help[c]=1;}//扫描s2for(int i=0;i<s2.length();i++){char c=s2.charAt(i);//HashMap若不存在,则返回nulif(map.get(c)==null)//help[c]==0return false;}//遍历每个,若是找到s1没有的字符集,则返回falsereturn true;}
旋转词
给定两个字符串s1和s2,要求判定s2是否能够呗通过s1作循环移位(rotate)得到的字符串包含。例如,给定s1=AABCD和s2=CDAA。返回true,给定s1=ABCD和S2=ACBD,返回false
public static boolean isRotate(String a,String b){//b+b;StringBuilder sb=new Stringbuilder(b).append(b);//append可以追加字符,也可以追加字符串return sb.toString().contains(a);//StringBuilder需要表示字符串形式,用toString()方法//contains()字符串中是否包含某一段字符串或字符
}
按单词翻转字符串
如here you are 翻转成 are you here
static String reverse(String src){String s1=reverseString(src);//将整个字符串翻转,这样就到达了翻转的效果,不过里面的单词还是翻转的//切割单词String[] words=s1.split("\\s");//按空格分割单词//split("\\s")分割字符串,将字符串分割为字符串数组StringBuilder sb= new StringBuilder();for(int i=0;i<word.length;i++){sb.append(reverseString(words[i])+" ");反转每个单词,然后将每个单词追加到字符串上}return sb.deleteCharAt(sb.length()-1).toString();//删除最后加的“ ”;//deleteCharAt(),按下标删除元素
}public static String reverseString(String iniString){StringBuilder sb=new StringBuilder(iniString);return sb.revverse().toString();
}
去掉字符串中连续出现k次的0
去掉字符串中连续出现k次的0
static String remove(String iniString,int k){String regexp="0{"+k+"}";//k次0自己定义return iniString.replaceAll(regexp,"");//直接API求解replaceAll(String str1,String str2);//在字符串中将所有的str1替换为str2
}static String remove(String iniString,int k){char[] arr=iniString.toCharArray();int count=1;char last=arr[0];StringBuilder sb=new StringBuilder();for(int i=0;i<arr.length;i++){char c=arr[i];if(c=='0'){count++;}else{for(int i=0;i<count%k;i++){//将k的整数倍删除,只留下不足k个的0sb.append('0');//追加到字符串中}sb.append(c);//到非‘0’,先把不足k的‘0’追加到字符串中,在追加非‘0’字符count=0;}}return sb.toString();
}
回文串
回文字符串public boolean isPolindrome(String src){if(StringUtils.isEmpty(src)){return true;}//翻转后和自己相同---回文字符串return src.eauals(new StringBuilder(src).reverse().toString());
}static void palindromeNumber(){for(int i=0;i<10;i++){for(int j=0;j<10;j++){System.out.println(i*1000+j*100+j*10+i);}}
}
最短摘要
给定一段产品的英文概述,包含M个英文单词,每个英文字母单词以空格分割,无其他标点符号:
再给定N个英文单词关键字,请说明思路并编程实现方法
String extractSummary(String description,String[] key words)
目标是找出此产品描述中包含N个关键字(每个关键字至少出现过一次)的尺取法
a[0] a[1] a[2] a[3] a[4] a[5] a[6]0 5 1 5 4 8 1
sum=10
区间长度:2
最短区间:3
int l=0,r=0,sum=0;//第一个存储值在a[1]开始
while(1){//无限循环while(sum<s&&r<n){//移动右指针r++;sum+=a[r];}//小于s的sum又变得大于sdif(sum<s)break;//如果右指针到最后一项还无法满足要求while(sum>=s&&l<r){//移动左指针ans=min(ans,r-l );//统计l++;//l所在位置不计入sumsum-=a[l];}//大于s的sum又变得小于s
}从第一个关键字开始,用尺取法找,当第一次找到全部关键词,i往右走一个,j从上一次找到全部关键词的位置开始,因为前面已经确定的关键词可以继续算入新的找全部关键词的数组中
//双指针也叫尺取法
private static int indexOf(String[] q,String word){//在单词字符串数组中查找相同的字符串for(int i=0;i<q.length;i++){if(q[i].equals(word))return i;//返回相同单词的位置}return -1;//如果没有找到相同的则返回-1
}public static void solve2(String[] w,String[] keys){//begin和end用于在找到更短的包含全部关键字的子数组时更新int begin=-1;int end=-1;int index;int p2=-1;//上一次囊括了所有关键词的有边界int minlen=Interger.MAX_VALUE;//记录最短长度int[] keyFound=new int[keys.length];//找到所有关键字的位置并标记出现Arrays.fill(keyFound,0);//我后来修改的*for(int i=0;i<w.length;i++){//Arrays.fill(keyFound,0);//每次从i作为起始点开始都要将记录关键词是否存在的数组清0;keyFound[index]=0;//将左端的第一个关键词取消标记//如果i位置是关键字,求以i开头包含所有关键字的序列String word1=w[i];//拿一个单词去比较关键词,看是否为关键词index=indexOf(keys,word1);//没有找到与word1相同的关键字if(-1==index){//没有找到关键词continue;}else{keyFound[index]=1;//找到了,标记下标位置为1,表示该关键字已出现}int j;if(p2!=-1){j=p2;//第一次j从i的下一个开始,之后j从上一个找到全部关键词终点开始,因为前面有重叠的关键词}else{j=i+1;//若是p2==-1,则意味着刚开始找关键词}for(;j<w.length;j++){//从第一个关键字词开始,往后找String word2=w[j];//再拿一个单词int index1=indexOf(keys,word2);//看该单词是否为关键字if(index1==-1||indexFound[index1]==1){//不是关键字,或是该关键字已有,跳过continue;}else{//找到没有发现的关键词keysFound[index1]=1;//标记一下if(sum(keyFound)==keys.length){//关键词全部找到p2=j;//p2标记找到全部关键词的当前位置if(j-i+1<minlen){//如果当前找到全部关键词的距离小于最短距离,更新最短距离minlen=j-i+1;//更新最短距离begin=i;//更新起点end=j;//更新终点}break;}}}}print(w,begin,end);}private static void print(String[] w,int begin,int end){System.out.println(begin+" "+end);for(int i=begin;i<=end;i++){System.out.println(w[i]+" ");}
}
private static int sum(int[] keyFound){int sum=0;for(int e:keyFound){sum+=e;}return sum;
}//未解决有重复的关键字的情况