hulkthedestroyer
BAN USERI think it can. We can even use HashMap and check the length during counting.
Say C(x) is the count of element x. While traversing the array count the occurrence of each element x and store it in the HashMap. Every time check if
C(x) + C(x-1) > max or C(x) + C(x+1) > max.
Here is the implementation of the above algorithm. A few assumption:
1) String is properly formatted. I don't check whether there is a correct number of parenthesis etc
2) There is no spaces between the characters
3) Only following operators are allowed: '+', '-', '*','/'
Code:
public static void main(String[] args) {
System.out.println(removeParenthesis(new StringBuilder("((a*b)+c*(e+f))")));
System.out.println(removeParenthesis(new StringBuilder("(a+(b*c))*(d*(f*j))")));
System.out.println(removeParenthesis(new StringBuilder("(a+(b))")));
System.out.println(removeParenthesis(new StringBuilder("((a+b)+((c+d)))")));
}
public static String removeParenthesis(StringBuilder sb) {
if (removeParenthesis(null, sb, 0)) {
sb.deleteCharAt(0);
}
return sb.toString();
}
public static boolean removeParenthesis(Integer leftPrecedence, StringBuilder sb, int start) {
Integer lastPrecedence = null;
Integer minPrecedence = null;
while (start < sb.length()) {
if (sb.charAt(start) == '(') {
if (removeParenthesis(lastPrecedence, sb, start + 1)) {
sb.deleteCharAt(start);
} else {
int count = 0;
do {
if (sb.charAt(start) == '(') {
count++;
} else if (sb.charAt(start) == ')') {
count--;
}
start++;
} while (start < sb.length() && count != 0);
continue;
}
} else if (sb.charAt(start) == ')') {
if(minPrecedence == null) {
sb.deleteCharAt(start);
return true;
}
Integer rightPrecedence = start == sb.length() - 1 || sb.charAt(start + 1) == ')' ? null
: getPrecedence(sb.charAt(start + 1));
if ((leftPrecedence != null && minPrecedence < leftPrecedence)
|| (rightPrecedence != null && minPrecedence < rightPrecedence)) {
return false;
} else {
sb.deleteCharAt(start);
return true;
}
} else if (sb.charAt(start) < 'a' || sb.charAt(start) > 'z') {
lastPrecedence = getPrecedence(sb.charAt(start));
if (minPrecedence == null || minPrecedence > lastPrecedence) {
minPrecedence = lastPrecedence;
}
}
start++;
}
return false;
}
public static int getPrecedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
throw new IllegalArgumentException(">>" + operator + "<<");
}
I agree with you, it's the max sum rectangle problem the only difference is to handle rows without 1s.
- hulkthedestroyer May 07, 2014Check Moore's voting algorithm.
- hulkthedestroyer May 03, 2014You wrote "ls if not you left with 3 balls", which 3 balls? How do you know whether to choose heavier or lighter group?
- hulkthedestroyer April 22, 2014It could be done in this way if you know whether the ball is heavier or lighter. Here you know only that the one ball is faulty.
- hulkthedestroyer April 22, 2014For a binary tree inorder traversal and either a postorder or preorder traversal can uniquely identify the tree.
The inorder sequence will resolve the left-right problem, and the other sequence (pre or post) will tell us the roots of the various subtrees. For example, if inorder is CBA, and preorder is CAB, then we know that C is at the root, and both B and A are in the right subtree.
In short to reconstruct the BT from the array we need at least two types of traversals. I don't think it is feasible to reconstruct BT with only post order traversal.
It can be done in 4 iteration:
1) Create 2 groups - 4 balls each, Say group A and B
2) Weight balls from group A in pairs (on one side put 2 balls and on the other side put 2 balls from group A). - First iteration
3) If the sides are equal the faulty ball is in group B otherwise in group A.
4) Take 2 balls from the group which contains proper balls and 2 balls from the group which contain faulty ball and weight then with each other. - Second iteration
5) If the sides are equal the faulty ball is in the remaining two balls from the faulty group,
If different the faulty ball is in the balls which we are weighting.
6) So we have a group of 2 balls which contain faulty ball, say C.
7) Take one proper ball and weight it with every ball from the group C to find faulty ball. - 2 weights.
Total 4 iterations.
How does your approach differ from swapping every element with each other (not with the empty one)?
1) Say we are at position 'i'.
2) The original position of a[i] is p. So swap a[i] with a[p].
3) Now the a[i] contains new element. Repeat the process till a[i] contains the correct element.
4) Move to a[i+1]
The only difference is that the empty element is handled as any other element in the array.
Moreover I don't get what does it mean 'with least number of swaps'. Did you reduce the number of swaps in your algo?
I think the number of swaps which is required to revert the modified array to the original form depends on the element distribution in the modified array.
Simple example:
Original array: {1,2,3,4}
Modified version 1: {3,4,1,2} - 2 swaps, because new elements already matches the position after swap.
Modified version 2: {2,3,4,1} - 3 swaps.
1) Create HashMap <String, Index> which maps a word to its latest position in the text.
2) Create priority Queue which contains indexes of the words which have been already found.
(Priority queue stores sorted elements so first element in the queue is the beginning of the segment.
3) Every time a matching word is found on the new position update queue:
- remove previous position and add new one
4) If all words have been found check if segment is smaller then the minimum.
Java:
public static void findSegment(String[] text, String[] dict) {
Map<String, Integer> wordToIndexMap = new HashMap<String, Integer>();
Queue<Integer> positions = new PriorityQueue<Integer>();
int missingWords = dict.length;
int minDist = Integer.MAX_VALUE;
int startIndex = -1;
int endIndex = -1;
for (int i = 0; i < dict.length; i++) {
wordToIndexMap.put(dict[i], null);
}
for (int i = 0; i < text.length; i++) {
if (!wordToIndexMap.containsKey(text[i])) {
continue;
}
if (missingWords > 0 && wordToIndexMap.get(text[i]) == null) {
missingWords--;
}
if (wordToIndexMap.get(text[i]) != null) {
positions.remove(wordToIndexMap.get(text[i]));
}
wordToIndexMap.put(text[i], i);
positions.add(i);
if (missingWords == 0 && (i - positions.peek() + 1 < minDist)) {
minDist = i - positions.peek() + 1;
startIndex = positions.peek();
endIndex = i;
}
}
if (missingWords == 0) {
System.out.println("Segment starts: " + startIndex + ", ends: " + endIndex);
} else {
System.out.println("Segment not found");
}
}
I think you can sort the dictionary first and then start generating permutations.Then the permutations are sorted out of the box and once the X is generated stop. The output is equal to the number of generated permutations.
- hulkthedestroyer May 10, 2014