VJ
BAN USERSlightly simplified version:
void findLongestSubString(String str) {
char[] c = str.toCharArray();
int maxLen = -1; int maxStartIndex = -1;
int startIndex = 0;
int Char1LastUniqueIndex = 0;
int Char2LastUniqueIndex = -1;
for(int i =0;i<c.length;i++) {
if(c[i] == c[Char1LastUniqueIndex]) {
Char1LastUniqueIndex = i;
}else if ( Char2LastUniqueIndex == -1) {
Char2LastUniqueIndex = i;
}else if(c[i] == c[Char2LastUniqueIndex]){
Char2LastUniqueIndex = i;
} else {
int len = i - startIndex;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
//choose the next startIndex
if(Char1LastUniqueIndex > Char2LastUniqueIndex) {
startIndex = Char2LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}else {
startIndex = Char1LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}
}
}
if (maxLen != -1) {
System.out.printf("MaxSubstring = %s, Len=%d", str.subSequence(maxStartIndex, maxStartIndex + maxLen), maxLen);
}
}
another solution. prints all possible combinations for a given N (else prints nothing)
void findLangford(int[] arr, int n) {
if (n == 0) {
for (int i = 0; i< arr.length;i++)
System.out.print(arr[i] + " ");
System.out.print("\n");
return;
}
for (int i=0;i<arr.length-n-1;i++) {
if(arr[i] == 0 && arr[i+n+1] == 0) { //empty slot
arr[i] = n; arr[i+n+1] = n;
findLangford(arr, n-1);
arr[i] = 0; arr[i+n+1] = 0; //undo
}
}
}
EDIT: the array should be of size 2*N - check can be added
- VJ April 17, 2013void getWordCounts(String filename) {
HashMap<String, Integer> counter = new HashMap();
HashSet<String> filter = new HashSet();
filter.add("to");
filter.add("the");
filter.add("and");
try{
Path p = Paths.get(filename);
Scanner s = new Scanner(p).useDelimiter("[ ,!?.]+");
String nextWord;
while (s.hasNext()) {
nextWord = s.next();
if(filter.contains(nextWord)) continue;
if (counter.containsKey(nextWord)) {
counter.put(nextWord, counter.get(nextWord) + 1);
}else {
counter.put(nextWord, 1);
}
}
}
catch (IOException e) {
}
for (Entry e:counter.entrySet()) {
System.out.println(e.getKey() + ":" + e.getValue());
}
}
something like this perhaps ..
...
class NumInfo {
public int dist;
public int firstInstance;
public NumInfo(int i) {
firstInstance = i;
dist = 0;
}
}
void findMaxDistances(int[] arr) {
HashMap<Integer, NumInfo> map;
map = new HashMap();
for(int i=0;i<arr.length;i++) {
if(map.containsKey(arr[i])) {
NumInfo n = map.get(arr[i]);
n.dist = i - n.firstInstance;
}else {
map.put(arr[i], new NumInfo(i));
}
}
for(Entry<Integer, NumInfo> n : map.entrySet()){
System.out.println("Value: " + n.getKey() + " MaxDist: " + n.getValue().dist);
}
}
java function:
public void findMaxSequence(int[] arr, int n) {
int maxIndex = -1;
int maxSum = 0;
if (n < 3) return;
int i = 0;
while ( i < (n-2)) {
if (arr[i] > arr[i+1] || arr[i+1] > arr[i+2]) {
i++;
continue;
}
if (arr[i] + arr[i+1] + arr[i+2] > maxSum) {
maxSum = arr[i] + arr[i+1] + arr[i+2];
maxIndex = i; i++;
}
}
if (maxIndex != -1 )
System.out.printf("Max Sub string: %d,%d,%d",arr[maxIndex],arr[maxIndex + 1], arr[maxIndex +2]);
}
just a thought:
if some offline/pre-processing can be done on the dataset, each word occurring in the sentence/line can be put in a hashmap which points to a list of occurrences (index, filename-line num etc.)
when a input string needs to be checked, we can fetch the occurrences of each of the words and then pick the ones that are common to all words.
selection sort can possibly reduce the inefficiency of bubblesort ..
void sort<int> (Node<int>* p) {
Node* currHead = p;
Node* scout = null;
Node* agent = null;
T min = INTEGER.MAX;
while(currHead != null) {
min = currHead->data;
agent = currHead;
scout = currHead->next;
while (scout != null) {
if (scout->data < min) {
min = scout->data;
agent = scout;
}
scout = scout->next;
}
if(scout != currHead) {
scout->data = currHead->data;
currHead->data = min;
}
currHead = currHead->next;
}
}
assuming we don't have the move history (for en-passant move), one of the solutions could be as follows:
void printPawnMoves(int[][] board, int x, int y) {
assert (isWithinBounds(x,y));
bool isWhite = false;
if (board[x][y] > 0 && board[x][y] < 10) { isWhite = true; }
else if (board[x][y] > 10 && board[x][y] < 20( { isWhite = false; }
else { assert(true); }
//each pawn can have a total of 4 possible moves
int forwardMove = isWhite ? y++:y--;
//forward moves
if (isWithinBounds(x,forwardMove)) {
if(isEmpty(board,x,forwardMove)) {
cout << "(" + x + "," + forwardMove + ")\n";
}
//check if in the starting grid position
if (y == (isWhite ? 1 : 6)) {
int forwardMove2 = isWhite ? y++:y--;
if(isEmpty(x,forwardMove2)) {
cout << "(" + x + "," + forwardMove2 + ")\n";
}
}
}
//diagonal moves
int diagLeftXMove = isWhite ? x++:x--;
int diagRightXMove = isWhite ? x--:x++;
if (isWithinBounds(diagLeftXMove,forwardMove) && !isEmpty(board,diagLeftXMove,forwardMove)) {
cout << "(" + diagLeftXMove + "," + forwardMove + ")\n";
}
if (isWithinBounds(diagRightXMove,forwardMove) && !isEmpty(board,diagRightXMove,forwardMove)) {
cout << "(" + diagRightXMove + "," + forwardMove + ")\n";
}
return;
}
bool isWithinBounds(int x, int y) {
return ((x < 0 || x > 7 || y < 0 || y > 7) ? true:false);
}
bool isEmpty(int[][] board,int x, int y) {
assert(isWithinBounds(x,y));
return ((board[x][y] < 0 || board[x][y] > 19 || board[x][y] == 10) ? true:false);
}
so if I have understood this right, after each player makes the decision, the sum of the digits/numbes left behind in the deque is added to their total ?
> since you can either pop an element from the head or tail, the decision can just be based on comparing head->peek() and tail->peek() (whichever is smaller).
If on the other hand, after each player decides the number formed out of the digits/numbers in the deque are added to their total, the decision is mainly based on what the next element to head is.
For example: if the deque is,
head-> 6 2 5 4 3 1 7 8 <-tail
if head->next->peek() < head->value() { pop (tail) }
else if head->next->peek() == head->value() {
if tail->prev->peek() > tail->value {
pop (tail)
} else { pop (head) }
else { pop(head) }
(am assuming that the deque has a suitable API to support the operations mentioned above. idea is to discuss what an ideal strategy should be)
there is another thing that can be kept in mind while solving: there is a fixed cost of either deletion or insertion if the lengths of the input strings are different. and the additional cost can be thought of as the minimum hemming distance (multiplied by appropriate cost).
tried some code, there could be some bugs (and scope for improving efficiency) ..
have a slightly modified hemming distance calculator (adjusts length) and there is some redundancy in code .. but you know what to do about that :)
- VJ April 24, 2013