bosung90
BAN USERBest runtime of O(NlogK)
import java.util.Arrays;
import java.util.PriorityQueue;
public class KthLargest {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
System.out.println(kthLargest(array, 2));
System.out.println(kthLargestEfficient(array, 2));
}
// O(NlogN)
public static int kthLargest(int[] array, int k) {
Arrays.sort(array);
return array[array.length - 1 - k];
}
// O(Nlogk)
public static int kthLargestEfficient(int[] array, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0; i<k+1; i++) {
pq.add(array[i]);
}
for(int i=k+1; i<array.length; i++) {
pq.add(array[i]);
pq.poll();
}
int kthLargest = pq.peek();
return kthLargest;
}
}
Runtime O(nlogn)
import java.util.Arrays;
public class KthLargest {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
System.out.println(kthLargest(array, 3));
}
public static int kthLargest(int[] array, int k) {
Arrays.sort(array);
return array[array.length - 1 - k];
}
}
import java.util.Stack;
public class ReverseSentence {
public static void main(String[] args) {
String ans = reverseSentence("Man bites dog");
System.out.println(ans);
}
public static String reverseSentence(String s) {
Stack<String> st = new Stack<String>();
String[] words = s.split(" ");
for(String w : words) {
st.push(w);
}
StringBuilder sb = new StringBuilder();
while(!st.empty()) {
sb.append(st.pop());
sb.append(" ");
}
sb.deleteCharAt(sb.length() -1);
return sb.toString();
}
}
I was able to get O(N) runtime
import java.util.Dictionary;
import java.util.Hashtable;
public class WordCombination {
public static void main(String[] args) {
long startTime = System.nanoTime();
System.out.println(new WordCombination().numEncoding("255156181465896518965139846518564115881623848947651321856468513215631856413651321847897794137971894654734768151128"));
long endTime = System.nanoTime();
System.out.println("Took "+(endTime - startTime)/1000000 + " ms");
}
boolean isValid(String s){
int num = Integer.parseInt(s);
if(num>=1 && num <=26)
return true;
else
return false;
}
public int numEncoding(String s, Dictionary<String, Integer> memory) {
if(s.length()==0) return 1;
if(s.length()==1) return 1;
int num = 0;
String s1 = s.substring(1);
int s1Num;
if(memory.get(s1) != null) {
s1Num = memory.get(s1);
} else {
s1Num = numEncoding(s1, memory);
memory.put(s1, s1Num);
}
num += s1Num;
if(isValid(s.substring(0, 2))) {
String s2 = s.substring(2);
int s2Num;
if(memory.get(s2) != null) {
s2Num = memory.get(s2);
} else {
s2Num = numEncoding(s2, memory);
memory.put(s2, s2Num);
}
num += s2Num;
}
return num;
}
private int numEncoding(String s){
Hashtable<String, Integer> memory = new Hashtable<String, Integer>();
return numEncoding(s, memory);
}
}
public class FlattenNode {
static class Node {
Node right;
Node down;
char a;
}
public static void main(String[] args) {
Node E = new Node();
E.a = 'E';
Node L = new Node();
L.a = 'L';
Node D = new Node();
D.a = 'D';
D.down = L;
D.right = E;
Node Y = new Node();
Y.a = 'Y';
Node T = new Node();
T.a = 'T';
T.down = Y;
T.right = E;
Node Z = new Node();
Z.a = 'Z';
Node X = new Node();
X.a = 'X';
X.down = Z;
Node N = new Node();
N.a = 'N';
N.down = X;
N.right = T;
Node A = new Node();
A.a = 'A';
Node C = new Node();
C.a = 'C';
C.down = A;
Node M = new Node();
M.a = 'M';
M.down = C;
M.right = N;
flatten(M);
}
static void flatten(Node head) {
if(head == null)
return;
System.out.print(head.a + "->");
flatten(head.down);
flatten(head.right);
}
}
runtime O(NM) where N is size of first linked list and M is size of second linked list
SpaceComplexity(1)
- bosung90 August 08, 2016