Java Practice

0ReadMe.md

Some Random Code Snippets

Fenwick_Tree_RangeSumQuery.jsh

// https://leetcode.com/problems/range-sum-query-mutable/
// could have been done easily by using a separate tree array.


class NumArray {

    int[] nums;

    public NumArray(int[] nums) {
        for(int i=0; i<nums.length; i++) {

            int el = i+1; // adjusting array starting from 0;
            el += (el & -el);
            if (el<=nums.length) nums[el-1] += nums[i];
        }
        this.nums = nums;
    }
    
    public void update(int index, int val) {
        int val_at_i = sumRange(index,index);
       // System.out.println(val_at_i);
        int diff = val - val_at_i;
        nums[index] += diff;
        int el = index+1;
        el += (el & -el);
        // update all parent lg(n)
        while (el<=nums.length) {
            nums[el-1] += diff;
            el += (el & -el);
        }
    }

    public int sumRange(int i) {
        if(i<0) return 0;
        int sum = nums[i];
        int el = i+1;
        el -= (el & -el);
        while(el>0) {
            sum += nums[el-1];
            el -= (el & -el);
            //System.out.println(el);
        }
        return sum;
    }
    
    public int sumRange(int left, int right) {
        return sumRange(right)-sumRange(left-1);
    }

    public int[] get() {
        return nums;
    }
}

print-triangle.jsh

/*
        http://www.javaproblems.com/2012/11/java-problem-g-triangles-shape.html
 */

 public static void main ()

 {
    for(int count = 1; count <= 10; count++) {
            // a
            for(int i=1; i<=count; i++) System.out.print("*");
            for(int j=10; j>count; j--) System.out.print(" ");
            // b
            for(int j=10; j>=count; j--) System.out.print("*");
            for(int i=1; i<count; i++) System.out.print(" ");
            // c
            for(int i=1; i<count; i++) System.out.print(" ");
            for(int j=10; j>=count; j--) System.out.print("*");
            // d
            for(int i=10; i>count; i--) System.out.print(" ");
            for(int j=1; j<=count; j++) System.out.print("*");

            System.out.println();
        }

}

segment-tree.jsh

int buildSegmentTree(int[] tree, int index) {
    // leaf node
    if (2*(index+1)-1 >= tree.length) return tree[index];
    // min of left and right
    tree[index] = Math.min(buildSegmentTree(tree, 2*(index+1)-1), buildSegmentTree(tree, 2*(index+1)));
    return tree[index];
}

public int[] largestRectangleArea(int[] heights) {

    int tree_height = (int) Math.ceil(Math.log(heights.length)/Math.log(2));
    int[] tree = new int[(int)Math.pow(2, tree_height+1)-1];
    //todo
    Arrays.fill(tree, Integer.MAX_VALUE);
    
    int index_leaf_node = ((int)Math.pow(2,tree_height))-1;
    for(int i=0;i<heights.length;i++) {
        tree[index_leaf_node+i]=heights[i];
    }
   
   buildSegmentTree(tree, 0);
   
   return tree;
 }


public int largestRectangleArea1(int[] heights) {
    int max = 0;
    int[] prev = new int[0];

    for(int i=0; i<heights.length; i++) {
        int val = heights[i];
        int[] cur = new int[val];
        for(int j=0; j<val; j++) {
            cur[j] = (j+1) + ((prev.length>j) ? prev[j]:0);
            max = Math.max(max, cur[j]);
        }
        prev = cur;
    }
    return max;
}


int[][] mem;
public int largestRectangleArea2(int[] heights) {
        
int len = heights.length;
int max =0;
int cols = Arrays.stream(heights).max().getAsInt();
mem = new int[len][cols];


for(int row=0; row<len; row++) {


    for(int col=1; col<=heights[row]; col++) {

        mem[row][col-1] = col + ( (row==0) ? 0  : mem[row-1][col-1]);
        max = Math.max(max, mem[row][col-1]);
    }


}

System.out.println(Arrays.toString(mem));

return max;

}