5.1
5.1.1
.
This is nowcoder
redocwon si sihT
//
public static String reverseString(String s){
int len=s.length();
char[] out=new char[len];
for (int i = 0; i < len; i++) {
out[len-i-1]=s.charAt(i);
}
return new String(out);
}
//
public static String reverseString1(String s) {
return new StringBuilder(s).reverse().toString();
}
5.1.2
: abc abc ,abc cba,aabcd bcada;
s t t s1: : s = anagram , t = nagaram
: true
2:: s = rat , t = car
: false
:
// 1
public static boolean isAnagram(String s, String t) {
if(s.length()!=t.length()){
return false;
}
char[] s1=s.toCharArray();
char[] t1=t.toCharArray();
Arrays.sort(s1);
Arrays.sort(t1);
return Arrays.equals(s1,t1);
}
// 2
public static boolean isAnagram1(String s, String t) {
int[] flag=new int[128];
if(s.length()!=t.length()){
return false;
}
for (int i = 0; i <s.length() ; i++) {
flag[(int)s.charAt(i)]++;
}
for (int i = 0; i < t.length(); i++) {
int a=(int)t.charAt(i);
flag[a]--;
if(flag[a]<0){
return false;
}
}
for (int a :flag) {
if(a!=0){
return false;
}
}
return true;
}
5.1.3 %20
%20
( 1000)
string iniString int len, string
"Mr John Smith ,13
Mr%20John%20Smith
Hello World ,12
Hello%20%20World
// 2
public static String replaceSpace(String s){
return s.replaceAll("\\s","%20");
}
// 1
public static String replaceSpace2(char[] s,int n){
int count=n;
for (int i = 0; i < n; i++) {
if(s[i]==' '){
count+=2;
}
}
int p1=n-1;
int p2=count-1;
while (p1>0){
if(s[p1]==' '){
s[p2--]='0';
s[p2--]='2';
s[p2--]='%';
}else {
s[p2--]=s[p1];
}
p1--;
}
return new String(s,0,count);
}
5.1.4
aabcccccaaa a2b1c5a3 a z
1:
aabcccccaaa
a2b1c5a3
2:abbccd
abbccd
abbccd" "a1b2c2d1
[0, 50000]
public static String compressString(String S) {
if (S.length()==0){
return "";
}
int last=0;
int count=1;
StringBuilder sb=new StringBuilder(S.charAt(0));
for (int i =1; i < S.length(); i++) {
if(S.charAt(i)==S.charAt(last)){
count++;
}else{
sb.append(S.charAt(last));
sb.append(count);
count=1;
}
last++;
}
sb.append(S.charAt(last));
sb.append(count);
if(sb.length()<S.length()){
return sb.toString();
}else{
return S;
}
}
5.1.5
s1 s2, s2 s1 ( rotate) s1= AABCD s2=CDAA, true; s1= ABCD S2= ACBD false
s2 s1
s1.apend(s1)
s2
public static boolean checkRotate(String s1,String s2){
return new StringBuilder(s1).append(s1).toString().contains(s2);
}
System.out.println(checkRotate("AABCD","CDAA"));//true
class Solution {
public boolean rotateString(String A, String B) {
if(A.length() != B.length())
return false;
boolean result = new StringBuilder(A).append(A).toString().contains(B);
return result;
}
}
5.1.6
+
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); //
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { //
if(strs[i].equals("")) continue; //
res.append(strs[i] + " "); // StringBuilder
}
return res.toString().trim(); //
}
}
5.2
str1= BBC ABCDAB ABCDABCDABDE str2= ABCDABD
str1 str2, , -1
str1 i str2 j
- str1[i] == str2[j]i++j++
- str1[i]! = str2[j]i = i - (j - 1)j = 0i j 0
- ( !)
public class ViolenceMatch {
public static void main(String[] args) {
//
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int index = violenceMatch(str1, str2);
System.out.println("index=" + index);
}
//
public static int violenceMatch(String str1, String str2) {
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int s1Len = s1.length;
int s2Len = s2.length;
int i = 0; //i s1
int j = 0; //j s2
while (i < s1Len && j < s2Len) {//
if(s1[i] == s2[j]) {// ok
i++;
j++;
} else { //
// str1[i]! = str2[j] i = i - (j - 1) j = 0
i = i - (j - 1);
j = 0;
}
}
//
if(j == s2Len) {
return i - j;
} else {
return -1;
}
}
}
KMP
- KMP
- KMP next next
- www.cnblogs.com/ZuoAndFutur
KMP
Str1 = BBC ABCDAB ABCDABCDABDE Str2 = ABCDABD
- Str1 Str2
- Str1 Str2
- Str1 Str2
- Str1 1 ( BCD D ABCDAB KMP )
- Str2
- D ABCDAB B 2 = -6 - 2 4 4
- 2 AB 0 = 2 - 02 2
- A
- C D = 6 - 24
- = 7 - 07
?
ABCDABD
- A 0
- AB [A][B]0
- ABC [A, AB][BC, C]0
- ABCD [A, AB, ABC][BCD, CD, D]0
- ABCDA [A, AB, ABC, ABCD][BCDA, CDA, DA, A]A 1
- ABCDAB [A, AB, ABC, ABCD, ABCDA][BCDAB, CDAB, DAB, AB, B]AB 2
- ABCDABD [A, AB, ABC, ABCD, ABCDA, ABCDAB][BCDABD, CDABD, DABD, ABD, BD, D]0
ABCDAB AB 2 AB AB 4 - AB
KMP
public class KMPAlgorithm {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
System.out.println("next=" + Arrays.toString(next));
int index = kmpSearch(str1, str2, next);
System.out.println("index=" + index); //15
}
/**
* @param str1 BBC ABCDAB ABCDABCDABDE
* @param str2 ABCDABD
* @param next , [0, 0, 0, 0, 1, 2, 0]
* @return -1
*/
public static int kmpSearch(String str1, String str2, int[] next) {
//
for (int i = 0, j = 0; i < str1.length(); i++) {
// str1.charAt(i) != str2.charAt(j), j
//KMP , ...
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {// j = 3 i
return i - j + 1;
}
}
return -1;
}
// ( )
//ABCDABD ---> [0, 0, 0, 0, 1, 2, 0]
public static int[] kmpNext(String dest) {
// next
int[] next = new int[dest.length()];
next[0] = 0; // 1 0
for (int i = 1, j = 0; i < dest.length(); i++) {
// dest.charAt(i) != dest.charAt(j) next[j-1] j
// dest.charAt(i) == dest.charAt(j)
// kmp
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
// dest.charAt(i) == dest.charAt(j) +1
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}