Leetcode atoi (สตริงเป็นจำนวนเต็ม)

Question

ลิงค์ที่นี่

ฉันจะรวมโซลูชันใน Python และ C ++ และคุณสามารถตรวจสอบได้ ฉันสนใจที่จะตรวจสอบโค้ด C ++ ซึ่งเป็นสิ่งที่ฉันเพิ่งเริ่มเรียนรู้ ผู้ที่ไม่ทราบ C ++ สามารถตรวจสอบโค้ด Python ได้

---

คำชี้แจงปัญหา

ใช้งานatoiซึ่งแปลงสตริงเป็นจำนวนเต็ม ฟังก์ชันแรกจะละทิ้งอักขระเว้นวรรคเท่าที่จำเป็นจนกว่าจะพบอักขระที่ไม่ใช่ช่องว่างตัวแรก จากนั้นการเริ่มต้นจากอักขระนี้จะใช้เครื่องหมายบวกหรือลบเริ่มต้นที่เป็นทางเลือกตามด้วยตัวเลขจำนวนมากที่สุดเท่าที่จะเป็นไปได้และตีความเป็นค่าตัวเลข สตริงสามารถมีอักขระเพิ่มเติมหลังจากที่เป็นจำนวนอินทิกรัลซึ่งจะถูกละเว้นและไม่มีผลกับลักษณะการทำงานของฟังก์ชันนี้ หากลำดับแรกของอักขระที่ไม่ใช่ช่องว่างใน str ไม่ใช่จำนวนอินทิกรัลที่ถูกต้องหรือหากไม่มีลำดับดังกล่าวเนื่องจาก str ว่างเปล่าหรือมีเพียงอักขระเว้นวรรคจะไม่มีการแปลง หากไม่สามารถทำการแปลงที่ถูกต้องได้ระบบจะส่งคืนค่าเป็นศูนย์

บันทึก:

เฉพาะอักขระ' 'ช่องว่างเท่านั้นที่ถือเป็นอักขระช่องว่าง สมมติว่าเรากำลังจัดการกับสภาพแวดล้อมที่สามารถจัดเก็บเฉพาะจำนวนเต็มภายในช่วงจำนวนเต็มที่มีลายเซ็น 32 บิตเท่านั้น: [−2³¹, 2³¹ - 1] หากค่าตัวเลขอยู่นอกช่วงของค่าที่แสดงได้ระบบจะส่งคืน2³¹ - 1 หรือ −2³¹

ตัวอย่างที่ 1:

Input: str = "42"
Output: 42

ตัวอย่างที่ 2:

Input: str = "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign. Then take as many numerical digits as possible, which gets 42.

ตัวอย่างที่ 3:

Input: str = "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

ตัวอย่างที่ 4:

Input: str = "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.

ตัวอย่างที่ 5:

Input: str = "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer. Thefore INT_MIN (−231) is returned.

---

str_int.py

def convert(s):
    chars = (c for c in s)
    ss = []
    while True:
        try:
            current = next(chars)
            if (space := current.isspace()) and ss:
                break
            if (pm := current in '+-') and ss:
                break
            if not current.isnumeric() and not pm and not space:
                break
            if not space:
                ss.append(current)
        except StopIteration:
            break
    try:
        number = int(''.join(ss).strip())
        if number < 0:
            return max(-2 ** 31, number)
        return min(2 ** 31 - 1, number)
    except ValueError:
        return 0


if __name__ == '__main__':
    print(convert("    48-"))

str_int.h

#ifndef LEETCODE_STR_TO_INT_H
#define LEETCODE_STR_TO_INT_H

#include <string>

int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx);
int convert_str(const std::string &s);

#endif //LEETCODE_STR_TO_INT_H

str_int.cpp

#include <string>
#include <iostream>


int atoi_impl(const std::string& s, size_t start_idx, size_t end_idx) {
    try {
        return std::stoi(s.substr(start_idx, end_idx));
    }
    catch (const std::out_of_range &e) {
        return (s[start_idx] == '-') ? INT32_MIN : INT32_MAX;
    }
    catch (const std::invalid_argument &e) {
        return 0;
    }
}


int convert_str(const std::string &s) {
    size_t start_idx = 0;
    size_t end_idx = s.size();
    for (size_t i = 0; i < s.size(); ++i) {
        bool digit = std::isdigit(s[i]);
        bool pm = s[i] == '+' || s[i] == '-';
        bool space = std::isspace(s[i]);
        if (i == start_idx && !space && !digit && !pm)
            return 0;
        if ((space || !digit) && i != start_idx) {
            end_idx = i;
            break;
        }
        if (space)
            start_idx++;
    }
    if (start_idx != end_idx)
        return atoi_impl(s, start_idx, end_idx);
    return 0;
}


int main() {
    std::cout << "result1: " << convert_str(" -912332") << "\n";
}

Answer 1

เป็นความคิดที่ดีที่จะเพิ่มการทดสอบหน่วยให้กับการใช้งานทั้งสองอย่างเพื่อแสดงให้เห็นว่าโค้ดทำงานได้ตามที่ตั้งใจไว้และเพื่อให้สามารถทำการ refactor ได้อย่างมั่นใจ รวมการทดสอบให้เพียงพอที่จะควบคุมข้อกำหนดทั้งหมดในข้อกำหนด (อยู่นอกช่วงอักขระที่ไม่ถูกต้อง+/ -/ ไม่มีอะไร ฯลฯ )

ฉันจะตรวจสอบรหัส C ++ โดยละเอียด

เรากำลังขาดหายไป#include <cctype>, ที่จำเป็นสำหรับการstd::isspace()และและstd::isdigit()#include <stdexcept>

ข้อกำหนดระบุว่า " อักขระเว้นวรรคเท่านั้น" ถือเป็นอักขระเว้นวรรค "ดังนั้นเราจึงไม่ควรใช้std::isspace()ซึ่งจะจับคู่กับชุดอักขระที่กว้างขึ้นรวมถึงขึ้นบรรทัดใหม่และแท็บ

อัลกอริทึมไม่มีประสิทธิภาพ - ไม่มีเหตุผลที่จะสำรวจสตริงมากกว่าหนึ่งครั้ง เราสามารถพิจารณาทีละอักขระเริ่มต้นการแปลงเมื่อเราเห็นอักขระที่ไม่ใช่ช่องว่างตัวแรกและสิ้นสุดที่ส่วนท้ายของตัวเลข

การใช้งานstd::stoi()อาจอยู่นอกจิตวิญญาณของการออกกำลังกายเช่นนี้ - คุณคาดว่าจะแสดงความสามารถในการเขียนโค้ดอัลกอริทึมหลัก!

เราจำเป็นต้องระมัดระวังอย่างยิ่งเพื่อหลีกเลี่ยงไม่ให้จำนวนเต็มล้น เราไม่สามารถตรวจสอบได้หลังจากที่มันเกิดขึ้นเนื่องจากเราอยู่ในโลกของพฤติกรรมที่ไม่ได้กำหนดทำให้โปรแกรมทั้งหมดไม่ระบุ! ความเป็นไปได้อย่างหนึ่งคือการสะสมผลลัพธ์ในประเภทที่ไม่ได้ลงชื่อซึ่งมีช่วงที่ใหญ่กว่าประเภทที่ลงนามที่เกี่ยวข้อง แต่ระวังเมื่อจัดการกับค่าที่เป็นลบมากที่สุดในช่วงซึ่งไม่มีค่าบวกที่สอดคล้องกัน!

---

การใช้งานทางเลือก

นี่คือวิธีที่ฉันจะแก้ไขปัญหาข้างต้น เริ่มต้นด้วยการทดสอบบางส่วน:

#include <iostream>
#include <cstdlib>

#define COMPARE(expected, actual)                       \
    do {                                                \
        if (expected != actual) {                       \
            ret = EXIT_FAILURE;                         \
            std::cerr << "Expected " << (expected)      \
                      << " but got " << (actual)        \
                      << " from " << #actual << '\n';   \
        }                                               \
    } while (0)

int main()
{
    int ret = EXIT_SUCCESS;
    COMPARE(0, convert_str(""));
    COMPARE(0, convert_str("0"));
    COMPARE(0, convert_str("-0"));
    COMPARE(1, convert_str("1"));
    COMPARE(1, convert_str("  1"));
    COMPARE(1, convert_str("1e2"));
    COMPARE(0, convert_str("\t1"));
    COMPARE(-1, convert_str(" -1"));
    COMPARE(-1, convert_str(" -001"));
    COMPARE(2147483647, convert_str("2147483647"));
    COMPARE(2147483647, convert_str("2147483648"));
    COMPARE(-2147483648, convert_str("-2147483648"));
    COMPARE(-2147483648, convert_str("-2147483649"));
    return ret;
}

ตอนนี้ขอใช้ฟังก์ชัน ฉันจะใช้ตัววนซ้ำผ่านมุมมองสตริงสำหรับสิ่งนี้:

#include <cctype>
#include <cstdint>
#include <string_view>
#include <type_traits>

int_fast32_t convert_str(std::string_view s)
{
    uint_fast32_t value = 0;
    bool negative = false;
    auto i = s.begin();
    auto const end = s.end();

    // skip whitespace
    while (i != end && *i == ' ') {
        ++i;
    }
    if (i == end) {
        return 0;
    }

    // handle optional sign indicator
    if (*i == '-') {
        negative = true;
        ++i;
    } else if (*i == '+') {
        ++i;
    }

    // process the digits
    while (i != end && std::isdigit(unsigned(*i))) {
        if (value > 214748364
            || value == 214748364 && *i > '7' + negative) {
            // would overflow
            return negative ? -2147483648 : 2147483647;
        }

        // usual case
        value = value * 10 + (*i - '0');
        ++i;
    }

    // convert to result type
    int_fast32_t signed_value = value;
    return negative ? -signed_value : signed_value;
}

ยังคงมีปัญหาบางอย่าง (ฉันไม่ชอบตัวเลขมายากลแบบฮาร์ดโค้ด) แต่ทั้งปลอดภัยและชัดเจนกว่าแบบเดิม

ออกกำลังกาย

ตอนนี้เปลี่ยนอินเทอร์เฟซเพื่อยอมรับประเภทอักขระใด ๆ และส่งคืนประเภทจำนวนเต็มที่ต้องการ (พร้อมค่าความอิ่มตัวที่เหมาะสม):

template<typename Integer, typename Char, typename Traits>
Integer convert_str(std::basic_string_view<Char,Traits> s);