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"。由于需要表示为恰好两位小数，我们将 "$2" 替换为 "$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^5
  • sentence 由小写英文字母、数字、' ' 和 '$' 组成
  • sentence 不含前导和尾随空格
  • sentence 的所有单词都由单个空格分隔
  • 所有价格都是不含前导零的正数
  • 所有价格都 最多 为 10 位数字
  • 0 <= discount <= 100

解题思路

这道题需要我们识别句子中的价格并应用折扣。

解题思路：

  1. 价格识别规则：一个有效的价格必须满足：

    • 以 ‘$’ 开头
    • ‘$’ 后面跟着至少一个数字
    • 只包含数字，不能有其他字符

  2. 处理流程：

    • 将句子按空格分割成单词数组
    • 遍历每个单词，判断是否为有效价格
    • 对有效价格应用折扣：新价格 = 原价格 × (100 - discount) / 100
    • 将结果格式化为两位小数，前面加上 ‘$’
    • 将处理后的单词重新组合成句子

  3. 实现细节：

    • 价格验证：检查第一个字符是否为 ‘$’，后续字符是否全为数字
    • 数值转换：将 ‘$’ 后的数字部分转换为数值进行计算
    • 格式化输出：使用格式化函数确保恰好保留两位小数

  4. 边界情况：

    • 只有 ‘$’ 的单词不是价格
    • ‘$’ 后包含非数字字符的单词不是价格
    • 折扣为 100% 时价格变为 0

代码实现

class Solution {
public:
    string discountPrices(string sentence, int discount) {
        istringstream iss(sentence);
        string word;
        vector<string> words;
        
        while (iss >> word) {
            if (isValidPrice(word)) {
                long long price = stoll(word.substr(1));
                double discountedPrice = price * (100 - discount) / 100.0;
                
                ostringstream oss;
                oss << "$" << fixed << setprecision(2) << discountedPrice;
                words.push_back(oss.str());
            } else {
                words.push_back(word);
            }
        }
        
        string result = "";
        for (int i = 0; i < words.size(); i++) {
            if (i > 0) result += " ";
            result += words[i];
        }
        
        return result;
    }
    
private:
    bool isValidPrice(const string& word) {
        if (word.length() <= 1 || word[0] != '$') {
            return false;
        }
        
        for (int i = 1; i < word.length(); i++) {
            if (!isdigit(word[i])) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split()
        result = []
        
        for word in words:
            if self.is_valid_price(word):
                price = int(word[1:])
                discounted_price = price * (100 - discount) / 100
                result.append(f"${discounted_price:.2f}")
            else:
                result.append(word)
        
        return " ".join(result)
    
    def is_valid_price(self, word: str) -> bool:
        if len(word) <= 1 or word[0] != '$':
            return False
        
        return word[1:].isdigit()

public class Solution {
    public string DiscountPrices(string sentence, int discount) {
        string[] words = sentence.Split(' ');
        
        for (int i = 0; i < words.Length; i++) {
            if (IsValidPrice(words[i])) {
                long price = long.Parse(words[i].Substring(1));
                double discountedPrice = price * (100 - discount) / 100.0;
                words[i] = $"${discountedPrice:F2}";
            }
        }
        
        return string.Join(" ", words);
    }
    
    private bool IsValidPrice(string word) {
        if (word.Length <= 1 || word[0] != '$') {
            return false;
        }
        
        for (int i = 1; i < word.Length; i++) {
            if (!char.IsDigit(word[i])) {
                return false;
            }
        }
        
        return true;
    }
}

var discountPrices = function(sentence, discount) {
    const words = sentence.split(' ');
    
    for (let i = 0; i < words.length; i++) {
        if (isValidPrice(words[i])) {
            const price = parseInt(words[i].substring(1));
            const discountedPrice = price * (100 - discount) / 100;
            words[i] = `$${discountedPrice.toFixed(2)}`;
        }
    }
    
    return words.join(' ');
};

function isValidPrice(word) {
    if (word.length <= 1 || word[0] !== '$') {
        return false;
    }
    
    for (let i = 1; i < word.length; i++) {
        if (!/\d/.test(word[i])) {
            return false;
        }
    }
    
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 为句子长度。需要遍历句子中的每个字符来分割和验证单词
空间复杂度O(n)，用于存储分割后的单词数组和结果字符串

相关题目