Medium

题目描述

一个通用微波炉支持的烹饪时间：

  • 至少 1 秒钟
  • 至多 99 分 99 秒

要设置烹饪时间，你最多可以按 4 个数字。微波炉会通过在前面补零将你按的数字标准化为 4 位数字。它将前两位数字解释为分钟，后两位数字解释为秒钟。然后将它们相加作为烹饪时间。例如：

  • 你按 9 5 4（三个数字）。它被标准化为 0954 并解释为 9 分 54 秒。
  • 你按 0 0 0 8（四个数字）。它被解释为 0 分 8 秒。
  • 你按 8 0 9 0。它被解释为 80 分 90 秒。
  • 你按 8 1 3 0。它被解释为 81 分 30 秒。

给你整数 startAt、moveCost、pushCost 和 targetSeconds。最初，你的手指在数字 startAt 上。将手指移动到任何特定数字上需要花费 moveCost 单位的疲劳度。按下手指下方的数字一次需要花费 pushCost 单位的疲劳度。

可能有多种方法来设置微波炉烹饪 targetSeconds 秒，但你希望用最小代价的方法。

返回设置 targetSeconds 秒烹饪时间的最小代价。

请记住，一分钟包含 60 秒。

示例 1：

输入：startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
输出：6
解释：有以下可能的设置烹饪时间的方法。
- 1000，解释为 10 分 0 秒。
  手指已经在数字 1 上，按 1（代价 1），移动到 0（代价 2），按 0（代价 1），按 0（代价 1），按 0（代价 1）。
  代价是：1 + 2 + 1 + 1 + 1 = 6。这是最小代价。
- 0960，解释为 9 分 60 秒。也是 600 秒。
  手指移动到 0（代价 2），按 0（代价 1），移动到 9（代价 2），按 9（代价 1），移动到 6（代价 2），按 6（代价 1），移动到 0（代价 2），按 0（代价 1）。
  代价是：2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12。
- 960，标准化为 0960 并解释为 9 分 60 秒。
  手指移动到 9（代价 2），按 9（代价 1），移动到 6（代价 2），按 6（代价 1），移动到 0（代价 2），按 0（代价 1）。
  代价是：2 + 1 + 2 + 1 + 2 + 1 = 9。

示例 2：

输入：startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
输出：6
解释：最优方法是按两个数字：76，解释为 76 秒。
手指移动到 7（代价 1），按 7（代价 2），移动到 6（代价 1），按 6（代价 2）。总代价是：1 + 2 + 1 + 2 = 6

提示：

  • 0 <= startAt <= 9
  • 1 <= moveCost, pushCost <= 10^5
  • 1 <= targetSeconds <= 6039

解题思路

解题思路

这道题的核心是理解微波炉的工作机制和找到最优的时间表示方法。

关键观察

  1. 微波炉接受最多4位数字，前两位表示分钟，后两位表示秒
  2. 对于给定的目标秒数，可能有多种表示方法，如600秒可以表示为10:00或9:60
  3. 需要考虑移动成本和按键成本

解法思路

由于分钟数的范围有限（0-99），我们可以枚举所有可能的分钟数：

  1. 枚举分钟数：对于每个可能的分钟数 mm（0到99），计算对应的秒数 ss = targetSeconds - mm * 60
  2. 验证合法性：检查计算出的秒数是否在有效范围内（0-99）
  3. 计算代价：对于每种合法的表示方法，计算按键序列的总成本
  4. 优化表示：对于同一个时间，可能有多种按键方式（如leading zeros），选择成本最小的

代价计算

对于给定的分钟和秒数组合，需要：

  1. 确定最优的按键序列（考虑前导零）
  2. 计算移动成本（从当前位置到目标数字）
  3. 计算按键成本

通过枚举所有可能的分钟数并计算对应的最小代价，最终返回全局最小值。

代码实现

class Solution {
public:
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int minCost = INT_MAX;
        
        // 枚举所有可能的分钟数
        for (int m = 0; m <= 99; m++) {
            int s = targetSeconds - m * 60;
            if (s < 0 || s > 99) continue;
            
            minCost = min(minCost, getCost(m, s, startAt, moveCost, pushCost));
        }
        
        return minCost;
    }
    
private:
    int getCost(int m, int s, int startAt, int moveCost, int pushCost) {
        vector<string> candidates;
        
        // 生成可能的按键序列
        string mmss = (m < 10 ? "0" : "") + to_string(m) + (s < 10 ? "0" : "") + to_string(s);
        candidates.push_back(mmss);
        
        // 去掉前导零的情况
        if (mmss[0] == '0') {
            candidates.push_back(mmss.substr(1));
            if (mmss[1] == '0') {
                candidates.push_back(mmss.substr(2));
                if (mmss[2] == '0') {
                    candidates.push_back(mmss.substr(3));
                }
            }
        }
        
        int minCost = INT_MAX;
        for (const string& seq : candidates) {
            if (seq.empty()) continue;
            int cost = 0;
            int current = startAt;
            
            for (char c : seq) {
                int digit = c - '0';
                if (digit != current) {
                    cost += moveCost;
                    current = digit;
                }
                cost += pushCost;
            }
            
            minCost = min(minCost, cost);
        }
        
        return minCost;
    }
};

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        def get_cost(m, s):
            # 生成所有可能的按键序列
            sequences = []
            
            # 4位数形式
            four_digit = f"{m:02d}{s:02d}"
            sequences.append(four_digit)
            
            # 去掉前导零的形式
            if four_digit[0] == '0':
                sequences.append(four_digit[1:])
                if four_digit[1] == '0':
                    sequences.append(four_digit[2:])
                    if four_digit[2] == '0':
                        sequences.append(four_digit[3:])
            
            min_cost = float('inf')
            for seq in sequences:
                if not seq:
                    continue
                    
                cost = 0
                current = startAt
                
                for digit_char in seq:
                    digit = int(digit_char)
                    if digit != current:
                        cost += moveCost
                        current = digit
                    cost += pushCost
                
                min_cost = min(min_cost, cost)
            
            return min_cost
        
        min_cost = float('inf')
        
        # 枚举所有可能的分钟数
        for m in range(100):
            s = targetSeconds - m * 60
            if s < 0 or s > 99:
                continue
                
            min_cost = min(min_cost, get_cost(m, s))
        
        return min_cost

public class Solution {
    public int MinCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int minCost = int.MaxValue;
        
        // 枚举所有可能的分钟数
        for (int m = 0; m <= 99; m++) {
            int s = targetSeconds - m * 60;
            if (s < 0 || s > 99) continue;
            
            minCost = Math.Min(minCost, GetCost(m, s, startAt, moveCost, pushCost));
        }
        
        return minCost;
    }
    
    private int GetCost(int m, int s, int startAt, int moveCost, int pushCost) {
        var candidates = new List<string>();
        
        // 生成可能的按键序列
        string mmss = m.ToString("D2") + s.ToString("D2");
        candidates.Add(mmss);
        
        // 去掉前导零的情况
        if (mmss[0] == '0') {
            candidates.Add(mmss.Substring(1));
            if (mmss[1] == '0') {
                candidates.Add(mmss.Substring(2));
                if (mmss[2] == '0') {
                    candidates.Add(mmss.Substring(3));
                }
            }
        }
        
        int minCost = int.MaxValue;
        foreach (string seq in candidates) {
            if (string.IsNullOrEmpty(seq)) continue;
            
            int cost = 0;
            int current = startAt;
            
            foreach (char c in seq) {
                int digit = c - '0';
                if (digit != current) {
                    cost += moveCost;
                    current = digit;
                }
                cost += pushCost;
            }
            
            minCost = Math.Min(minCost, cost);
        }
        
        return minCost;
    }
}

var minCostSetTime = function(startAt, moveCost, pushCost, targetSeconds) {
    function getCost(m, s) {
        // 生成所有可能的按键序列
        const sequences = [];
        
        // 4位数形式
        const fourDigit = m.toString().padStart(2, '0') + s.toString().padStart(2, '0');
        sequences.push(fourDigit);
        
        // 去掉前导零的形式
        if (fourDigit[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 虽然有枚举，但分钟数最多100个，每个序列最多4位数字，都是常数级别
空间复杂度O(1) - 只使用常数额外空间存储候选序列

相关题目