| class Solution { | |
| public int climbingStairs(int n) { | |
| int dp[] = new int[n+1]; | |
| Arrays.fill(dp, -1); | |
| return solve(n, dp); | |
| } |
| /* | |
| Programare Dinamica | |
| ------------------- | |
| Programarea dinamica (dezvoltata in 1950 de Bellman) esteo tehnica algoritmica ce conduce, de ce le mai multe ori, la un timp de calcul polinomial(O(n^2), O(n)). Spre deosebire de alte tehnici, | |
| ea furnizeaza intotdeauna solutia optima, dar nu se poate aplica oricarei probleme, ci doar celor care indepliplinesc anumite conditii. | |
| Principiul de Optimalitate |
| //Floyd's Algorithms Cycle detection - find duplicate Complexity O(n) | |
| class Solution { | |
| public int findDuplicate(int[] nums) { | |
| int slow = nums[0]; | |
| int fast = nums[0]; |
| //solution: n log n | |
| //n log n (Array.sort(nums)) | |
| //O(n^2) | |
| //O(n) | |
| class Solution { | |
| //[1,3,4,2,2] | |
| //length = 5 | |
| //low = 1; | |
| //high = 5; |
| class Solution { | |
| public int findDuplicate(int[] nums) { | |
| Arrays.sort(nums); //quicksort O(n log n) | |
| for(int i = 0; i < nums.length; ++i) { //O(n) | |
| if(nums[i] == nums[i+1]) return nums[i]; |
| import java.io.*; | |
| import java.util.Scanner; | |
| /* | |
| 1 2 3 | |
| 1 3 2 | |
| ..... | |
| 3 2 1 | |
| n! = 1 * 2 * ... * n | |
| */ |
/* Introducere in Big O Notation
Cum calculam suma 1 + 2 + 3 + ... + n = ?
Varianta1: Big O(n^2) - complexitate patratica - 2 for Varianta2: Big O(n) - complexitate liniara - un for Varianta3: Big O(1) - complexitate constanta - 1 formula
n^k . unde k = 0,1,2,3,4,5....
| /* | |
| 1 | |
| 1 1 | |
| 1 2 1 | |
| 1 3 3 1 | |
| 1 4 6 4 1 | |
| 1 | |
| 1 1 | |
| 1 1 1 |
| Binary Search | |
| ------------ | |
| Cautarea binara este un algoritm eficient de cautare a unui element intr-un array sortat, care functioneaza prin injumatatirea repetata a spatiului de cautare. | |
| Cum functioneaza? | |
| - se porneste cu intregul array; |
| //11 12 22 25 64 | |
| public class SortingAlgorithms { | |
| //Selection Sort (by minimum) | |
| //la fiecare pas , gasim minimul in subsirul [i, n-1] | |
| //si il punem pe pozitia i prin swap | |
| public static void selectionByMin(int[] arr) { |