shou3301
BAN USERWe do not need to use extra space even we wanna use heap. We can make use of the array given to store result. For example, we can make use of the tail of the result array. At the beginning, the tail won't be touched, so we can use last n position in this array, and make it work as a heap.
- shou3301 December 24, 2012GasLeft[j] = GasLeft[i] + gas[i] - distance[i] (start point <= i < j)
GasLeft array keeps the record that the max gas can be left when arrive gas station j (starting from a certain gas station). If we find at some gas station the gas left is less than zero, it means the car can never reach that gas station.
Now we apply this idea to every gas station on the circle, and return the first gas station that has all its GasLeft positive.
Can we do better with this way?
public int findKth (int[][] mat, int m, int n, int k) {
if (k > m*n)
return -1; // Just an error code
int[] count = new int[m];
int total = 0;
// when there are still elements in the matrix
while (true) {
int min = Integer.MAX_VALUE;
int idx;
// Find the min one
for (int i = 0; i < m; i++) {
if (count[i] < n) {
if (mat[i][count[i]] < min) {
min = mat[i][count[i]];
idx = i;
}
}
}
total++;
count[idx]++;
if (total == k) {
return min;
}
}
}
In this way, the running time should be O(k*m), and we should always choose min(m, n) to use here. If I am wrong, please correct me. Thanks!
- shou3301 October 22, 2012The idea is to use backtracking.
class Solution {
private int count = 0;
private int expect;
private int size;
private int len;
public int subsetsSum (int[] val, int expect, int size) {
this.expect = expect;
this.size = size;
this.len = vl.length - 1;
backtrack (0, 0, 0, val);
return this.count;
}
private void backtrack (int idx, int currentSize, int currentVal, int[] val) {
// If meet the end of the array
if (idx > this.len)
return;
// If find a solution
if (currentSize == this.size && currentVal == this.expect) {
count++;
return;
}
// Soltuions
// Get current value
backtrack(idx + 1, currentSize + 1, currentVal + val[idx], val);
// Do not get current value
backtrack(idx + 1, currentSize, currentVal, val);
}
}
I think backtracking is really straightforward.
class Solution {
private List<List<Integer>> paths = new ArrayList<List<Integer>>();
public List<List<Integer>> getPaths(Node root) {
backtrack(0, new ArrayList<Integer>(), root);
return paths;
}
private void backtrack(int level, List<Integer> path, Node current) {
if (current == null)
return;
if (current.getChildren() == null) {
List<Integer> newPath = path.clone();
paths.add(newPath);
return;
}
for (Node child : current.getChildren()) {
path.add(child);
backtrack(level+1, path, child);
path.remove(path.size() - 1);
}
}
}
class Solution {
// the method to call
public int numConnected(int[][] mat) {
int w = mat[0].length;
int h = mat.length;
int[][] visited = new int[h][w];
int sum = 0;
// init visited matrix
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
visited[i][j] = 0;
}
/* For each point, flood it;
If it is a new connected component, then skip;
Otherwise, count++;
*/
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
sum += flood(i, j, mat, visited);
}
}
return sum;
}
private int flood(int x, int y, int[][] mat, int[][] visited) {
if (visited[x][y] == 1)
return 0;
if (mat[x][y] == -1) {
visited[x][y] = 1;
flood(x+1, y, mat, visited);
flood(x, y+1, mat, visited);
flood(x-1, y, mat, visited);
flood(x, y-1, mat, visited);
return 1;
}
return 0;
}
}
Using n/2 is not necessary. It still takes k*T (T is the time cost to do a single matrix multiplication) on the kth recursion level. Thus the total running time is still O(T*n).
- shou3301 December 28, 2012