Tarkibga o'tish

Songa aylantirish (atoi)

Matn qatori (string) berilgan. Uni butun songa aylantiring.

C dasturlash tilida bu amal atoi funksiyasi nomi bilan tanilgan. Masala shartlari:

  1. Boshidagi bo'sh joylarni (' ') o'tkazib yuboring.
  2. Ixtiyoriy '+' yoki '-' ishorasini o'qing.
  3. Raqam bo'lmagan belgi yoki string tugaguncha raqamlarni o'qing.
  4. Natija 32-bitli ishorali butun son oralig'ida bo'lishi kerak: [-2^31, 2^31 - 1]. Oshib ketsa — chegaraga qisqartiring.
Kirish: "42"
Chiqish: 42

Kirish: "   -042"
Chiqish: -42

Kirish: "1337c0d3"
Chiqish: 1337   // raqam bo'lmagan belgida to'xtatiladi

Kirish: "0-1"
Chiqish: 0   // '-' raqam emas, darhol to'xtatiladi

Kirish: "-91283472332"
Chiqish: -2147483648   // 32-bit minimumga qisqartirildi

Kirish: "words and 987"
Chiqish: 0   // birinchi belgi raqam emas

Asosiy g'oya: holat bo'yicha o'qish

Masala qoidalari tartibli: oldin bo'sh joy, keyin ishora, keyin raqamlar. Har belgi uchun "hozir qaysi bosqichdaman?" degan savolga javob berib, mos harakat qilamiz.

Bosqichlar:

  1. Bo'sh joy belgilarini o'tkazib yuborish.
  2. Ixtiyoriy '+' yoki '-' ni aniqlash.
  3. Raqam belgilarini son sifatida yig'ish.
  4. Har qadam natijaning 32-bit chegarasini tekshirish.

Pseudocode

FUNCTION ATOI(s)
    i    = 0
    n    = LENGTH(s)
    sign = 1      // musbat

    // 1. Boshidagi bo'sh joylarni o'tkazib yuborish
    WHILE i < n VA s[i] = ' '
        i = i + 1

    // 2. Ishtiorani aniqlash
    IF i < n VA (s[i] = '+' YO s[i] = '-')
        IF s[i] = '-'
            sign = -1
        i = i + 1

    // 3. Raqamlarni o'qish
    result = 0

    WHILE i < n VA s[i] raqam belgisi
        digit = s[i] - '0'       // '7' → 7

        // 4. Overflow tekshirish (qo'shishdan oldin)
        IF result > (INT_MAX - digit) / 10
            RETURN INT_MAX IF sign = 1 ELSE INT_MIN

        result = result * 10 + digit
        i = i + 1

    RETURN sign * result

INT_MAX = 2 147 483 647, INT_MIN = -2 147 483 648.

Overflow tekshirishi nima uchun murakkab?

result * 10 + digit overflow qilishidan oldin tekshirish zarur — chunk overflow qilib, keyin tekshirish kech. Shuning uchun:

IF result > (INT_MAX - digit) / 10

Bu result * 10 + digit > INT_MAX sharti bilan ekvivalent (qayta tartiblab):

result * 10 > INT_MAX - digit
result > (INT_MAX - digit) / 10

Hisoblash ketma-ketligi muhim: INT_MAX - digit avval hisoblansa, natija hali INT_MAX ichida; keyin / 10. Agar result bundan katta bo'lsa — keyingi qadam overflow qiladi.

Bosqichma-bosqich dry run

s = " -4193 with words":

i=0: ' ' → o'tkazib yuborish
i=1: ' ' → o'tkazib yuborish
i=2: '-' → sign = -1, i=3
i=3: '4' → raqam. digit=4, result = 0*10+4 = 4
i=4: '1' → raqam. digit=1, result = 4*10+1 = 41
i=5: '9' → raqam. digit=9, result = 41*10+9 = 419
i=6: '3' → raqam. digit=3, result = 419*10+3 = 4193
i=7: ' ' → raqam emas, to'xtash

RETURN -1 * 4193 = -4193

s = "2147483648" (INT_MAX + 1):

Raqamlarni o'qish:
  ...
  result = 214748364, digit = 8

  Tekshirish:
    (INT_MAX - 8) / 10 = (2147483647 - 8) / 10 = 214748363

  result = 214748364 > 214748363 → overflow!
  RETURN INT_MAX = 2147483647

Vaqt va xotira murakkabligi

Xususiyat Qiymat Izoh
Vaqt O(n) String bir marta o'qiladi
Xotira O(1) Bir nechta o'zgaruvchi

n — string uzunligi.

Edge case'lar

Bo'sh string. n = 0 yoki faqat bo'sh joy — result = 0.

Faqat ishora. "+" yoki "-" — raqam yo'q, result = 0.

Nol bilan boshlanuvchi. "007" → 7. Oldingi nollar muammo emas.

Raqamlardan oldin raqam bo'lmagan belgi. "abc" → 0, birinchi belgida to'xtatiladi.

Positive overflow. "21474836470" → INT_MAX.

Negative overflow. "-21474836480" → INT_MIN.

+ va - ikkalasi. "+-3" → '+' ishorasi o'qiladi, keyin '-' raqam emas → result = 0.

Note

'0' belgisining raqam qiymatini olish uchun s[i] - '0' ishlatiladi. Bu ASCII kodlashda ishlaydi: '0' = 48, '1' = 49, ... '9' = 57. Farq raqamning o'zini beradi.

Keng tarqalgan xatolar

Bo'sh joyni faqat boshida tekshirish. Masala faqat boshidagi bo'sh joylarni o'tkazishni aytadi. O'rtadagi yoki oxiridagi bo'sh joy allaqachon raqam yo'q deb to'xtatiladi.

Overflow ni raqam qo'shgandan keyin tekshirish. result * 10 o'zi overflow qilishi mumkin. Tekshirish oldin bajarilishi kerak.

Ishorani hisobga olmaslik. INT_MIN = -2147483648, lekin INT_MAX = 2147483647. |INT_MIN| > |INT_MAX|. Overflow tekshirishida INT_MAX ishlatish ishorali holat uchun yetarli, chunki sign * result qaytarilganda INT_MIN ga yetib boradi.

Xulosa

Songa aylantirish — tartibli holat o'qish masalasi. Bo'sh joy → ishora → raqamlar. Har raqamda result = result * 10 + digit va overflow tekshirish. Raqam bo'lmagan belgida to'xtatish.

O(n) vaqt va O(1) xotira. Masalaning murakkablik qismi — overflow aniqlashning to'g'ri tartibda bajarilishi.