Lexi's Leetcode solutions

如果两个field没关系,可以生成两个锁,这样update c1必须是synchronized, c2也是。但是要是直接synchronize两个函数,说明update c1的时候c2也得干瞅着,浪费了。就跟reader writer类似,read的时候另一个reader明明也可以read的,但要是完全上锁,则read, write都要等别人了。

public class Foo {
ReentrantLock L1 = new ReentrantLock();
ReentrantLock L2 = new ReentrantLock();
int c1, c2;

public void incrementC1 {
synchronized(L1) {
c1++;
}
}

public void incrementC2 {
L2.lock();
c2++;
L2.unlock();
}
}

 

一种用lock,一种用synchronized object的区别就是,用lock的可以手动处理c2++ throw exception的情况,而用synchronized出了scope索就自动丢了。

给一个String[] L,里面可以有重复,在S里找能包括所有L且都只出现一次的window的start。比如foobarthebarfooman, L={foo, bar}, return 0, 9.
这题正经做了一段时间。

public ArrayList<Integer> findSubstring(String S, String[] L) {
    final Map<String, Integer> need = new HashMap<String, Integer>();
    for (int i = 0; i < L.length; i++) {
        need.put(L[i], need.get(L[i]) == null ? 1 : need.get(L[i]) + 1);
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < L[0].length(); i++) {
        populateResult(result, S, L, i, need);
    }
    return result;
}
private void populateResult(ArrayList<Integer> result, String S, String[] L, 
                            int start, final Map<String, Integer> need) {
    int k = L[0].length();
    HashMap<String, Integer> has = new HashMap<String, Integer>();
    for (int end = start; end <= S.length() - k; end += k) {
        String sub = S.substring(end, end + k);
        if (need.containsKey(sub)) {
            while (has.get(sub) == need.get(sub)) {
                String tmp = S.substring(start, start + k);
                has.put(tmp, has.get(tmp) - 1);
                start += k;
            }
            has.put(sub, has.get(sub) == null ? 1 : has.get(sub) + 1);
            if (end - start + k == L.length * L[0].length())
                result.add(start);
        } else {
            has.clear();
            start = end + k;
        }
    }
}
Tags: ,

算法:

  • arch代表穿过当前节点的路径(左边一支儿+自己节点+右边一支儿)。
  • 注意树的节点可以是负数,所以arch不一定是最长的。
  • 每次return以root(当前节点)开头最大的单只path sum。
  • res[]就是一个存result的reference object,java不支持c++那种直接&传reference,
    所以要么用个长度为一的数组,要么写个wrapper。还是用数组简单。
  • update res[0],用arch和以自己开头一支儿的比,谁大就把res[0] update成谁。
public int maxPathSum(TreeNode root) {
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    maxPath(root, res);
    return res[0];
}
private int maxPath(TreeNode root, int[] res) {
    if (root == null)
        return 0;
    int left = maxPath(root.left, res);//左边一支儿(不算自己)
    int right = maxPath(root.right, res);
    int arch = left + right + root.val; //穿过自己
    int single = Math.max(root.val, Math.max(left, right) + root.val);
    //(算上自己)
    res[0] = Math.max(res[0], Math.max(arch, single));//update结果
    return single;
}
Tags: ,

这题太经典了,在amz wiki上见过解法,才知道可以把指数分一半,从O(n)改成O(logn)。有几个要注意的地方:

  1. 初中数学不会了。(-2)^(-3) = 1 / (-2)^3。所以正负号还是和指数是否是偶数有关。
  2. 不要分四种情况讨论,简洁的代码是如果n<0,则直接/x,因为前面算好half的也是1/something的!
  3. 要特别讨论x == 0的情况,因为后面要1/x,不想挂在这吧。
public double pow(double x, int n) {
    if (x == 0)
        return 0;
    return power(x, n);
}
private double power(double x, int n) {
    if (n == 0)
        return 1;
    double left = power(x, n / 2);
    if (n % 2 == 0) {
        return left * left;
    } else if (n < 0) {
        return left * left / x;
    } else {
        return left * left * x;
    }
}
Tags:

a->b->c->d->e => a->e->b->d->c,要求inplace,不能用额外空间(要不然直接reverse成另一个就好办了),不能直接改动list的值。

这题有点写长了,过一阵看看网上有没有好点的做法。O(n)。

算法:

  1. 过一遍算出总长度len
  2. 再过一遍找到中点或第二部分的第一个点(a->b->c->d->e和a->b->c->d的都是c)
  3. reverse后半部分,变成a->b->c<-d<-e 或者 a->b->c<-d,最后中点c的next置空
  4. 两头穿插合并,直到找到c这点。c肯定是一起找到(奇数)或者右半部分先找到(偶数)
public void reorderList(ListNode head) {
    if (head == null)
        return;
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }
    p = head;
    for (int k = 0; k < len / 2; k++) {
        p = p.next;
    } //p points to mid point
    ListNode curr = p.next, next;
    p.next = null;
    while (curr != null) { //开始reverse后半部分
        next = curr.next;
        curr.next = p;
        p = curr;
        curr = next;
    }//now p points to the last ele
    ListNode h = head;
    while (h.next != p && h != p) {
        ListNode tempH = h.next;
        ListNode tempP = p.next;
        h.next = p;
        p.next = tempH;
        h = tempH;
        p = tempP;
    }
}
Tags:

几道典型two pointers一快一慢题。记住j要匀速的走,i指向最终想要的数组的最后一个元素(或者倒数第二个,或者第一个可以被change的。。因题而异)。做的挺焦躁的,记下来对比练习:

1. Remove Elements:一个数组,删掉所有出现的x,返回新长度。

  • 两个pointer,一个正常走,一个指向真正去掉x的数组的长度。
  • public int removeElement(int[] A, int elem) {
        int i = 0;
        for (int j = 0; j < A.length; j++) {
            if (A[j] != elem) { //should be used 
                A[i] = A[j];
                i++;
            }
        }
        return i;
    }

2. 一个排好序的数组,删掉所有重复,让新数组每个数字只出现一次,返回新数组长度。不许用额外空间。

  • i指向最后一个保证valid的元素
  • j指向当前exam的元素,所以从1开始;当A[j] == A[i]的时候,说明A[j]是个invalid的,所以接着走
  • 可以看出来j肯定走的比i快,所以不用担心i的出界问题
  • public int removeDuplicates(int[] A) {
        if (A.length == 0)
            return 0;
        int i = 0; //right most valid element
        for (int j = 1; j < A.length; j++) {
            if (A[j] != A[i]) { //when not equals to right most valid, means this is also valid, extend the valid array
                i++;
                A[i] = A[j];
            }
        }
        return i + 1; 
    }

3.每个数字最多出现两次,比如1, 1, 1, 2, 2, 3 => 1, 1, 2, 2, 3

  • 同样,是当前exam的元素和valid array的最后一个(其实这里是倒数第二个)元素比较,而不是A[j]和A[j – 1]比较。后者就要混乱很多。
  • public int removeDuplicates(int[] A) {
        if (A.length < 2)
            return A.length;
        int i = 1;
        for (int j = 2; j < A.length; j++) {
            if (A[j] == A[i - 1]) {
                continue;
            } else {
                i++;
                A[i] = A[j];
            }
         }
         return i + 1;
    }

4. 单链表,删除所有出现过两次或以上的元素,比如1->1->2->2->2 => null

  • 同样,i指向最后一个valid元素,j是当前exam的
  • 但是当A[i] == A[j]的时候,i要缩短,所以要keep一个prev pointer
  • j一定要每次都往后走,保证匀速,千万别i动了j却没动。就挂在这了。
  • public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, i = head, j = head.next;
        while (j != null) {
            if (i.val == j.val) {
                while (j != null && i.val == j.val) {
                    i.next = j.next; //remove j
                    j = j.next;
                }
                prev.next = i.next; //remove i
                i = prev.next;
                j = i == null ? null : i.next;
            } else {
                j = j.next;
                i = i.next;
                prev = prev.next;
            }
        }
        return dummy.next;
    }

这题完全没印象,后来发现是之前做用了string.indexOf这个函数cheat成功了。这也是two pointers一快一慢的练习题,挺难做的,需要重做。

  • i:当前unique substring的头
  • j:当前unique substring的尾
  • 注意最后可能忘记算最后一段的长度了(因为dup那个条件已经不存在)
public int lengthOfLongestSubstring(String s) {
    int i = 0, len = 0, n = s.length();
    char A[] = s.toCharArray();
    Set<Character> set = new HashSet<Character>();
    for (int j = 0; j < n; j++) {
        if (set.contains(A[j])) { //found dup
            len = Math.max(len, j - i);
            while (i < n && A[i] != A[j]) {
                set.remove(A[i]);
                i++;
            }
            i++;
        } else {
            set.add(A[j]);
        }
    }
    return Math.max(len, n - i);
}