Lexi's Leetcode solutions

Posts Tagged ‘undone

给一个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;
        }
    }
}
Advertisements
Tags: ,

private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}

private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

这题说的不清楚,其实T可以有重复字母,比如AAA,那S中必须包括3个A才行。不是包括A就行了。

自己的做法只能cover木有重复字母的情况。思路: 先把T中的每个字母在S中的位置记录下来,生成一个Map<Char, Queue<Index>>。然后像n个pipe一样,每次找到最小的和最大的head,然后算diff(即包括所有queue head的interval的长度)。用diff update resultLength。最后把最小的那个dequeue,然后新的head和max, min比较,update,都是O(1)的时间。这样是O(n) + O(n)。不过解决不了重复字母的问题。尼玛。。好不容易自己想出来一个。。

下次再想想怎么办,或者干脆看答案。

Tags: ,

这个是要算到达最后一步最少要跳几步。不用非的跳到last index上,越过去也算。

还是,用dp的话有重复,不需要算d[i]跳到每一步用的最小步数,只要算最后一步能不能跳到,最少用几步就行了。这题其实自己还不够理解,下次还得重做。

算法:在每一步i,都已知到当前这一点用的最小step数k(但是不是存在数组里的,而是local variable)。在每层小循环里,都是“走一步能到的这些点中”, 最远能到哪一点,记载为p,那么到p就能最少用k + 1步就能到了。如果p出了数组边界,直接返回k + 1,就做出来了。要是没出界,则小循环之后,继续下一层循环,但是下一层循环和当前循环不重合,因为下一层说明多走了一步,则k++, 那循环的起始部分就是上一个小循环的尾。(每层小循环的意义是:用k步能走到的这些点,都试探一下,看看从他们身上走一步最远能走到哪)。

public int jump(int[] A) {
 if (A.length == 0 || A.length == 1)
   return 0;
 int examingStart = 0;
 int currSectionCanReach = 0;
 int steps = 0;
 while (examingStart <= currSectionCanReach) {
   int examingEnd = currSectionCanReach;
   int nextSectionCanReach = examingStart;
   for (int i = examingStart; i <= examingEnd; i++) {
     nextSectionCanReach = Math.max(nextSectionCanReach, i + A[i]);
     if (nextSectionCanReach >= A.length - 1)
       return steps + 1;
   }
   examingStart = examingEnd + 1;
   currSectionCanReach = nextSectionCanReach;
   steps++;
 }
 return -1;
}