#1. Robot in a Grid (p.d.)
Un robot se află într-o matrice, in coltul din stanga sus. El se poate deplasa doar la dreapta sau in jos, daca celula vizata nu contine un obstacol. Tinta lui este sa ajunga in coltul din dreapta jos al matricii. Sa se afle in cate moduri poate ajunge robotul la destinatie.
class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
// go from destination to origin
Map<Integer,Integer> cache = new HashMap<>();
return search(grid, grid.length-1, grid[0].length-1, cache);
}
private int search(int[][] grid, int i, int j, Map<Integer,Integer> cache) {
if (reachedBack(grid, i, j)) {
return 1; // found one way!
}
// Number of ways to reach grid[i][j] = ways to reach grid[i-1][j] (go up) +
// ways to reach grid[i][j-1] (left)
if (isCellFit(grid, i, j)) {
int indexUp = (i-1) * grid[0].length + j;
int pathUp = 0;
// element indexUp could be already visited but not necessarily attainable from grid[i][j]
if (isCellFit(grid, i-1, j)) {
pathUp = cache.containsKey(indexUp) ? cache.get(indexUp) : search(grid, i-1, j, cache);
}
int indexLeft = i * grid[0].length + j-1;
int pathLeft = 0;
if (isCellFit(grid, i, j-1)) {
pathLeft = cache.containsKey(indexLeft) ? cache.get(indexLeft) : search(grid, i, j-1, cache);
}
int index = i * grid[0].length + j;
cache.put(index, pathUp + pathLeft); // grid[i][j] is visited and its result established
return pathUp + pathLeft;
}
return 0;
}
private boolean isCellFit(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
return false; // out of grid
}
return grid[i][j] == 0; // should be obstacle free
}
private boolean reachedBack(int[][] grid, int i, int j) {
return i==0 && j==0 && grid[i][j] == 0;
}
}
#2. Toate submultimile unei multimi (recursivitate)
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
result.addAll(find(Arrays.stream(nums).boxed().collect(Collectors.toList())));
return result;
}
private List<List<Integer>> find(List<Integer> set) {
if (set.size() == 1) {
return Arrays.asList(Arrays.asList(set.get(0)));
}
List<List<Integer>> result = new ArrayList<>();
result.add(Arrays.asList(set.get(0))); // primul element
List<List<Integer>> subsets = find(set.subList(1, set.size()));
result.addAll(subsets); // submultimile din (A - primul elem)
for (List<Integer> subset : subsets) {
List<Integer> subsetCopy = clone(subset);
// adaug primul element la toate submultimile din (A - primul elem)
subsetCopy.add(set.get(0));
result.add(subsetCopy);
}
return result;
}
private List<Integer> clone(List<Integer> set) {
List<Integer> clonedSet = new ArrayList<>();
clonedSet.addAll(set);
return clonedSet;
}
}
#3. Inmultirea a doua numere fara a folosi * , doar prin adunari, scaderi sau deplasari de biti, in numar minim de operatii. (recursivitate)
public class MultiplyIntegers {
public static int solve(int a, int b) {
int minAb = Math.min(a, b);
int maxAb = Math.max(a, b);
return multiply(minAb, maxAb); // to optimize the number of recursions
}
private static int multiply(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
if (a == 1) {
return b;
}
// a is even => multiply(a,b) = 2 * multiply(a/2, b)
// a is odd => multiply(a,b) = 2 * multiply(a/2, b) + b
int partialRes = multiply(a >> 1, b); // multiply (a/2, b)
partialRes <<= 1; // partialRes *= 2
if (a % 2 == 1) {
partialRes += b;
}
return partialRes;
}
public void test() {
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase(5, 3, 15));
testCases.add(new TestCase(10, 7, 70));
testCases.add(new TestCase(31, 35, 1085));
testCases.add(new TestCase(16, 6, 96));
testCases.add(new TestCase(3, 0, 0));
testCases.add(new TestCase(27, 4, 108));
testCases.add(new TestCase(36475, 4249, 154982275));
testCases.add(new TestCase(4585, 42339, 194124315));
long startTime = System.nanoTime();
for (TestCase testCase : testCases) {
int result = MultiplyIntegers.solve(testCase.a, testCase.b);
System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
(result == testCase.result ?
"PASSED" :
"FAILED with output=" + result + " " +
"[expected=" + testCase.result + "] \t\t<------"));
}
long endTime = System.nanoTime();
System.out.println("Executed in " + (endTime - startTime)/1000000 + " ms.");
}
public static void main(String args[]) {
new MultiplyIntegers().test();
}
public class TestCase {
public final int a;
public final int b;
public final int result;
public TestCase(int a, int b, int result) {
this.a = a;
this.b = b;
this.result = result;
}
}
}
#4. Turnurile din Hanoi
Se dau 3 turnuri: A, B, C. Pe fiecare turn se pot aseza discuri aranjate descrescator, cele mai mari stand la baza si cele mai mici deasupra. Sa se mute toate discurile din A in C, folosind B ca intermediar, respectand conditia. Care e numarul minim de miscari pentru a realiza acest transfer?
Nota: se porneste de la cazul de baza - 1 disc, care are nevoie de o singura miscare pt a ajunge in C. Apoi simulam pe hartie ce se intampla cand avem 2 discuri. Apoi 3. De fiecare data se poate observa (de la n >= 2) ca turnul B se comporta ca un buffer. De asemenea, pentru a rezolva cazuri superioare, ne putem folosi de rezultatul anterior deja calculat, la care mai avem de mutat un singur disc (ultimul). Astfel: pentru a muta n discuri, trebuie sa mutam n-1 discuri din A in B (folosind C ca intermediar) pentru a lasa liber ultimul disc din A, apoi mutat direct discul din A in C, apoi mutate cele n-1 discuri din B in C (folosind A ca intermediar). Se observa ca numarul de mutari este 2^n - 1.
Nota: design-ul solutiei. Obiectele Disk si Tower sunt "personalizate". Am facut cateva validari. Tower detine o stiva de obiecte Disk. Adaugarea se face intr-o metoda din Tower afectand un alt obiect Tower din care se scoate un disc.
import java.util.*;
public class Hanoi {
private int moveDisks (int n, Tower origin, Tower destination, Tower buffer) throws Exception {
if (n == 1) {
destination.takeFrom(origin);
return 1; // one move
}
int steps = 0;
steps += moveDisks(n-1, origin, buffer, destination); // move first n-1 from origin to buffer
destination.takeFrom(origin); // move last element from origin to dest
steps++;
steps += moveDisks(n-1, buffer, destination, origin); // move back n-1 elements from buffer to dest
return steps;
}
public static void main(String args[]) {
Hanoi hanoi = new Hanoi();
hanoi.test();
}
public void test() {
Hanoi hanoi = new Hanoi();
List<Disk> disks = new ArrayList<>();
disks.add(new Disk(1, 5));
disks.add(new Disk(2, 2));
disks.add(new Disk(3, 8));
disks.add(new Disk(4, 1));
disks.add(new Disk(5, 3));
disks.add(new Disk(6, 4));
disks.add(new Disk(6, 7));
disks.add(new Disk(6, 6));
// hanoi(n) = 2^n - 1
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase(new Tower("A", disks.subList(0, 1)), new Tower("B"), new Tower("C"), 1));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 2)), new Tower("B"), new Tower("C"), 3));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 3)), new Tower("B"), new Tower("C"), 7));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 4)), new Tower("B"), new Tower("C"), 15));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 5)), new Tower("B"), new Tower("C"), 31));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 6)), new Tower("B"), new Tower("C"), 63));
testCases.add(new TestCase(new Tower("A", disks.subList(0, 7)), new Tower("B"), new Tower("C"), 127));
testCases.add(new TestCase(new Tower("A", disks), new Tower("B"), new Tower("C"), 255));
for (TestCase tc : testCases) {
try {
int numberOfDisks = tc.origin.getNumberOfDisks();
int res = hanoi.moveDisks(numberOfDisks, tc.origin, tc.destination, tc.buffer);
boolean testResult = res == tc.expectedMoves && tc.origin.getNumberOfDisks() == 0 &&
tc.buffer.getNumberOfDisks() == 0 &&
tc.destination.getNumberOfDisks() == numberOfDisks;
System.out.println("Test case #" + testCases.indexOf(tc) + " " +
(testResult ?
"PASSED" :
"FAILED with moves=" + res + " " +
"[expected.moves=" + tc.expectedMoves + "] AND " +
"with origin.size=" + tc.origin.getNumberOfDisks() + " AND " +
"with buffer.size=" + tc.buffer.getNumberOfDisks() + " AND " +
"with destination.size=" + tc.destination.getNumberOfDisks() +
" [expected.dest.size=" + numberOfDisks + "] \t\t<------"));
} catch (Exception e) {
e.printStackTrace();
}
}
}
class Tower {
String label;
Stack<Disk> disks;
public Tower(String label) {
this.label = label;
this.disks = new Stack<>();
}
public Tower(String label, List<Disk> initDisks) {
this.label = label;
this.disks = new Stack<>();
Collections.sort(initDisks);
for (Disk disk : initDisks) {
this.disks.push(disk);
}
}
public void takeFrom(Tower from) throws Exception {
if (from.disks.isEmpty()) {
throw new Exception("Nothing to add from!");
}
Disk diskToAdd = from.disks.peek();
if (!disks.isEmpty() && diskToAdd.value > disks.peek().value) {
throw new Exception("Cannot add disk with value " + diskToAdd.value + " to tower " + label);
}
disks.push(from.disks.pop());
}
public int getNumberOfDisks() {
return this.disks.size();
}
@Override
public String toString() {
return "Tower " + label + " has " + disks.size() + " disks.";
}
}
class Disk implements Comparable<Disk> {
int label;
int value;
public Disk(int label, int value) {
this.label = label;
this.value = value;
}
@Override
public int compareTo(Disk disk) {
if (disk.value == value) {
return 0;
}
return disk.value - value;
}
}
public class TestCase {
public final Tower origin;
public final Tower buffer;
public final Tower destination;
public final int expectedMoves;
public TestCase(Tower tower, Tower buffer, Tower destination, int expectedMoves) {
this.origin = tower;
this.buffer = buffer;
this.destination = destination;
this.expectedMoves = expectedMoves;
}
}
}
Niciun comentariu:
Trimiteți un comentariu