Forwarded from Azamov | Dev (Azamov)
Merge sort. Birlashtirish orqali massivni tartiblash.
Salom! Bugun ancha qiyinroq mavzu - Birlashtirish orqali massivni tartiblash. Keling birgalashib, massivni tartibga solib qo'yamiz.😁 😄 😁
😇 Github: MergeSort
⏰ Time complexity: O(N * logN)
🔎 Space complexity: O(N)
🧑💻 G'oya 🧑💻
Birlashtirish orqali massivni tartiblash algoritmi berilgan massivni kichikroq massivlarga bo'lish va har bir kichik massivni tartiblash, keyin shu tartiblangan kichik massivlardan katta massivni birlashtirish orqali ishlaydi.
Boshqa so'z bilan aytganda, siz berilgan massivni ikkita teng massivga bo'lasiz, har birini tartiblaysiz va keyin ularni bir qayta birlashtirasiz. Bu jarayonni to'la massiv tartibga solingani qadar bajarasiz.
Nimaga bu algoritm zo'r? Chiziqli funksiya logarifmlik funksiyaga ko'paytirilgan funksiyani kvadrat funksiya bilan taqqoslashtiring.
🧑💻 Algorithm 🧑💻
Agar code-ga qarasangiz, siz 3ta metodni ko'rasiz. Bular mergeSort(), recursiveMergeSort() va merge().
Ahamiyat bering: Men ishlatgan usulda yangi kichik massivlarni yaratilmaydi. Buning o'rniga bitta uzunligi teng massiv yaratiladi va u elementlarni vaqtincha saqlab turish uchun ishlatiladi. Bunga elementlarning indekslarini chegaralar sifatida ishlatilish orqali erishiladi.
👩💻 mergeSort():
- workSpace massivini elementlarni vaqtincha saqlash uchun ishlatasiz.
- recursiveMergeSort() metodini chaqirasiz va unga parametrlar sifatida workSpace, chap chegara va o'ng chegaralarni berib yuborasiz.
👩💻 recursiveMergeSort():
Bu metod berilgan massivni teng qismlarga bo'lib chiqish va keyin ularni ulash uchun ishlatiladi.
- Agar chap va o'ng chegaralar teng bo'lsa, metod hozirgi bajarilishini to'xtatasiz.
- Aksincha massivning o'rta indeksini topasiz. Bundan so'ng rekursiv tarzda shu metodni chap qism va o'ng qism uchun bajarasiz. Keyin esa ikkita qism birlashtiriladi.
👩💻 merge():
Bu metod ikkita (yarim) qismni birlashtirish uchun ishlatiladi.
- Sizda chap chegara va chap chegara yana alohida ko'rsatgich bo'ladi. Chap chegara ko'rsatgichi bu vaqtincha massivga chap tarafdan qo'shiladigan elementning ko'rsatgichidir. Sizda yana o'ng chegara va o'ng qismning boshini ko'rsatuvchi o'zgaruvchi bo'ladi. Bular o'ng tarafda qo'shiladigan elementlarning chegaralarni ko'rsatuvchi sonlar.
- Birinchi while loop ichida siz ikkita qismdan eng kichik elementdan boshlab, eng katta elementgacha workSpace massiviga kiritib chiqasiz.
- Ikkinchi while loop ichida chap qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- Uchinchi while loop ichida esa o'ng qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- for loop ichida biz merge() metodining hozirgi bajarilishida tartiblangan elementlarni berilgan massivga yozib qo'yamiz.
☝️ Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. Wikipedia
Bugunga shu.
Agar qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.
Omad!✌️ 😎
@azamovme
Salom! Bugun ancha qiyinroq mavzu - Birlashtirish orqali massivni tartiblash. Keling birgalashib, massivni tartibga solib qo'yamiz.
Birlashtirish orqali massivni tartiblash algoritmi berilgan massivni kichikroq massivlarga bo'lish va har bir kichik massivni tartiblash, keyin shu tartiblangan kichik massivlardan katta massivni birlashtirish orqali ishlaydi.
Boshqa so'z bilan aytganda, siz berilgan massivni ikkita teng massivga bo'lasiz, har birini tartiblaysiz va keyin ularni bir qayta birlashtirasiz. Bu jarayonni to'la massiv tartibga solingani qadar bajarasiz.
Nimaga bu algoritm zo'r? Chiziqli funksiya logarifmlik funksiyaga ko'paytirilgan funksiyani kvadrat funksiya bilan taqqoslashtiring.
Agar code-ga qarasangiz, siz 3ta metodni ko'rasiz. Bular mergeSort(), recursiveMergeSort() va merge().
Ahamiyat bering: Men ishlatgan usulda yangi kichik massivlarni yaratilmaydi. Buning o'rniga bitta uzunligi teng massiv yaratiladi va u elementlarni vaqtincha saqlab turish uchun ishlatiladi. Bunga elementlarning indekslarini chegaralar sifatida ishlatilish orqali erishiladi.
- workSpace massivini elementlarni vaqtincha saqlash uchun ishlatasiz.
- recursiveMergeSort() metodini chaqirasiz va unga parametrlar sifatida workSpace, chap chegara va o'ng chegaralarni berib yuborasiz.
Bu metod berilgan massivni teng qismlarga bo'lib chiqish va keyin ularni ulash uchun ishlatiladi.
- Agar chap va o'ng chegaralar teng bo'lsa, metod hozirgi bajarilishini to'xtatasiz.
- Aksincha massivning o'rta indeksini topasiz. Bundan so'ng rekursiv tarzda shu metodni chap qism va o'ng qism uchun bajarasiz. Keyin esa ikkita qism birlashtiriladi.
Bu metod ikkita (yarim) qismni birlashtirish uchun ishlatiladi.
- Sizda chap chegara va chap chegara yana alohida ko'rsatgich bo'ladi. Chap chegara ko'rsatgichi bu vaqtincha massivga chap tarafdan qo'shiladigan elementning ko'rsatgichidir. Sizda yana o'ng chegara va o'ng qismning boshini ko'rsatuvchi o'zgaruvchi bo'ladi. Bular o'ng tarafda qo'shiladigan elementlarning chegaralarni ko'rsatuvchi sonlar.
- Birinchi while loop ichida siz ikkita qismdan eng kichik elementdan boshlab, eng katta elementgacha workSpace massiviga kiritib chiqasiz.
- Ikkinchi while loop ichida chap qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- Uchinchi while loop ichida esa o'ng qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- for loop ichida biz merge() metodining hozirgi bajarilishida tartiblangan elementlarni berilgan massivga yozib qo'yamiz.
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. Wikipedia
Bugunga shu.
Agar qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.
Omad!
@azamovme
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1
Fun Main() {
Val Scanner = Scanner(System.`In`)
Print("Enter Calculation: ")
Val Calculate = Scanner.Next()
Val Numbers = Arraylist<Float>()
Val Symbols = Arraylist<String>()
Var Currentindex = ""
For (C In Calculate) {
If (C.Isdigit() || C == '.') {
Currentindex += C
} Else If (C In "+-*/") {
Numbers.Add(Currentindex.Tofloat())
Symbols.Add(C.Tostring())
Currentindex = ""
}
}
Numbers.Add(Currentindex.Tofloat())
Var I = 0
While (I < Symbols.Size) {
If (Symbols[I] == "*" || Symbols[I] == "/") {
Val Result = If (Symbols[I] == "*") {
Numbers[I] * Numbers[I + 1]
} Else {
Numbers[I] / Numbers[I + 1]
}
Numbers[I] = Result
Numbers.Removeat(I + 1)
Symbols.Removeat(I)
} Else {
I++
}
}
Var Result = Numbers[0]
For (J In Symbols.Indices) {
When (Symbols[J]) {
"+" -> Result += Numbers[J + 1]
"-" -> Result -= Numbers[J + 1]
}
}
Println("Result: $Result")
}Tomorrow Contest 😄
Please open Telegram to view this post
VIEW IN TELEGRAM
This media is not supported in your browser
VIEW IN TELEGRAM
An unforgettable moment in history, captured through code and innovation 🥹
Please open Telegram to view this post
VIEW IN TELEGRAM
class Solution {
public int minimumTime(int[][] grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (var e : dist) {
Arrays.fill(e, 1 << 30);
}
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[] {0, 0, 0});
int[] dirs = {-1, 0, 1, 0, -1};
while (true) {
var p = pq.poll();
int i = p[1], j = p[2];
if (i == m - 1 && j == n - 1) {
return p[0];
}
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
int nt = p[0] + 1;
if (nt < grid[x][y]) {
nt = grid[x][y] + (grid[x][y] - nt) % 2;
}
if (nt < dist[x][y]) {
dist[x][y] = nt;
pq.offer(new int[] {nt, x, y});
}
}
}
}
}
}https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid/?envType=daily-question&envId=2024-11-29
LeetCode
Minimum Time to Visit a Cell In a Grid - LeetCode
Can you solve this real interview question? Minimum Time to Visit a Cell In a Grid - You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which…