题目描述与示例
题目描述
- 字符串 s，只包含
a-z，A-Z，+-； - 合法的整数包括
1） 正整数 一个或者多个0-9组成，如 0 2 3 002 102
2）负整数 负号 - 开头，数字部分由一个或者多个0-9组成，如 -0 -012 -23 -00023
输入描述
包含数字的字符串
输出描述
所有整数的最小和
示例一
输入
bb1234aa
输出
10
说明
示例二
输入
bb12-34aa
输出
-31
说明
1+2+(-34) = -31
解题思路
贪心地思考问题：为了使得和尽可能地小，当
- 遇到正数，我们逐个数字相加，譬如遇到
"123"，不应该当作数字123来使用，而是应该当作三个数字1、2、3来相加。 - 遇到负数，我们对整个负数进行整体地考虑。因此需要维护一个变量
num，用来表示字符串中的负数。
代码
解法一：从头到尾直接遍历字符串
Python
# 题目：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();
s = s.replace("-", " -");
String[] lst = s.split(" ");
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 (int i = 1; i < sub_s.length(); i++) {
char ch = sub_s.charAt(i);
if (Character.isDigit(ch)) {
if (flag) {
num = num * 10 - Character.getNumericValue(ch);
} else {
ans += Character.getNumericValue(ch);
}
} else {
flag = false;
}
}
ans += num;
}
System.out.println(ans);
}
}
C++
“`C++
#include
#include
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
```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)
</code></pre>
<h3>Java</h3>
<pre><code class="language-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);
}
}
</code></pre>
<h3>C++</h3>
```C++
#include
#include
#include
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 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``)。储存切割后的字符串的数组所占用的空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
