Pages

Leetcode: 463. Island Perimeter

 

You are given a map in the form of a two-dimensional integer grid where 1 represents land and 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
 Example:
Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

PROGRAM:


class Solution {
 
    public int islandPerimeter(int[][] grid) {
        int wallCount = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == 1){
                    
                    if(j == 0) wallCount++;
                    else if(j > 0 && grid[i][j-1] == 0) wallCount++;
                    
                    if(i == 0) wallCount++;
                    else if(i > 0 && grid[i-1][j] == 0) wallCount++;
                    
                    if(j+1 >= grid[0].length) wallCount++;
                    else if(grid[i][j+1] == 0) wallCount++;
                    
                    if(i+1 >= grid.length) wallCount++;
                    else if(grid[i+1][j] == 0) wallCount++;
                }
            }
        }
        return wallCount;
    }
}


OUTPUT:

16

Enum.ordinal() Method in Java

 
Returns the ordinal of this enumeration constant (its position in its enum declaration, where the initial constant is assigned an ordinal of zero). For example, let's have weekdays in an enum starting from Monday, Tuesday till Sunday. So the ordinal of Monday will be 0, Tuesday will be 1, etc.,

Enum.ordinal() Method in Java


Let's see simple Java for the same.


enum Days{
// 0 1  2     3         4       5  6 
 MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY;
}

public class EnumOrdinal {
 public static void main(String[] args) {
  Days mon = Days.MONDAY;
  Days wed = Days.WEDNESDAY;
  Days tus = Days.TUESDAY;
  Days fri = Days.FRIDAY;
  Days sun = Days.SUNDAY;
  
  System.out.println("Monday ordinal    : "+mon.ordinal());
  System.out.println("Wednesday ordinal : "+wed.ordinal());
  System.out.println("Tuesday ordinal   : "+tus.ordinal());
  System.out.println("Friday ordinal    : "+fri.ordinal());
  System.out.println("Sunday ordinal    : "+sun.ordinal());
 }
}


OUTPUT:


Monday ordinal    : 0
Wednesday ordinal : 2
Tuesday ordinal   : 1
Friday ordinal    : 4
Sunday ordinal    : 6

Find the Occurrences Of Each Character In a String

 
Find the Occurrences Of Each Character In a String without using collection.
Here we are going to create simple array to store the character occurrence. If we look at ASCII value of each character including space then it starts from 32 to 126. So we will create array size of 94 which can hold all the character occurrences.

Find the Occurrences Of Each Character In a String


Let's see simple example in Java how to implement in a simple way.

public class CharacterOccurrance {

 public static void main(String[] args) {
  String str = "Java Discover~";

  CharacterOccurrance obj = new CharacterOccurrance();
  int[] occurrance = obj.findCharOccurrance(str);
  obj.printOccurrance(occurrance);
 }

 public int[] findCharOccurrance(String str) {
  int[] occurrance = new int[95];
  for (int i = 0; i < str.length(); i++) {
   int index = str.charAt(i);
   occurrance[index - 32]++;
  }
  return occurrance;
 }

 public void printOccurrance(int[] occurrance) {
  System.out.println("Character : Occurrance");
  for (int i = 0; i < occurrance.length; i++) {
   if (occurrance[i] > 0) {
    char ch = (char) (i + 32);
    System.out.println(ch + " \t  : " + occurrance[i]);
   }
  }
 }
}



OUTPUT:


Character : Occurrance
     : 1          <----- Space
D    : 1
J    : 1
a    : 2
c    : 1
e    : 1
i    : 1
o    : 1
r    : 1
s    : 1
v    : 2
~    : 1

Longest palindrome Sub-sequence from the given String using Dynamic Programming

 
Write a program to find the longest sub-sequence palindrome from the given string by using dynamic programming. For example

Input String : ABCDQRDC

Longest sub-sequence palindrome: 5
Longest palindrome Sub-sequence from the given String using Dynamic Programming

  •  So let's see how we will solve and find the longest subsequence palindrome using dynamic programming. 

  • Construct the solution matrix of size NxN where N is the length of given string. 
  • We will calculate the size of each character sequence palindrome size and will the memorised in the solution matrix which will referred for the next incremental sequence.
  • For example in above example all strings of 1 character will be palindrome size of 1. A, B, C, D, Q, R, D, C
  • On next cycle it will add another character and makes 2 character string like 
  • AB, BC, CD, DQ, QR, RD, DC and goes on like 
  • ABC, BCD, CDQ, DQR, QRD, RDC etc.,
  • Each sequences palindrome size will be stored in the solution array and finally returns the maximum size as output.
Now lets see simple Java code 


 public class LongestPalindromeSequence {

 public static void main(String[] args) {

  String str = "ABCDQRDC";

  LongestPalindromeSequence obj = new LongestPalindromeSequence();

  System.out.println("\nLength of Longest palindrome subsequence : " + obj.lps(str));

 }

 public int lps(String seq) {
  int n = seq.length();
  int j, k, i;
  int L[][] = new int[n][n];

  // Strings of 1 character will be palindrome size of 1 
  // starting with upper matrix and all single character falls diagonally and size will be 1
  for (j = 0; j < n; j++)
   L[j][j] = 1;

  for (i = 2; i <= n; i++) {
   for (j = 0; j < n - i + 1; j++) {

    k = j + i - 1;

    if (seq.charAt(j) == seq.charAt(k)) {
     L[j][k] = L[j + 1][k - 1] + 2;

    } else {
     L[j][k] = Math.max(L[j][k - 1], L[j + 1][k]);
    }
   }
  }

  /*System.out.println("Final solution Matrix :::: ");
  for (j = 0; j < n; j++) {
   System.out.print(seq.charAt(j) +" - ");
   for (k = 0; k < n; k++) {
    System.out.print(L[j][k] + "\t");
   }
   System.out.println();
  }*/
  return L[0][n - 1];
 }
}

OUTPUT:


Length of Longest palindrome subsequence : 5

How to create a graph using Java

 
Let's see simple graph creation using core java and printing all the vertex along with list of edges which goes from that particular Vertex.

How to create a graph using Java




public class MyGraph {

 public static void main(String[] args) {
  
  /* Initilize graph with 5 vertex and as 
   * going to be directed graph
   */
  
  Graph myGra = new Graph(5, "directed");
  
  /*
   * Add vertex 
   */
  myGra.addVertex("A");
  myGra.addVertex("B");
  myGra.addVertex("C");
  myGra.addVertex("D");
  myGra.addVertex("E");
  
  /*
   * Add edges between each vertex and their distance 
   */
  myGra.addEdge("A", "B",5);
  myGra.addEdge("A", "E",1);
  myGra.addEdge("B", "C",2);
  myGra.addEdge("C", "D",2);
  myGra.addEdge("E", "D",2);
  myGra.addEdge("E", "A",2);
  
  // Print the created graph
  myGra.printMyGraph();
  
 }
}





public class Graph {

 // Graph direction (directed / undirected graph)
 private boolean undirected = true;
 
 // No. of vertex in the graph
 private Vertex[] arrayOfVertex;
 
 private int indexCounter = 0;
 
 // Constructor to create graph vertex 
 public Graph(int noOfVertex, String graphType) {
  if (graphType.equalsIgnoreCase("directed")) {
   this.undirected = false;
  }
  arrayOfVertex = new Vertex[noOfVertex];
 }
 
 // Vertex class
 class Vertex {
  // Name of the Vertex
  private String name;
  
  // Holds the list of all edges from current vertex 
  private Edge edge;

  // Create vertex 
  public Vertex(String name, Edge aNode) {
   this.name = name;
   this.edge = aNode;
  }
 }
 
 // Edge between 2 Vertex
 class Edge {
  // Destination vertex Id
  private int vertexId;
  
  // In list point to next edge if its else null 
  private Edge next;
  
  // Weight of current edge
  private int weight;

  // Create edge
  public Edge(int vertexId, Edge next, int weight) {
   this.vertexId = vertexId;
   this.next = next;
   this.weight = weight;
  }
 }

 // Adding Vertex 
 public void addVertex(String vertexName) {
  arrayOfVertex[indexCounter] = new Vertex(vertexName, null);
  indexCounter++;
 }

 // Adding Edge
 public void addEdge(String sVertex, String dVertex, int weight) {
  int sId = indexOfName(sVertex);
  int dId = indexOfName(dVertex);

  /*
   * Find source and destination vertexId and create new Edge and 
   * point it to source edge link
   */
  arrayOfVertex[sId].edge = new Edge(dId, arrayOfVertex[sId].edge, weight);
  
  /*
   * If undirected then create 2 edge's between source and destination and 
   * destination to source 
   */
  if (undirected) {
   arrayOfVertex[dId].edge = new Edge(sId, arrayOfVertex[dId].edge, weight);
  }
 }

 /*
  * Getting indexId of given vertex name
  */
 private int indexOfName(String name) {
  for (int v = 0; v < arrayOfVertex.length; v++) {
   if (arrayOfVertex[v].name.equals(name)) {
    return v;
   }
  }
  return -1;
 }

 /*
  * Print the graph in vertex order and listing all outgoing edges from that vertex
  */
 public void printMyGraph() {
  System.out.println("VERTEX\t----> EDGES WITH WEIGHT");
  for (int v = 0; v < arrayOfVertex.length; v++) {
   System.out.print(arrayOfVertex[v].name +" \t ----> ");
   for (Edge aNode = arrayOfVertex[v].edge; aNode != null; aNode = aNode.next) {
    System.out.print( "<==>"+ arrayOfVertex[aNode.vertexId].name + ":" + aNode.weight);
   }
   System.out.println();
  }

 }
}



OUTPUT:


VERTEX         ----> EDGES WITH WEIGHT
A          ----> <==>E:1<==>B:5
B          ----> <==>C:2
C          ----> <==>D:2
D          ----> 
E          ----> <==>A:2<==>D:2

Add two numbers represented by linked lists using recursive

 
Add two numbers represented by linked lists using recursive method and generate the 3td linked with addition of 1st and 2nd linked list.

For example:


val_1[] = {       7, 6, 5 }
val_2[] = { 9, 6, 4, 1, 6 }


then the output should be {9, 7, 1, 8, 1} basically its addition of 1st and 2nd linked lists as same normal 2 numbers addition.

Add two numbers represented by linked lists using recursive

         
Let's see simple java code to create linked lists using input array and to get the addition of 2 linked list in 3rd linked list.



public class SumOfTwoLL {
 
 class NODE {

  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {

  SumOfTwoLL obj = new SumOfTwoLL();
  
  int val_1[] = new int[] {       7, 6, 5 };
  int val_2[] = new int[] { 9, 6, 4, 1, 6 };

  // Create linked list out of arrays
  NODE first = obj.createLinkedList(val_1);
  NODE second = obj.createLinkedList(val_2);
  
  // Check no. of nodes in both Linked list
  int t1 = obj.noOfNodes(first);
  int t2 = obj.noOfNodes(second);
  
  // Adjusting Linked List with leading zero node's to make it equal size
  if(t1 < t2) first = obj.adjustLinkedList(first, (t2-t1));
  else if(t2 < t1) second = obj.adjustLinkedList(second, (t1-t2));
  
  // add method call
  NODE third = obj.addTwoLL(first, second, 0);
  
  obj.print(third);
  
 }
 
 // Method to get sum of 2 Linked List
 private NODE addTwoLL(NODE first, NODE second, int cnt) {
  
  if(first != null && second != null){
   
   // Recursive call moving to last node 
   NODE node = addTwoLL(first.next, second.next, cnt+1);
   
   // Calculating sum from last 2 values 
   int val = (first.data + second.data) +node.data;
   
   int carry = val/10;
   int sum = val%10;
   
   // If carry present or not the first node in list then create a node with carry value
   if(cnt != 0 || carry > 0) {
   
    NODE carryNode = new NODE(carry);
    node.data = sum;
    carryNode.next = node;
    return carryNode;
   
   }else {
    // Assign final sum to the previous cycle carry node
    node.data = sum;
    return node;
   }
  }
  // Create last carry node with zero
  return new NODE(0);
 }
 

 private NODE adjustLinkedList(NODE ll, int noOfNodesToAdd){
  while(noOfNodesToAdd > 0){
   NODE tmp = new NODE(0);
   tmp.next = ll;
   ll = tmp;
   noOfNodesToAdd--;
  }
  return ll;
 }
 
 
 private int noOfNodes(NODE ll){
  int count = 0;
  while(ll !=  null){
   count ++;
   ll = ll.next;
  }
  return count;
  
 }
 
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
 

 public void print(NODE tmp){
  while(tmp != null ){
   System.out.print(tmp.data +", ");
   tmp = tmp.next;
  }
 }
}



OUTPUT:

9, 7, 1, 8, 1,



Reverse words in a given String using recursion

 
Reverse words in a given String using recursion. We need to reverse words by words in a given line and not the character in a given string. We need to solve this by using backtracking and recursion logic.
Reverse words in a given String using recursion

Let's see simple Java code for getting the given of words in a reverse order by using recursion.


public class ReverseLineByWords {

 public static void main(String[] args) {
  
  String str = "Hello Java Discover";
  
  String finalStr = new ReverseLineByWords().reverseLine(str);
  
  System.out.println(finalStr);
  
 }
 
 public String reverseLine(String str){
  String word = "";
  int i = 0;
  for(;i<str.length();i++){
   if(str.charAt(i) == ' ') {
    word = word + " ";
    break;
   }else{
    word = word + str.charAt(i);
   }
  }

  if(i < str.length()) 
   return reverseLine(str.substring(i+1)) + word;
  
  return (word + " ");
 }
}


OUTPUT:


Discover Java Hello


Rotate matrix by clockwise

 
Given a NxN matrix and need to rotate by clockwise as given below

Examples:
Rotate matrix by clockwise


Let's see simple java code to rotate given NxN matrix.


public class MatrixRotate {

 private int prev, curr;

 public static void main(String[] args) {

  int[][] matrix = new int[][] { { 1, 2, 3, 4 }, 
                   { 5, 6, 7, 8 }, 
            { 9, 10, 11, 12 }, 
            { 13, 14, 15, 16 } };
  

  MatrixRotate obj = new MatrixRotate();
  obj.rotateMatrix(matrix);

  for (int i = 0; i < matrix.length; i++) {
   System.out.println();
   for (int j = 0; j < matrix[0].length; j++) {
    System.out.print(matrix[i][j] + ", ");
   }
  }
 }

 public void rotateMatrix(int[][] matrix) {

  int r = matrix.length;
  int c = matrix[0].length;
  int row = 0, col = 0;

  for (int cnt = 0;cnt<(r*c);cnt++) {
   
   prev = matrix[row + 1][col];

   for (int i = col; i < c; i++) {
    swap(row, i, matrix); cnt++;   }
   row++;

   for (int i = row; i < r; i++) {
    swap(i, c - 1, matrix); cnt++;   }
   c--;

   if (row < r) {
    for (int i = c - 1; i >= col; i--) {
     swap(r - 1, i, matrix); cnt++;
    }
   }
   r--;

   if (col < c) {
    for (int i = r - 1; i >= row; i--) {
     swap(i, col, matrix); cnt++;
    }
   }
   col++;
  }
 }

 public void swap(int i, int j, int matrix[][]) {
  curr = matrix[i][j];
  matrix[i][j] = prev;
  prev = curr;
 }
}


OUTPUT:


 5,  1,  2,  3, 
 9, 10,  6,  4, 
13, 11,  7,  8, 
14, 15, 16, 12,



Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.