Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalar Universititeti “R va ma” fakulteti

Muhammad al-Xorazmiy nomidagi
Toshkent Axborot Texnologiyalar
Universititeti “R va MA” fakulteti
051-20 guruh talabasi Alijonov Muhammadqodir.

Ma’lumotlar tuzilmasi va algoritmlar.
Kodlar C# (.NET 6) da yozildi.Masalalar LeetCode saytidan olindi.

Bajardi:Alijonov Muhammadqodir.
Tekshirdi:

Toshkent 2022

1-masala;
English version:
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
UZB version:
Tartibga solinmagan butun sonlar qatori berilgan bo'lsa, eng kichik etishmayotgan musbat sonni qaytaring.
Siz O(n) vaqtida ishlaydigan va doimiy qo'shimcha joydan foydalanadigan algoritmni amalga oshirishingiz kerak.

public class Solution {

public int FirstMissingPositive(int[] nums) {
if (nums.Length == 1 && nums[0] == 1) return 2;
else if (nums.Length == 1 && nums[0] != 1) return 1;

Array.Sort(nums);

int i = 0;
int lowest = int.MaxValue;
for (; i < nums.Length - 1; i++) {
// ignore negative numbers
if (nums[i] < 0) continue;

// save lowest number

if (nums[i] < lowest) lowest = nums[i];

// checks for if the numbers are one after the other

if (nums[i] + 1 == nums[i + 1] || nums[i] == nums[i + 1]) continue;

// if they aren't return based on the lowest number

return lowest == 1 || lowest + 1 == 1 ? nums[i] + 1 : 1;
}
// return based on the lowest number if nothing
// was returned during the loop
return lowest == 1 || lowest + 1 == 1 || nums[i] == 1 ? nums[i] + 1 : 1;
}
}

2-maslala;
English version:
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
UZB version:
n butun son berilgan bo'lsa, yig'indisi n ga teng bo'lgan eng kam mukammal kvadrat sonlarni qaytaring.
Mukammal kvadrat - bu butun sonning kvadrati bo'lgan butun son; boshqacha qilib aytganda, u o'zi bilan qandaydir butun sonning ko'paytmasidir. Masalan, 1, 4, 9 va 16 mukammal kvadratlar, 3 va 11 esa emas.

public class Solution {
public int NumSquares(int n) {
int[] d = new int[n + 1];

for(int i = 1; i <= n; i++)

{
d[i] = int.MaxValue;

for(int j = 1; j * j <= i; j++)

{
d[i] = Math.Min(d[i], d[i - j * j] + 1);
}
}

return d[n];

}
}