-
第 11 楼 / webdriver
- 时间: 2014-9-28 21:20算法问题推荐解法来了...
Use first row and column as auxiliary spaces instead of newly allocating ones.
解法（Java）
代码:
public class SetMatrixZeroes {
public void setZeroes(int[][] matrix) {
int row = matrix.length;
if (row == 0)
return;
int col = matrix[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
for (int k = 0; k < col; k++) {
if (matrix[i][k] != 0)
matrix[i][k] = -1;
}
for (int f = 0; f < row; f++) {
if (matrix[f][j] != 0)
matrix[f][j] = -1;
}
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = 0;
}
}
}
}
} -
-
- 时间: 2014-9-28 21:21S算法问题: Simplify Path
问题描述:
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo". -
-
- 时间: 2014-9-28 21:22算法问题推荐解法来了...
Add an additional '/' at the end of 'path' for simply detecting the end.
解法（Java）
代码: import java.util.LinkedList;
import java.util.List;
public class SimplifyPath {
public String simplifyPath(String path) {
int length = path.length();
if (length == 0)
return path;
List<String> dicts = new LinkedList<String>();
int slow = 0;
int fast = 0;
while (true) {
while (slow < length && path.charAt(slow) == '/') {
slow++;
}
if (slow >= length)
break;
fast = slow;
while (fast < length && path.charAt(fast) != '/') {
fast++;
}
String s = path.substring(slow, fast);
if (s.equals("..")) {
if (!dicts.isEmpty()) {
dicts.remove(dicts.size() - 1);
}
} else if (!s.equals(".")) {
dicts.add(s);
}
slow = fast;
}
StringBuffer ret = new StringBuffer();
for (String s : dicts) {
ret.append('/');
ret.append(s);
}
return ret.length() == 0 ? "/" : ret.toString();
}
}
-
- 时间: 2014-9-28 21:23
-
- 时间: 2014-9-28 21:24算法问题推荐解法来了...
Count the number of each bit.
解法（Java）
代码: public class SingleNumberII {
public int singleNumber(int[] A) {
int ones = 0, twos = 0, xthrees = 0;
for (int i = 0; i < A.length; ++i) {
twos |= (ones & A[i]);
ones ^= A[i];
xthrees = ~(ones & twos);
ones &= xthrees;
twos &= xthrees;
}
return ones;
}
}
-
- 时间: 2014-9-28 21:26
-
- 时间: 2014-9-28 21:27
-
- 时间: 2014-9-28 21:30S算法问题: Sort Colors
问题描述:
Given an array with n objects colored red, white or blue, sort them so that objects of the same color
are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with
total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space? -
- 时间: 2014-9-28 21:31算法问题推荐解法来了...
0 0 0 1 1 1 1 ...... 2 2 2 2
| | |
zero i two
-> -> <-
解法（Java）
代码:
public class SortColors {
public void sortColors(int[] A) {
int length = A.length;
int left = -1;
int right = length;
int i = 0;
while (i < right) {
if (A[i] == 0) {
swap(A, ++left, i++);
} else if (A[i] == 2) {
swap(A, i, --right);
} else {
i++;
}
}
}
private void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
} -
- 时间: 2014-9-28 21:34
Leetcode Hacking Practice -- Solution in Java Part 3
