继续刷题
常用的函数
s.substring(start,end) 是区间[start,end) 不是区间 [start，end] 区别是end 取没有
Queue 创建 Queuequeue = new LinkedList ();
Leetcode 5
Boolean[][] board = new Boolean[s.length()][s.length()];
for(int i=0;i<s.length();i++){
for(int j=0;j<s.length();j++){
if(i==j){
board[i][j]=true;
}else{
board[i][j]=false;
}
}
}
if(s==null||s.length()==0){
return "";
}
if(s.length()==1){
return s;
}
int maxLen=0,start=0,end=0;
for(int l=2;l<=s.length();l++){
for(int j=s.length()-1; j>0;j--){
if(j-l+1>=0&& j+1<=s.length()-1 && board[j-l+1][j]==true && s.charAt(j-l)==s.charAt(j+1)){
board[j-l][j+1]=true;
if(l>maxLen){
maxLen=l;
start=j-l;
end=j+1;
}
}
}
}
return s.substring(start,end);
修改后代码变为
int maxLen=0,start=0,end=0;
for(int l=1;l<=s.length();l++){
for(int j=s.length()-1; j>=0;j--){
if(j-l>=0&& j+1<=s.length()-1 && board[j-l+1][j]==true && s.charAt(j-l)==s.charAt(j+1)){
board[j-l][j+1]=true;
if(l+2>maxLen){
maxLen=l+2;
start=j-l;
end=j+1;
}
}else if(l==2){
if(j-l+1>=0 &&s.charAt(j-1)==s.charAt(j)){
board[j-1][j]= true;
if(l>maxLen){
maxLen = l;
start = j-1;
end = j;
}
}
}
}
}
return s.substring(start,end+1);
依旧有样例过不去
最终
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
需要思考的边界条件
考虑长度小于3 例子"ac"是否能过去 即初始化maxLen的长度
是从长度为2开始枚举目的是4 ，还是从长度为2开始枚举目的是2 （意思就是把l 当作是已知条件，还是结论）
Leetcode 15
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int len= nums.length;
if(nums.length<3){
return new ArrayList();
}
int begin = 0 ,end = 0;
for(int i=0;i<nums.length-2;i++){
if(i>0 && nums[i]==nums[i-1]){
continue;
}
begin =i+1;
end =len-1;
while(begin<end){
if(nums[i]+nums[begin]+nums[end]==0){
List<Integer> list = Arrays.asList(nums[i],nums[begin],nums[end]);
while(begin<end && nums[begin]==nums[begin+1]){
begin++;
}
while(begin<end && nums[end ]==nums[end-1]){
end--;
}
begin++;
end--;
res.add(list);
}else if(nums[i]+nums[begin]+nums[end]<0){
begin++;
}else{
end--;
}
}
}
return res;
注意点 Arrays.asList()，还有跳过重复元素 i>0 && num[i]==num[i-1];
Leetcode 剑指 09
private Stack<Integer> data;
private Stack<Integer> help;
public CQueue() {
data = new Stack<>();
help = new Stack<>();
}
public void appendTail(int value) {
help.push(value);
}
public int deleteHead() {
if(!data.isEmpty()){
return data.pop();
}
if(help.isEmpty()){
return -1;
}
while(!help.isEmpty()){
data.push(help.pop());
}
return data.pop();
}
需要注意的
Leetcode 225
private Queue<Integer> data;
private Queue<Integer> help;
public MyStack() {
data = new LinkedList<>();
help = new LinkedList<>();
}
public void push(int x) {
if(data.isEmpty()){
data.add(x);
}else{
while(!data.isEmpty()){
help.add(data.poll());
}
data.add(x);
while(!help.isEmpty()){
data.add(help.poll());
}
}
}
public int pop() {
return data.poll();
}
public int top() {
return data.peek();
}
public boolean empty() {
return data.isEmpty();
}
Leetcode 1996
Arrays.sort(properties, (p1,p2)->{
if(p2[0]==p1[0]){
return p1[1]-p2[1];
}
return p1[0]-p2[0];
});
int len = properties.length;
int res = 0;
for(int i = 0 ; i< len ;i++){
for(int j = i+1 ; j < len ; j++){
if(properties[i][1]<properties[j][1] && properties[i][0] !=properties[j][0] ){
res++;
System.out.println(properties[i][0] + " " + properties[j][0]);
break;
}
}
}
return res;
解答时间超过限度