Archive for November 2nd, 2013
[leetcode] Longest Substring Without Repeating Characters | 最长的unique char组成的substring
Posted on: November 2, 2013
这题完全没印象，后来发现是之前做用了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);
}
- In: leetcode | summery
- Leave a Comment
- d[i][j]表示从(0, 0)到(i, j)有几种走法，因为只能从上面来或从左边来，所以每次计算只需要d[i – 1][j]和d[i, j – 1]，左上角的全都浪费了。
- f[i]表示从(0,0)到(当前row, j)有几种走法，上面来的就是自己，左边来的已经算好了，所以 f[j] = f[j] + f[j – 1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
// one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
int f[] = new int[n];
f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) { //comes from above or left
if (obstacleGrid[i][j] > 0) {
f[j] = 0;
} else {
if (j == 0) //first col only from above
f[j] = f[j];
else
f[j] = f[j] + f[j - 1];
}
}
}
return f[n - 1];
}
