Lexi's Leetcode solutions

Posts Tagged ‘hard

思路:

  1. 因为没有random access,所以用in order的方式,一个一个遍历element,然后assign给parent
  2. 平时正常array convert bst都是用pre order的方式,root算好,然后left=.., right =…
  3. 一般你做树的bottom up是post order,left做出来,right做出来,root取决于这两个值
  4. 这里为什么要in order呢? 左,中,右的方式,正好是sorted。所以每次做完子树,然后下一个节点就是下一个位置。但是什么时候是个头呢,因为h.next会一直存在的,但是你的子树怎么知道什么时候返回到上一层?所以就要用p, q两个指针了,p代表当前sub list的头,q是尾。但是不要真的用他们来random access,就是用来stop就行了。
public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}
Advertisements
Tags: , , ,

还是两个map,一个want, 一个has,i指当前window的开头,j指结尾;want满足了的时候就试试能不能从i处删点什么。写了25分钟然后各种debugger,这题还得重做。

public String minWindow(String S, String T) {
    Map<Character, Integer> has = new HashMap<Character, Integer>();
    Map<Character, Integer> want = new HashMap<Character, Integer>();
    String res = S + S;
    char[] s = S.toCharArray();
    char[] t = T.toCharArray();
    for (int i = 0; i < t.length; i++) {
        want.put(t[i], want.get(t[i]) == null ? 1 : want.get(t[i]) + 1);
        has.put(t[i], 0);
    }
    int i = 0;
    for (int j = i; j < s.length; j++) {
        if (want.containsKey(s[j])) {
            has.put(s[j], has.get(s[j]) + 1);
            if (satisfy(has, want)) {// satisfies everything nows, try move i
                while (!want.containsKey(s[i]) || has.get(s[i]) > want.get(s[i])) { //move i until not movable
                    if (want.containsKey(s[i]) && has.get(s[i]) > want.get(s[i]))
                        has.put(s[i], has.get(s[i]) - 1); 
                    i++;
                }
                String currWindow = S.substring(i, j + 1);
                res = res.length() > currWindow.length() ? currWindow : res;
            }
        }
    }
    return res.length() > S.length() ? "" : res;
}
private boolean satisfy( Map<Character, Integer> has, Map<Character, Integer> want) {
    for (Character c : want.keySet()) {
        if (has.get(c) < want.get(c))
            return false;
    }
    return true;
}
Tags: ,

Hands down,这是我leetcode做的最难的题top 5。别的都是可以用算法说得通的,这题就是纯数学。我这辈子最怕的就是数学,要死要活。

几个要点:

  1. 找没用过的里面的第(k – 1) / (n – 1)!个数字,放第一位上
  2. k = (k – 1) % (n – 1)!,第一个数字确定了,剩下这些里面重新找第k个。
  3. n每次-1,比如第一位确定后有(n-1)!种后面数字的排法,第二位也确定了后面的数字排法就又少了一位(n – 1 – 1)!

还是不是很清楚,今晚睡觉接着想。

public String getPermutation(int n, int k) {
    boolean[] used = new boolean[n];
    // used[i] means the digit i + 1 is used, e.g. used[0] means digit '1' is used
    StringBuilder sb = new StringBuilder();
    int factorial = getFactorial(n - 1);
    int originalN = n;
    while (k > 0) {
        int index = (k - 1) / factorial;
        int count = 0;
        for (int i = 0; i < originalN; i++) {
            if (used[i] == false)
                count++;
            if (index == count - 1) {
                sb.append(i + 1);
                used[i] = true;
                break;
            }
        }
        n--;
        k = (k - 1) % factorial + 1;
        if (n == 0)
            break;
        factorial /= n;
    }
    return sb.toString();
}
private int getFactorial(int n) {
    if (n == 1 || n == 0)
        return 1;
    return n * getFactorial(n - 1);
}
Tags: ,

非常非常难,用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。

算法:

  1. 首先把每个substring是不是palindrome先二维dp的做出来,参见上一题的分析。其实这一步可以合在下一步里,但是下一步本身的logic就够难想了,所以这里分开来写。
  2. 一维dp(为神马是一维啊!!头一次看这样的一维啊!!一维dp却是两层循环啊卧槽!!!),d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
  3. 把d[i]先赋成最大值。
  4. i从后往前,然后j在每个i处从前往后。这样做就能保证在i处,i + 1…j – 1的所有两两combination(中间的小节substring)都已经算出来了,就能用了。如果str[i, j]是个palindrome,那么可以在j 和j + 1中间切一刀,这样的#就是d[j + 1] + 1([i..j], 一刀, [j + 1..本来有几刀])。这样切法可能就比之前算的d[i]小了,于是update。
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) { // i is always <= j
        for (int j = i; j < n; j++) {
            boolean isPalindrome = s.charAt(i) == s.charAt(j) 
                && (j - i < 2 || isPalin[i + 1][j - 1]);
            isPalin[i][j] = isPalindrome;
        }
    }
    int[] d = new int[n];
    // initialize as cut between every letter
    for (int i = 0; i < n; i++) {
        d[i] = n - 1 - i;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (isPalin[i][j]) {
                if (j == n - 1)
                    d[i] = 0;
                else
                    d[i] = Math.min(d[i], d[j + 1] + 1);
            }
         }
    }
    return d[0];
}

括号题也不是只用stack才能做,这题是算长度,所以stack那种一match就俩一起pop了的方式就不适合了。求极值,一维dp最好使。

  • d[i]: 以i开头的最长valid parentheses有多长。
  • d[i] =
    • if  (str[i] == ‘)’),以右括号开头必定invalid,d[i] = 0
    • if (str[i] == ‘(‘),以左括号开头
      1. 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾,所以我们想catch((…))这种情况。j = i + 1 + d[i + 1],正好就是str[i]后面越过完整sequence的下一个,若是右括号,d[i] = 2 + d[i + 1]
      2. 除此之外,还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况,如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]

这个定义和最长公共字串那题的定义类似,都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的,一下复习好多东西。

public int longestValidParentheses(String s) {
    if (s.length() == 0)
        return 0;
    int maxLen = 0;
    int[] d = new int[s.length()];
    // d[i] means substring starts with i has max valid lenth of d[i]
    d[s.length() - 1] = 0;
    for (int i = s.length() - 2; i >= 0; i--) {
        if (s.charAt(i) == ')')
            d[i] = 0;
        else {
            int j = (i + 1) + d[i + 1];
            if (j < s.length() && s.charAt(j) == ')') {
                d[i] = d[i + 1] + 2; //(()())的外包情况
                if (j + 1 < s.length())
                    d[i] += d[j + 1];//()()的后面还有的情况
            }
        }
        maxLen = Math.max(maxLen, d[i]);
    }
    return maxLen;
}

—————————-用stack的做法———————————–

  1. stack里面装的一直是“还没配好对的那些可怜的括号的index”
  2. 是'(‘的时候push
  3. 是’)’的时候,说明可能配对了;看stack top是不是左括号,不是的话,push当前右括号
  4. 是的话,pop那个配对的左括号,然后update res:i和top的(最后一个配不成对的)index相减,就是i属于的这一段的当前最长。如果一pop就整个栈空了,说明前面全配好对了,那res就是最大=i+1
public int longestValidParentheses(String s) {
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    char[] arr = s.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
            stack.pop();
            if (stack.isEmpty())
                res = i + 1;
            else
                res = Math.max(res, i - stack.peek());
        } else {
            stack.push(i);
        }
    }
    return res;
}

这个题是非常常见的面试题,自己试着implement了两种方法,一个O(logn),一个O(n),但是写起来都不是很简洁。

O(n)的方法:binary search by start,找到一个要insert的位置(start1<start<=start2),取那个大的start2(因为它肯定会被start给replace掉,start1则不一定)。插入这个新interval,然后从头到尾检查overlap(两个参数无论谁前谁后都能用这个helper查出来),有就merge,不断吞噬overlap的。代码写起来有点长,不过思路非常清晰,不用考虑任何边界条件(什么a.start <= b.end…那些都烦死人了)。interview的时候可以写这种,因为binary search那段可能都不让你写。

还有一个trick是用iterator可以直接修改正在iterate的list,不会报modification exception,第一次用,很方便。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    int insertPosition = insertByStart(intervals, newInterval.start, 0, intervals.size() - 1);
    intervals.add(insertPosition, newInterval);
    Iterator<Interval> it = intervals.iterator();
    Interval prev = it.next();
    while (it.hasNext()) {
        Interval curr = it.next();
        if (overlap(prev, curr)) {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
            it.remove();
        } else {
            prev = curr;
        }
    }
    return intervals;
}
private int insertByStart(ArrayList<Interval> intervals, int x, int p, int q) {
    if (p > q)
        return p;
    int mid = (p + q) / 2;
    if (intervals.get(mid).start < x) {
        return insertByStart(intervals, x, mid + 1, q);
    } else {
        return insertByStart(intervals, x, p, mid - 1);
    }
}
private boolean overlap(Interval a, Interval b) {
    return within(a.start, b) || within(a.end, b) || within(b.start, a) || within(b.end, a);
}
private boolean within(int v, Interval b) {
    return v >= b.start && v <= b.end;
}

另一种方法是binary search,找出要start属于的位置,end属于的位置。但是很不好写,需要判断那些this.start >=that.end之类的,就更长了。回头看看能不能写简洁点。

Tags: , ,

不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。

算法:a / b

  1. a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
  2. 然后到了一定程度,b实在太大了,大于a剩余的部分了,那么就停止。然后剩下的a再一点点开始减,b回归成最开始的值,重做这两步。

重点是一旦超过,b应该不要一下回到原始值,而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的,搞得各种溢出,然后才发现Math.abs(MIN_VALUE)其实还是-2147483648(坑爹呢吧abs还是负数),而不是2147483648。

下面的解法是能跑过的。因为测试数据出现了-2147483648,还不能把它转成正的(2147483648就溢出了),所以直接全转换成long(64位),跑一遍就过了。

public int divide(int dividend, int divisor) {
    if (dividend == 0)
        return 0;
    if (divisor == 1)
        return dividend; //纯粹是为了防止超时
    boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
    long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
    long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
    int result = dividePositive(absDividend, absDivisor, absDivisor);
    return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
    if (p < q)
        return 0; //这个十分必要,否则会因为p > 0而直接下一层递归,pq永远不变,死循环了就。
    int result = 0;
    int e = 0;
    while (p >= q) { //等于应该也进去。
        result += 1 << e;
        p -= q;
        q = q << 1;
        e++;
    }
    return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
 }
Tags: , ,