力扣热题1-最长回文子串
按照leetcode刷一遍:leetcode hot
1. 两数之和
这题可能的问题是数字重复问题,如3,3。
输入:nums = [3,2,4], target = 6
输出:[1,2]
解决办法就是在查找target-nums[i]
之前,不放入nums[i]
。
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> numPos = new HashMap<>();
for(int i=0;i<nums.length;i++) {
if(numPos.containsKey(target-nums[i])) {
return new int[]{numPos.get(target-nums[i]),i};
}
numPos.put(nums[i],i);
}
return new int[0];
}
2. 两数相加
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
int curVal;
ListNode fakeHead = new ListNode();
ListNode curNode = fakeHead;
int nodeSum;
while(l1!=null||l2!=null) {
nodeSum = (l1==null?0:l1.val)+(l2==null?0:l2.val)+carry;
curVal = nodeSum%10;
carry = nodeSum/10;
curNode.next = new ListNode(curVal);
curNode = curNode.next;
if(l1!=null) l1 = l1.next;
if(l2!=null) l2 = l2.next;
}
if(carry!=0) {
curNode.next = new ListNode(carry);
curNode.next.next = null;
}
return fakeHead.next;
}
}
两点:
- 要考虑到最后的进位问题
l1
和l2
判空代码组合在一起
3. 无重复字符的最长子串
滑窗问题,可以判断当前字符,如果有重复,则left
向右滑动到重复不存在位置。
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return 0;
if(s.length()==1) return 1;
int[] count = new int[128];
int left = 0;
int cur;
int maxLen = 0;
for(cur=0;cur<s.length();cur++) {
count[s.charAt(cur)]++;
while(count[s.charAt(cur)]>1) {
count[s.charAt(left)]--;
left++;
}
maxLen = Math.max(maxLen,cur-left+1);
}
return maxLen;
}
(再看看)4. 寻找两个正序数组的中位数
双指针,效率O(m+n)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 3 -> 1
// 4 -> 1 2
// number ((sum-1)/2 + sum/2)/2
int pm = 0;
int pn = 0;
int cur;
int result = 0;
while(pm+pn<=(m+n)/2) {
if(pm>=m) cur=nums2[pn++];
else if(pn>=n) cur=nums1[pm++];
else if(nums1[pm]>nums2[pn]) cur = nums2[pn++];
else cur = nums1[pm++];
if(pm+pn-1==(m+n-1)/2||pm+pn-1==(m+n)/2) {
result+=cur;
}
}
return (m+n)%2==1?result:result/2.0;
}
}
但是题目要求是log级别的,那就不能递增了,要用二分。
每次筛掉一半。
emm,其实并不好写,看过题解的代码才写出来,自己写的时候边界条件没处理好,一团乱麻。再看看吧,复杂度
O(log(m+n))
,这个还不是最优的,不过思想对于两个序列的top k问题可以借鉴。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int totalLen = nums1.length+nums2.length;
int k = (totalLen-1)/2;
if(totalLen%2==1) {
return getKthElement(nums1,nums2,k+1);
} else {
return getKthElement(nums1,nums2,k+1)/2+getKthElement(nums1,nums2,k+2)/2;
}
}
// topk问题,k从1开始
private double getKthElement(int[] nums1,int[] nums2,int k) {
int m = nums1.length;
int n = nums2.length;
int idx1 = 0;
int idx2 = 0;
while(true) {
if(m==idx1) return nums2[idx2+k-1];
if(n==idx2) return nums1[idx1+k-1];
if(k==1) return Math.min(nums1[idx1],nums2[idx2]);
int nextIdx1 = Math.min(m,idx1+k/2)-1;
int nextIdx2 = Math.min(n,idx2+k/2)-1;
if(nums1[nextIdx1]>nums2[nextIdx2]) {
k-=nextIdx2-idx2+1;
idx2 = nextIdx2+1;
} else {
k-=nextIdx1-idx1+1;
idx1 = nextIdx1+1;
}
}
}
}
最短数组二分,log(min(m,n))
先放着。
(看看)5. 最长回文子串
回文串问题,这么一想,力扣前几题还真经典。
解法一:暴力破解(超时)
对于每一个可能的字符串($O(n^2)$),判断是否是回文串($O(n$),总复杂度$O(n^3)$。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String cur;
String result = "";
for(int i=0;i<n;i++) {
for(int j=i;j<n;j++) {
cur = isPalindrome(s,i,j);
if(cur!=null&&cur.length()>result.length()) {
result = cur;
}
}
}
return result;
}
private String isPalindrome(String s,int i,int j) {
int left = i;
int right = j;
while(left<right) {
if(s.charAt(left)!=s.charAt(right)) return null;
left++;
right--;
}
return s.substring(i,j+1);
}
}
解法二:中心扩展
`$(n^2)$,Manacher写不出来就写这个。
class Solution {
private int pos = 0;
private int maxLen = 1;
public String longestPalindrome(String s) {
int n = s.length();
for(int i=0;i<n-1;i++) {
expand(s,i,i);
expand(s,i,i+1);
}
expand(s,n-1,n-1);
return maxLen%2==1?s.substring(pos-maxLen/2,pos+maxLen/2+1):s.substring(pos-maxLen/2+1,pos+maxLen/2+1);
}
private void expand(String s,int left_,int right_) {
int len = 0;
int left = left_;
int right = right_;
int n = s.length();
while(left>=0&&right<n) {
if(s.charAt(left)==s.charAt(right)) {
len++;
left--;
right++;
} else {
break;
}
}
if(right_-left_==1) len=2*len;
else len=len*2-1;
if(len>=maxLen) {
pos = left_;
maxLen = len;
}
}
}
解法三:最长公共子串
最长回文串问题,反转一下字符串,就变成了寻找最长公共子串问题。
class Solution {
public String longestPalindrome(String s) {
if(s==null||s.length()<=1) return s;
String s1 = s;
String s2 = new StringBuilder(s).reverse().toString();
return longestCommonSubString(s1,s2);
}
private String longestCommonSubString(String s1,String s2) {
//abcdc
//cdcba
//dp[i][j]:长度
//dp[i][j]=if s1[i]==s2[j]:dp[i-1][j-1]+1
int n = s1.length();
int[][] dp = new int[n][n];
int maxLen = 0;
int pos = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(s1.charAt(i)==s2.charAt(j)) {
//可以降维
if(i==0||j==0) dp[i][j]=1;
else dp[i][j] = dp[i-1][j-1]+1;
if(dp[i][j]>maxLen) {
//还需要筛选,如abc123cba abc321cba,abc并不是回文串
//如判断第一段abc和abc相等,要比较一下开始坐标和另一个的结束坐标,看是否相等
//否则就是不相关的串,而不是回文串
//cbbd 开始1
//dbbc 结束n-1-1 对的
if(i-dp[i][j]+1==n-1-j) {
maxLen = dp[i][j];
pos = i;
}
}
}
//else dp[i][j]=0;
}
}
return s1.substring(pos-maxLen+1,pos+1);
}
}
dp优化
可以看出数组使用时候的性质,dp[i][j]
仅和dp[i-1][j-1]
有关,也就是其他都是冗余的,根据这个性质,降成一维逆序。
class Solution {
public String longestPalindrome(String s) {
if(s==null||s.length()<=1) return s;
String s1 = s;
String s2 = new StringBuilder(s).reverse().toString();
return longestCommonSubString(s1,s2);
}
private String longestCommonSubString(String s1,String s2) {
//abcdc
//cdcba
//dp[i][j]:长度
//dp[i][j]=if s1[i]==s2[j]:dp[i-1][j-1]+1
int n = s1.length();
int[] dp = new int[n];
int maxLen = 0;
int pos = 0;
for(int i=0;i<n;i++) {
for(int j=n-1;j>=0;j--) {
if(s1.charAt(i)==s2.charAt(j)) {
//可以降维
if(i==0||j==0) dp[j]=1;
else dp[j] = dp[j-1]+1;
if(dp[j]>maxLen) {
//还需要筛选,如abc123cba abc321cba,abc并不是回文串
//如判断第一段abc和abc相等,要比较一下开始坐标和另一个的结束坐标,看是否相等
//否则就是不相关的串,而不是回文串
//cbbd 开始1
//dbbc 结束n-1-1 对的
if(i-dp[j]+1==n-1-j) {
maxLen = dp[j];
pos = i;
}
}
}
//之前二维数组,每次用的是不同的列,所以不用置 0 。
else dp[j]=0;
}
}
return s1.substring(pos-maxLen+1,pos+1);
}
}
解法四:Manacher
class Solution {
public String longestPalindrome(String s) {
// 1
//^ # c # b # c # b # c # d # e # $
//0 0 1
// C R
// 2
//^ # c # b # c # b # c # d # e # $
//0 0 1 0
// C R
// 3 c遇到了边界,就不能用对称了
//^ # c # b # c # b # c # d # e # $
//0 0 1 0 3 0 5 0
// C R
// 4
//^ # c # b # c # b # c # d # e # $
//0 0 1 0 3 0 1 0 3 0 1 0
// C R
// 5
//^ # c # b # c # b # c # d # e # $
//0 0 1 0 3 0 1 0 3 0 1 0 1 0 1 0
//
return manacher(s);
}
private String manacher(String source) {
int n = source.length();
StringBuilder sb = new StringBuilder("^#");
for(int i=0;i<n;i++) {
sb.append(source.charAt(i));
sb.append('#');
}
sb.append('$');
String s = sb.toString();
int C = 1;
int R = 1;
int[] P = new int[s.length()];
for(int i=1;i<s.length()-1;i++) {
int iMirror = 2*C-i;
if(R>i) {
//如果i在半径范围内,能通过对称得到
//P[i] = P[iMirror];
//问题:当前i加上范围之后可能超过R,如iMirror是上一个范围的中心
P[i] = Math.min(P[iMirror],R-i);
} else {
//R==i
P[i] = 0; //交给后面的扩展,这里置0
}
//能由对称做的上面已经做了,下面由中心扩展补全
while(s.charAt(i+1+P[i])==s.charAt(i-1-P[i])) {
P[i]++;
}
}
// 找出 P 的最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < s.length() - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
return source.substring(start, start + maxLen);
}
}