أهم 100 مشكلة في LeetCode وحلولها – الجزء الأول

_حلال مشاكل

المشكلة رقم 1: مجموع اثنين

تكمن المشكلة في العثور على رقمين في مصفوفة يصل مجموعهما إلى رقم مستهدف محدد. علينا إعادة أرقام هذين الرقمين بأي ترتيب. يمكننا أن نفترض أن هناك حل واحد صالح فقط، ولا يمكننا استخدام نفس العنصر مرتين.

لحل هذه المشكلة، يمكننا استخدام جدول التجزئة لتخزين مؤشرات كل رقم في مصفوفة الإدخال. بعد ذلك، بالنسبة لكل رقم في المصفوفة، يمكننا التحقق مما إذا كان مكمله (أي الرقم الذي يضاف إلى الهدف مع الرقم الحالي) موجود بالفعل في جدول التجزئة. إذا كان الأمر كذلك، فإننا نعيد مؤشرات الرقمين.

التعقيد الزمني لهذه الخوارزمية هو O(n)، حيث نحتاج فقط إلى التكرار عبر المصفوفة مرة واحدة، وكل بحث في جدول التجزئة يستغرق O(1) وقتًا. التعقيد المكاني هو أيضًا O(n)، حيث نحتاج إلى تخزين مؤشرات كل رقم في جدول التجزئة.

فيما يلي الخطوات المتخذة لحل المشكلة:

  1. إنشاء جدول تجزئة فارغ.
  2. قم بالتكرار من خلال مصفوفة الإدخال ولكل رقم:
    1. احسب مكملته (أي الهدف – العدد).
    2. تحقق مما إذا كان مكمله موجودًا بالفعل في جدول التجزئة. إذا كان كذلك، قم بإرجاع مؤشرات الرقم الحالي ومكمله.
    3. إذا لم يكن مكمله موجودًا في جدول التجزئة، أضف الرقم الحالي وفهرسه إلى جدول التجزئة.
  3. إذا لم يتم العثور على حل، قم بإرجاع مصفوفة فارغة.

حل جافا سكريبت

function twoSum(nums, target) {
  // Create an empty hash table.
  const indices = {};

  // Iterate through the input array.
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    // Calculate the complement of the current number.
    const complement = target - num;

    // Check if the complement is in the hash table.
    if (indices[complement] !== undefined) {
      // Return the indices of the current number and its complement.
      return [indices[complement], i];
    }

    // Add the current number and its index to the hash table.
    indices[num] = i;
  }

  // If no solution is found, return an empty array.
  return [];
}

// Example usage:
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));  // Output: [0, 1]

const nums2 = [3, 2, 4];
const target2 = 6;
console.log(twoSum(nums2, target2));  // Output: [1, 2]

const nums3 = [3, 3];
const target3 = 6;
console.log(twoSum(nums3, target3));  // Output: [0, 1]

حل بايثون:

def twoSum(nums, target):
    # Create an empty hash table.
    indices = {}

    # Iterate through the input array.
    for i, num in enumerate(nums):
        # Calculate the complement of the current number.
        complement = target - num

        # Check if the complement is in the hash table.
        if complement in indices:
            # Return the indices of the current number and its complement.
            return [indices[complement], i]

        # Add the current number and its index to the hash table.
        indices[num] = i

    # If no solution is found, return an empty list.
    return []

# Example usage:
nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))  # Output: [0, 1]

nums2 = [3, 2, 4]
target2 = 6
print(twoSum(nums2, target2))  # Output: [1, 2]

nums3 = [3, 3]
target3 = 6
print(twoSum(nums3, target3))  # Output: [0, 1]

المشكلة رقم 2: إضافة رقمين

يتم إعطاؤك قائمتين مرتبطتين غير فارغتين تمثلان عددين صحيحين غير سالبين. يتم تخزين الأرقام بترتيب عكسي، وتحتوي كل عقدة منها على رقم واحد. أضف الرقمين وأعد المجموع كقائمة مرتبطة.

يمكنك أن تفترض أن الرقمين لا يحتويان على أي صفر بادئ، باستثناء الرقم 0 نفسه.

مثال:

الإدخال: l1 = [2,4,3], l2 = [5,6,4]
الإخراج: [7,0,8]
الشرح: 342 + 465 = 807.

خطوات حل المشكلة:

  1. تهيئة العقدة الوهمية ومتغير الحمل.
  2. قم بالتكرار عبر قوائم الإدخال حتى نصل إلى نهاية كلتا القائمتين.
  3. أضف قيم العقد، إذا كانت موجودة، والحمل.
  4. احسب الحمل الجديد وقيمة العقدة الحالية.
  5. انتقل إلى العقد التالية وكرر الخطوات من 2 إلى 4.
  6. إذا كان هناك حمل متبقي في النهاية، أضف عقدة جديدة بقيمة الحمل.
  7. قم بإرجاع النتيجة كالعقدة الوهمية التالية.

كود مزيف:

تهيئة الدمية والتيار والحمل
بينما l1 أو l2:
مجموع = تحمل
إذا l1:
مجموع += l1.val
l1 = l1.next
إذا l2:
مجموع += l2.val
l2 = l2.next
تحمل = مجموع // 10
الحالي .التالي = العقدة (مجموع % 10)
الحالي = الحالي.التالي
إذا حمل:
الحالي.التالي = العقدة (حمل)
إرجاع الدمية.التالي

حل جافا سكريبت:

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(); // Create a dummy node
    let current = dummy; // Set current node to dummy
    let carry = 0; // Initialize carry to 0

    while (l1 || l2) { // Iterate through the lists until the end of both
        let sum = carry; // Set sum to the value of carry
        if (l1) {
            sum += l1.val; // If l1 exists, add its value to sum
            l1 = l1.next; // Move to the next node in l1
        }
        if (l2) {
            sum += l2.val; // If l2 exists, add its value to sum
            l2 = l2.next; // Move to the next node in l2
        }
        carry = Math.floor(sum / 10); // Calculate new carry
        current.next = new ListNode(sum % 10); // Create a new node with the current digit
        current = current.next; // Move to the next node
    }

    if (carry) {
        current.next = new ListNode(carry); // If there's a carry left, create a new node with its value
    }

    return dummy.next; // Return the result as the next of the dummy node
};

حل بايثون:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy = ListNode() # Create a dummy node
    current = dummy # Set current node to dummy
    carry = 0 # Initialize carry to 0

    while l1 or l2: # Iterate through the lists until the end of both
        _sum = carry # Set sum to the value of carry
        if l1:
            _sum += l1.val # If l1 exists, add its value to sum
            l1 = l1.next # Move to the next node in l1
        if l2:
            _sum += l2.val # If l2 exists, add its value to sum
            l2 = l2.next # Move to the next node in l2
        carry = _sum // 10 # Calculate new carry
        current.next = ListNode(_sum % 10) # Create a new node with the current digit
        current = current.next # Move to the next node

    if carry:
        current.next = ListNode(carry) # If there's a carry left, create a new node with its value

    return dummy.next # Return the result as the next of the dummy node

المشكلة رقم 3: أطول سلسلة فرعية بدون تكرار الأحرف

بالنظر إلى سلسلة s، ابحث عن طول أطول سلسلة فرعية دون تكرار الأحرف.

مثال:

الإدخال: s = “abcabcbb”
الإخراج: 3
الشرح: الإجابة هي “abc”، بطول 3.

لقد حصلنا على سلسلة، ونحن بحاجة إلى العثور على أطول سلسلة فرعية متجاورة دون أي أحرف متكررة. ويتمثل التحدي في القيام بذلك بكفاءة دون استخدام نهج القوة الغاشمة، والذي قد يتضمن التحقق من جميع السلاسل الفرعية الممكنة.

لحل هذه المشكلة، سنستخدم تقنية النافذة المنزلقة ، والتي تحافظ على نافذة من الأحرف دون أي أحرف متكررة. تتضمن هذه التقنية مؤشرين، يسارًا ويمينًا، يجتازان السلسلة من اليسار إلى اليمين. سنستخدم أيضًا خريطة التجزئة (أو القاموس) لتخزين فهرس كل حرف في السلسلة.

أثناء تكرارنا للسلسلة باستخدام المؤشر الأيمن، سنتحقق مما إذا كان الحرف الحالي موجودًا بالفعل في خريطة التجزئة وما إذا كان فهرسه أكبر من المؤشر الأيسر أو يساويه. إذا كان الأمر كذلك، فهذا يعني أننا وجدنا حرفًا متكررًا، ونحتاج إلى تحديث المؤشر الأيسر إلى الفهرس التالي بعد فهرس الحرف المتكرر. سيضمن هذا أن نافذتنا تحتوي فقط على أحرف فريدة.

بعد ذلك، سنقوم بتحديث خريطة التجزئة بفهرس الأحرف الجديد وحساب الحد الأقصى لطول السلسلة الفرعية التي تم العثور عليها حتى الآن. بنهاية التكرار، سيحتفظ متغير الحد الأقصى للطول بطول أطول سلسلة فرعية دون تكرار الأحرف.

خطوات حل المشكلة:

  1. قم بتهيئة hashmap لتخزين فهرس الأحرف.
  2. قم بتهيئة مؤشرين، اليسار واليمين، للتكرار عبر السلسلة.
  3. قم بالتكرار عبر السلسلة باستخدام المؤشر الأيمن.
  4. إذا كان هناك حرف موجود بالفعل في خريطة التجزئة وكان فهرسه أكبر من أو يساوي المؤشر الأيسر، فقم بتحديث المؤشر الأيسر إلى الفهرس التالي.
  5. قم بتحديث الهاشماب بفهرس الأحرف الجديد.
  6. قم بتحديث الحد الأقصى لطول السلسلة الفرعية.

كود مزيف:

تهيئة charIndexMap، يسار، أقصى طول
لليمين في النطاق (0، len(s)):
إذا كان s[يمين] في charIndexMap وcharIndexMap[s[يمين]] >= يسار: يسار
= charIndexMap[s[يمين]] + 1
charIndexMap [s[يمين]] = اليمين
maxLength = max(maxLength، يمين - يسار + 1)
إرجاع maxLength

حل جافا سكريبت:

const lengthOfLongestSubstring = (s) => {
    let charIndexMap = new Map(); // Initialize a hashmap to store the index of characters
    let left = 0; // Initialize the left pointer
    let maxLength = 0; // Initialize the maximum length

    for (let right = 0; right < s.length; right++) { // Iterate through the string with the right pointer
        if (charIndexMap.has(s[right]) && charIndexMap.get(s[right]) >= left) {
            // If a character is already in the hashmap and its index is greater than or equal to the left pointer,
            // update the left pointer to the next index
            left = charIndexMap.get(s[right]) + 1;
        }
        charIndexMap.set(s[right], right); // Update the hashmap with the new character index
        maxLength = Math.max(maxLength, right - left + 1); // Update the maximum length of the substring
    }

    return maxLength;
};

حل بايثون:

def length_of_longest_substring(s):
    char_index_map = {} # Initialize a hashmap to store the index of characters
    left = 0 # Initialize the left pointer
    max_length = 0 # Initialize the maximum length

    for right in range(len(s)): # Iterate through the string with the right pointer
        if s[right] in char_index_map and char_index_map[s[right]] >= left:
            # If a character is already in the hashmap and its index is greater than or equal to the left pointer,
            # update the left pointer to the next index
            left = char_index_map[s[right]] + 1
        char_index_map[s[right]] = right # Update the hashmap with the new character index
        max_length = max(max_length, right - left + 1) # Update the maximum length of the substring

    return max_length

المشكلة رقم 4: متوسط ​​مصفوفتين مفروزتين

بالنظر إلى صفيفين مفروزين nums1 وnums2 بحجم m وn على التوالي، قم بإرجاع متوسط ​​الصفيفين اللذين تم فرزهما.

مثال:

الإدخال: nums1 = [1,3]، nums2 = [2]
الإخراج: 2.0
الشرح: المصفوفة المدمجة = [1,2,3] والوسيط هو 2.

بالنظر إلى مصفوفتين مفروزتين، نحتاج إلى العثور على العنصر (العناصر) المتوسطة بعد دمجهما. ويتمثل التحدي في القيام بذلك في التعقيد الزمني O(log(min(m, n)))، حيث m وn هما طول الصفيفتين. سنستخدم بحثًا ثنائيًا على المصفوفة الأصغر للعثور على نقاط التقسيم الصحيحة التي تقسم المصفوفة المدمجة إلى جزأين متساويين.

خطوات حل المشكلة:

  1. تأكد من أن nums1 هو المصفوفة الأصغر. إذا لم يكن الأمر كذلك، قم بتبديل nums1 وnums2.
  2. ابحث عن نقاط التقسيم في كلا المصفوفتين بحيث يحتوي النصف الأيسر على نفس عدد العناصر الموجودة في النصف الأيمن.
  3. البحث الثنائي على المصفوفة الأصغر للعثور على نقاط القسم الصحيحة.
  4. تحقق من شروط القسم الصحيح واحسب الوسيط بناءً على نقاط القسم.

كود مزيف:

إذا لين (nums1) > لين (nums2):
مبادلة (nums1، nums2)

منخفض، مرتفع، Partition_x، Partition_y = 0، len(nums1)، 0، 0
Total_length = len(nums1) + len(nums2)

بينما منخفض <= مرتفع:
Partition_x = (منخفض + مرتفع) // 2
Partition_y = (total_length + 1) // 2 - Partition_x

max_left_x = nums1[partition_x – 1] إذا Partition_x > 0 else -inf
min_right_x = nums1[partition_x] إذا Partition_x < len(nums1) else inf

max_left_y = nums2[partition_y – 1] إذا Partition_y > 0 else -inf
min_right_y = nums2[partition_y] إذا Partition_y < len(nums2) else inf

إذا كان max_left_x <= min_right_y وmax_left_y <= min_right_x:
إذا كان الطول الإجمالي % 2 == 0:
return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
آخر:
إرجاع max(max_left_x, max_left_y)
elif max_left_x > min_right_y :
عالي = Partition_x – 1
آخر:
منخفض = Partition_x + 1

العودة 0

حل جافا سكريبت:

const findMedianSortedArrays = (nums1, nums2) => {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]; // Ensure nums1 is the smaller array
    }

    let low = 0;
    let high = nums1.length;
    let totalLength = nums1.length + nums2.length;

    while (low <= high) {
        let partitionX = Math.floor((low + high) / 2); // Find the partition point in nums1
        let partitionY = Math.floor((totalLength + 1) / 2) - partitionX; // Find the partition point in nums2

        let maxLeftX = partitionX > 0 ? nums1[partitionX - 1] : -Infinity;
        let minRightX = partitionX < nums1.length ? nums1[partitionX] : Infinity;

        let maxLeftY = partitionY > 0 ? nums2[partitionY - 1] : -Infinity;
        let minRightY = partitionY < nums2.length ? nums2[partitionY] : Infinity;

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // If the correct partition is found
            if (totalLength % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    return 0;
};

حل بايثون:

import sys

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # Ensure nums1 is the smaller array

    low, high = 0, len(nums1)
    total_length = len(nums1) + len(nums2)

    while low <= high:
        partition_x = (low + high) // 2  # Find the partition point in nums1
        partition_y = (total_length + 1) // 2 - partition_x  # Find the partition point in nums2

        max_left_x = nums1[partition_x - 1] if partition_x > 0 else -sys.maxsize
        min_right_x = nums1[partition_x] if partition_x < len(nums1) else sys.maxsize

        max_left_y = nums2[partition_y - 1] if partition_y > 0 else -sys.maxsize
        min_right_y = nums2[partition_y] if partition_y < len(nums2) else sys.maxsize

        if max_left_x <= min_right_y and max_left_y <= min_right_x:
            # If the correct partition is found
            if total_length % 2 == 0:
                return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
            else:
                return max(max_left_x, max_left_y)
        elif max_left_x > min_right_y:
            high = partition_x - 1
        else:
            low = partition_x + 1

    return 0

https://ahmedradwan.dev

تواصل معنا إذا كنت ترغب في الانضمام إلي وكتابة مقالات مع المهووسين 🙂


© 2024 · الطالب الذي يذاكر كثيرا المستوى التقنية

فئات

وسائل التواصل الاجتماعي

ابق على اتصال على وسائل التواصل الاجتماعي