重刷经典

重刷经典老题

4. Median of Two Sorted Arrays

MergeSort

https://leetcode.com/problems/median-of-two-sorted-arrays/solution/

思路：

1. if m+n is odd, (m+n)/2 th
2. if m+n is even, the average of (m+n)/2 and (m+n)/2-1

int p1=0;
int p2=0;
private int get(int[] nums1, int[] nums2){
    if(p1<nums1.length && p2<nums2.length){
        return nums1[p1]<=nums2[p2] ? nums1[p1++] : nums2[p2++];
    }
    if(p1<nums1.length){
        return nums1[p1++];
    }
    return nums2[p2++];
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m=nums1.length;
    int n=nums2.length;
    if((m+n)%2==1){
        //(m+n)/2
        for(int i=0; i<=(m+n)/2-1; i++){
            get(nums1,nums2);
        }
        return get(nums1,nums2);
    }else{
        //average of (m+n)/2 and (m+n)/2-1
        for(int i=0; i<(m+n)/2-1; i++){
            get(nums1,nums2);
        }
        return (get(nums1,nums2)+get(nums1,nums2))/2.0;
    }
}

BinarySearch

The overall run time complexity should be O(log (m+n))

死记硬背吧！<放一边，>=放另一边

思路：

• 每次分4半，舍去不可能的那1半
  • 若target在较小的2半，则舍弃最大的那1半
  • 若target在较大的2半，则舍弃最小的那1半

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int na = A.length, nb = B.length;
        int n = na + nb;
        return (double)(solve(A, B, n / 2, 0, na - 1, 0, nb - 1) + solve(A, B, (n -1)/ 2 , 0, na - 1, 0, nb - 1)) / 2;
        }
    }
    
    public int solve(int[] A, int[] B, int k, int aStart, int aEnd, int bStart, int bEnd) {
        // If the segment of on array is empty, it means we have passed all
        // its element, just return the corresponding element in the other array.
        if (aEnd < aStart) {
            return B[k - aStart];
        }
        if (bEnd < bStart) {
            return A[k - bStart];
        }
        
        // Get the middle indexes and middle values of A and B.
        int aIndex = (aStart + aEnd) / 2, bIndex = (bStart + bEnd) / 2;
        int aValue = A[aIndex], bValue = B[bIndex];
        
        // If k is in the right half of A + B, remove the smaller left half.
        if (aIndex + bIndex < k) { 
            if (aValue >= bValue) {
                return solve(A, B, k, aStart, aEnd, bIndex + 1, bEnd);
            } else {
                return solve(A, B, k, aIndex + 1, aEnd, bStart, bEnd);
            }
        }
        // Otherwise, k is in the left half of A+B, remove the larger right half.
        //注意edge case：必须把>=放一起考虑，不可以把<=放一起考虑
        //当idx1+idx2==k时, 切掉了较大的mid，
        else { 
            if (aValue >= bValue) {
                return solve(A, B, k, aStart, aIndex - 1, bStart, bEnd);
            } else {
                return solve(A, B, k, aStart, aEnd, bStart, bIndex - 1);       
            }
        }
    }
}

5. Longest Palindromic Substring

public String longestPalindrome(String s) {
    int n=s.length();
    int start=0;
    int end=0;
    for (int i = 0; i < n; i++) {
        int len1=expandFromMid(s,i,i);
        int len2=expandFromMid(s,i,i+1);
        int len=Math.max(len1,len2);
        if(len>end-start+1){
            start=i-(len-1)/2;
            end=i+len/2;
        }
    }
    return s.substring(start,end+1);
}

int expandFromMid(String s, int left, int right){
    if(left>right){
        return 0;
    }
    while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
        left--;
        right++;
    }
    return right-left-1;
}

6. Zigzag Conversion

public String convert(String s, int numRows) {
    StringBuilder[] sbs=new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) {
        sbs[i]=new StringBuilder();
    }
    int n=s.length();
    int idx=0;
    char[] chars=s.toCharArray();
    a:while(idx<n){
        for (int i = 0; i < numRows; i++) {
            sbs[i].append(chars[idx++]);
            if(idx>=n){
                break a;
            }
        }
        for (int i = numRows-2; i > 0; i--) {
            sbs[i].append(chars[idx++]);
            if(idx>=n){
                break a;
            }
        }
    }
    StringBuilder res=sbs[0];
    for (int i = 1; i < numRows; i++) {
        res.append(sbs[i]);
    }
    return res.toString();
}

7. Reverse Integer

public int reverse(int x) {
            long res=0;
    while(x!=0){
        res*=10;
        res+=x%10;
        x/=10;
        if(res>Integer.MAX_VALUE || res<Integer.MIN_VALUE){
            return 0;
        }
    }
    return (int)res;
}

Follow up: Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

public int reverse(int x) {
    //[-2147483648,2147483647]
    int res=0;
    while(x!=0){
        int pop=x%10;
        x/=10;
        if(res>Integer.MAX_VALUE/10 || res==Integer.MAX_VALUE/10 && pop>7){
            return 0;
        }
        if(res<Integer.MIN_VALUE/10 || res==Integer.MIN_VALUE/10 && pop<-8){
            return 0;
        }
        res*=10;
        res+=pop;
    }
    return res;
}

8. String to Integer (atoi)

public int myAtoi(String s) {
    if(s==null || s.length()==0) return 0;
    double res=0;   //double 比 long 更大
    s=s.trim();
    int n=s.length();
    boolean negative=false;
    int i=0;
    if(s.charAt(0)=='+' || s.charAt(0)=='-'){
        i++;
    }
    if(s.charAt(0)=='-'){
        negative=true;
    }
    while(i<n){
        char c=s.charAt(i++);
        if(c<'0' || c>'9'){
            break;
        }
        res*=10;
        res+=c-'0';
    }
    if(negative){
        res=-res;
    }
    if(res<Integer.MIN_VALUE){
        return Integer.MIN_VALUE;
    }
    if(res>Integer.MAX_VALUE){
        return Integer.MAX_VALUE;
    }
    return (int)res;
}

9. Palindrome Number

public boolean isPalindrome(int x) {
    String s=String.valueOf(x);
    if(s.charAt(0)=='-'){
        return false;
    }
    for(int i=0,j=s.length()-1;i<j;i++,j--){
        if(s.charAt(i)!=s.charAt(j)){
            return false;
        }
    }
    return true;
}

10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/discuss/191830/Java-DP-solution-beats-100-with-explanation

//abd
//ad*
//a.*
//ac*
public boolean isMatch(String s, String p) {
    boolean[][] dp=new boolean[s.length()+1][p.length()+1];
    dp[0][0]=true;
    for (int i = 1; i <= p.length(); i++) {
        //a*b*
        dp[0][i]=p.charAt(i-1)=='*' && dp[0][i-2];
    }
    for (int i = 1; i <= p.length(); i++) {
        for (int j = 1; j <= s.length(); j++) {
            if(p.charAt(i-1)==s.charAt(j-1) || p.charAt(i-1)=='.'){
                dp[j][i]=dp[j-1][i-1];
            }else if(p.charAt(i-1)=='*'){
                dp[j][i]=dp[j][i-2] ||
                        dp[j-1][i]&&(p.charAt(i-2)==s.charAt(j-1) || p.charAt(i-2)=='.');
            }
        }
    }
    return dp[s.length()][p.length()];
}

12. Integer to Roman

public String intToRoman(int num) {
    String[] M=new String[]{"","M","MM","MMM"};
    String[] C=new String[]{"","C","CC","CCC","CD","D","DC",
            "DCC","DCCC","CM"};
    String[] X=new String[]{"","X","XX","XXX","XL","L","LX",
    "LXX","LXXX","XC"};
    String[] I=new String[]{"","I","II","III","IV","V","VI",
    "VII","VIII","IX"};
    return M[num/1000]+C[(num%1000)/100]+X[(num%100)/10]+I[num%10];
}

13. Roman to Integer

public int romanToInt(String s) {
    Map<Character,Integer> map=new HashMap<>();
    map.put('I',1);
    map.put('V',5);
    map.put('X',10);
    map.put('L',50);
    map.put('C',100);
    map.put('D',500);
    map.put('M',1000);
    int res=0;
    int n=s.length();
    for (int i = 0; i < n; i++) {
        if(i==0){
            res+=map.get(s.charAt(i));
        }else if(map.get(s.charAt(i))>map.get(s.charAt(i-1))){
            res=res+map.get(s.charAt(i))-2*map.get(s.charAt(i-1));
        }else{
            res+=map.get(s.charAt(i));
        }
    }
    return res;
}

14. Longest Common Prefix

public String longestCommonPrefix(String[] strs) {
    int n=strs.length;
    for (int i = 0; i < strs[0].length(); i++) {
        char c=strs[0].charAt(i);
        for (int j = 1; j < n; j++) {
            if(i==strs[j].length() || strs[j].charAt(i)!=c){
                return strs[0].substring(0,i);
            }
        }
    }
    return strs[0];
}

17. Letter Combinations of a Phone Number

public List<String> letterCombinations(String digits) {
    List<String> res=new ArrayList<>();
    int n=digits.length();
    if(n==0){
        return res;
    }
    String[] list=new String[10];
    list[2]="abc";
    list[3]="def";
    list[4]="ghi";
    list[5]="jkl";
    list[6]="mno";
    list[7]="pqrs";
    list[8]="tuv";
    list[9]="wxyz";
    res.add("");
    for (int i = 0; i < n; i++) {
        res=combine(res,list[digits.charAt(i)-'0']);
    }
    return res;
}

List<String> combine(List<String> res, String chars){
    List<String> newRes=new ArrayList<>();
    for (String s : res) {
        for (int i = 0; i < chars.length(); i++) {
            newRes.add(s+chars.charAt(i));
        }
    }
    return newRes;
}

68. Text Justification

public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> res=new ArrayList<>();
    int n= words.length;
    int index=0;

    while (index<n){
        int totalChars=words[index].length();
        int last=index+1;

        while (last<n){//本行[index,last-1]
            //装不下了，此时last已经指向下一行的首个word
            if(totalChars+words[last].length()+1>maxWidth){
                break;
            }
            //能装下，考虑至少1个空格
            totalChars+=1+words[last].length();
            last++;
        }
        //本行共last-index个数，有last-index-1个gap, 此时每个gap已经有1个空格
        int gaps=last-1-index;//本行间隔数
        StringBuilder sb=new StringBuilder();

        if(last==n || gaps==0){ //最后一行或没有间隔
            for(int i=index; i<last; i++){
                sb.append(words[i]);
                sb.append(' ');
            }
            sb.deleteCharAt(sb.length()-1); //去掉最后一个空格
            while(sb.length()<maxWidth){
                sb.append(' ');
            }
        }else{//本行不是最后一行，也不止一个单词
            //spaces: 本行每个gap还需要添加的空格
            //rest: 分剩下的空格，从前往后各匀一个
            int spaces=(maxWidth-totalChars)/gaps;
            //[index, index+rest-1] 各分1个
            int rest=(maxWidth-totalChars)%gaps;

            for(int i=index;i<last-1;i++){
                sb.append(words[i]);
                sb.append(' ');
                for(int j=0;j<spaces+(i-index<rest?1:0);j++){//间隔不止一个空格
                    sb.append(' ');
                }
            }
            sb.append(words[last-1]);
        }
        
        res.add(sb.toString());
        index=last;

    }
    return res;
}

79. Word Search

int row;
int col;
public boolean exist(char[][] board, String word) {
    row=board.length;
    col=board[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(board[i][j]==word.charAt(0)){
                if(helper(board,word,i,j,0,new boolean[row][col])){
                    return true;
                }
            }
        }
    }
    return false;
}

boolean helper(char[][] board, String word, int i, int j, int idx, boolean[][] visited){
    if(idx==word.length()){
        return true;
    }
    if(i<0 || i>=row || j<0 || j>=col || visited[i][j]){
        return false;
    }
    if(board[i][j]!=word.charAt(idx)){
        return false;
    }
    visited[i][j]=true;
    if(helper(board,word,i+1,j,idx+1,visited)||
            helper(board,word,i-1,j,idx+1,visited)||
            helper(board,word,i,j+1,idx+1,visited)||
            helper(board,word,i,j-1,idx+1,visited)){
        return true;
    }
    visited[i][j]=false;
    return false;
}

273. Integer to English Words

String[] twenties=new String[]{"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten",
        "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
String[] tens=new String[]{"","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
String[] thousands=new String[]{"","Thousand","Million","Billion"};
public String numberToWords(int num) {
    if(num==0){
        return "Zero";
    }
    String word="";
    int i=0;
    while(num!=0){
        if(num%1000!=0){
            word=helper(num%1000)+thousands[i]+" "+word;
        }
        num/=1000;
        i++;
    }
    return word.trim();
}

String helper(int n){
    if(n==0){
        return "";
    }
    if(n<20){
        return twenties[n]+" ";
    }
    if(n<100){
        return tens[n/10]+" "+helper(n%10);
    }
    return twenties[n/100]+" Hundred "+helper(n%100);
}

772. Basic Calculator III

通法：双栈operands+operators + comparePrecedence

• ( < +,- < *,/
• 遇到 ( 直接进栈
• 遇到 ) 则一直算到 (
• 遇到 其他运算符 则一直算到 栈顶 < curOp
  • 不可接受：栈顶 >= curOp
    • 1*2+3
    • 2*2/3
    • 2-2-1
  • 可以接受：1+2*3

class Solution {
	Map<Character, Integer> map;
    public int calculate(String s) {
        s = s.replace(" ", "");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c == '+' || c == '-') && (i == 0 || s.charAt(i - 1) == '(')) {
                sb.append(0);
            }
            sb.append(c);
        }
        s = sb.toString();
        Deque<Integer> operands = new ArrayDeque<>();
        Deque<Character> operators = new ArrayDeque<>();
        map = new HashMap<>();
        map.put('(', -1);
        map.put('+', 0);
        map.put('-', 0);
        map.put('*', 1);
        map.put('/', 1);
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            } else if (Character.isDigit(c)) {
                int val = Character.getNumericValue(c);
                while (i + 1 < n && Character.isDigit(s.charAt(i + 1))) {
                    val = val * 10 + Character.getNumericValue(s.charAt(i + 1));
                    i++;
                }
                operands.push(val);
            } else if (c == '(') {
                operators.push(c);
            } else if (c == ')') {
                while (operators.peek() != '(') {
                    int a = operands.pop();
                    int b = operands.pop();
                    operands.push(operate(b, a, operators.pop()));
                }
                operators.pop();
            } else {
                while (!operators.isEmpty() && comparePrecedence(operators.peek(), c) >= 0) {
                    int a = operands.pop();
                    int b = operands.pop();
                    operands.push(operate(b, a, operators.pop()));
                }
                operators.push(c);
            }
        }
        while (!operators.isEmpty()) {
            int a = operands.pop();
            int b = operands.pop();
            operands.push(operate(b, a, operators.pop()));
        }
        return operands.pop();
    }
    
    private int operate(int a, int b, char c) {
        switch(c) {
            case '+' :
                return a + b;
            case '-' :
                return a - b;
            case '/' :
                return a / b;
            case '*' :
                return a * b;
            default :
                return a + b;
        }
    }
    
    private int comparePrecedence(char a, char b) {
        return map.get(a) - map.get(b);
    }
    
}

1597. Build Binary Expression Tree From Infix Expression

与772异曲同工

  class Node {
  char val;
  Node left;
  Node right;
  Node() {this.val = ' ';}
  Node(char val) { this.val = val; }
  Node(char val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}

public Node expTree(String s) {
    Deque<Node> nodes = new LinkedList<>();
    Deque<Character> operators = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(Character.isDigit(c)){
            nodes.push(new Node(c));
        }else if(c=='('){
            operators.push(c);
        }else if(c==')'){
            while(operators.peek()!='('){
                nodes.push(build(operators.pop(),nodes.pop(),nodes.pop()));
            }
            operators.pop();
        }else{
            while(!operators.isEmpty() && compare(operators.peek(),c)){
                nodes.push(build(operators.pop(),nodes.pop(),nodes.pop()));
            }
            operators.push(c);
        }
    }
    while(!operators.isEmpty()){
        nodes.push(build(operators.pop(),nodes.pop(),nodes.pop()));
    }
    return nodes.peek();
}

private Node build(char val, Node first, Node second){
      return new Node(val,second,first);
}

private boolean compare(char o1, char o2){
      if(o1=='(' || o1==')'){
          return false;
      }
      return o1=='*' || o1=='/' || o2=='+' || o2=='-';
}

33. Search in Rotated Sorted Array

81. Search in Rotated Sorted Array II