C++ مدرن برای LeetCode 🧑‍💻🚀

Summarize this content to 400 words in Persian Lang
C++ از روزهای اولیه خود راه درازی را پیموده است، و C++ “مدرن” (شروع با C++11 و فراتر از آن) مجموعه‌ای از ویژگی‌ها را ارائه می‌دهد که حل مشکلات را در پلتفرم‌هایی مانند LeetCode کارآمدتر و لذت‌بخش‌تر می‌کند. مدیریت دستی حافظه، حلقه های پرمخاطب و محاسبات اشاره گر مرموز را فراموش کنید! C++ مدرن ابزارهایی مانند std::unordered_map، حلقه‌های مبتنی بر محدوده، و توابع لامبدا را در اختیار ما قرار می‌دهد که به ما امکان می‌دهد بیشتر روی حل مشکلات تمرکز کنیم و کمتر روی کد دیگ بخار تمرکز کنیم. بیایید به برخی از الگوهای الگوریتمی رایج بپردازیم و ببینیم که C++ مدرن چگونه آنها را عالی می کند! 💡

1. Hashmaps (با استفاده از std::unordered_map) 🗺️

در مدرسه قدیمی C، پیاده‌سازی نقشه هش به معنای نوشتن ساختار داده‌های خود با توابع درهم‌سازی، مدیریت برخورد و تمام آن جاز بود. دیگر نه! C++ مدرن به ما std::unordered_map می دهد که استفاده از آن سریع و آسان است.

مثال: دو جمع (LeetCode #1)

#include
#include

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> map; // Key: number, Value: index
for (int i = 0; i < nums.size(); ++i) {
int complement = target – nums[i];
if (map.count(complement)) { // Check if complement exists in map
return {map[complement], i};
}
map[nums[i]] = i;
}
return {};
}

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

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

چرا عالی است:

جستجوهای سریع: میانگین O(1) برای جستجوهای کلید-مقدار.نیازی به نوشتن توابع هش سفارشی یا پرداختن به تخصیص حافظه نیست.

2. جستجوی باینری (با استفاده از std::binary_search) 🔍

جستجوی باینری یک الگوریتم کلاسیک است، اما در C++، توابع کمکی را از هدر دریافت می‌کنیم که زندگی را آسان‌تر می‌کند.

مثال: جستجوی موقعیت درج (LeetCode #35)

#include
#include

int searchInsert(const std::vector<int>& nums, int target) {
return std::lower_bound(nums.begin(), nums.end(), target) – nums.begin();
}

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

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

چرا عالی است:

std::lower_bound: اولین عنصر را کمتر از هدف پیدا می کند.تمیز و مختصر: دیگر نیازی به ردیابی دستی نشانگرهای پایین، بالا و متوسط ​​نیست.

3. Quicksort (با استفاده از std::sort) ⚡

در حالی که اجرای مرتب سازی سریع به صورت دستی یک تمرین سرگرم کننده است، این چیزی نیست که بخواهید در هر مشکل LeetCode انجام دهید. C++ مدرن دارد std::sort، که بسیار بهینه شده است.

مثال: مرتب سازی یک آرایه (LeetCode #912)

#include
#include

std::vector<int> sortArray(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
return nums;
}

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

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

چرا عالی است:

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

4. تکنیک دو نشانگر (حلقه های مبتنی بر محدوده + std::string Utilities) 🏃‍♂️🏃‍♀️

تکنیک دو نقطه ای برای مشکلات مربوط به آرایه ها یا رشته ها عالی است. C++ مدرن با حلقه‌های مبتنی بر محدوده و توابع کمکی برای رشته‌ها کار را آسان‌تر می‌کند.

مثال: Valid Palindrome (LeetCode #125)

#include
#include

bool isPalindrome(const std::string& s) {
int left = 0, right = s.size() – 1;
while (left < right) {
while (left < right && !std::isalnum(s[left])) ++left;
while (left < right && !std::isalnum(s[right])) –right;
if (std::tolower(s[left]) != std::tolower(s[right])) return false;
++left; –right;
}
return true;
}

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

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

چرا عالی است:

std::isalnum و std::tolower: ابزارهای داخلی برای کنترل کاراکترها.بدون نیاز به چک های ASCII دستی!

5. نمودارها (با استفاده از std::queue و std::vector) 🌉

مشکلات نمودار اغلب شامل BFS یا DFS می شود. C++ مدرن در اینجا با کانتینرهایی مانند std::vector برای لیست های مجاورت و std::queue برای BFS می درخشد.

مثال: تعداد جزایر (LeetCode #200)

#include
#include

void bfs(std::vector<std::vector<char>>& grid, int r, int c) {
std::queue<std::pair<int, int>> q;
q.push({r, c});
grid[r][c] = ‘0’; // Mark visited
std::vector<std::pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

while (!q.empty()) {
auto [row, col] = q.front(); q.pop();
for (const auto& [dr, dc] : directions) {
int nr = row + dr, nc = col + dc;
if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] == ‘1’) {
q.push({nr, nc});
grid[nr][nc] = ‘0’;
}
}
}
}

int numIslands(std::vector<std::vector<char>>& grid) {
int count = 0;
for (int r = 0; r < grid.size(); ++r) {
for (int c = 0; c < grid[0].size(); ++c) {
if (grid[r][c] == ‘1’) {
++count;
bfs(grid, r, c);
}
}
}
return count;
}

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

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

چرا عالی است:

std::queue: برای BFS عالی است، تمام سردردهای اشاره گر/حافظه را از بین می برد.

جفت سازی ساختار با [row, col]: کد تمیز و خوانا.

نتیجه گیری 🎉

C++ مدرن بسیاری از کدگذاری دیگ بخار و کارهای دستی مستعد خطا را که زمانی ضروری بود، از بین می برد. این ویژگی‌های جدید چه نقشه‌های هش، مرتب‌سازی، یا مدیریت رشته‌ها و نمودارها باشد، به شما امکان می‌دهد به جای مبارزه با زبان، روی حل مسئله تمرکز کنید.

ویژگی های TL;DR of Modern C++:

std::unordered_map: O(1) جستجو می کند!
std::lower_bound و std::sort: جستجو و مرتب‌سازی را ساده می‌کند.
حلقه‌های مبتنی بر محدوده، lambdas و std::string utilities: کد پاک‌تر، ایمن‌تر و سریع‌تر.
std::vector و std::queue: ایده آل برای نمودارها، آرایه های پویا و موارد دیگر.

اکنون فنجان قهوه مورد علاقه خود را بردارید و شروع به حل مشکلات LeetCode کنید!

#include 
#include 

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map; // Key: number, Value: index
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (map.count(complement)) { // Check if complement exists in map
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

#include 
#include 

int searchInsert(const std::vector<int>& nums, int target) {
    return std::lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}

#include 
#include 

std::vector<int> sortArray(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    return nums;
}

#include 
#include 

bool isPalindrome(const std::string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        while (left < right && !std::isalnum(s[left])) ++left;
        while (left < right && !std::isalnum(s[right])) --right;
        if (std::tolower(s[left]) != std::tolower(s[right])) return false;
        ++left; --right;
    }
    return true;
}

#include 
#include 

void bfs(std::vector<std::vector<char>>& grid, int r, int c) {
    std::queue<std::pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = '0'; // Mark visited
    std::vector<std::pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
        auto [row, col] = q.front(); q.pop();
        for (const auto& [dr, dc] : directions) {
            int nr = row + dr, nc = col + dc;
            if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] == '1') {
                q.push({nr, nc});
                grid[nr][nc] = '0';
            }
        }
    }
}

int numIslands(std::vector<std::vector<char>>& grid) {
    int count = 0;
    for (int r = 0; r < grid.size(); ++r) {
        for (int c = 0; c < grid[0].size(); ++c) {
            if (grid[r][c] == '1') {
                ++count;
                bfs(grid, r, c);
            }
        }
    }
    return count;
}