Archive for November 2013
- In: leetcode
- 5 Comments
遇见这种matrix题就腿发软，bf给讲了个四条边bound的方法，立刻15分钟bug free了。高兴够呛。
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int k = 1;
int top = 0, bottom = n - 1, left = 0, right = n - 1;
while (left < right && top < bottom) {
for (int j = left; j < right; j++) {
res[top][j] = k++;
}
for (int i = top; i < bottom; i++) {
res[i][right] = k++;
}
for (int j = right; j > left; j--) {
res[bottom][j] = k++;
}
for (int i = bottom; i > top; i--) {
res[i][left] = k++;
}
left++;
right--;
top++;
bottom--;
}
if (n % 2 != 0)
res[n / 2][n / 2] = k;
return res;
}
Tags: matrix
[leetcode] Valid Number
Posted on: November 23, 2013
- In: leetcode
- 7 Comments
这就是典型的try and fail，尼玛谁知道什么算是数什么不算啊？让我用眼睛看我也不知道啊！总之，试出来的规则是这样的：
- AeB代表A * 10 ^ B
- A可以是小数也可以是整数，可以带正负号
- .35, 00.神马的都算valid小数；就”.”单独一个不算
- B必须是整数，可以带正负号
- 有e的话，A,B就必须同时存在
算法就是按e把字符串split了，前面按A的法则做，后面按B做。
public boolean isNumber(String s) {
s = s.trim();
if (s.length() > 0 && s.charAt(s.length() - 1) == 'e')
return false; //avoid "3e" which is false
String[] t = s.split("e");
if (t.length == 0 || t.length > 2)
return false;
boolean res = valid(t[0], false);
if (t.length > 1)
res = res && valid(t[1], true);
return res;
}
private boolean valid(String s, boolean hasDot) {
if (s.length() > 0 && (s.charAt(0) == '+' || s.charAt(0) == '-')) //avoid "1+", "+", "+."
s = s.substring(1);
char[] arr = s.toCharArray();
if (arr.length == 0 || s.equals("."))
return false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '.') {
if (hasDot)
return false;
hasDot = true;
} else if (!('0' <= arr[i] && arr[i] <= '9')) {
return false;
}
}
return true;
}
Tags: math
- In: leetcode
- 3 Comments
这个题要用反证法来理解。算法：
- 从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
- 如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？假设能从k (i <=k<=j)走，那么i..j < 0，若k..j >=0，说明i..k – 1更是<0，那从k处就早该断开了，根本轮不到j。
- 所以一旦sum<0，i就赋成j + 1，sum归零。
- 最后total表示能不能走一圈。
- 这个题算法简单，写起来真是够呛。对数组一快一慢双指针的理解还是不行。注意千万不能出现while (i < 0) { i++, A[i]}这种先++然后取值的情况，必须越界。
public int canCompleteCircuit(int[] gas, int[] cost) {
int i = 0, j = 0;
int sum = 0;
int total = 0;
while (j < gas.length) {
int diff = gas[j] - cost[j];
if (sum + diff < 0) {
i = j + 1;
sum = 0;
} else {
sum += diff;
}
j++;
total += diff;
}
return total >= 0 ? i : -1;
}
[leetcode] Triangle
Posted on: November 18, 2013
这题其实和robot一样，每个点取决于从上到自己和从左上角到自己哪个小，但是一变成一维dp就做了好久。主要是因为这个不是取决于头顶和左边了，而是头顶和左上角，于是需要一个临时数组。
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
int res = Integer.MAX_VALUE;
int[] d = new int[triangle.get(triangle.size() - 1).size()];
d[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
int rowSize = triangle.get(i).size();
int[] tmp = new int[rowSize];
for (int j = 0; j < rowSize; j++)
tmp[j] = d[j];
for (int j = 0; j < triangle.get(i).size(); j++) {
int fromAbove = j < rowSize - 1 ? d[j] : Integer.MAX_VALUE;
int fromUpperLeft = j > 0 ? tmp[j - 1] : Integer.MAX_VALUE;
d[j] = Math.min(fromAbove, fromUpperLeft) + triangle.get(i).get(j);
}
}
for (int i = 0; i < d.length; i++) {
res = Math.min(res, d[i]);
}
return res;
}
Tags: 2WayDP
- 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;
}
如果两个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;
}
}
}
算法：
- 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;
}
[leetcode] Pow(x, n) | 指数运算
Posted on: November 4, 2013
这题太经典了，在amz wiki上见过解法，才知道可以把指数分一半，从O(n)改成O(logn)。有几个要注意的地方：
- 初中数学不会了。(-2)^(-3) = 1 / (-2)^3。所以正负号还是和指数是否是偶数有关。
- 不要分四种情况讨论，简洁的代码是如果n<0，则直接/x，因为前面算好half的也是1/something的！
- 要特别讨论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: math
Lexi's Leetcode solutions 