حل مسئله و الگوریتم

قراره هر شب حدود ساعت ده یک مسئله رو توی کانال قرار بدم تا با هم حلش کنیم.

اول از همه مسئله های وب سایت leetcode رو قرار میدم تا با هم حلش کنیم.

از مسائل مبتدی شروع میکنیم تا برسیم به سخت ترین ها.
هدفمون اینه تا آخر سال 1402 حدود 90 تا مسئله رو با هم بررسی کنیم و کلی حل مسئلمون رو تقویت کنیم 🔥

بهترین جواب هر مسئله فرداش توی کانال قرار میگیره.

پس اگه دوست دارید حتما هشتگ problems رو از این به بعد دنبال کنید

(جواب مسئله با زبان پایتون و یا گو قرار میگیره)

#problems

@Syntax_fa

1. Two Sum
مسئله ی اول:

یک آرایه داریم و یک target
کاری که باید بکنید این است درون آرایه، اندیس دو عدد را پیدا کنید که جمع(داده) آنها مساوی با target شود و این جفت عدد(اندیس) را در output نشان دهید.
اگر جفت عدد پیدا نشد در خروجی [0, 0] را نمایش می‌دهیم.

یعنی داده‌ی اندیس x به علاوه داده‌ی اندیس y برابر شد با target، خروجی: [x, y]

ورودی: nums = [2,7,11,15], target = 9

خروجی: [0,1]

توضیحات: زیرا nums[0] + nums[1] == 9، و ما [0, 1] نمایش می‌دهیم.

(آرایه را در پایتون همان لیست در نظر بگیرید.)
(متغیر target یک عدد است که از ورودی دریافت می شود.)

بهینه ترین کد فردا قرار میگیره(همراه با توضیح جواب رو توی کامنت ارسال کنید تا بهترین جواب با اسم خودتون قرار بگیره)


#Problems

@Syntax_fa

یکی از روش های خوب و پر سرعت:

میایم یک مپ(دیکشنری) تعریف میکنیم.
درون آرایه پیمایش میکنیم.
اولین قدم چک میکنیم عددمون فاصلش با تارگت چقدره‌ (یکی از اشتباهاتی که بعضی از دوستان کردن این بود که چک کردن اگه عدد از target بزرگ تر بود کلا بیخیالش شه بره بعدی اما ممکنه عدد منفیم تو لیست باشه. پس هر کی اینکارو کرده تست رو رد نمیکنه)

بعد از اینکه بدست آوردیم که عددمون چقدر با target فاصله داره. توی دیکشنری دنبال اون عددی میگردیم که عنصر ما با اون جمع بشه مساوی با تارگت میشه.
توی دیکشنری اعداد رو به این صورت ذخیره میکنیم
{value: index}
سرچ درون لیست با o(1) انجام میشه.
اگه توی دیکشنری نبود عنصر رو با ایندکسش توی دیکشنری اضافه میکنیم و به پیمایش ادامه میدیم

تو بهترین حالت کمتر از o(n) هستش و تو بدترین حالت o(n) میشه.

مثال توی پایتون:

class Solution(object):
    def twoSum(self, nums, target):
        checked = {}
        for index, num in enumerate(nums, start=0):
            index2 = checked.get(target - num)
            if index2 is not None:
                return [index2, index]
            checked[num] = index
        return [0, 0]

مثال توی گو:

 Go
func twoSumWithMakeMapAndExtraAssign(nums []int, target int) []int {
  checked := make(map[int]int)
  for index, num := range nums {
    complete := target - num
    if _, ok := checked[complete]; ok {
      return []int{checked[complete], index}
    }
    checked[num] = index
  }
  return []int{}
}

نکته:
از نظر مصرف memory بهینه نیست. روش بهینه تر رو توی کامنت ها بگید.

#Problems

@Syntax_fa

2. Longest Substring Without Repeating Characters

مسئله دوم
سطح: متوسط

توضیح:
رشته s را دریافت کنید و تعداد کاراکتر های بدون تکرارش را در خروجی برگردانید.
 
مثال:
Example 1:

Input: s = "abcabcbb" 
Output: 3 

Explanation: The answer is "abc", with the length of 3

Example 2:

Input: s = "bbbbb"
Output: 1 

Explanation: The answer is "b", with the length of 1. 

Example 3:

Input: s = "pwwkew"
Output: 4

نکته:
رشته s می تواند شامل حروف انگلیسی، اعداد، سمبل ها و فاصله(space) باشد.

ورودی اعداد سمبل ها و حروف انگلیسی هستش.
ولی خروجی تعداد حروف بی تکرار انگلیسی

برای اینکه تست کنید جوابتون درسته حتما به این وب سایت سر بزنید و کدتون‌ رو تست کنید:
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

جایزه:
به بهترین جواب کانفیگ ده گیگابایت شخصی داده میشود.

#Problems

@Syntax_fa

نکاتی در خصوص حل مسئله:

در مصاحبه‌ها برای شغل‌های مرتبط با برنامه‌نویسی عموماً توصیه می‌شود در حل مسائل و الگوریتم‌ها از ویژگی‌های خاص زبان استفاده نشود و مسائل به طور عام بدون اتکا به یک زبان ویژه حل شوند. دلایل این توصیه عبارتند از:

- در مصاحبه بررسی می‌شود که شخص چگونه می‌تواند مسئله را به طور عام حل کند، نه آنکه از یک زبان مشخص استفاده کند.

- در شرکت‌های مختلف زبان‌های برنامه‌نویسی متفاوتی مورد استفاده قرار می‌گیرند. پس مهم است که کاربردی بودن الگوریتم‌ها نشان داده شود.

- بدون اتکا به زبان، باید از مفاهیم پایه‌ای مانند ریاضیات، منطق و طراحی الگوریتم استفاده شود.

بنابراین در مصاحبه‌ها توصیه می‌شود که بدون استفاده از ویژگی‌های خاص زبان، مسائل را حل کرد تا قدرت تحلیل و حل مسئله فرد بهتر به نمایش گذاشته شود.

#Problems

@Syntax_fa

3. Integer to English Words

مسئله سوم
سطح:‌ سخت

توضیح:
یک عدد بزرگ تر مساوی با صفر (عدد حسابی) را با اسم متغیر num از ورودی دریافت میکنید و در خروجی بصورت حروف انگلیسی نمایشش می دهید.

مثال:

 LeetCode
Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"


Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"


Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

نکته:
برای اینکه بتونیم خروجی رو به راحتی تست کنیم. هممون با یه ساختار کد بزنیم
توی پایتون به این شکل جواب رو بفرستید:

def numberToWords(num: int) -> str:
    """
    :type num: int
    :rtype: str
    """

توی گو:

func numberToWords(num int) string {
    
}

جایزه 💥:
به بهترین جواب کانفیگ ده گیگابایت شخصی داده میشود.

#Problems

@Syntax_fa

بهترین پاسخ برای امیرحسین عزیز هستش.

پاسخ:

def numberToWords(num):
    d_one = {0: "", 1: "One ", 2: "Two ", 3: "Three ", 4: "Four ", 5: "Five ", 6: "Six ", 7: "Seven ", 8: "Eight ",
             9: "Nine ", 10: "Ten ", 11: 'Eleven ', 12: "Twelve ",
             13: "Thirteen ", 14: "Fourteen ", 15: "Fifteen ", 16: "Sixteen ", 17: "Seventeen ", 18: "Eighteen ",
             19: "Nineteen "}
    d_villagers = {2: "Twenty ", 3: "Thirty ", 4: "Forty ", 5: "Fifty ", 6: "Sixty ", 7: "Seventy ", 8: "Eighty ",
                   9: "Ninety "}

    def score(num):
        if num // 1_000_000_000 > 0:
            return score(num // 1_000_000_000) + "Billion " + score(num % 1_000_000_000)
        if num // 1_000_000 > 0:
            return score(num // 1_000_000) + "Million " + score(num % 1_000_000)
        elif num // 1_000 > 0:
            return score(num // 1_000) + "Thousand " + score(num % 1_000)
        elif num // 100:
            return d_one[num // 100] + "Hundred " + score(num % 100)
        elif num > 19:
            return d_villagers[num // 10] + d_one[num % 10]
        elif num <= 19:
            return d_one[num]

    return score(num).strip() if num != 0 else "Zero"

همچنین یه اشاره ای به جواب یکی از دوستان کنم. خیلی خوب کلک زدن😂

from num2words import num2words

def number_to_words(number):
    return num2words(number)


input_number = 1234567
output_words = number_to_words(input_number)
print(output_words)

#Problems

@Syntax_fa

مسئله چهارم
سطح:‌ ساده

توضیح:
برنامه ای بنویسید که خروجی زیر را داشته باشد

 Python
1
22
333
55555
88888888
13131313131313131313131313
212121212121212121212121212121212121212121

#Problems

@Syntax_fa

چند تا از جواب ها:

s= 1
i = 0
for h in range(7):
    s ,i = s+i,s
    for n in range(1,s+1):
        print(s,end="")
    print()

fib = [1, 1]
for _ in range(7):
 print(str(fib[1])*fib[1])
 fib.append(sum(fib))
 fib.pop(0)

first_sequence = 1
second_sequence = 1
sequence_counter = 1
while sequence_counter < 8:
    print_obj = str(second_sequence)
    print_num = second_sequence
    second_sequence += first_sequence
    first_sequence = second_sequence - first_sequence
    while print_num != 0:
        print(print_obj, end='')
        print_num -= 1
    print('')
    sequence_counter += 1

func Example() {
  number := 1
  oldNumber := 1

  for {
    for i := 0; i < number; i++ {
      fmt.Printf("%d", number)
    }

    fmt.Printf("\n")

    if number >= 21 {
      break
    }
    number, oldNumber = number+oldNumber, number
  }
}

کدوم بهتره ؟

#Problems

@Syntax_fa

مسئله پنجم
سطح: متوسط

توضیح:

ما سه آدرس زیر را داریم:
https://jsonplaceholder.typicode.com/todos/1
https://jsonplaceholder.typicode.com/todos/2
https://jsonplaceholder.typicode.com/todos/3

برنامه ای بنویسید که همزمان به هر سه آدرس درخواست get بزند و هرکدام که زودتر جواب داد. در خروجی response body را نمایش بدهد و بگوید پاسخ مال کدام آدرس است.
اگر بعد از گذشت 3 ثانیه هیچکدام از آدرس ها جواب ندادند. در خروجی Timeout را نمایش بدهد و برنامه متوقف شود.

(نمونه خروجی json رو تلگرام خودش زحمت کشید به پیام اضافش کرد)

(💥جایزه کانفیگ یه ماهه)

#Problems

@Syntax_fa