-
Hidden Numbers Solution (December)
There's probably a more concise way to do this... but here's a brute-force attack that avoids duplicate operations and uses a binary-search method for inserting objects into a sorted list:
import java.util.*;
public class HiddenNumbers {
ArrayList numbers;
int size;
class NumberInfo {
public String str;
public double val;
public double len;
public NumberInfo(String str) {
this.str = str;
this.val = Double.parseDouble(str);
this.len = str.length();
}
}
private int insertNumber(NumberInfo add, int start, int end) {
if (end == 0) {
numbers.add(end, add);
} else if (start + 1 >= end) {
NumberInfo current = (NumberInfo)numbers.get(end - 1);
if (add.val < current.val) {
numbers.add(end - 1, add);
} else if (add.val > current.val) {
numbers.add(end, add);
} else if (add.len < current.len) {
numbers.add(end - 1, add);
} else if (add.len > current.len) {
numbers.add(end, add);
} else {
numbers.add(end, add);
}
} else {
int middle = start + ((end - start + 1) / 2);
NumberInfo current = (NumberInfo)numbers.get(middle - 1);
if (add.val > current.val) {
return insertNumber(add, middle, end);
} else if (add.val < current.val) {
return insertNumber(add, start, middle);
} else if (add.len > current.len) {
return insertNumber(add, middle, end);
} else if (add.len < current.len) {
return insertNumber(add, start, middle);
} else {
numbers.add(middle, add);
}
}
return 1;
}
public String[] findAll(String[] text) {
numbers = new ArrayList();
size = 0;
int snum = 0;
while (snum < text.length) {
String str = text[snum];
StringTokenizer st = new StringTokenizer(str, " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
while (st.hasMoreTokens())
{
String strNext = st.nextToken();
while ((snum < text.length - 1) &&
!st.hasMoreTokens() &&
str.endsWith(strNext)) {
snum++;
str = strNext + text[snum];
st = new StringTokenizer(str, " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
strNext = st.nextToken();
}
NumberInfo insert = new NumberInfo(strNext);
size += insertNumber(insert, 0, size);
}
snum++;
}
int outputSize = (size + 1) / 2;
String[] output = new String[outputSize];
for (int i=0; i < outputSize; i++) {
output[i] = ((NumberInfo)(numbers.get(size - outputSize + i))).str;
}
return output;
}
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
Forum Rules
|
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL
|
Bookmarks