价格减免

难度: Medium

句子是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。

例如 "$100"、"$23" 和 "$6" 表示价格，而 "100"、"$" 和 "$1e5 不是。

给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并更新该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

注意：所有价格最多为 10 位数字。

示例 1：

输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
输出："there are $0.50 $1.00 and 5$ candies in the shop"
解释：
表示价格的单词是 "$1" 和 "$2" 。 
- "$1" 减免 50% 为 "$0.50" ，所以 "$1" 替换为 "$0.50" 。
- "$2" 减免 50% 为 "$1" ，所以 "$1" 替换为 "$1.00" 。

示例 2：

输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
解释：
任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。
每个单词都替换为 "$0.00"。

提示：

1 <= sentence.length <= 10⁵
sentence 由小写英文字母、数字、' ' 和 '$' 组成
sentence 不含前导和尾随空格
sentence 的所有单词都用单个空格分隔
所有价格都是正整数且不含前导零
所有价格最多为 10 位数字
0 <= discount <= 100

Submission

运行时间: 83 ms

内存: 17.9 MB

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        arr=sentence.split()
        p=1-0.01*discount
        for i,v in enumerate(arr):
            if v[0]=="$" and v[1:].isdigit():
                c=f"${int(v[1:])*p:.2f}"
                arr[i]=c
        return " ".join(arr)

Explain

此题解首先通过空格将句子分割成单词列表。然后计算出折扣后的价格因子 p，即原价的剩余百分比。接着遍历单词列表，对于每个单词，检查其是否以美元符号'$'开头并且其后跟随的字符全为数字，满足条件则视为有效的价格。对于这些价格单词，将其后的数字部分转换为整数并乘以 p，再格式化为两位小数的字符串形式，并更新到原位置。最后，将处理后的单词列表重新拼接成字符串返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        arr = sentence.split()  # 将句子分割成单词列表
        p = 1 - 0.01 * discount  # 计算折扣因子
        for i, v in enumerate(arr):  # 遍历单词列表
            if v[0] == '$' and v[1:].isdigit():  # 检查是否为有效的价格格式
                c = f'${int(v[1:]) * p:.2f}'  # 计算折扣后价格并格式化为两位小数的字符串
                arr[i] = c  # 更新单词列表中的价格
        return ' '.join(arr)  # 将处理后的单词列表重新组合为字符串并返回

Explore

为了避免处理大数字导致的整数溢出问题，可以在转换整数前检查数字的长度。如果数字长度超过安全处理的位数（例如10位），则可以拒绝处理该数字或者使用更大范围的数据类型如Python的`long`或使用库如`decimal`来处理大数值。此外，Python的整型在较新版本中是动态扩展的，理论上可以处理任意大的整数，只受限于系统内存。

使用`v[1:].isdigit()`方法仅检查字符串是否全部由数字组成，不包括小数点或负号。如果价格字符串中包含小数点或负号，`isdigit()`将返回`False`，该字符串就不会被视为有效的价格格式。这保证了只处理格式严格为`$`后直接跟随整数的情况。如果需要处理包含小数或负数的价格，需要更复杂的检测逻辑来分析和验证字符串。

浮点数运算可能引起精度问题，尤其是在金融计算中。在这个题解中，将整数转换为浮点数进行运算后，结果通过格式化为两位小数来限制精度。这种处理在许多实际应用中是可接受的，但对于需要高度精确的金融应用，可能需要使用如Python的`decimal.Decimal`类来进行精确的十进制计算，避免浮点误差。

将价格从字符串转换为整数可以确保在进行数学运算时的准确性和效率。直接在字符串上进行数学运算需要先解析字符串中的数字，这不仅增加了实现的复杂性，而且容易出错。转换为整数后，可以利用标准的数学运算来进行折扣计算，这样的处理更直观、更可靠。此外，整数和浮点数操作通常比字符串解析和操作更快，更适合性能敏感的应用。