Deklarata e problemit
Duke pasur parasysh një grup numrash të plotë jo-negativë numra, ju jeni pozicionuar fillimisht në indeksin e parë të grupit.
Çdo element në grup përfaqëson gjatësinë tuaj maksimale të kërcimit në atë pozicion.
Qëllimi juaj është të arrini indeksin e fundit në numrin minimal të kërcimeve.
Ju mund të supozoni se gjithmonë mund të arrini indeksin e fundit.
Deklarata e problemit është marrë nga: https://leetcode.com/problems/jump-game-ii/
Shembulli 1:
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.Shembulli 2:
Input: nums = [2, 3, 0, 1, 4]
Output: 2Kufizimet:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000Shpjegim
Problemi është një zgjatje e postimit tonë të vjetër në blog "Jump Game". Në problemin Jump Game, duhej të llogarisnim nëse mund të arrijmë indeksin e fundit të grupit apo jo. Në këtë problem, ne duhet të llogarisim numrin minimal të kërcimeve.
Qasja Brute Force
Qasja naive është zgjidhja e problemit duke përdorur rekursion. Rasti bazë në këtë rekursion do të ndodhë kur të arrijmë indeksin e fundit.
Ne do të thërrasim në mënyrë rekursive për të gjithë elementët e arritshëm nga elementi i parë. Kjo do të thotë që ne do të eksplorojmë të gjitha degët në pirgun e rekursionit dhe do të kthejmë numrin minimal të kërcimeve për të arritur indeksin e fundit.
Një fragment C++ i kësaj qasjeje është si më poshtë:
int minJumps(vector<int> &nums, int index){ if(index >= nums.size() - 1) return 0;int jumps = INT_MAX;for(int index = index + 1; i <= index + nums[index]; i++) jumps = min(jumps, 1 + minJumps(nums, i));return jumps; }
Kompleksiteti kohor i qasjes së mësipërme është O(2^N), dhe kompleksiteti i hapësirës është O(1).
Programimi dinamik
Duke përdorur programimin dinamik, ne mund ta reduktojmë kompleksitetin kohor në O(N²). Qasja naive ka nënprobleme të mbivendosura dhe rezultatet e tyre ruhen në një grup. Gjatë llogaritjes së kërcimit minimal për nyjen, kontrollojmë nëse rezultati është i pranishëm në grupin e ruajtur apo jo.
Një fragment C++ i kësaj qasjeje është si më poshtë:
int jump(vector<int>& nums) { int n = nums.size(); vector<int> store(n); store[0] = 0;for(int i = 1; i < n; i++) { store[i] = INT_MAX;for(int j = 0; j < i; j++) { if(i <= nums[j] + j && store[j] != INT_MAX){ store[i] = min(store[i], store[j] + 1); break; } } }return store[n - 1]; }
Kompleksiteti kohor i qasjes së mësipërme është O(N²) dhe kompleksiteti i hapësirës është O(n).
Qasje optimale e babëzitur
Në këtë qasje, ne përdorim një algoritëm të babëzitur që bën një zgjedhje optimale në çdo hap. Në çdo indeks, ne përcaktojmë hapat e ardhshëm që do të na afrojnë indeksit të fundit.
Le të kontrollojmë së pari algoritmin.
- set count, current, farthest = 0, 0, 0- if nums[0] == 0 || nums.length == 1 - return 0- loop for i = 0; i < nums.length; i++ - if nums[i] + i > farthest - set farthest = nums[i] + i- if i == current - increment count: count++ - current = farthest- for end- return count
Le të kontrollojmë zgjidhjet tona në C++, Golang dhe Javascript.
Zgjidhja C++
class Solution { public: int jump(vector<int>& nums) { int count = 0, current = 0, farthest = 0;if(nums[0] == 0 || nums.size() == 1) { return 0; }for(int i = 0; i < nums.size() - 1; i++) { if(nums[i] + i > farthest) { farthest = nums[i] + i; }if(i == current) { count++; current = farthest; } }return count; } };
Zgjidhja Golang
func jump(nums []int) int { count, current, farthest := 0, 0, 0if nums[0] == 0 || len(nums) == 1 { return 0 }for i := 0; i < len(nums) - 1; i++ { if nums[i] + i > farthest { farthest = nums[i] + i }if i == current { count++ current = farthest } }return count }
Zgjidhje Javascript
var jump = function(nums) { let count = 0, current = 0, farthest = 0;if(nums[0] == 0 || nums.length == 1) { return 0; }for(let i = 0; i < nums.length - 1; i++) { if(nums[i] + i > farthest) { farthest = nums[i] + i; }if(i == current) { count++; current = farthest; } }return count; };
Le të ekzekutojmë algoritmin tonë për një hyrje të caktuar.
Input: nums = [2, 3, 1, 1, 4]Step 1: count = 0 current = 0 farthest = 0Step 2: if nums[0] == 0 || nums.length == 1 2 == 0 || 5 == 1 falseStep 3: loop for i = 0; i < nums.length - 1; i++ i < nums.length - 1 0 < 5 - 1 0 < 4 trueif nums[i] + i > farthest nums[0] + 0 > 0 2 + 0 > 0 truefarthest = nums[i] + i = 2if i == current 0 == 0 truecount++ count = 1current = farthest = 2i++ i = 1Step 4: loop for i < nums.length - 1 i < nums.length - 1 1 < 5 - 1 1 < 4 trueif nums[i] + i > farthest nums[1] + 1 > 2 3 + 1 > 2 truefarthest = nums[i] + i = 4if i == current 1 == 2 falsei++ i = 2Step 5: loop for i < nums.length - 1 i < nums.length - 1 2 < 5 - 1 2 < 4 trueif nums[i] + i > farthest nums[2] + 2 > 4 1 + 2 > 4 falseif i == current 2 == 2 truecount++ count = 2current = farthest = 4i++ i = 3Step 6: loop for i < nums.length - 1 i < nums.length - 1 3 < 5 - 1 3 < 4 trueif nums[i] + i > farthest nums[3] + 3 > 4 1 + 1 > 4 falseif i == current 3 == 4 falsei++ i = 4Step 7: loop for i < nums.length - 1 i < nums.length - 1 4 < 5 - 1 4 < 4 falseStep 8: return countWe return the answer as 2.
Botuar fillimisht në https://alkeshghorpade.me.
Nëse ky postim ishte i dobishëm, ju lutemi klikoni butonin duartrokas 👏 më poshtë disa herë për të treguar mbështetjen tuaj për autorin 👇
