AJ
BAN USERJava Version:
public class KClosestNodes {
public static void kClosestNodes(BinaryTreeNode root, int target, int k, Deque<Integer> q){
if(root == null)
return;
kClosestNodes(root.getLeft(), target, k, q);
if(q.size() < k){
q.addLast(root.getData());
}else if(Math.abs(target - root.getData()) < Math.abs(target - q.peekFirst())){
q.removeFirst();
q.addLast(root.getData());
}else{
return;
}
kClosestNodes(root.getRight(), target, k, q);
}
public static List<Integer> kClosestNodes(BinaryTreeNode root, int target, int k){
Deque<Integer> q = new LinkedList<Integer>();
List<Integer> result = new ArrayList<>();
kClosestNodes(root, target, k, q);
while(!q.isEmpty()){
result.add(q.removeFirst());
}
return result;
}
public static void main(String[] args) {
BinaryTreeNode root = buildBST();
int target = 21, k = 3;
System.out.println(kClosestNodes(root, target, k));
}
public static BinaryTreeNode buildBST(){
BinaryTreeNode node3 = new BinaryTreeNode(3);
BinaryTreeNode node5 = new BinaryTreeNode(5);
BinaryTreeNode node7 = new BinaryTreeNode(7);
BinaryTreeNode node20 = new BinaryTreeNode(20);
BinaryTreeNode node6 = new BinaryTreeNode(6);
node6.setLeft(node5);
node6.setRight(node7);
BinaryTreeNode node22 = new BinaryTreeNode(22);
node22.setRight(node20);
BinaryTreeNode node4 = new BinaryTreeNode(4);
node4.setLeft(node3);
node4.setRight(node6);
BinaryTreeNode node17 = new BinaryTreeNode(17);
node17.setRight(node22);
BinaryTreeNode root = new BinaryTreeNode(9);
root.setLeft(node4);
root.setRight(node17);
return root;
}
}
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(int data){
this.data = data;
this.left = null;
this.right = null;
}
public int getData(){
return this.data;
}
public void setData(int data){
this.data = data;
}
public BinaryTreeNode getLeft(){
return this.left;
}
public void setLeft(BinaryTreeNode left){
this.left = left;
}
public BinaryTreeNode getRight(){
return this.right;
}
public void setRight(BinaryTreeNode right){
this.right = right;
}
}
Java Version using Topological Sort:
public class AlphabeticalOrdering {
static Map<Character, List<Character>> tuples = new HashMap<Character, List<Character>>();
static int alphabetCount = 0;
static Map<Character, Boolean> vertex = new HashMap<Character, Boolean>();
public static List<Character> ordering(Tuple tuple[]){
for(Tuple t : tuple){
if(tuples.containsKey(t.x)){
tuples.get(t.x).add(t.y);
}else{
List<Character> list = new LinkedList<Character>();
list.add(t.y);
tuples.put(t.x, list);
}
vertex.put(t.x, false);
vertex.put(t.y, false);
}
alphabetCount = vertex.size();
return topologicalSort();
}
public static List<Character> topologicalSort(){
Stack<Character> s = new Stack<Character>();
for(Map.Entry<Character, Boolean> entry : vertex.entrySet()){
if(!entry.getValue())
topologicalSortUtil(entry.getKey(), s);
}
List<Character> result = new LinkedList<Character>();
while(!s.isEmpty())
result.add(s.pop());
return result;
}
public static void topologicalSortUtil(char v, Stack<Character> s){
vertex.put(v, true);
if(tuples.containsKey(v)){
Iterator<Character> it = tuples.get(v).listIterator();
while(it.hasNext()){
char n = it.next();
if(!vertex.get(n))
topologicalSortUtil(n, s);
}
}
s.push(v);
}
public static void main(String[] args) {
Tuple tuple[] = {
new Tuple('A', 'B'),
new Tuple('C', 'D'),
new Tuple('C', 'E'),
new Tuple('D', 'E'),
new Tuple('A', 'C'),
new Tuple('B', 'C')
};
System.out.println(ordering(tuple));
}
}
class Tuple{
char x;
char y;
public Tuple(char a, char b){
x = a;
y = b;
}
}
Java DP Version:
public class IdsGenerator {
static Set<String> idsSet = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if(o1.length() <= o2.length())
return -1;
else
return 1;
}
});
static Queue<String> q = new LinkedList<String>();
public static void idGenerator(Set<Character> set, int m){
Set<String> dict = new HashSet<String>();
Map<Integer, Set<String>> cache = new HashMap<Integer, Set<String>>();
for(Character ch : set){
dict.add(String.valueOf(ch));
}
cache.put(1, dict);
idsSet.addAll(makeUniqueIds(dict, m, cache));
q.addAll(idsSet);
}
public static Set<String> makeUniqueIds(Set<String> dict, int level, Map<Integer, Set<String>> cache){
Set<String> ids = new HashSet<String>();
for(int i = 1; i <= level; i++){
ids.addAll(makeIdsForLevel(dict, i, cache));
}
return ids;
}
public static Set<String> makeIdsForLevel(Set<String> dict, int level, Map<Integer, Set<String>> cache){
if(cache.containsKey(level)){
return cache.get(level);
}
Set<String> mergedSet = new HashSet<String>();
for(String str : dict){
for(String ids : makeIdsForLevel(dict, level - 1, cache)){
mergedSet.add(str + ids);
}
}
cache.put(level, mergedSet);
return mergedSet;
}
public static boolean hasNext(){
return q.size() > 0;
}
public static String next(){
return q.poll();
}
// To Do: DP
public static void main(String[] args) {
Set<Character> set = new HashSet<>();
set.add('1');
set.add('2');
set.add('3');
idGenerator(set,3);
while(hasNext()){
System.out.print(next() + " ");
}
}
}
Java Version:
public class IdsGenerator {
static Set<String> idsSet = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if(o1.length() <= o2.length())
return -1;
else
return 1;
}
});
static Queue<String> q = new LinkedList<String>();
public static void idGenerator(Set<Character> set, int m){
Set<String> dict = new HashSet<String>();
for(Character ch : set){
dict.add(String.valueOf(ch));
}
idsSet.addAll(makeUniqueIds(dict, m));
q.addAll(idsSet);
//System.out.println(idsSet);
}
public static Set<String> makeUniqueIds(Set<String> dict, int level){
Set<String> ids = new HashSet<String>();
for(int i = 1; i <= level; i++){
ids.addAll(makeIdsForLevel(dict, i));
}
return ids;
}
public static Set<String> makeIdsForLevel(Set<String> dict, int level){
if(level == 1)
return dict;
Set<String> mergedSet = new HashSet<String>();
for(String str : dict){
for(String ids : makeIdsForLevel(dict, level - 1)){
mergedSet.add(str + ids);
}
}
return mergedSet;
}
public static boolean hasNext(){
return q.size() > 0;
}
public static String next(){
return q.poll();
}
// To Do: DP
public static void main(String[] args) {
Set<Character> set = new HashSet<>();
set.add('1');
set.add('2');
set.add('3');
idGenerator(set,3);
while(hasNext()){
System.out.print(next() + " ");
}
}
}
public String intToRoman(int num) {
int numbers[] = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String roman[] = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int index = 0, x = num;
StringBuilder result = new StringBuilder();
while(x != 0){
int count = x / numbers[index];
if(count > 0){
while(count > 0){
result.append(roman[index]);
count--;
}
x = x % numbers[index];
}
index++;
}
return result.toString();
}
Approach-1:
public String pushDominoes(String dominoes) {
if(dominoes.length() == 0)
return dominoes;
char result[] = new char[dominoes.length()];
char lastDominoe = '.';
int lastIndex = 0;
for(int i = 0; i < dominoes.length(); i++){
char ch = dominoes.charAt(i);
result[i] = ch;
if(ch == '.'){
continue;
}
if(lastDominoe == '.'){
if(ch != 'R'){
int k = i - 1;
while(k >= lastIndex){
result[k] = ch;
k--;
}
}
}else{
if(lastDominoe == 'R' && ch == 'L'){
int low = lastIndex + 1;
int high = i - 1;
while(low < high){
result[low] = 'R';
result[high] = 'L';
low++;
high--;
}
}else if(lastDominoe == ch){
int low = lastIndex + 1;
while(low < i){
result[low] = ch;
low++;
}
}
}
lastDominoe = ch;
lastIndex = i;
}
if(lastDominoe == 'R' && lastIndex < dominoes.length()){
lastIndex++;
while(lastIndex < dominoes.length()){
result[lastIndex++] = 'R';
}
}
return String.valueOf(result);
}
Approach-2:
public String pushDominoes(String dominoes) {
int n = dominoes.length();
if(n == 0)
return dominoes;
int f[] = new int[n];
char A[] = dominoes.toCharArray();
int force = 0;
for(int i = 0; i < n; i++){
char ch = A[i];
if(ch == 'R')
force = n;
else if(ch == 'L')
force = 0;
else
force = Math.max(force - 1, 0);
f[i] += force;
}
force = 0;
for(int i = n - 1; i >= 0; i--){
char ch = A[i];
if(ch == 'L')
force = n;
else if(ch == 'R')
force = 0;
else
force = Math.max(force - 1, 0);
f[i] -= force;
}
StringBuilder result = new StringBuilder();
for(int i = 0; i < n; i++){
result.append(f[i] > 0 ? "R" : (f[i] < 0 ? "L" : "."));
}
return result.toString();
}
- AJ July 28, 2018