Leetcode atoi (string para inteiro)

Nov 12 2020

Incluirei uma solução em Python e C ++ e você pode revisar uma. Estou mais interessado em revisar o código C ++, algo que comecei a aprender recentemente; aqueles que não conhecem C ++ podem revisar o código Python.

Declaração do problema

Implementar atoique converte uma string em um inteiro. A função primeiro descarta quantos caracteres de espaço em branco forem necessários até que o primeiro caractere diferente de espaço em branco seja encontrado. Em seguida, começar a partir desse caractere pega um sinal de mais ou menos inicial opcional seguido por tantos dígitos numéricos quanto possível e os interpreta como um valor numérico. A string pode conter caracteres adicionais após aqueles que formam o número integral, que são ignorados e não têm efeito no comportamento desta função. Se a primeira sequência de caracteres sem espaço em branco em str não for um número inteiro válido, ou se nenhuma sequência existir porque str está vazio ou contém apenas caracteres de espaço em branco, nenhuma conversão é executada. Se nenhuma conversão válida puder ser realizada, um valor zero será retornado.

Nota:

Apenas o caractere de espaço ' 'é considerado um caractere de espaço em branco. Suponha que estamos lidando com um ambiente que só pode armazenar inteiros dentro do intervalo de inteiros com sinal de 32 bits: [−2³¹, 2³¹ - 1]. Se o valor numérico estiver fora da faixa de valores representáveis, 2³¹ - 1 ou −2³¹ é retornado.

Exemplo 1:

Input: str = "42"
Output: 42

Exemplo 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.

Exemplo 3:

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

Exemplo 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.

Exemplo 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";
}

Respostas

4 TobySpeight Nov 13 2020 at 09:14

Seria uma boa ideia adicionar testes de unidade a ambas as implementações, tanto para demonstrar que o código funciona como pretendido, quanto para permitir refatorações com confiança. Inclua testes suficientes para cumprir todos os requisitos da especificação (fora do intervalo, caracteres inválidos, +/ -/ nada, etc.).

Vou revisar o código C ++ com mais detalhes.

Estamos ausentes #include <cctype>, necessários para std::isspace()e std::isdigit(), e #include <stdexcept>.

O requisito diz que " Somente o caractere de espaço '' é considerado um caractere de espaço em branco ", portanto, não devemos usar o std::isspace()que corresponderá a um conjunto mais amplo de caracteres, incluindo nova linha e tabulação.

O algoritmo é ineficiente - não há razão para percorrer a string mais de uma vez. Podemos considerar um único caractere por vez, iniciando a conversão quando vemos o primeiro caractere sem espaço e terminando no final dos dígitos.

Usar std::stoi()provavelmente está fora do espírito de um exercício como este - espera-se que você demonstre a capacidade de codificar o algoritmo principal!

Precisamos ser extremamente cuidadosos para evitar estouro de inteiros. Não podemos verificar isso depois que aconteceu, pois estamos no mundo do Undefined Behavior, tornando todo o programa não especificado! Uma possibilidade é acumular o resultado em um tipo sem sinal que tem um alcance maior do que o tipo com sinal correspondente. Mas tenha cuidado ao lidar com o valor mais negativo do intervalo, que não tem um valor positivo correspondente!