# 题目：2023B-求字符串中所有整数的最小和
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


# 输入原字符串
s = input()

# flag为遇到负号"-"的标志
flag = False
# 用于记录字符串中的负数的变量num
num = 0
# 答案变量
ans = 0

# 遍历s中的所有字符ch
for ch in s:
    # 遇到负号，将num加入ans中（此时num可能是负数，也可能是0）
    # 重置num为0，设置flag为True，表示后续应该考虑一个负数
    if ch == "-":
        ans += num
        num = 0
        flag = True
    # 遇到数字
    elif ch.isdigit():
        # 如果flag为True，说明此时ch正处于一个负数中
        # num扩大10倍后减去int(ch)，进行延长
        if flag == True:
            num = num * 10 - int(ch)
        # 如果flag为False，说明此时ch正处于一个正数中
        # 为了使得总和尽可能小，直接将int(ch)加入ans中即可
        else:
            ans += int(ch)
    # 遇到其他字符，将num加入ans中（此时num可能是负数，也可能是0）
    # 重置num为0，设置flag为True，表示后续不用考虑负数
    else:
        ans += num
        num = 0
        flag = False

# 最后一个负数可能位于字符串末尾，
# 还需要再做一次相加才能得到正确答案
ans += num
print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入原字符串
        String s = scanner.nextLine();

        // flag为遇到负号"-"的标志
        boolean flag = false;
        // 用于记录字符串中的负数的变量num
        int num = 0;
        // 答案变量
        int ans = 0;

        // 遍历s中的所有字符ch
        for (char ch : s.toCharArray()) {
            // 遇到负号，将num加入ans中（此时num可能是负数，也可能是0）
            // 重置num为0，设置flag为true，表示后续应该考虑一个负数
            if (ch == '-') {
                ans += num;
                num = 0;
                flag = true;
            }
            // 遇到数字
            else if (Character.isDigit(ch)) {
                // 如果flag为true，说明此时ch正处于一个负数中
                // num扩大10倍后减去ch - '0'，进行延长
                if (flag) {
                    num = num * 10 - (ch - '0');
                }
                // 如果flag为false，说明此时ch正处于一个正数中
                // 为了使得总和尽可能小，直接将ch - '0'加入ans中即可
                else {
                    ans += ch - '0';
                }
            }
            // 遇到其他字符，将num加入ans中（此时num可能是负数，也可能是0）
            // 重置num为0，设置flag为false，表示后续不用考虑负数
            else {
                ans += num;
                num = 0;
                flag = false;
            }
        }

        // 最后一个负数可能位于字符串末尾，
        // 还需要再做一次相加才能得到正确答案
        ans += num;
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    bool flag = false;
    int num = 0;
    int ans = 0;

    for (char ch : s) {
        if (ch == '-') {
            ans += num;
            num = 0;
            flag = true;
        } else if (isdigit(ch)) {
            if (flag) {
                num = num * 10 - (ch - '0');
            } else {
                ans += (ch - '0');
            }
        } else {
            ans += num;
            num = 0;
            flag = false;
        }
    }

    ans += num;
    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历字符串s。

空间复杂度：O(1)。仅需若干常数变量。

解法二：切割字符串后对每一个字符串单独处理

Python

# 题目：2023B-求字符串中所有整数的最小和
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问

s = input()
# 在所有负号"-"前面加上一个空格，便于进行分割操作
s = s.replace("-", " -")
# 以空格" "为分割依据，对修改后的s进行分割
# 分割后的每一个子字符串，除了第一个子字符串lst[0]以外
#  其他子字符串第一个字符一定负号"-"
lst = s.split(" ")

# 由于第一个子字符串lst[0]的首个字符不一定是负号"-"
# 如果不是，我们可在其最前面插上"-a"
#（或者"-"加上任意一个字母均可）
# 使得其可以与其他子字符串进行相同的操作
if lst[0][0] != "-":
    lst[0] = "-a" + lst[0]

ans = 0
for sub_s in lst:
    # 用于计算位于每一个子字符串最前的负数
    num = 0
    # 用于判断负数是否计算完毕的标志
    flag = True
    for ch in sub_s[1:]:
        # 如果遇到数字
        if ch.isdigit():
            # 如果负数尚未计算完毕
            if flag:
                num = num * 10 - int(ch)
            # 如果负数已经计算完毕
            else:
                ans += int(ch)
        # 如果遇到其他字符，说明负数计算完毕，将flag修改为False
        else:
            flag = False
    # 退出关于子字符串的循环后，ans必须加上位于子字符串开头的负数
    ans += num

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        // 在所有负号"-"前面加上一个空格，便于进行分割操作
        s = s.replace("-", " -");
        // 以空格" "为分割依据，对修改后的s进行分割
        // 分割后的每一个子字符串，除了第一个子字符串lst[0]以外
        // 其他子字符串第一个字符一定负号"-"
        String[] lst = s.split(" ");

        // 由于第一个子字符串lst[0]的首个字符不一定是负号"-"
        // 如果不是，我们可在其最前面插上"-a"
        // 使得其可以与其他子字符进行相同的操作
        if (lst[0].charAt(0) != '-') {
            lst[0] = "-a" + lst[0];
        }

        int ans = 0;
        for (String sub_s : lst) {
            // 用于计算位于每一个子字符串最前的负数
            int num = 0;
            // 用于判断负数是否计算完毕的标志
            boolean flag = true;
            for (char ch : sub_s.substring(1).toCharArray()) {
                // 如果遇到数字
                if (Character.isDigit(ch)) {
                    // 如果负数尚未计算完毕
                    if (flag) {
                        num = num * 10 - Character.getNumericValue(ch);
                    }
                    // 如果负数已经计算完毕
                    else {
                        ans += Character.getNumericValue(ch);
                    }
                }
                // 如果遇到其他字符，说明负数计算完毕，将flag修改为false
                else {
                    flag = false;
                }
            }
            // 退出关于子字符串的循环后，ans必须加上位于子字符串开头的负数
            ans += num;
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    size_t pos = s.find("-");
    while (pos != string::npos) {
        s.replace(pos, 1, " -");
        pos = s.find("-", pos + 2);
    }
    istringstream iss(s);
    vector<string> lst;
    string sub_s;
    while (iss >> sub_s) {
        lst.push_back(sub_s);
    }
    
    if (lst[0][0] != '-') {
        lst[0] = "-a" + lst[0];
    }
    
    int ans = 0;
    for (const string& sub_s : lst) {
        int num = 0;
        bool flag = true;
        for (size_t i = 1; i < sub_s.length(); i++) {
            char ch = sub_s[i];
            if (isdigit(ch)) {
                if (flag) {
                    num = num * 10 - (ch - '0');
                } else {
                    ans += (ch - '0');
                }
            } else {
                flag = false;
            }
        }
        ans += num;
    }
    
    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(``N``)。仅需一次遍历字符串s。

空间复杂度：O(``N``)。储存切割后的字符串的数组所占用的空间。