2375. کمترین تعداد را از رشته DI بسازید

2375. کمترین تعداد را از رشته DI بسازید

مشکل: واسطه

مباحث: Stringبا Backtrackingبا Stackبا Greedy

به شما داده می شود 0-شاخص رشته pattern از طول n متشکل از شخصیت ها 'I' به معنای افزایش و 'D' معنی کاهش دهندهبشر

بوها 0-شاخص رشته num طول n + 1 با استفاده از شرایط زیر ایجاد می شود:

• num از رقم تشکیل شده است '1' به '9'، جایی که هر رقم حداکثر یک بار استفاده می شود.
• اگر pattern[i] == 'I'، پس num[i] < num[i + 1]بشر
• اگر pattern[i] == 'D'، پس num[i] > num[i + 1]بشر

بازگشت واژگان شناسی کوچکترین رشته num این شرایط را برآورده می کندبشر

مثال 1:

• ورودی: الگوی = “iiididdd”
• خروجی: “123549876”
• توضیح:
  • در شاخص های 0 ، 1 ، 2 و 4 باید آن شماره را داشته باشیم[i] <[i+1]بشر
  • در شاخص های 3 ، 5 ، 6 و 7 باید آن شماره را داشته باشیم[i] > شماره[i+1]بشر
  • برخی از مقادیر ممکن NUM “245639871” ، “135749862” و “123849765” است.
  • می توان ثابت کرد که “123549876” کوچکترین شماره ممکن است که شرایط را برآورده می کند.
  • توجه داشته باشید که “123414321” امکان پذیر نیست زیرا رقم “1” بیش از یک بار استفاده می شود.

مثال 2:

• ورودی: الگوی = “DDD”
• خروجی: “4321”
• توضیح:
  • برخی از مقادیر احتمالی NUM “9876” ، “7321” و “8742” است.
  • می توان ثابت کرد که “4321” کوچکترین شماره ممکن است که شرایط را برآورده می کند.

محدودیت ها:

• 1 <= pattern.length <= 8
• pattern فقط از نامه ها تشکیل شده است 'I' وت 'D'بشر

نکته:

1. با محدودیت ها ، آیا می توانیم هر رشته ممکن را تولید کنیم؟
2. بله ما می توانیم حال ما فقط باید بررسی کنیم که آیا رشته تمام شرایط را برآورده می کند یا خیر.

راه حل:

ما باید بر اساس الگوی مشخصی از شخصیت های “I” (در حال افزایش) و “D” (کاهش) ، کوچکترین رشته را از نظر واژگونی بسازیم. راه حل باید اطمینان حاصل کند که هر رقم از 1 تا 9 دقیقاً یک بار استفاده می شود و توالی به الگوی داده شده پایبند است.

رویکرد

بینش کلیدی این است که تشخیص دهیم که شخصیت های متوالی “D” در این الگوی نیاز به کاهش توالی رقم ها دارند. با معکوس کردن بخش هایی از یک دنباله در ابتدا در حال افزایش از رقم در هر زمان که گروهی از D های متوالی مواجه شود ، می توانیم توالی مورد نیاز را به طور مؤثر تولید کنیم. این رویکرد تضمین می کند که ما با استفاده از خواص بخش های معکوس برای رسیدگی به دنباله های کاهش ، از نظر واژگونی کوچکترین دنباله را تولید می کنیم.

بیایید این راه حل را در PHP پیاده سازی کنیم: 2375. کمترین تعداد را از رشته DI بسازید

/**
 * @param String $pattern
 * @return String
 */
function smallestNumber($pattern) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $arr
 * @param $start
 * @param $end
 * @return void
 */
function reverseSubarray(&$arr, $start, $end) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example cases
echo smallestNumber("IIIDIDDD") . "\n"; // Output: "123549876"
echo smallestNumber("DDD") . "\n";       // Output: "4321"
?>

توضیح:

1. شروع: با کوچکترین دنباله ممکن از ارقام از 1 تا n+1 شروع کنید ، جایی که n طول الگوی است.
2. از طریق الگوی تکرار می شود: هر شخصیت را در الگوی برای شناسایی بخش های متوالی “دنبال کنید.
3. بخش های معکوس برای 'd: برای هر بخش از D ’متوالی ، بخش مربوطه را در دنباله رقمی معکوس کنید تا از ترتیب کاهش نیاز استفاده کنید.
4. نتیجه ساخت: آرایه حاصل از رقم ها را به یک رشته تبدیل کرده و آن را برگردانید.

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

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: