jjongpark
BAN USERSince the matrix is sparse, I would like to store the data in a hashmap of hashmap rather than the traditional [][].
class SparseMatrix {
private final Map<Integer, Map<Integer, Integer>> map;
private final int N;
private final int M;
SparseMatrix(int numRow, int numCol) {
N = numRow;
M = numCol;
map = new HashMap<>();
}
// assume 0 index
void set(int row, int col, int val) {
if (row < 0 || row >= N || col < 0 || col >= M) {
throw new IllegalArgumentException();
}
Map<Integer, Integer> rowMap = map.get(row);
if (rowMap == null) {
rowMap = new HashMap<>();
map.put(row, rowMap);
}
rowMap.put(col, val);
}
int sum(int row, int col) {
int sum = 0;
for(int r : map.keySet()) {
if (r <= row) {
for(int c : map.get(r).keySet()) {
if (c <= col) {
sum += map.get(r).get(c);
}
}
}
}
return sum;
}
}
abstract class Tree {
int value;
}
class Node extends Tree{
Tree left;
Tree right;
}
class Leaf extends Tree {
}
void printNodesInRange(Tree t, int from /* inclusive */, int to /* inclusive */) {
// if this is a leaf node, then just test if value is within the range
if (t instanceof Leaf) {
if (t.value >= from && t.value <= to) {
println (t.value);
}
}
else {
Node n = (Node)t;
if (n.value < from) {
// search only right subtree
printNodesInRange(n.right, from, to);
}
else if (n.value > to) {
// search only left subtree
printNodesInRange(n.left, from, to);
}
else {
// search both left and right with divided range
printNodesInRange(n.left, from, n.value);
printNodesInRange(n.right, n.value, to);
}
}
}
Using recursion:
define s(n): total number of valid cases with length n
define a(n): number of valid cases with length n starting with 'a'
define b(n): '' with 'b'
define c(n): '' with 'c'
base cases:
a(1) = 1 // "a" is the only valid string of length 1
b(1) = 1 // "b"
c(1) = 1 // "c"
s(1) = a(1) + b(1) + c(1)
s(n) = a(n) + b(n) + c(n) // the string can start with either a, b or c
a(n) = s(n-1) // "a" + any valid string of length n-1
b(n) = 1 + (n-1) + (n-2) // if "b" is the first character, the remaining string only consists of 'a' and 'c'.
// 1 is for "b" + "aaaa....a" is the only valid string with no 'c'
// (n-1) is for "b" + any valid string of length n-1 with only one 'c'
// (n-2) is for "b" + any valid string of length n-1 with only one 'cc'
c(n) = s(n-1) - 1 (if n >2)// "c" + any valid sting of length n-1 except for 'cc????'
= s(n-1) (if (n <= 2)
int a(int n) {
if (n == 1) return 1;
else return s(n-1);
}
int b(int n) {
if (n == 1) return 1;
else return 1 + (n-1) + (n-2);
}
int c(int n) {
if (n == 1) return 1;
else if (n == 2) return s(n-1);
else return s(n-1) - 1;
}
int s(int n) {
return a(n) + b(n) + c(n);
}
s(3) = a(3) + b(3) + c(3)
= s(2) + 4 + s(2) -1 = 2 * s(2) + 3
s(2) = a(2) + b(2) + c(2)
= s(1) + 2 + s(1) = 2 * s(1) + 2
s(1) = a(1) + b(1) + c(1) = 1 + 1+ 1 = 3
Therefore, s(2) = 2 * 3 + 2 =8
s(3) = 2 * 8 + 3 = 19 // correct
int[] addBy1(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Input must be non-empty array");
}
int[] newArray = new int[array.length];
int hasCarry = true
for(int i=newArray.length-1; i>=0; i--) {
int val = array[i] + (hasCarry ? 1 : 0);
newArray[i] = val % 10;
hasCarry = val / 10 == 1;
}
if (!hasCarry) {
return newArray;
}
else {
int[] temp = new int[array.length+1];
temp[0] = 1;
// other entries in temp should be 0
return temp;
}
}
// the class with id and weight
class SomeObj {
int id;
int weight;
SomeObj(int id, int weight) {
this.id = id;
this.weight = weight;
}
}
// the two arrays
SomeObj[] array1 = new SomeObj[] { ... };
SomeObj[] array2 = new SomeObj[] { ... };
SomeObj[] merge(SomeObj[] a1, SomeObj[] a2) {
// maps id to obj
Map<Integer, SomeObj> map = new HashMap<>();
// add objects in a1 to map
for(SomeObj o: a1) {
SomeObj entry = map.get(o.id);
if (entry == null) {
entry = new SomeObj(o.id, o.weight);
map.put(o.id, entry);
}
else {
// if same id is found, update its weight
entry.weight += o.weight;
}
}
// same for a2
for(SomeObj o: a2) {
SomeObj entry = map.get(o.id);
if (entry == null) {
entry = new SomeObj(o.id, o.weight);
map.put(o.id, entry);
}
else {
entry.weight += o.weight;
}
}
// convert the set of values to array and sort it based on weight
SomeObj[] result = new SomeObj[map.size()];
Arrays.sort(map.values().toArray(result), new Comp());
}
class Comp<SomeObj> implements Comparator<SomeObj> {
int compare(SomeObj o1, SomObj o2) {
return o1.weight - o2.weight;
}
}
Inspired by ricardolira48
The problem can be solved in O(n) time where n is the number of nodes.
Since the graph has no cycle, an edge e divides the graph into two sub graphs. For any path between the two graphs, the edge is always used exactly once. And there are (n1 * n2) number of possible paths between the sub-graphs (n1 is the number of nodes in sub-graph 1 and n2 is the number of the nodes in sub-graph 2). Therefore, the amount of value that the edge contributes to the final sum is 'w * n1 * n2, where w is the weight of the edge.
So, we basically calculate w * n1 * n2 for all edges and sum them up. Then how do we calculate n1 and n2? It is obvious that n1 + n2 = n, where n is the number of all nodes in the graph. So we need to only calculate either n1 or n2.
At this point, let's treat the graph as a tree by taking an arbitrary node as root. Note that this possible since the graph does not have any cycle.
Then, we can solve the problem by traversing the tree and sum up (w * size of a sub-tree * (n - size of a sub-tree) when visiting a node.
// convert the graph g into a tree with node n as the root.
Tree convertToTree(Graph g, Node n) {// left unimplemented; }
abstract class Tree {
int size; // number of nodes in a tree (including this node)
}
// Leaf node.
class Leaf extends Tree {
Leaf() {
size = 1; // size of the leaf node is always 1 since it is the only node
}
// returns the amount of values that the edge
// between this node and its parent node contributes to the final sum
int visit(int weight) {
// the edge is used to connect this node to other g.size -1 nodes.
return weight * (g.size - 1);
}
}
// non-leaf node
class Parent extends Tree {
List<Tree> children; // list of children
List<Integer> weights; // weight of edges for each child
int visit(int weight) {
int sum = 0;
int size = 1;
// visit child nodes
for(int i=0; i<children.size(); i++) {
// accumulate the sum
sum += children.get(i).visit(weights.get(i));
// accumulate the number of nodes under this node
size += children.get(i).size;
}
// consider edge from parent node to this node
sum += weight * size * (g.nodes.size() - size);
// update the size of this node (to be used by parent node)
this.size = size;
}
}
int sumOfAllPathWeights(Graph g) {
if (g.nodes.size == 0) { return 0;}
// convert to a tree by taking the first node as root
Tree t = convertToTree(g, g.nodes.get(0));
// the root node has no incoming edge so the initial weight is 0.
return t.visit(0);
}
I am also using bits to represent states.
long bulbs = 0L; // bit 0 for off, bit 1 for on
boolean isOn(int bulbIndex) {
if (bulbIndex >= sizeof(bulbs)*8 || bulbIndex < 0) {
throw new IllegalArgumentException(
"bulbIndex must in between 0 and " + sizeof(bulbs)*8);
}
// just test whether bit at bulbIndex is 1 or not.
return (bulbs & (1L << bulbIndex)) != 0;
}
void toggle(int left, int right) {
if (left > right) {
throw new IllegalArgumentException("left must be equal or smaller than right");
}
if (left < 0 || left >= sizeof(bulbs)*8 || right < 0 || right >= sizeof(bulbs)*8) {
throw new IllegalArgumentException("left or right must in between 0 and " + sizeof(bulbs)*8);
}
int totalNumBulbs = sizeof(bulbs)*8;
int numBulbsToToggle = right - left + 1;
// -1L >> (totalNumBulbs - numBulbsToToggle) is to clear bits after 'right'
// << left is to clear bits before left
// xor implements toggle
bulbs ^= (-1L >> (totalNumBulbs - numBulbsToToggle)) << left
}
Java code with O(n) performance
class City {
private final int population;
private final List<City> neighbors;
// this is to cache the calculated traffic value from this city to a neighbor city
private final Map<City, Integer> trafficCache;
public City(int population) {
this.population = population;
neighbors = new ArrayList<City>();
trafficCache = new HashMap<City, Integer>();
}
/**
* traffic from this city to city c
*/
private int trafficTo(City c) {
if (!neighbors.contains(c)) {
return 0;
}
// if we already calculated the value, return it immediately
if (trafficCache.contains(c)) {
return trafficCache.get(c);
}
// sum of all traffic from neighbors(except c) + pop. of this city
int traffic = 0;
for(City n: neighbors) {
if (n == c) { continue;}
traffic += n.trafficTo(this);
}
traffic += this.population;
// save the result for later use
trafficCache.put(c, traffic);
return traffic;
}
/**
* maximum traffic expected for this city
*/
int maximumTraffic() {
int maximum = 0;
// this is simply the maximum among traffic from neighbors
for(City n: neighbors) {
int traffic = n.trafficTo(this);
if (traffic > maximum) maximum = traffic;
}
return maximum;
}
}
Here is my code.
It converts (in-place) a min heap {1, 4, 2, 5, 6, 7, 3} to a correct BST {4, 2, 6, 1, 3, 5, 7}.
The basic idea is as follows:
1) Do the in-order traverse of the tree.
2) When visiting a node
2-1) extract min value from the heap
2-2) add value of the current node into the min heap
2-3) put the min value to the current node
This way, we are gradually converting the min heap into BST.
- jjongpark September 28, 2016