Given a one dimensional array of integers representing the height of cliffs of a valley, find the total amount of water that can be filled in the valley.
Diagram:
Java Program:
package com.sourabh.test; import java.util.ArrayList; import java.util.List; public class ValleyWater { class Valley { private int start; private int end; private int water; public Valley() { super(); } public Valley(int start, int end) { super(); this.start = start; this.end = end; } public int getStart() { return start; } public void setStart(int start) { this.start = start; } public int getEnd() { return end; } public void setEnd(int end) { this.end = end; } public int getWater() { return water; } public void setWater(int water) { this.water = water; } } public List<Valley> getValleys(int... A) { List<Integer> maxima = new ArrayList<>(); List<Integer> minima = new ArrayList<>(); List<Valley> valleysList = new ArrayList<>(); int index = 0; for(int i=0;i<A.length - 1;i++) { if(A[i+1] > A[i]) { minima.add(i); index = i; break; } if(A[i+1] < A[i]) { maxima.add(i); index = i; break; } } for(int i=index+1;i+1<A.length;i++) { if(A[i+1] < A[i] && A[i] >= A[i-1]) { maxima.add(i); } if(A[i+1] > A[i] && A[i] <= A[i-1]) { minima.add(i); } } for(int i = 0; i < maxima.size() - 1; i++) { valleysList.add(new Valley(maxima.get(i), maxima.get(i+1))); } return valleysList; } public int addWater(List<Valley> valleysList, int... A) { int totalWater = 0; for(Valley valley : valleysList) { int min = A[valley.getStart()] < A[valley.getEnd()] ? A[valley.getStart()] : A[valley.getEnd()]; int water = 0; for(int i=valley.getStart(); i<=valley.getEnd(); i++) { if(A[i] < min) { water += min - A[i]; } } valley.setWater(water); totalWater += water; } for(Valley valley : valleysList) { System.out.println(valley.getWater()); } return totalWater; } public int getWater(int... A) { return addWater(getValleys(A), A); } }
Unit Tests:
package com.sourabh.test; import static org.junit.Assert.*; import java.util.List; import com.sourabh.test.ValleyWater.Valley; import org.junit.Assert; import org.junit.Test; public class ValleyWaterTests { ValleyWater instance = new ValleyWater(); @Test public void getValleysTest() { int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1}; List<Valley> valleysList = instance.getValleys(A); Assert.assertEquals(3, valleysList.size()); Assert.assertEquals(2,valleysList.get(0).getStart()); Assert.assertEquals(4,valleysList.get(0).getEnd()); Assert.assertEquals(4,valleysList.get(1).getStart()); Assert.assertEquals(7,valleysList.get(1).getEnd()); Assert.assertEquals(7,valleysList.get(2).getStart()); Assert.assertEquals(12,valleysList.get(2).getEnd()); } @Test public void getWaterTest() { int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1}; int totalWater = instance.getWater(A); Assert.assertEquals(5, totalWater); } }
thank u for sharing this post Meraki Firewall
ReplyDeleteMeraki Cloud