暴力枚举所有的字符串
class Solution {
public boolean isAdditiveNumber(String num) {
int n=num.length();
for(int secondStart=1;secondStart<n;secondStart++){
if(num.charAt(0)=='0'&&secondStart!=1){
break;
}
//对于结束位置
for(int secondEnd=secondStart;secondEnd<n;secondEnd++){
if(num.charAt(secondStart)=='0'&&secondEnd!=secondStart){
break;
}
if(check(num,secondStart,secondEnd)){
return true;
}
}
}
return false;
}
public boolean check(String s,int secondStart,int secondEnd){
int n=s.length();
int firstStart=0;int firstEnd=secondStart-1;
while(secondEnd<n){
String third=StringAdd(s,firstStart,firstEnd,secondStart,secondEnd);
System.out.println(third);
int len=third.length();
if(secondEnd+len>=n||!s.substring(secondEnd+1,secondEnd+len+1).equals(third)){
break;
}
if(secondEnd+len==n-1){
return true;
}
// System.out.println("firstStart="+firstStart+"firstENd="+firstEnd+"secondSTart="+secondStart+"secondEnd="+secondEnd);
firstStart=secondStart;firstEnd=secondEnd;
secondStart=secondEnd+1;secondEnd=secondEnd+len;
}
return false;
}
public String StringAdd(String s,int firstStart,int firstEnd,int secondStart,int secondEnd){
//创建对应的StrinBuilder进行结果
StringBuilder sb=new StringBuilder();
int carry=0;
while(firstEnd>=firstStart&&secondEnd>=secondStart){
int res=s.charAt(firstEnd--)-'0'+s.charAt(secondEnd--)-'0'+carry;
sb.append(res%10);
carry=res/10;
}
while(firstEnd>=firstStart){
int res=s.charAt(firstEnd--)-'0'+carry;
sb.append(res%10);
carry=res/10;
}
while(secondEnd>=secondStart){
int res=s.charAt(secondEnd--)-'0'+carry;
sb.append(res%10);
carry=res/10;
}
if(carry!=0){
sb.append(carry);
}
return sb.reverse().toString();
}
}
颠倒字符串中的所有的单词
class Solution {
public String reverseWords(String s) {
s=s.trim();
for(int i=0;i<s.length();i++){//这里虽然字符串s在变化,但是依旧取s.length()
while(i+1<s.length()&&s.charAt(i)==' '&&s.charAt(i+1)==' '){
s=s.substring(0,i+1)+s.substring(i+2);
}
}
String[] str=s.split(" ");
String res="";
for(int i=str.length-1;i>=0;i--){
res+=str[i];
if(i!=0){
res+=" ";
}
}
return res;
}
}
括号生成
括号生成
每一个位置可以选择是否放( )进行dfs搜索
class Solution {
List<String> res=new ArrayList<String>();
public List<String> generateParenthesis(int n) {
dfs(n,0,0,"");
return res;
}
public void dfs(int n,int lc,int rc,String s){
if(lc==n&&rc==n){
res.add(s);
return;
}
if(lc<n){
dfs(n,lc+1,rc,s+'(');
}
if(lc>rc&&rc<n){
dfs(n,lc,rc+1,s+')');
}
}
}