Binary Tree Level Order Traversal II LeetCode Java

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution:-

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
        traversal(root,map, 0);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int level = map.size();
        for(int i = level ; i >=0 ; i--){
            List<Integer> temp = map.get(i);
            if(temp != null){
                res.add(temp);
            }
        }
       
        return res;
    }
   
    private void traversal(TreeNode root, HashMap<Integer,List<Integer>> map, int level){
       
        if(root != null){
            if(map.containsKey(level)){
                List<Integer> temp = map.get(level);
                temp.add(root.val);
                map.put(level,temp);
            }
            else{
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(root.val);
                map.put(level,temp);
            }
            traversal(root.left, map, level + 1);
            traversal(root.right, map, level + 1);
           
           
        }
       
       
       
    }
}

Implement Trie (Prefix Tree) Leet Code Java Solution

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution:-


class TrieNode {
   
    public TrieNode [] children;
    public boolean isLeaf;
    // Initialize your data structure here.
    public TrieNode() {
        children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode temp = root;
        int length = word.length();
        for(int level = 0 ; level < length ; level ++){
           
            if(temp.children[word.charAt(level) - 'a'] == null){
                temp.children[word.charAt(level) - 'a'] = new TrieNode();
               
            }
            temp = temp.children[word.charAt(level) - 'a'];
           
        }
        temp.isLeaf = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode temp = root;
        int length = word.length();
       
        for(int level = 0 ; level < length ; level++ ){
            if(temp.children[word.charAt(level) - 'a'] != null){
                temp = temp.children[word.charAt(level) - 'a'];
            }
            else{
                return false;
            }
        }
        if(temp != null && temp.isLeaf == true){
            return true;
        }
        return false;
       
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode temp = root;
        int length = prefix.length();
       
        for(int level = 0 ; level < length ; level++ ){
            if(temp.children[prefix.charAt(level) - 'a'] != null){
                temp = temp.children[prefix.charAt(level) - 'a'];
            }
            else{
                return false;
            }
        }
   
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

3Sum -Leet Code Java Solutiion

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:-

public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        

        Arrays.sort(nums);

        

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        

        Map<String , Integer> map =  new HashMap<String, Integer>();

        

        HashSet<List<Integer>> set = new HashSet<List<Integer>>();

        

        for(int i = 0 ; i < nums.length -2 ; i++){

            

            int start = i + 1 ;

            int end = nums.length - 1;

            

            while(start < end){

                

                if(nums[i] + nums[start]+ nums[end] == 0){

                    List<Integer> temp = new ArrayList<Integer>();

                    temp.add(nums[i]);

                    temp.add(nums[start]);

                    temp.add(nums[end]);

                    set.add(temp);

                    start++;

                    end--;

                }

                else{

                if(nums[i] + nums[start]+ nums[end] < 0){

                    start++;

                }

                else{

                    end--;

                }

                }

            }

        }

        res.addAll(set);

        return res;

        

    }

}

4Sum (Leet Code Java Solution)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution:-

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        
        Map<String , Integer> map =  new HashMap<String, Integer>();
        
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        
        for(int t = 0 ; t < nums.length - 3 ; t++){
            for(int i = t+1 ; i < nums.length - 2 ; i++){
            
            int start = i + 1 ;
            int end = nums.length - 1;
            
            while(start < end){
                
                if(nums[t] + nums[i] + nums[start]+ nums[end] == target){
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[t]);
                    temp.add(nums[i]);
                    temp.add(nums[start]);
                    temp.add(nums[end]);
                    set.add(temp);
                    start++;
                    end--;
                }
                else{
                if(nums[t] + nums[i] + nums[start]+ nums[end] < target){
                    start++;
                }
                else{
                    end--;
                }
                }
            }
            }
        }
        res.addAll(set);
        return res;
    }

}

Heap Data Structure Implementation in Java

Here is the Implementation of Maximum Heap in Java.Although best approach is to implement Object oriented approach during developing Classes.


import java.util.Scanner;


class Heap{
public int [] array; // containing the heap

public int capacity ;

public int count ; //num of element in a heap


public Heap(int capacity){
this.capacity = capacity;
this.array = new int[capacity];

}

public int parent(int i){
return i - 1 / 2 ;

}

public int left(int i){
int left = 2 * i + 1;

if(left >= this.count || i < 0){
return -1;
}

return left;
}

public int right(int i){

int right = 2 * i + 2;

if(right >= this.count || i < 0){
return -1;
}
return right ;
}

public int getMaximum(){
if(this.count == 0 ){
return -1;
}
else{
return this.array[0];
}
}

public void percolateDown(int i){

int l = left(i);
int r = right(i);
int max = 0 ;
if(l != -1 && this.array[i] < this.array[l]){
max = l;
}
else{
max = i ;
}
if(r != -1 && this.array[i] > this.array[max]){
max = r;
}


if(max != i){
int temp  = this.array[max];
this.array[max] = this.array[i];
this.array[i] = temp;
percolateDown(max);
}

}

public int deleteMax(){
if(this.count == 0){
return -1;
}
int data = this.array[0];
this.array[0] = this.array[this.count -1 ];
this.count--;
percolateDown(0);

return data;
}

public void insert(int data){
if(this.count == this.capacity){
System.out.println("Heap is Full");
}
else{
this.count++;
int i = this.count - 1 ;
while(i > 0 && this.array[(i-1)/2] < data){
this.array[i] = this.array[(i-1)/2];
i = (i - 1) / 2 ;
}
this.array[i] = data;
}
}


}





public class Solution {

public static void main(String [] args)
{
System.out.println("heap");

Heap heap = new Heap(8);
heap.insert(1);
heap.insert(13);
heap.insert(6);
heap.insert(17);
heap.insert(4);
heap.insert(2);
heap.insert(5);


for(int i = 0 ; i < 8 ; i++){
System.out.println("max is " +heap.getMaximum());
System.out.println("left is "+ heap.left(i)+" right "+ heap.right(i));
if(heap.left(i) != -1){
System.out.println("data left "+ heap.array[heap.left(i)]);
}
if(heap.right(i) != -1){
System.out.println("data right "+ heap.array[heap.right(i)]);
}
heap.deleteMax();
}

}

}

Dynamic Programming (Cutting a Rod)

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n.Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

Solution:-

public class Solution {

public static void main(String [] args)

{

int [] price = new int[]{1, 5, 8, 9, 10, 17, 17, 20};

int n = 8 ;

int [] [] dp = new int [n+1][n+1];

for(int i = 1 ; i <= n ; i++){

for(int j = 1 ; j <= n ; j++){

if(i >= j ){

dp[i][j] = Math.max(dp[i][j-1] , dp[i][i - j] + price[j-1]);

}

else{

dp[i][j] = dp[i-1][j];

}

}

}

System.out.println(dp[n][n]);

}

}