الگوریتم های رمزگشایی: دو نشانگر – انجمن DEV

Summarize this content to 400 words in Persian Lang

تکنیک دو نقطه چیست؟

تکنیک Two Pointers یک رویکرد بسیار کارآمد است که اغلب برای حل مسائلی که شامل آرایه ها یا لیست های مرتبط هستند استفاده می شود. از دو نشانگر برای عبور داده ها پشت سر هم استفاده می کند و محاسبات غیر ضروری را کاهش می دهد. این تکنیک به ویژه برای داده های مرتب شده به خوبی کار می کند و به شما کمک می کند تا راه حل های مربوط به مسائل مربوط به جفت ها، سه قلوها یا پارتیشن ها را بهینه کنید.

نمای فنی

پیچیدگی زمانی: O(n) (در اکثر موارد).

هر دو نشانگر معمولاً یک بار آرایه ورودی را طی می کنند که منجر به پیچیدگی زمانی خطی می شود.

پیچیدگی فضا: O (1).

هیچ ساختار داده اضافی استفاده نمی شود، زیرا تنها مقدار ثابتی از فضا برای ردیابی اشاره گرها مورد نیاز است.

خلاصه آنوراک

تکنیک Two Pointers از دو نشانگر برای اسکن موثر داده ها استفاده می کند. این نشانگرها ممکن است در یک جهت، جهت مخالف یا به صورت پویا بر اساس شرایط خاص حرکت کنند. این ابزار قدرتمندی برای کار با آرایه های مرتب شده یا کاهش پیچیدگی حلقه های تو در تو است.

خلاصه یک دانش آموز کلاس پنجم

تصور کنید با دوستی در وسط یک طناب بلند با شروع از دو طرف مقابل و راه رفتن به سمت یکدیگر ملاقات می کنید. با همکاری و ملاقات در میانه، از اتلاف وقت برای جستجوی تصادفی جلوگیری می کنید.

مثال دنیای واقعی

فرض کنید به دنبال یک جفت جوراب در یک کشوی مرتب شده هستید. به جای جستجوی تصادفی، شما از یک سر کشو شروع می کنید و دوستتان از سر دیگر شروع می کند. شما در وسط ملاقات می کنید و به طور سیستماتیک جفت منطبق را سریعتر پیدا می کنید.

مثال هایی با کد، پیچیدگی و الگوهای بهینه شده

1. دو جمع در یک آرایه مرتب شده

مشکل: با توجه به یک آرایه مرتب شده، دو عدد را پیدا کنید که مجموع آنها به یک مجموع هدف می رسد.

کد:

def two_sum_two_pointers(nums, target):
left, right = 0, len(nums) – 1
while left < right:
current_sum = nums[left] + nums[right] if current_sum == target:
return [left, right] elif current_sum < target:
left += 1
else:
right -= 1
return None

# Example Usage
nums = [2, 3, 4, 6, 8] target = 10
print(two_sum_two_pointers(nums, target)) # Output: [1, 3]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی:

پیچیدگی زمانی: O(n)

دو نشانگر یک بار آرایه را طی می کنند.

پیچیدگی فضا: O (1)

الگوی بهینه شده: دو اشاره گر در حال حاضر بهینه است برای این مشکل

2. معکوس کردن یک آرایه

مشکل: عناصر یک آرایه را در جای خود معکوس کنید.

کد:

def reverse_array(nums):
left, right = 0, len(nums) – 1
while left < right:
nums[left], nums[right] = nums[right], nums[left] left += 1
right -= 1
return nums

# Example Usage
nums = [1, 2, 3, 4, 5] print(reverse_array(nums)) # Output: [5, 4, 3, 2, 1]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی:

پیچیدگی زمانی: O(n)

هر عنصر یک بار با یکدیگر مبادله می شود زیرا دو نشانگر در وسط به هم می رسند.

پیچیدگی فضا: O (1)

آرایه در جای خود اصلاح شده است و نیازی به فضای اضافی ندارد.

الگوی بهینه شده: دو اشاره گر در حال حاضر بهینه است برای معکوس کردن آرایه ها

3. ظرف با بیشترین آب

مشکل: با توجه به آرایه ای که ارتفاع خطوط عمودی را نشان می دهد، دو خط را پیدا کنید که همراه با محور x ظرفی با حداکثر مساحت را تشکیل می دهند.

کد:

def max_area(heights):
left, right = 0, len(heights) – 1
max_area = 0
while left < right:
current_area = min(heights[left], heights[right]) * (right – left)
max_area = max(max_area, current_area)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_area

# Example Usage
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7] print(max_area(heights)) # Output: 49

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی:

پیچیدگی زمانی: O(n)

دو نشانگر یک بار آرایه را طی می کنند.

پیچیدگی فضا: O (1)

هیچ حافظه اضافی استفاده نمی شود.

الگوی بهینه شده: دو اشاره گر در حال حاضر بهینه است برای این مشکل

4. Subsequence است

مشکل: بررسی کنید که آیا یک رشته است s دنباله ای از رشته است t.

کد:

def is_subsequence(s, t):
s_ptr, t_ptr = 0, 0
while s_ptr < len(s) and t_ptr < len(t):
if s[s_ptr] == t[t_ptr]:
s_ptr += 1
t_ptr += 1
return s_ptr == len(s)

# Example Usage
s = “abc”
t = “ahbgdc”
print(is_subsequence(s, t)) # Output: True

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی:

پیچیدگی زمانی: O(n)

هر دو نشانگر یک بار رشته های مربوطه خود را طی می کنند.

پیچیدگی فضا: O (1)

فقط مقدار ثابتی از حافظه استفاده می شود.

الگوی بهینه شده: دو اشاره گر در حال حاضر بهینه است برای این مشکل

5. ادغام دو آرایه مرتب شده

مشکل: دو آرایه مرتب شده را در یک آرایه مرتب شده ادغام کنید.

کد:

def merge_sorted_arrays(nums1, nums2):
result = [] i, j = 0, 0
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
result.extend(nums1[i:])
result.extend(nums2[j:])
return result

# Example Usage
nums1 = [1, 3, 5] nums2 = [2, 4, 6] print(merge_sorted_arrays(nums1, nums2)) # Output: [1, 2, 3, 4, 5, 6]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی:

پیچیدگی زمانی: O(n + m)

هر دو نشانگر یک بار از آرایه های مربوطه عبور می کنند.

پیچیدگی فضا: O(n + m)

آرایه ادغام شده به فضای اضافی نیاز دارد.

الگوی بهینه شده: دو اشاره گر در حال حاضر بهینه است برای ادغام آرایه های مرتب شده

نتیجه گیری

تکنیک Two Pointers ابزاری همه کاره برای حل مسائل به طور موثر با پیچیدگی زمانی خطی و حداقل فضای مورد نیاز است. این به ویژه برای کارهایی که شامل داده های مرتب شده یا مشکلاتی هستند که به طور طبیعی به بخش ها تقسیم می شوند، قدرتمند است.

با تسلط بر Two Pointers، به یک تکنیک بهینه سازی کلیدی دست خواهید یافت که برای بسیاری از مسائل دنیای واقعی و الگوریتمی قابل استفاده است.

def two_sum_two_pointers(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

# Example Usage
nums = [2, 3, 4, 6, 8]
target = 10
print(two_sum_two_pointers(nums, target))  # Output: [1, 3]

def reverse_array(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

# Example Usage
nums = [1, 2, 3, 4, 5]
print(reverse_array(nums))  # Output: [5, 4, 3, 2, 1]

def max_area(heights):
    left, right = 0, len(heights) - 1
    max_area = 0
    while left < right:
        current_area = min(heights[left], heights[right]) * (right - left)
        max_area = max(max_area, current_area)
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return max_area

# Example Usage
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(heights))  # Output: 49

def is_subsequence(s, t):
    s_ptr, t_ptr = 0, 0
    while s_ptr < len(s) and t_ptr < len(t):
        if s[s_ptr] == t[t_ptr]:
            s_ptr += 1
        t_ptr += 1
    return s_ptr == len(s)

# Example Usage
s = "abc"
t = "ahbgdc"
print(is_subsequence(s, t))  # Output: True

def merge_sorted_arrays(nums1, nums2):
    result = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

# Example Usage
nums1 = [1, 3, 5]
nums2 = [2, 4, 6]
print(merge_sorted_arrays(nums1, nums2))  # Output: [1, 2, 3, 4, 5, 6]