josbimosbi
BAN USERpublic int moveMinimumSwapCrane(int input[], int len) {
int space = -1;
int swap = 0;
Map<Integer, Integer> ktv = new HashMap<>();
for (int i = 0; i < len; i++) {
ktv.put(input[i], i);
}
ktv.put(space, len);
for (int idx = 0; idx < len; idx++) {
int seeker = input[idx];
// at position 1 if we have 2 than it is at correct position.
if (seeker == idx + 1)
continue;
move(idx, ktv.get(space), ktv, input);
swap = swap + 1;
int pos = idx;
while (pos != len) {
int expVal = pos + 1;
int newPos = ktv.get(expVal);
move(newPos, pos, ktv, input);
swap = swap + 1;
pos = newPos;
}
}
return swap;
}
void move(int fromIdx, int toIdx, Map<Integer, Integer> ktv, int input[]) {
int val = input[fromIdx];
input[fromIdx] = input[toIdx];
ktv.put(input[toIdx], fromIdx);
input[toIdx] = val;
ktv.put(val, toIdx);
}
/**
Optimized by remembering previous length and previous sum
*/
public class WordLengthFunction {
public static void main(String args[]) {
int input[] = {3, 1, 2, 3};
int max = 4;
System.out.println(findLength(input, max));
}
private static int findLength(int[] input, int max) {
int maxLength = 0;
int psum = 0;
int plength = 0;
for(int i=0; i< input.length; i++) {
int sum = 0;
if(psum != 0) {
sum = sum - input[i -1];
}
int ci = (plength <= 1) ? i : i + plength + 1;
for(int j = ci; j < input.length; j++) {
if(sum + input[j] <= max) {
sum = sum + input[j];
ci = j;
} else {
break;
}
}
int clength = (ci == i) ? 0 : ci - i + 1;
maxLength = Math.max(maxLength, clength);
}
return maxLength;
}
}
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
binaryTreePaths(root, result, "");
return result;
}
public void binaryTreePaths(TreeNode root, List<String> resultList, String resultString) {
if(root == null) return;
if(root.left == null && root.right == null) {
resultString = resultString + root.val;
resultList.add(resultString);
return;
}
binaryTreePaths(root.left, resultList, resultString + root.val + "->");
binaryTreePaths(root.right, resultList, resultString + root.val + "->");
}
}
Find angles for all the points in 2D. For -ve angles subtract from 360 (only required for ease in code)
System.out.println(Math.atan2(3, 3) * 180 / Math.PI); //45
System.out.println(Math.atan2(3, -3) * 180 / Math.PI); // 135
System.out.println(Math.atan2(-3, -3) * 180 / Math.PI); // -135 // 360 - 135 = 225
System.out.println(Math.atan2(-3, 3) * 180 / Math.PI); // -45 // 360 - 45 = 315
sort angles
int ei = lowerBound(List<Integer> angles, int si, int ei, int ev);
append values from 0 to ei to end of the angles array. // required for search in cicural sorted array. e.g
angles = [1, 20, 45, 134, 260, 359, 361, 380] ..here 380 ==> 1, 390 ==> 20
total points seen in 45 viewing angle from 359 is 3 (359, 361, 380)
int maxpoint(int angles[], ) {
int max = 0;
for(int si = 0; si < angles.length && angles[si] < 361; si ++) {
int ev = angles[si] + 45;
int ei = lowerBound(angles, si, angles.length, ev);
max = Math.max(max, ei - si);
}
return max;
}
int lowerbound(List<Inetger> angles, int si, int ei, int ev) {
if(si >= ei) return si;
while(si < ei) {
int mi = (si + ei)/2
int mv = angles[mi];
if(mv = ev) return mi;
if(mv > ev) {
ei = mi;
} else {
si = mi;
}
}
return si;
}
O(2^n)
public class CoinAllPossibleSum {
static int count = 0;
public static void main(String[] args) {
int[] coins={10,20};
int[] quantity={5,3};
//int[] coins={10, 20, 40};
//int[] quantity={2, 2, 1};
Set<Integer> set=new HashSet<>();
generateSums(coins, quantity, 0, 0,set);
System.out.println(set);
System.out.println(count);
}
private static void generateSums(int[] coins, int[] quantity, int sum, int pos, Set<Integer> set) {
count = count + 1;
set.add(sum);
if(pos == coins.length) return;
for(int q=1; q <= quantity[pos]; q++) {
//sum = sum + coins[pos];
generateSums(coins, quantity, sum + (q * coins[pos]), pos + 1, set);
}
//sum = sum - (coins[pos] * quantity[pos]);
}
}
public class WordBreak2 {
public static void main(String args[]) {
String dict[] = {"cat", "cats", "and", "sand", "dog"};
Trie trie = new Trie();
for(int i = 0; i < dict.length; i++) {
trie.insert(dict[i], trie.root);
}
String input = "catsanddog";
printWordBreak(input, trie.root, 0, "", trie);
}
private static void printWordBreak(String input, TrieNode root, int pos, String result, Trie rootObj) {
if(pos >= input.length()) return;
Character ch = input.charAt(pos);
TrieNode child = root.children.get(ch);
if(child == null) return;
result = result + ch;
pos = pos + 1;
if(child.isEnd) {
if(pos == input.length()) {
System.out.println(result);
return;
}
printWordBreak(input, rootObj.root, pos, result + " ", rootObj);
}
printWordBreak(input, child, pos, result, rootObj);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FindLongChunkedPalindorme {
public static void main(String args[]) {
String inputString = "eaepaveae";
Map<Integer, List<String>> result = new HashMap<>();
longest(inputString, 0, result, 1);
}
private static boolean longest(String inputString, int pos, Map<Integer, List<String>> result, Integer id) {
if (inputString == null || inputString.length() == 0)
return false;
for (int start = pos + 1; start < inputString.length() / 2; start++) {
String beg = inputString.substring(pos, start);
String end = inputString.substring(inputString.length() - start, inputString.length() - pos);
if (beg.equals(end)) {
List<String> can = result.get(id);
if (can == null) {
can = new ArrayList<>();
}
can.add(beg);
result.put(id, can);
longest(inputString, start, result, id + 1);
}
}
// TODO: before adding +1 validate
if(id.intValue() == 1) {
System.out.println(result.size() * 2 + 1);
return true;
}
return false;
}
}
Solution to what ChisK mentioned earlier. Build Trie for dictionary of words and than iterate input string for each character. There are 2 possibilities
A. current char was found in Trie.
B. current char is not found
public class FindWordMinDeletionMatchingDictionary {
public static void main(String args[]) {
Trie trie = new Trie();
List<String> dictionary = Arrays.asList("fellow", "hello", "whatsapp", "zukam");
String inputstring = "zwhatufellkamow";
for(String dic: dictionary) {
trie.insert(dic, trie.root);
}
List<Integer> delpos = new ArrayList<Integer>();
List<Integer> result = lookup(inputstring, trie.root, 0, delpos);
System.out.println(result.size());
for(Integer pos: result) {
System.out.println(inputstring.charAt(pos));
}
}
private static List<Integer> lookup(String inputstring, TrieNode parentNode, int pos, List<Integer> delpos) {
if(inputstring.length() == pos) return delpos;
TrieNode childNode = parentNode.children.get(inputstring.charAt(pos));
if(childNode != null) {
List<Integer> resultA = lookup(inputstring, childNode, pos + 1, delpos);
List<Integer> temp = new ArrayList<>(delpos);
temp.add(pos);
List<Integer> resultB = lookup(inputstring, parentNode, pos + 1, temp);
return resultA.size() < resultB.size() ? resultA : resultB;
} else {
List<Integer> temp = new ArrayList<>(delpos);
temp.add(pos);
List<Integer> resultB = lookup(inputstring, parentNode, pos + 1, temp);
return resultB;
}
}
}
- josbimosbi January 02, 2017