C++ 从给定的字符串中找到有效的整数

在这个问题中，我们需要通过遵循问题陈述中的规则，从给定的字符串中提取整数。我们可以通过检查字符串的初始子字符串是否满足每个给定的有效整数值的规则来解决这个问题。

问题陈述 - 我们有一个包含数字、’.’、’+’和’-‘字符的字符串digits。我们需要从给定的字符串中提取有效的整数值。

有效整数的规则

• 它不应该包含前导零和空格。
• 整数应该以符号或数字开头。
• 如果没有给出任何符号，则认为整数是正数。
• 如果字符串包含小数部分，则从字符串中提取整数部分。
• 如果字符串中的整数值之前包含其他字符（除了数字），则打印0。
• 如果字符串中的整数值之后包含其他字母数字，则提取并打印整数值。
• 整数应该介于-2147483647和2147483647之间。如果不是，则打印限制值。
• 如果字符串中间包含其他字符，则提取初始整数。

示例示例

输入

digits = "+234567.4234"

输出

234567

解释 – 它从十进制数中提取了整数部分。此外，符号为‘+’，因此它打印了没有符号的正数。

输入

digits = "-23324";

输出

-23324

解释 – 它已经打印出带符号的数字的小数部分。

输入

digits = "   000122";

输出

122

解释 – 它忽略了前导空格和0。

输入

digits = "   000122";

输出

0

解释 - 字符串中包含数字之前的其他字母字符。因此，打印0。

方法1

在这种方法中，我们将检查前导空格、零、符号等，并管理字符串的小数部分。简而言之，我们将找到一个符合所有给定规则的整数值。

用户可以按照下面的算法逐步操作。

算法

步骤1 - 使用最小和最大整数值初始化mini和maxi变量。

步骤2 - 定义‘final_int’变量来存储整数值，‘sign’变量来存储整数的符号，‘digitPresent’变量来跟踪包含数字的字符串。‘digitPresent’变量对于检查字符串是否包含其他字符、中间的空格等非常有用。

步骤3 - 开始遍历数字字符串。

步骤4 - 如果第i个索引处的字符是空格，并且‘digitPresent’为true，那么这意味着空格在整数的中间。所以，使用break关键字中断循环。否则，如果空格在开头，则使用‘continue’关键字移动到下一次迭代。

步骤5 - 如果第i个字符是‘-’或‘+’，按照以下步骤进行。

步骤5.1 - 如果‘sign’不为零，则中断循环，因为‘-’或‘+’在整数值的中间。

步骤5.2 - 如果字符是‘-’，将‘sign’变量的值更新为-1，并将‘digitsPresent’变量的值更新为true，表示整数已开始。

步骤5.3 - 如果字符是‘+’，将‘sign’变量的值更新为1，并将‘digitPresent’变量的值更新为true。

步骤6 - 如果当前字符是‘.’或其他字符，中断循环。

步骤7 - 如果第i个字符是0到9之间的数字，请按照以下步骤进行。

步骤7.1 - 将‘digitPresent’的值更新为true。

步骤7.2 - 如果‘sign’的值为0，请将其更新为1，因为字符串不包含任何符号。因此，默认情况下我们认为它是正数。否则，保持原样。

步骤7.3 - 如果final_int < mini/10 || final_int > maxi/10 || final_int * 10 + (digits[i] – ‘0’) < mini || final_int * 10 + (digits[i] – ‘0’) > maxi) 为true，将final_int乘以10，然后加上数字值。否则，如果整数值超过了限制，则根据符号值分配mini或maxi。

步骤 8 – 返回 final_int*sign 的值。

示例

#include <iostream>
#include <cmath>
using namespace std;

int getValidInt(string digits) {
    // Get the minimum and maximum integer value
    int mini = (-1) * pow(2, 31);
    int maxi = pow(2, 31) - 1;
    // Variable initialization
    long final_int = 0;
    int sign = 0, digitPresent = false;
    // Traverse the string
    for (int i = 0; i < digits.length(); i++) {
        // Ignoring only leading white spaces
        if (digits[i] == ' ') {
            if (digitPresent)
                break;
            else
                continue;
        }
        // handling the sign
        else if (digits[i] == '-' || digits[i] == '+') {
            // Case 1 - The sign is in the middle of the string
            if (sign != 0)
                break;
            // Case 2 - The sign is at the start of the string
            else if (digits[i] == '-' && sign == 0) {
                sign = -1;
                digitPresent = true;
            } else if (digits[i] == '+' && sign == 0) {
                sign = 1;
                digitPresent = true;
            }
        }
         // handling other characters.
        // Removing decimal part
        else if ((digits[i] == '.' || !(digits[i] - '0' >= 0 && digits[i] - '0' < 10))) {
            break;
        }
        // Handling digits
        else if (digits[i] - '0' >= 0 && digits[i] - '0' < 10) {
            digitPresent = true;
            sign = sign == 0 ? 1 : sign;
            if (!(final_int < mini / 10 || final_int > maxi / 10 || final_int * 10 + (digits[i] - '0') < mini || final_int * 10 + (digits[i] - '0') > maxi)) {
                final_int = final_int * 10 + (digits[i] - '0'); 
            } else {
                final_int = sign == -1 ? mini : maxi;
                break;
            }
        }
    }
    return final_int * sign;
}
int main() {
    string digits = "  +234567.4234";
    cout << "The valid integer from the given string is - " << getValidInt(digits);
    return 0;
}

输出

The valid integer from the given string is - 234567

时间复杂度 – 提取整数值的时间复杂度为O（N）。

空间复杂度 – O（1）

程序员需要按照上述代码中的顺序编写if-else语句。如果他们按照不同的顺序编写，则代码有时会给出错误的输出。因此，我们可以知道在某些类似问题中，保持if-else语句的顺序也很重要。