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;
}
}
}
[onsite] 找两个排好序的数组中的第k大的数
Posted on: August 24, 2013
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)。不过解决不了重复字母的问题。尼玛。。好不容易自己想出来一个。。
下次再想想怎么办，或者干脆看答案。
[leetcode] Jump Game 2
Posted on: July 21, 2013
这个是要算到达最后一步最少要跳几步。不用非的跳到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;
}
Lexi's Leetcode solutions 