最朴素的方法就是依次从待匹配串的每一个位置开始，逐一与模版串匹配， 因为最多检查 (n - m)个位置，所以方法的复杂度为 O(m*(n-1))。
//haystack 是待匹配串
//needle 是模板串
public int strStr(String haystack, String needle) {
if(needle==null || needle.length()==0){
return 0;
}
int i=0,j=0;
//k存储的是模板串在待匹配串的位置
int k=i;
while(i<haystack.length() && j<needle.length()){
if(haystack.charAt(i)==needle.charAt(j)){
i++;
j++;
}else{
j=0;
i=++k;
}
}
//说明模板串是待匹配串的子串
if(j==needle.length()){
return k;
}
return -1;
}1.求next数组
private int[] getNext(String needle) {
int[] next=new int[needle.length()];
int j=0,t=-1;
next[0]=-1;
while (j<needle.length()-1){
if(t==-1 || needle.charAt(j)==needle.charAt(t)){
//needle.charAt(j): 表示后缀的单个字符
//needle.charAt(t): 表示前缀的单个字符
next[j+1]=t+1;
t++;
j++;
}else{
t=next[t];
}
}
return next;
}next[j]的值（也就是t）表示，当P[j] != T[i]时，j指针的下一步要移动到的位置(其中P是模式串，T是主串)。
当P[k] == P[j]时，有next[j+1] == next[j] + 1
当P[k] != P[j]时，则循环将k赋值给next[k],一直到k=-1为止。初始时next[0]=-1。
public int strStr(String haystack, String needle) {
if(needle==null || needle.length()==0){
return 0;
}
int[] next=getNext(needle);
int i=0,j=0;
while(i<haystack.length() && j<needle.length()){
if(j==-1 || haystack.charAt(i)==needle.charAt(j)){
i++;
j++;
}else{
j=next[j];
}
}
//说明模板串是待匹配串的子串
if(j==needle.length()){
//返回的是待匹配串的下标
return i-needle.length();
}
return -1;
}
private int[] getNext(String needle) {
int[] next=new int[needle.length()];
next[0]=-1;
int j=0,t=-1;
while (j<needle.length()-1){
if(t==-1 || needle.charAt(j)==needle.charAt(t)){
next[j+1]=t+1;
t++;
j++;
}else{
t=next[t];
}
}
return next;
}//思路：关键是如何去除空字符串，比如 ""、" " 和 " " 等等。
public String reverseWords(String s) {
if(s==null){
return s;
}
String[] arr = s.trim().split(" ");
Stack<String> stack = new Stack<>();
for(String ss : arr){
String str=ss.trim();
if(str.length()!=0){ //去除空字符串
stack.push(str);
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()){
res.append(stack.pop()).append(" ");
}
return res.toString().trim();
}
@Test
public void test(){
//String s="the sky is blue";
//String s=" hello world! ";
String s="a good example";
System.out.println(reverseWords(s));
}public String reverseWords(String s) {
StringBuilder res = new StringBuilder();
String[] words =s.split(" ");
for(String word : words){
word=reverseWord(word);
res.append(word).append(" ");
}
return res.toString().trim();
}
//翻转字符串
private String reverseWord(String word){
char[] chs = word.toCharArray();
int start =0,end=chs.length-1;
while(start<end){
swap(chs,start,end);
start++;
end--;
}
return new String(chs);
}
private void swap(char[] chs,int i,int j){
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
@Test
public void test(){
String s="Let's take LeetCode contest";
System.out.println(reverseWords(s));
}public int countSegments(String s) {
if(s==null || s.length()==0){
return 0;
}
int res=0;
String[] words=s.trim().split(" ");
for(String word:words){
word = word.trim();
if(word.length()!=0){
res++;
}
}
return res;
}
@Test
public void test(){
String s="Hello, my name is John";
System.out.println(countSegments(s));
}//思路：从后向前相相加
public String addBinary(String a, String b) {
StringBuilder res = new StringBuilder();
char[] chsA = a.toCharArray();
char[] chsB = b.toCharArray();
int indexA=chsA.length-1;
int indexB=chsB.length-1;
int c=0;
while(indexA>=0 || indexB>=0 || c==1){
//TODO： c==1 判断条件是针对：a = "11", b = "1" 两数相加的情况的。
c+=((indexA>=0)?chsA[indexA]-'0':0);
c+=((indexB>=0)?chsB[indexB]-'0':0);
res.append(c%2);
c/=2; //作为下一次的值
indexA--;
indexB--;
}
return res.reverse().toString(); //注意是从后向前加的
}
@Test
public void test(){
//String a = "11", b = "1";
String a = "1010", b = "1011";
System.out.println(addBinary(a,b));
}public int firstUniqChar(String s) {
char[] chs = s.toCharArray();
int[] freq = new int[26];
for(char ch : chs){
freq[ch-'a']++;
}
for(int i=0;i<chs.length;i++){
if(freq[chs[i]-'a']==1){
return i;
}
}
return -1;
}//思路：
//由于字符串中只会出现'0'和'1'，并且要求是所有的'0'和'1'组合在一起
//统计一下每个连续 '0' 或者 '1'的个数,实际上就是连续子串的最大个数。
public int countBinarySubstrings(String s) {
char[] chs = s.toCharArray();
int[] count = new int[chs.length]; //统计一下每个连续 '0' 或者 '1'的个数
int index=0; //新数组的下标，index<=chs.length;
for(int i=0;i<chs.length-1;i++){
count[index]++;
if(chs[i]!= chs[i+1]){
index++;
}
}
count[index]++; //注意(i+1)<chs.length,所以需要统计最后一个字符
// count[i] 就能表示子串数？
// 举个例子："000111" 对应 count[0]=3、count[1]=3。
// "000111" 的子串 --> 由内向外 "01"、"0011"和"000111"。
int res=0;
for(int i=0;i<index;i++){ //注意这里 i<index,因为后面存在（i+1）下标
res+=Math.min(count[i],count[i+1]);
}
return res;
}
@Test
public void test(){
String s="00110011";
//String s="10101";
System.out.println(countBinarySubstrings(s));
}public int[] numberOfLines(int[] widths, String S) {
char[] chs = S.toCharArray();
int line =1;
int width =0;
for(int i=0;i<chs.length;i++){
int index = chs[i]-'a';
width += widths[index];
if(width > 100){
line++;
i--; //TODO: i 元素不能写到 line 行了
width = 0;
}else if(width==100){
line++;
width =0;
}
}
return new int[]{line,width};
}
@Test
public void test(){
int[] widths = {4,10,10,10,10,10,10,10,10,10,10,10,
10,10,10,10,10,10,10,10,10,10,10,10,10,10};
String S = "bbbcccdddaaa";
//int [] widths = {10,10,10,10,10,10,10,10,10,10,10,
// 10,10,10,10,10,10,10,10,10,10,10,10,10,10,10};
//String S = "abcdefghijklmnopqrstuvwxyz";
int[] res = numberOfLines(widths,S);
for(int num : res){
System.out.println(num);
}
}/**
* 思路：
* 指针i指向修改内容的位置，指针j遍历整个数组chars，
* 当下一个字符与当前字符不相同时，直接将该字符赋值到i处，然后i++，j++；
* 否则若相同，k指向j所在位置，j继续向前出发遍历所有与k处相同的字符，则相同的个数为j-k，
* 将j-k转化为字符串s，
* 将s的每一个字符都赋值在i所在位置开始的chars中～最后直到j>=n时退出循环，此时i的值即为in-place后新数组中的个数
*/
public int compress(char[] chars) {
int i = 0, j = 0;
int n=chars.length;
while (j<n) {
if (j == n - 1 || chars[j] != chars[j + 1]) {
chars[i++] = chars[j++];
} else {
chars[i++] = chars[j];
int k = j;
while (j < n && chars[j] == chars[k]){
j++;
}
String s = (j - k)+"";
for(int m=0;m<s.length();m++){
chars[i++]=s.charAt(m);
}
}
}
return i;
}/**
* 思路:
* S中出现的字符，在T中按照S出现的顺序进行拼接
* S中该字符只出现一次，但是T中相应字符可能出现多次，所以要对T中字符出现次数进行统计
* S中未出现的字符的字符，直接拼接到T中
*/
public String customSortString(String S, String T) {
//统计T中字符出现的次数
int[] freq=new int[26];
//判断该元素是否在S中出现过
boolean[] visited=new boolean[26];
//
for(int i=0;i<T.length();i++){
freq[T.charAt(i)-'a']++;
}
StringBuilder builder=new StringBuilder();
for(int i=0;i<S.length();i++){
if(freq[S.charAt(i)-'a']>=1){
visited[S.charAt(i)-'a']=true;
for(int j=0;j<freq[S.charAt(i)-'a'];j++){
builder.append(S.charAt(i));
}
}
}
for(int i=0;i<T.length();i++){
if(visited[T.charAt(i)-'a']==false){
if(freq[T.charAt(i)-'a']>=1){
visited[T.charAt(i)-'a']=true;
for(int j=0;j<freq[T.charAt(i)-'a'];j++){
builder.append(T.charAt(i));
}
}
}
}
T=builder.toString();
return T;
}/**
* 思路：
* 当输入为heeellooo时，题目给出的字符串数组为"hello", "hi", "helo"，
* 显然e和o都是可扩展的，h和l都是不可扩展的，因此符合情况的字符串应该至少有一个h、e、o和两个l
* 再看一个例子：当输入为zzzzzyyyyy时，题目给出的字符串数组为"zzyy", "zy", "zyy"，
* 显然z和y都是可扩展的，因此符合情况的字符串应该至少有一个z和y。
*
* 所以，我们就建立以下规则：
* 根据标准字符串S，计算字符串匹配的规则，表示为字母和字母次数。
* 如：S = "heeellooo" --> [<h, 1>, <e, 3>, <l, 2>, <o, 3>]
* 根据规则，判断每个待测字符串是否满足标准。其实就是根据字母的次数决定字母在待测字符串的正确存在。具体如下：
* （1）出现次数小于3：根据题意可知，这组字母不属于扩展组，所以待测字符串中必须有等于该次数的该字母。
* （2）出现次数大于等于3：属于扩展组，待测字符串中可以有小于等于该次数的该字母。
*/
public int expressiveWords(String S, String[] words) {
char[] sc=S.toCharArray();
int res=0;
for(String word:words){
char[] wc=word.toCharArray();
if(check(sc,wc)){
res++;
}
}
return res;
}
private boolean check(char[] sc, char[] wc) {
if (sc.length < wc.length) {
return false;
}
int i = 0, j = 0;
while (i < sc.length && j < wc.length) {
if (sc[i] != wc[j]) {
return false;
}
int sStart = i, wStart = j;
while (i < sc.length && sc[i] == sc[sStart]) {
i++;
}
while (j < wc.length && wc[j] == wc[wStart]) {
j++;
}
//计算S、W中连续相等元素的长度
int sLen = i - sStart;
int wLen = j - wStart;
//出现次数大于等于3：属于扩展组，待测字符串中可以有小于等于该次数的该字母。
if (sLen >= 3 && sLen >= wLen) {
continue;
}
//出现次数小于3：根据题意可知，这组字母不属于扩展组，所以待测字符串中必须要等于该次数的该字母。
if (sLen == wLen) {
continue;
}
return false;
}
return i == sc.length && j == wc.length;
}//思路：
//构成回文串的 2 种情况：
//1、字符出现次数为双数的组合
//2、字符出现次数为双数的组合 + 一个只出现一次的字符//写法一：使用数组来统计
public int longestPalindrome(String s) {
int[] cnts = new int[256];
for (char c : s.toCharArray()) {
cnts[c]++;
}
int res=0;
//统计出现双数的次数，比如 "aaa" -> 3/2=1 (出现 1 次双数)
for(int cnt : cnts){
res+=(cnt/2)*2; // cnt/2 该字符能够有多少次双数
}
if(res < s.length()){
res++;// res++，就是加上一个值出现一次的字符
}
return res;
}
@Test
public void test(){
String s="abccccdd";
System.out.println(longestPalindrome(s));
}//写法二：使用 set 进行统计
public int longestPalindrome(String s) {
int count =0; //用于统计字符出现次数为 2 的字符个数
char[] chs = s.toCharArray();
Set<Character> set=new HashSet<>(); //利用 set 存储的值不能相同的特性
for(char ch:chs){
if(!set.contains(ch)){
set.add(ch);
}else{ //说明 ch 出现次数是偶数
set.remove(ch);
count++;
}
}
return set.isEmpty()?(2*count):(2*count+1);
}
@Test
public void test(){
String s="abccccdd";
System.out.println(longestPalindrome(s));
}/**
* 思路:
* 这里只考虑字母（忽略大小写）和数字，
* 使用Character来进行判断。
*/
public boolean isPalindrome(String s) {
if(s==null || s.length()==0){
return true;
}
//将所有的字母都转换成小写
s=s.toLowerCase();
int start=0;
char[] chs=new char[s.length()];
for(int i=0;i<s.length();i++){
if(Character.isLetterOrDigit(s.charAt(i))){
chs[start++]=s.charAt(i);
}
}
s=new String(chs,0,start);
return isPalindrome(s,0,s.length()-1);
}
private boolean isPalindrome(String s,int start,int end){
while (start<=end){
if(s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}/**
* 改进自private boolean isPalindrome(String,int,int)方法
*/
public boolean isPalindrome(String s) {
if(s==null || s.length()==0){
return true;
}
int start=0;
int end=s.length()-1;
while(start<=end){
if(!Character.isLetterOrDigit(s.charAt(start))){
//start位置不是字母或者字符
start++;
}else if(!Character.isLetterOrDigit(s.charAt(end))){
//end位置不是字母或者字符
end--;
}else{
char c1=Character.toLowerCase(s.charAt(start));
char c2=Character.toLowerCase(s.charAt(end));
if(c1!=c2){
return false;
}
start++;
end--;
}
}
return true;
}/**
* 思路：中心扩展法
* 中心扩展就是把给定的字符串的每一个字母当做中心，
* 向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。
* 但是要考虑两种情况：
* （1）像aba，这样长度为奇数。
* （2）想abba，这样长度为偶数。
*/
public String longestPalindrome(String s) {
if(s.length()< 2){
return s;
}
int len=s.length();
int maxLen=0;
//最长回文串的起始位置和结束位置
int startIndex=0;
int endIndex=0;
//类似于aba这种情况，以i为中心向两边扩展
for(int i=1;i<len;i++){
//以i为中心向两边扩展
int l=i-1;
int r=i+1;
while((l>=0 && r<len) && s.charAt(l)==s.charAt(r)){
int tmpLen=r-l+1;
if(tmpLen>maxLen){
maxLen=tmpLen;
startIndex=l;
endIndex=r;
}
l--;
r++;
}
}
//类似于abba这种情况，以i，i+1为中心向两边扩展
for(int i=0;i<len;i++){
int l=i;
int r=i+1;
while((l>=0 && r<len) && s.charAt(l)==s.charAt(r)){
int tmpLen=r-l+1;
if(tmpLen>maxLen){
maxLen=tmpLen;
startIndex=l;
endIndex=r;
}
l--;
r++;
}
}
return s.substring(startIndex,endIndex+1);
}public int longestPalindromeSubseq(String s) {
if(s.length()==0){
return 0;
}
int len=s.length();
//dp[i][j]表示字符串i-j下标所构成的子串中最长回文子串的长度
int[][] dp=new int[len][len];
for(int i=len-1;i>=0;i--){
dp[i][i]=1;
for(int j=i+1;j<len;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=dp[i+1][j-1]+2;
}else{
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
//最后返回的是[0,len-1]所构成的子串中最长回文子串的长度
return dp[0][len-1];
}