II.Wilhelm
Hectopat
Daha fazla
- Cinsiyet
- Erkek
- Meslek
- König
Merhaba. Biraz algoritma yeteneğimi geliştirmek için leetcode sitesinden soru çözmek istedim ve şöyle bir soruyla karşılaştım.
Kısacası şunu diyor. Bize bir sayı dizisi verilecek. Bu diziyi birbirine bitişik şekilde tamamen parçalara bölmemiz gerekiyor. Bu parçalar, aşağıda verilmiş 3 kuraldan birine uymak zorunda.
1. Parçada iki tane sayı olacak ve bu iki sayı birbirine eşit olacak. Örnek: [2,2]
2. Parçada üç tane sayı olacak ve bu üç sayı birbirine eşit olacak. Örnek [4,4,4]
3. Parçada üç tane sayı olacak ve bunlar birer birer artar şekilde olacak. Örnek [3,4,5]
Dizi, bu şekilde parçalanabiliyorsa true, değilde false döndürülecek.
Bu soru için şöyle bir çözüm getirdim. Recursive metot kullanıyor.
Bu kod başarılı bir şekilde çalışıyor, ama eleman sayısı arttıkça iyice yavaşlamaya başlıyor ve çok yavaş kaldığı için bu çözümü kabul etmiyor. Başka nasıl bir çözüm üretilebilir?
Check if There is a Valid Partition For The Array - LeetCode
Can you solve this real interview question? Check if There is a Valid Partition For The Array - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Kısacası şunu diyor. Bize bir sayı dizisi verilecek. Bu diziyi birbirine bitişik şekilde tamamen parçalara bölmemiz gerekiyor. Bu parçalar, aşağıda verilmiş 3 kuraldan birine uymak zorunda.
1. Parçada iki tane sayı olacak ve bu iki sayı birbirine eşit olacak. Örnek: [2,2]
2. Parçada üç tane sayı olacak ve bu üç sayı birbirine eşit olacak. Örnek [4,4,4]
3. Parçada üç tane sayı olacak ve bunlar birer birer artar şekilde olacak. Örnek [3,4,5]
Dizi, bu şekilde parçalanabiliyorsa true, değilde false döndürülecek.
Bu soru için şöyle bir çözüm getirdim. Recursive metot kullanıyor.
C#:
namespace YazilimCalismasiConsole69;
internal class Program
{
static void Main(string[] args)
{
int[] Nums;
Nums = new int[] { 4, 4, 4, 5, 6, 7, 8, 9,}; //Herhangibi sayı dizisi
Solution solution = new Solution();
bool Validation = solution.ValidPartition(Nums);
Console.WriteLine(Validation);
Console.ReadLine();
}
}
public class Solution
{
delegate bool IsValidNumberConditionHandler(int[] nums, int startIndex, out int HowManyElementLeft);
public bool ValidPartition(int[] nums)
{
IsValidNumberConditionHandler Conditions = IsValidConditionOne;
Conditions += IsValidConditionTwo;
Conditions += IsValidConditionThree;
return IsValidArray(nums, 0, Conditions);
}
private bool IsValidArray(int[] nums, int startIndex, IsValidNumberConditionHandler Conditions)
{
Delegate[] Delegates = Conditions.GetInvocationList();
for (int i = 0; i < Delegates.Length; i++)
{
IsValidNumberConditionHandler conditionHandler = (IsValidNumberConditionHandler)Delegates[i];
int HowManyElementLeft = -1;
bool isValids = conditionHandler.Invoke(nums, startIndex, out HowManyElementLeft); //Verilen şartlara uyan bir dizi parçası oluşturabiliyormu kontrolü
if (isValids) // evetse
{
if (HowManyElementLeft == 0) //dizideki elemanlar bitirilmiş, tamamen başarılı bir şekilde parçalara ayrıldıysa
{
return true;
}
else if (HowManyElementLeft == 1 || HowManyElementLeft < 0) //dizi başarılı bir şekilde parçalara ayrılamamış ve tıkanmışsa
{
continue; // diğer parçalama şekline geç
}
else if (HowManyElementLeft >= 2) // Eğer dizi parçalanmış ama hala parçalanmamış kısımlar kaldıysa
{
bool ContinueValidation = IsValidArray(nums, nums.Length - HowManyElementLeft, Conditions); //Recursive ile geri kalan yerine aynı işlemler yaptırılıyor.
if (ContinueValidation) //eğer yukardan true dönmüş ve geri kalan yer başarıyla parçalanmışsa
{
return true;
}
else //geri kalanı başarıyla parçalanmadıysa diğer parçalama şekline geç
{
continue;
}
}
}
else if (!isValids) // daha baştan parçalanma başarısız olmuşsa diğer parçalama şekline geç
{
continue;
}
}
return false; // dizi parçalanmamış
}
private bool IsValidConditionOne(int[] nums, int startIndex, out int HowManyElementLeft)
{
HowManyElementLeft = ((nums.Length - 1) - (startIndex + 1));
if (nums.Length - 1 >= startIndex + 1)
{
return nums[startIndex] == nums[startIndex + 1];
}
return false;
}
private bool IsValidConditionTwo(int[] nums, int startIndex, out int HowManyElementLeft)
{
HowManyElementLeft = (nums.Length - 1) - (startIndex + 2);
if (nums.Length - 1 >= startIndex + 2)
{
return (nums[startIndex] == nums[startIndex + 1]) && (nums[startIndex] == nums[startIndex + 2]);
}
return false;
}
private bool IsValidConditionThree(int[] nums, int startIndex, out int HowManyElementLeft)
{
HowManyElementLeft = (nums.Length - 1) - (startIndex + 2);
if (nums.Length - 1 >= startIndex + 2)
{
return nums[startIndex] + 1 == nums[startIndex + 1] && nums[startIndex] + 2 == nums[startIndex + 2];
}
return false;
}
}
Bu kod başarılı bir şekilde çalışıyor, ama eleman sayısı arttıkça iyice yavaşlamaya başlıyor ve çok yavaş kaldığı için bu çözümü kabul etmiyor. Başka nasıl bir çözüm üretilebilir?