تایپ اسکریپت کدگذاری Chronicles: Can Place Flowers

بیان مسأله:

شما یک گلدان بلند دارید که برخی از قطعات در آن کاشته شده اند و برخی نه. با این حال، گل را نمی توان در زمین های مجاور کاشت.

یک آرایه عدد صحیح داده شده است flowerbed حاوی 0 و 1 که 0 به معنای خالی و 1 به معنای خالی نبودن و یک عدد صحیح است n، برگشت true اگر n گلهای جدید را می توان بدون نقض قانون عدم وجود گل مجاور در گلدان کاشت false در غیر این صورت.

مثال 1:

• ورودی: flowerbed = [1,0,0,0,1]، n = 1
• خروجی: true

مثال 2:

• ورودی: flowerbed = [1,0,0,0,1]، n = 2
• خروجی: false

محدودیت ها:

• 1
• flowerbed[i] 0 یا 1 است.
• در گلزار دو گل مجاور وجود ندارد.
• 0

فرآیند تفکر اولیه:

برای حل این مشکل، باید از طریق بستر گل تکرار کنیم و هر موقعیت را بررسی کنیم تا مشخص شود آیا می توان گلی را کاشت. اگر یک موقعیت خالی (0) باشد و هر دو موقعیت مجاور یا خالی یا خارج از محدوده باشند، می‌توانیم یک گل در آنجا بکاریم.

راه حل اساسی:

کد:

function canPlaceFlowersBruteForce(flowerbed: number[], n: number): boolean {
    let count = 0;

    for (let i = 0; i  flowerbed.length; i++) {
        if (flowerbed[i] === 0) {
            let prevEmpty = (i === 0) || (flowerbed[i - 1] === 0);
            let nextEmpty = (i === flowerbed.length - 1) || (flowerbed[i + 1] === 0);

            if (prevEmpty && nextEmpty) {
                flowerbed[i] = 1;
                count++;
                if (count >= n) {
                    return true;
                }
            }
        }
    }

    return count >= n;
}

تجزیه و تحلیل پیچیدگی زمانی:

• پیچیدگی زمانی: O(n^2)، که در آن n طول آرایه تخت گل است. حلقه داخلی به طور موثر این رویکرد را کارآمدتر می کند.
• پیچیدگی فضا: O(1)، همانطور که ما آرایه تخت گل را در جای خود اصلاح می کنیم و فقط از مقدار ثابتی از فضای اضافی استفاده می کنیم.

محدودیت ها:

راه حل brute force برای اندازه های ورودی بزرگتر به دلیل پیچیدگی زمانی بالاتر بهینه نیست.

راه حل بهینه:

راه‌حل بهینه‌سازی شده همچنان از طریق آرایه تخت گل تکرار می‌شود، اما پس از کاشت گل، از بررسی‌های غیر ضروری با حرکت به موقعیت بعدی پس از کاشت گل صرفنظر می‌کند و اطمینان حاصل می‌کند که گل‌های مجاور را نکاریم.

کد:

function canPlaceFlowersOptimized(flowerbed: number[], n: number): boolean {
    let count = 0;
    let i = 0;

    while (i  flowerbed.length) {
        if (flowerbed[i] === 0 && 
            (i === 0 || flowerbed[i - 1] === 0) && 
            (i === flowerbed.length - 1 || flowerbed[i + 1] === 0)) {
            flowerbed[i] = 1;  // Plant a flower here
            count++;
            i += 2;  // Move to the position after the next one
        } else {
            i++;
        }

        if (count >= n) {
            return true;
        }
    }

    return count >= n;
}

تجزیه و تحلیل پیچیدگی زمانی:

• پیچیدگی زمانی: O(n)، که در آن n طول آرایه تخت گل است. یک بار از طریق آرایه تخت گل تکرار می کنیم.
• پیچیدگی فضا: O(1)، همانطور که ما آرایه تخت گل را در جای خود اصلاح می کنیم و فقط از مقدار ثابتی از فضای اضافی استفاده می کنیم.

بهبودها نسبت به راه حل اساسی:

• راه‌حل بهینه‌شده با حرکت به موقعیت بعد از کاشت گل، بررسی‌های غیرضروری را نادیده می‌گیرد و تضمین می‌کند که گل‌های مجاور را نکاریم.

موارد لبه و تست:

موارد لبه:

1. تخت گل کاملاً خالی است.
2. تخت گل دارای کرت های خالی و غیر خالی متناوب است.
3. n 0 است، یعنی نیازی به کاشت گل جدید نیست.
4. n بزرگتر از تعداد احتمالی موقعیت های قابل کاشت در بستر گل است.

موارد آزمون:

console.log(canPlaceFlowersBruteForce([1,0,0,0,1], 1)); // true
console.log(canPlaceFlowersBruteForce([1,0,0,0,1], 2)); // false
console.log(canPlaceFlowersBruteForce([0,0,1,0,0], 1)); // true
console.log(canPlaceFlowersBruteForce([0,0,1,0,0], 2)); // true
console.log(canPlaceFlowersBruteForce([0,0,1,0,1], 1)); // false
console.log(canPlaceFlowersBruteForce([1,0,0,0,0,1], 1)); // true
console.log(canPlaceFlowersBruteForce([1,0,0,0,0,1], 2)); // false
console.log(canPlaceFlowersBruteForce([0,0,0,0,0,0], 3)); // true
console.log(canPlaceFlowersBruteForce([0,0,0,0,0,0], 4)); // false

console.log(canPlaceFlowersOptimized([1,0,0,0,1], 1)); // true
console.log(canPlaceFlowersOptimized([1,0,0,0,1], 2)); // false
console.log(canPlaceFlowersOptimized([0,0,1,0,0], 1)); // true
console.log(canPlaceFlowersOptimized([0,0,1,0,0], 2)); // true
console.log(canPlaceFlowersOptimized([0,0,1,0,1], 1)); // false
console.log(canPlaceFlowersOptimized([1,0,0,0,0,1], 1)); // true
console.log(canPlaceFlowersOptimized([1,0,0,0,0,1], 2)); // false
console.log(canPlaceFlowersOptimized([0,0,0,0,0,0], 3)); // true
console.log(canPlaceFlowersOptimized([0,0,0,0,0,0], 4)); // false

راهبردهای کلی حل مسئله:

1. مشکل را درک کنید: برای درک الزامات و محدودیت ها، بیانیه مشکل را به دقت بخوانید.
2. شناسایی عملیات کلیدی: عملیات کلیدی مورد نیاز را تعیین کنید، مانند بررسی کرت های مجاور و کاشت گل.
3. بهینه سازی برای خوانایی: از منطق واضح و مختصر استفاده کنید تا مطمئن شوید کد به راحتی قابل پیگیری است.
4. به طور کامل تست کنید: برای اطمینان از صحت محلول را با موارد مختلف از جمله موارد لبه تست کنید.

شناسایی مشکلات مشابه:

1. دستکاری آرایه:

   • مشکلاتی که در آنها باید عناصر یک آرایه را بر اساس شرایط خاص تغییر دهید.
   • مثال: انتقال صفرها به انتهای یک آرایه.

2. الگوریتم های حریص:

   • مشکلاتی که در آنها می توان از رویکرد حریصانه برای یافتن راه حل بهینه با انجام بهترین انتخاب در هر مرحله استفاده کرد.
   • مثال: زمان‌بندی فاصله برای یافتن حداکثر تعداد بازه‌های غیر همپوشانی.

3. مشکلات شبیه سازی:

   • مشکلاتی که در آن باید یک فرآیند را گام به گام بر اساس قوانین داده شده شبیه سازی کنید.
   • مثال: شبیه سازی گسترش یک ویروس در جمعیتی که با یک آرایه نشان داده شده است.

نتیجه:

• مشکل تعیین اینکه آیا می‌توان گل‌های جدید را بدون نقض قانون عدم وجود گل‌های مجاور در یک گلخانه کاشت کرد، می‌تواند با استفاده از رویکرد brute force و رویکرد بهینه‌شده به طور موثر حل شود.
• درک مشکل و تقسیم آن به بخش های قابل مدیریت بسیار مهم است.
• استفاده از منطق روشن و بهینه سازی برای خوانایی، تضمین می کند که راه حل آسان است.
• تست با لبه های مختلف استحکام را تضمین می کند.
• شناخت الگوها در مسائل می تواند به اعمال راه حل های مشابه برای چالش های دیگر کمک کند.

با تمرین چنین مسائل و استراتژی هایی می توانید مهارت های حل مسئله خود را ارتقا دهید و برای چالش های مختلف کدنویسی آمادگی بیشتری داشته باشید.