2683. همسایه Bitwise XOR – DEV Community

2683. Bitwise XOR همسایه

سختی: متوسط

موضوعات: Array، Bit Manipulation

الف 0-شاخص شده آرایه derived با طول n از محاسبه به دست می آید به صورت بیتی XOR (⊕) مقادیر مجاور در a آرایه باینری original از طول n.

به طور خاص، برای هر شاخص i در محدوده [0, n - 1]:

• اگر i = n - 1، سپس derived[i] = original[i] ⊕ original[0].
• در غیر این صورت، derived[i] = original[i] ⊕ original[i + 1].

یک آرایه داده شده است derived، وظیفه شما این است که تعیین کنید آیا الف وجود دارد یا خیر آرایه باینری معتبر original که می توانست تشکیل شود derived.

بازگشت درست است اگر چنین آرایه ای وجود داشته باشد یا نادرست در غیر این صورت.

• آرایه باینری آرایه ای است که فقط شامل 0 ها و 1

مثال 1:

• ورودی: مشتق شده = [1,1,0]
• خروجی: درست است
• توضیح: یک آرایه اصلی معتبر که مشتق شده است [0,1,0].
  • مشتق شده است[0] = اصلی[0] ⊕ اصل[1] = 0 ⊕ 1 = 1
  • مشتق شده است[1] = اصلی[1] ⊕ اصل[2] = 1 ⊕ 0 = 1
  • مشتق شده است[2] = اصلی[2] ⊕ اصل[0] = 0 ⊕ 0 = 0

مثال 2:

• ورودی: مشتق شده = [1,1]
• خروجی: درست است
• توضیح: یک آرایه اصلی معتبر که مشتق شده است [0,1].
  • مشتق شده است[0] = اصلی[0] ⊕ اصل[1] = 1
  • مشتق شده است[1] = اصلی[1] ⊕ اصل[0] = 1

مثال 3:

• ورودی: مشتق شده = [1,0]
• خروجی: نادرست
• توضیح: هیچ آرایه اصلی معتبری وجود ندارد که مشتق شده باشد.

محدودیت ها:

• n == derived.length
• 1 <= n <= 105
• مقادیر در derived هستند 0 ها یا 1

اشاره:

1. درک کنید که از عنصر اصلی، ما از هر عنصر دو بار برای ساخت آرایه مشتق شده استفاده می کنیم
2. مجموع xor آرایه مشتق شده باید 0 باشد زیرا همیشه یک تکرار تکراری از هر عنصر وجود دارد.

راه حل:

برای تعیین اینکه آیا یک آرایه باینری معتبر است یا خیر original وجود دارد که می تواند داده را تشکیل دهد derived آرایه، می توانیم از خواص XOR استفاده کنیم:

مشاهدات کلیدی:

1. هر کدام derived[i] XOR دو عنصر مجاور در است original:

   • برای i = n - 1، derived[i] = original[n-1] ⊕ original[0].
   • در غیر این صورت، derived[i] = original[i] ⊕ original[i+1].

2. خواص XOR:

   • a ⊕ a = 0 (XOR یک عدد با خودش 0 است).
   • a ⊕ 0 = a (XOR یک عدد با 0 خود عدد است).
   • XOR جابجایی و انجمنی است.

3. برای ساخت یک معتبر original، XOR همه عناصر موجود در derived باید برابر 0 باشد. چرا؟ زیرا برای اینکه یک رابطه XOR دایره ای کار کند (شروع و پایان به ابتدا بسته می شود)، XOR تجمعی از derived باید لغو شود.

مراحل:

1. XOR تمام عناصر موجود را محاسبه کنید derived.
2. اگر نتیجه 0 باشد، یک معتبر است original وجود دارد؛ در غیر این صورت، آن را ندارد.

الگوریتم:

• XOR تمام عناصر موجود را محاسبه کنید derived.
• اگر XOR 0 است، برگردید true.
• در غیر این صورت برگرد false.

بیایید این راه حل را در PHP پیاده سازی کنیم: 2683. Bitwise XOR همسایه

/**
 * @param Integer[] $derived
 * @return Boolean
 */
function doesValidArrayExist($derived) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? 'true' : 'false'; // Output: true

// Example 2
$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? 'true' : 'false'; // Output: true

// Example 3
$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? 'true' : 'false'; // Output: false
?>

توضیح:

1. مقداردهی اولیه می کنیم $xorSum به 0.
2. برای هر عنصر در derived، ما آن را با XOR می کنیم $xorSum.
3. در انتهای حلقه، $xorSum حاوی XOR تمام عناصر موجود در آن خواهد بود derived.
4. اگر $xorSum 0 است، بازگشت true; در غیر این صورت، بازگشت false.

پیچیدگی:

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

این رویکرد به طور موثر وجود یک معتبر را بررسی می کند original آرایه در محدودیت های داده شده

لینک های تماس

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

اگر محتوای مفیدتری مانند این می‌خواهید، در صورت تمایل من را دنبال کنید: