rishi t
BAN USERFrom what I understood, we need to add smallest string in successive order to find min cost
Please let me know if my understanding is incorrect of logic is flawed.
Steps:
Assuming n strings are passed in string array
Iterate in loop n times-for all strings
in each iteration, pick out smallest string and concatenate with output,calculate cost and make that string in array null;
return output
public static String concatString(String[] input) {
int size = input.length;
String output = "";
int cost = 0;
int outputcost = 0;
while (size > 0) {
int min = 0;
for (int i = 0; i < input.length; i++)
if (input[i] != "" && input[i].length() < input[min].length())
min = i;
cost = cost + output.length() + input[min].length();
output = output + input[min];
input[min] = "";
size--;
}
System.out.println(cost);
return output;
}
public static void main(String args[]) {
String[] input = { "Helloo ", "Hows ", "are ", "u " };
System.out.println(concatString(input));
}
Algorithm as suggested by eugene
1.Create hashmap and put all substrings of size 3 in it
2. reverse string
3. for each substring of reversed string, print all entries that are already present in hashmap
import java.util.HashMap;
class TreeClass {
public static void main(String Args[]) {
String text = "qwertyabcasdfgcba";
int length = 0;
HashMap<String, Integer> map = new HashMap<String, Integer>();
while (length < text.length() - 2) {
String tmp = text.substring(length, length + 3);
if (map.containsKey(tmp)) {
int val = map.get(tmp);
val++;
map.put(tmp, val);
} else
map.put(tmp, 1);
length++;
}
String rev = "";
length = text.length() - 1;
while (length >= 0) {
rev = rev.concat(Character.toString(text.charAt(length)));
length--;
}
length = 0;
while (length < rev.length() - 2) {
String tmp = rev.substring(length, length + 3);
if (map.containsKey(tmp)) {
System.out.println(tmp);
}
length++;
}
}
}
Algo
1. Store number of nodes in a subtree in its data field.
2. Do inorder traversal and at each node sum up the nodes in left subtree+right sub tree+1.
int node_method(node* x)
{
x.data=1;
if(x.left==null && x.right== null)
return 1;
if(x.left!=null)
x.data+=node_method(x.left);
if(x.right!=null)
x.data+=node_method(x.right);
return x.data;
}
Complexity is O(n)
search node with max value of x.data
This is better solution compared to finding center of linkedlist.
- rishi t September 15, 2014