(C卷,100分)- 求字符串中所有整数的最小和（Java & JS & Python & C）

题目描述

输入字符串s，输出s中包含所有整数的最小和。

说明：

字符串s，只包含 a-z A-Z ± ；
合法的整数包括

1） 正整数 一个或者多个0-9组成，如 0 2 3 002 102
2）负整数 负号 – 开头，数字部分由一个或者多个0-9组成，如 -0 -012 -23 -00023

输入描述

包含数字的字符串

输出描述

所有整数的最小和

用例

题目解析

本题看上去很难，其实想清楚三点那就很简单

• 正数字符串的最小值如何计算？比如1234的最小值是多少，那肯定是1+2+3+4，即每位都是一个独立数，且都是一个小于10的数，它们之和就是最小的。
• 负数字符串的最小值如何计算？比如-34，那肯定是整体当成一个负数时，最小。
• 正数负数混合字符串最小值如何计算？比如12-34，那肯定是正数部分12每位单独计算，负数部分当成整体

我的解题思路如下：

定义一个容器negative，用于存储负数的数字字符

定义一个标识isNegative，用来记录是否遇到负数，初始化为false，标识一开始没有遇到负数

遍历输入字符串s的每一个字符c

• 如果 c == '-'，则说明负数要开始了，因此更新isNegative = true
• 如果 c 是数字字符，则此时需要分情况讨论：

1. isNegative == false，则此时直接将c字符转成对应的数值合入结果，ans += parseInt(c)
2. isNegative == true，则说明c是负数的字符，此时应该将c加入缓存容器negative中

• 如果 c 是字母字母，若isNegative == true，则需要将negative容器中内容拼接，然后转化为负数合入结果，ans -= parseInt(negative.join(""))，完成后，将isNeagtive = false，并且清空negative容器。

需要注意的是，当c == '-'，也需要注意出现 “-34-40” 这种情况，即 c == '-'，也需要先判断isNegative == true，则需要将negative容器中内容拼接，然后转化为负数合入结果，ans -= parseInt(negative.join(""))，完成后，将isNeagtive = false，并且清空negative容器。

2023.06.01

本题没有说明数字长度，因此Java和JS需要使用大数处理。

2023.12.08

修复一个问题，比如用例

bb12–a-34aa

可能会出现不完整负数情况，即只有一个符号的情况，此时我们应该过滤掉这种不完整负数场景

Java算法源码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static String getResult(String s) {
    boolean isNegative = false;
    StringBuilder negative = new StringBuilder();

    //    int ans = 0;
    BigInteger ans = new BigInteger("0");

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      if (c >= '0' && c <= '9') {
        if (isNegative) {
          negative.append(c);
        } else {
          //          ans += Integer.parseInt(c + "");
          ans = ans.add(new BigInteger(c + ""));
        }
      } else {
        if (isNegative && negative.length() > 0) {
          //          ans -= Integer.parseInt(negative.toString());
          ans = ans.subtract(new BigInteger(negative.toString()));
          negative = new StringBuilder();
        }

        isNegative = c == '-';
      }
    }

    if (negative.length() > 0) {
      //      ans -= Integer.parseInt(negative.toString());
      ans = ans.subtract(new BigInteger(negative.toString()));
    }

    return ans.toString();
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(s) {
  let isNegative = false;
  const negative = [];

  // let ans = 0;
  let ans = BigInt(0);
  for (let c of s) {
    if (c >= "0" && c <= "9") {
      if (isNegative) {
        negative.push(c);
      } else {
        // ans += parseInt(c);
        ans += BigInt(c);
      }
    } else {
      if (isNegative && negative.length > 0) {
        // ans -= parseInt(negative.join(""));
        ans -= BigInt(negative.join(""));
        negative.length = 0;
      }

      isNegative = c == "-";
    }
  }

  if (negative.length > 0) {
    // ans -= parseInt(negative.join(""));
    ans -= BigInt(negative.join(""));
  }

  return ans.toString();
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    isNegative = False
    negative = []

    ans = 0
    for c in s:
        if '0' <= c <= '9':
            if isNegative:
                negative.append(c)
            else:
                ans += int(c)
        else:
            if isNegative and len(negative) > 0:
                ans -= int("".join(negative))
                negative.clear()
            isNegative = c == '-'

    if len(negative) > 0:
        ans -= int("".join(negative))

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10000

int main() {
    char s[MAX_SIZE];
    gets(s);

    int isNegative = 0;

    char negative[MAX_SIZE];
    int negative_size = 0;

    long long ans = 0;
    int i = 0;
    while (s[i] != '') {
        char c = s[i];

        if (c >= '0' && c <= '9') {
            if (isNegative) {
                negative[negative_size++] = c;
            } else {
                ans += c - '0';
            }
        } else {
            if (isNegative && negative_size > 0) {
                ans -= atol(negative);
                memset(negative, '', MAX_SIZE);
                negative_size = 0;
            }

            isNegative = c == '-';
        }

        i++;
    }

    if (negative_size > 0) {
        ans -= atol(negative);
    }

    printf("%lldn", ans);

    return 0;
}