Posts Tagged ‘hard’
- In: leetcode
- 2 Comments
还是两个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;
}
Hands down，这是我leetcode做的最难的题top 5。别的都是可以用算法说得通的，这题就是纯数学。我这辈子最怕的就是数学，要死要活。
几个要点：
- 找没用过的里面的第(k – 1) / (n – 1)!个数字，放第一位上
- k = (k – 1) % (n – 1)!，第一个数字确定了，剩下这些里面重新找第k个。
- 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);
}
[leetcode] Palindrome Partitioning 2 | 一个String最少切几刀能让分成的substring全是palindrome
Posted on: October 20, 2013
非常非常难，用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。
算法：
- 首先把每个substring是不是palindrome先二维dp的做出来，参见上一题的分析。其实这一步可以合在下一步里，但是下一步本身的logic就够难想了，所以这里分开来写。
- 一维dp（为神马是一维啊！！头一次看这样的一维啊！！一维dp却是两层循环啊卧槽！！！），d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
- 把d[i]先赋成最大值。
- 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];
}
- In: leetcode
- 6 Comments
括号题也不是只用stack才能做，这题是算长度，所以stack那种一match就俩一起pop了的方式就不适合了。求极值，一维dp最好使。
- d[i]: 以i开头的最长valid parentheses有多长。
- d[i] =
- if (str[i] == ‘)’)，以右括号开头必定invalid，d[i] = 0
- if (str[i] == ‘(‘)，以左括号开头
- 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾，所以我们想catch((…))这种情况。j = i + 1 + d[i + 1]，正好就是str[i]后面越过完整sequence的下一个，若是右括号，d[i] = 2 + d[i + 1]
- 除此之外，还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况，如((..))()()()。所以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的做法———————————–
- stack里面装的一直是“还没配好对的那些可怜的括号的index”
- 是'(‘的时候push
- 是’)’的时候，说明可能配对了；看stack top是不是左括号，不是的话，push当前右括号
- 是的话，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之类的，就更长了。回头看看能不能写简洁点。
不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的，所以到最后还得不断缩小范围，好能贴近结果。
算法：a / b
- a本来是想一直-b，然后减到<0了，算counter。但是这样慢，所以类似c++ vector的思路，每次发现还没减没，那减数就翻倍（b <<= 1）
- 然后到了一定程度，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;
}
- In: leetcode
- 5 Comments
有点后悔，这个题当时看了就好了，T家真的就考了类似的。要是看了就不至于现场出现当天同时买卖那个bug；从后往前scan array也不会那么生疏。。G家也是，要是看了CC150那道题就不会挂在拓扑排序上。没事，记住教训就好了——题是不能越过去的，越是skip的越有考的可能。
这个题一开始是二分法做的，每次切一刀然后左边O(n)做一次右边O(n)做一次，整体是O(n^2)，超时。正确方法是一维dp从左到右扫一遍，再从右到左扫一遍，然后两次加和。
两个一维数组的定义一定要搞清，onsite的时候就栽在这上面了！
- d[i]: [0…i]这段时间的买卖一次的最大利润。所以i应该从1开始。
- f[i]: [i…n – 1]这段时间的买卖一次的最大利润。所以i应该最大n – 2。
- 然后就看出问题了——两个i不能同步，否则就当天买卖了。最后加和的时候要错开。
- 因为“最多买卖两次”， 所以还要包括买卖一次的情况。用d[n-1]就是[0…n-1]可以表达这种情况。
public int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int[] d = buildMaxProfitFromStart(prices);
int[] f = buildMaxProfitFromEnd(prices);
int maxProfit = d[prices.length - 1];
for (int i = 0; i < prices.length - 1; i++) {
maxProfit = Math.max(maxProfit, d[i] + f[i + 1]);
}
return maxProfit;
}
private int[] buildMaxProfitFromEnd(int[] arr) {
int[] f = new int[arr.length];
f[arr.length - 1] = 0;
int max = arr[arr.length - 1];
int maxProfit = 0;
for (int i = arr.length - 2; i >= 0; i--) {
maxProfit = Math.max(maxProfit, max - arr[i]);
max = Math.max(max, arr[i]);
f[i] = maxProfit;
}
return f;
}
private int[] buildMaxProfitFromStart(int[] arr) {
int[] d = new int[arr.length];
d[0] = 0;
int min = arr[0];
int maxProfit = 0;
for (int i = 1; i < arr.length; i++) {
maxProfit = Math.max(maxProfit, arr[i] - min);
min = Math.min(min, arr[i]);
d[i] = maxProfit;
}
return d;
}
这个题尽管是CC150上的，理论上很简单，但是想明白（而且用好的方法）很不容易。
1. 数组没有重复
- 既然是断开一次的数组，说明A[p] > A[q]。我们从中间一刀划分，想出找sorted那一半，看是否包含x，包含的话就在sorted那一半找；不包含就在broken那一半找。
- 这个是根据A[mid]和A[p]来初步划分，平时binary search都是根据A[mid]和x来直接划分。所以一开始做复杂了。这个题按上面说的定义做最好，简单易懂。
- 当A[mid] == A[p]的时候，说明mid==p，就左边这一个点，既然已经判断过A[mid] != x了，所以直接找右边就好了。
public int search(int[] A, int target) {
return find(A, 0, A.length - 1, target);
}
private int find(int[] arr, int p, int q, int x) {
if (p > q)
return -1;
int mid = (p + q) / 2;
if (arr[mid] == x)
return mid;
if (arr[p] < arr[mid]) { // left is ordered, right is broken
if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
return find(arr, p, mid - 1, x);
else // x doesn't belong to left ordered part
return find(arr, mid + 1, q, x);
} else if (arr[p] > arr[mid]) {// left is broken, so right is ordered
if (arr[mid] <= x && x <= arr[q])
return find(arr, mid + 1, q, x);
else
return find(arr, p, mid - 1, x);
} else { // a[p] == a[mid], directly search right
return find(arr, mid + 1, q, x);
}
}
2. 数组有重复数字
- 还是从中间一刀划分，想找出sorted那一半，看是否包含x。
- 但是当A[p] == A[mid]的时候，不能说明左边就是长度为1的一半了。左边可以是全是repeat，也可以是包含x。
- 这时要和A[q]比较，如果A[mid] == A[q]，总不能整个数组平了吧。这时候x可以是左边也可以是在右边，必须两边找。
- 如果A[mid] != A[q]，说明右半部分有起伏，左边的平的这段就不能有起伏了（自己画一下吧）。所以还是找右边。
public boolean search(int[] A, int target) {
return find(A, 0, A.length - 1, target) >= 0;
}
private int find(int[] arr, int p, int q, int x) {
if (p > q)
return -1;
int mid = (p + q) / 2;
if (arr[mid] == x)
return mid;
if (arr[p] < arr[mid]) { //left is ordered, right is broken
if (arr[p] <= x && x <= arr[mid]) // x is in the left ordered part
return find(arr, p, mid - 1, x);
else //x doesn't belong to left orderd part
return find(arr, mid + 1, q, x);
} else if (arr[p] > arr[mid]) {//left is broken, so right is ordered
if (arr[mid] <= x && x <= arr[q])
return find(arr, mid + 1, q, x);
else
return find(arr, p, mid - 1, x);
} else { // arr[p] = arr[mid], don't know which side is broken
if (arr[mid] == arr[q]) {
int leftResult = find(arr, p, mid - 1, x);
return leftResult == -1 ? find(arr, mid + 1, q, x) : leftResult;
} else { //mid is not equals right, so left is all repeats, search right
return find(arr, mid + 1, q, x);
}
}
}
Tags: binarySearch, hard
- In: leetcode
- 3 Comments
这是好难好难的二维DP题。尽管知道两个String比较很可能是二维DP，但是状态方程真是不好定义；定义了关系也特别不直观。
A: RABBBIT; B: RABBIT
- d[i][j]: A[0…i]里面出现了几次B[0…j]，比如RAB里出现了几次RA
- d[i][j] =
- if A[i] != B[j]，比如RABC和RAB，那么C(A[i]就得被删除，d[i][j]就是RAB在RAB包含的之前算过的情况d[i – 1][j]
- if A[i] == B[j]，比如RABB和RAB，那么
- 可以把RABB的第二个B删除得到RAB，所以d[i][j]最少也是d[i – 1][j]
- 可以用RABB的第二个B直接对应RAB的那个B消掉，所以相当于A=RAB和B=RA，d[i][j] += d[i – 1][j – 1]
- 初始值就是二维DP那么做就行了。
- 这个是真心难想通。还得多做多练习。
public int numDistinct(String S, String T) {
if (T.length() > S.length())
return 0;
char[] A = S.toCharArray();
char[] B = T.toCharArray();
int[][] d = new int [A.length][B.length];
d[0][0] = A[0] == B[0] ? 1 : 0;
int count = d[0][0];
for (int i = 1; i < A.length; i++) {
if (A[i] == B[0])
count++;
d[i][0] = count;
}
for (int j = 1; j < B.length; j++) {
d[0][j] = 0;
}
for (int i = 1; i < A.length; i++) {
for (int j = 1; j < B.length; j++) {
if (A[i] == B[j]) {
d[i][j] = d[i - 1][j] + d[i - 1][j - 1];
} else {
d[i][j] = d[i - 1][j];
}
}
}
return d[A.length - 1][B.length - 1];
}
Lexi's Leetcode solutions 