力扣热题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;
    }
}

两点:

  • 要考虑到最后的进位问题
  • l1l2判空代码组合在一起

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);
    }
}