mger1979
BAN USERUPD: Sorry did not understand task.
Code in Java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class TestClass{
public static void main(String[] args) {
City c1 = new City(1);
City c2 = new City(2);
City c3 = new City(3);
City c4 = new City(4);
City c5 = new City(5);
City c7 = new City(7);
City c15 = new City(15);
City c8 = new City(8);
City c38 = new City(38);
c1.neighbors.add(c5);
c2.neighbors.add(c5);
c3.neighbors.add(c5);
c4.neighbors.add(c5);
c2.neighbors.add(c7);
c2.neighbors.add(c15);
c5.neighbors.add(c1);
c5.neighbors.add(c3);
c5.neighbors.add(c4);
c5.neighbors.add(c2);
c7.neighbors.add(c2);
c15.neighbors.add(c2);
c8.neighbors.add(c7);
c7.neighbors.add(c8);
c8.neighbors.add(c38);
c38.neighbors.add(c8);
Queue<City> queue = new LinkedList<City>();
int totalPopulation = 0;
for (City c : new City[] { c1, c2, c3, c4, c5, c7, c15, c8 , c38 }) {
totalPopulation += c.population;
if (c.neighbors.size() == 1) {
queue.add(c);
}
}
while (!queue.isEmpty()) {
City c = queue.remove();
int maxPopulation = totalPopulation - c.sumPopulation - c.population;
maxPopulation = maxPopulation > c.maxPopulation ? maxPopulation : c.maxPopulation;
System.out.println(c.population + ":" + maxPopulation);
if (c.neighbors.isEmpty()) {
continue;
}
City linked = c.neighbors.iterator().next();
linked.neighbors.remove(c);
if (linked.neighbors.size()==1) {
queue.offer(linked);
}
linked.maxPopulation = linked.maxPopulation < c.sumPopulation + c.population ? c.sumPopulation
+ c.population : linked.maxPopulation;
linked.sumPopulation += c.population + c.sumPopulation;
}
}
static class City {
int population;
Set<City> neighbors = new HashSet<City>();
// helpers
int maxPopulation;
int sumPopulation;
City(int population) {
this.population = population;
}
}
}
Java solution without recursion
Complexity is O(2N)
Memory usage ~ N elements
1. Search for the middle of list
2. Split into two lists by middle
3. Reverse second list
4. Mix two list.
public class TestClass{
public static void main(String[] args) {
Node root = new Node(null, "1");
Node node = root;
for (int i = 2; i < 7; i++) {
node.next = new Node(null, i + "");
node = node.next;
}
node = findMiddle(root);
node = reverse(node);
mixTwoList(root, node);
print(root);
}
static void mixTwoList(Node one, Node two) {
while (one != null && two != null) {
Node oneNext = one.next;
Node twoNext = two.next;
one.next = two;
two.next = oneNext;
one = oneNext;
two = twoNext;
}
}
static Node findMiddle(Node root) {
Node preMiddle = null;
Node middle = root;
Node end = root;
while (middle != null && end != null && end.next != null) {
preMiddle = middle;
middle = middle.next;
end = end.next.next;
}
if (end != null) {
preMiddle = middle;
middle = middle.next;
}
// should split list in the middle
preMiddle.next = null;
return middle;
}
public static Node reverse(Node node) {
Node next = node.next;
node.next = null;
while (node != null && next != null) {
Node lnext = next.next;
Node lnode = next;
next.next = node;
node = lnode;
next = lnext;
}
return node;
}
static void print(Node node) {
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println("");
}
static class Node {
String value;
Node next;
public Node(Node next, String value) {
this.next = next;
this.value = value;
}
}
}
Task is incorrect.
Probably it is required to find such I and B where B+I is minimum.
public class TestClass{
public static void main(String[] args) {
int n = 12;
int i = (int) Math.sqrt((double) n);
int b = (int) Math.round((double) n / (double) i);
System.out.println(n + ": " + i + "x" + b);
}
}
It is very nice idea but I can't understand a few things
1) Why you do this
count += Math.abs(subSet.first().second - subSet.last().second)+1;
See, you have done
treeSet.add(new Pair(cumsum, i));
where i is index of element. It is NOT the index of cumsum in TreeSet and you put it into second field.
So the expression
'Math.abs(subSet.first().second - subSet.last().second)+1;' is equal to the number of ELEMENTS between Sa and Sb
Yes in case when cumsum is increasing because of only positive values it will be the same as size() but what about the negative values case? It will not work!
You can check this for example input {1,2,-3,4,5} a=-100,b=100
2) It seems there are some error in calculation
For instance for input { 5,2,4,7} a=0, b=10 your code will return 8 but the right answer is 6
In java it is very simple.
The following code demonstrating 3 ways of doing this with time comparison
package TEST;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestBT {
public static void main(String[] args) {
// filling trees
Integer[] valuesA = new Integer[100000];
for (int i = 0; i < 100000; i++) {
valuesA[i] = i;
}
Integer[] valuesB = new Integer[100000];
for (int i = 99999; i >= 0; i--) {
valuesB[i] = i;
}
Node rootA = fillAsBinaryTreeUseFlatData(valuesA);
Node rootB = fillAsBinaryTreeUseFlatData(valuesB);
final int MAX_CIRCLE = 100;
long start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsTreeSet(rootA, rootB);
}
System.out.println("checkAsTreeSet: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkSimple(rootA, rootB);
}
System.out.println("checkSimple: " + (new Date().getTime() - start));
start = new Date().getTime();
for (int i = 0; i < MAX_CIRCLE; i++) {
checkAsMixedSet(rootA, rootB);
}
System.out.println("checkAsMixedSet: " + (new Date().getTime() - start));
if (checkAsMixedSet(rootA, rootB)) {
System.out.println("the same");
} else {
System.out.println("not the same");
}
}
public static boolean checkSimple(Node rootA, Node rootB) {
// starting to compare
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
// yes Set will compare collections, but if this is uncomfortable
// for you then you can use alternative way setA.containsAll(setB)
return setA.equals(setB);
}
public static boolean checkAsTreeSet(Node rootA, Node rootB) {
// starting to compare
TreeSet<Integer> setA = new TreeSet<Integer>();
TreeSet<Integer> setB = new TreeSet<Integer>();
recursive(rootA, setA);
recursive(rootB, setB);
if (setA.size() == setB.size()) {
Iterator<Integer> iterA = setA.iterator();
Iterator<Integer> iterB = setB.iterator();
while (iterA.hasNext()) {
if (iterA.next() != iterB.next()) {
return false;
}
}
}
return true;
}
public static boolean checkAsMixedSet(Node rootA, Node rootB) {
// the best way is to make set of the smallest tree first, but it is fast even without this
HashSet<Integer> setA = new HashSet<Integer>();
// make set of first Tree
recursive(rootA, setA);
//check all nodes from second tree whether they are in setA
return recursiveSetCheck(rootB, setA);
}
public static void recursive(Node parent, Set<Integer> setValues) {
setValues.add(parent.getValue());
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
recursive(child, setValues);
}
}
}
public static boolean recursiveSetCheck(Node parent, Set<Integer> setValues) {
// if current node value is not in set we can stop recursion and exit
if (!setValues.contains(parent.getValue())) {
return false;
}
if (parent.getChildren() != null && !parent.getChildren().isEmpty()) {
for (Node child : parent.getChildren()) {
if (!recursiveSetCheck(child, setValues)) {
return false;
}
}
}
return true;
}
/**
* Method for filling tree as binary tree
*
* @param values
* - sequence of integer values of binary tree should be as node
* sequences root, 1L,1R,2LL,2LR,2RL,2LL,3LLL,3LLR,3LRL,3LRR...
*/
public static Node fillAsBinaryTreeUseFlatData(Integer... values) {
int parentIndex = 0;// index of current parent node
Node root = new Node(values[0]); // root node
Node[] parents = new Node[] { root }; // all current parents
for (int i = 1; i < values.length; i++) {
// getting current node and his parent
Node n = new Node(values[i]);
Node parent = parents[parentIndex];
if (parent.getChildren() == null) {
parent.setChildren(new ArrayList<Node>());
}
parent.getChildren().add(n);
// if current parent already has two children, we should take
// another sibling
if (parent.getChildren().size() == 2) {
if (parentIndex + 1 >= parents.length) {
// if there is no other sibling we should make all children
// of current parents as parents for the next level nodes
parentIndex = 0;
List<Node> newParents = new ArrayList<Node>();
for (Node child : parents) {
newParents.addAll(child.getChildren());
}
// now all previous level nodes become a parents
parents = newParents.toArray(new Node[newParents.size()]);
} else {
// taking another sibling
parentIndex++;
}
}
}
return root;
}
public static class Node {
private Integer value;
private List<Node> children;
public Node(Integer value) {
this.value = value;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
}
}
On Java:
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public class TestParenthesis{
public static void main(String[] args) {
String text = "<sjd>iua[dsds(d]<sa)sa<sasa>>sasasa";
System.out.println(checkSimple(text, '<', '>'));
Map<Character,Character> mp= new HashMap<Character,Character>();
mp.put('<', '>');
mp.put('(', ')');
mp.put('[', ']');
mp.put('{', '}');
System.out.println(checkMap(text, mp));
}
public static boolean checkSimple(String text, char begin, char end) {
char[] textArray = text.toCharArray();
int firstError = -1;
int cnt = 0;
for (int i = 0; i < textArray.length; i++) {
char a = textArray[i];
if (a == begin) {
cnt++;
if (cnt == 1) {
firstError = i;
}
} else if (a == end) {
cnt--;
if (cnt < 0) {
firstError = i;
break;
}
}
}
if (cnt != 0 && firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}
public static boolean checkMap(String text, Map<Character, Character> map) {
// making set of ends
Set<Character> ends = new HashSet<Character>();
ends.addAll(map.values());
char[] textArray = text.toCharArray();
// position of error
int firstError = -1;
// here will store ends which we expect
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < textArray.length; i++) {
Character a = map.get(textArray[i]);
if (a != null) {
// pushing into stack expected end
stack.push(a);
if (stack.size() == 1) {
// if this is first element at stack we should keep it's position as suspect for error
firstError = i;
}
} else if (ends.contains(textArray[i])) {
if (stack.isEmpty() || textArray[i] != (char) stack.pop()) {
firstError = i;
break;
}else{
firstError = -1;
}
}
}
if (firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}
}
Also it will output the error position.
- mger1979 October 03, 2015
- mger1979 May 16, 2017