“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

This is the third question in the Biweekly Contest 71. The difficulty Medium, which examines the ability to understand practical problems, is not very difficult if I think correctly. I only stopped here during the Contest, so I have no time to do the fourth question.

describe

A generic microwave supports cooking times for:

  • at least 1 second.
  • at most 99 minutes and 99 seconds.

To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example,

  • You push 9 5 4 (three digits). It is normalized as 0954 and interpreted as 9 minutes and 54 seconds.
  • You push 0 0 0 8 (four digits). It is interpreted as 0 minutes and 8 seconds.
  • You push 8 0 9 0. It is interpreted as 80 minutes and 90 seconds.
  • You push 8 1 3 0. It is interpreted as 81 minutes and 30 seconds.

You are given integers startAt, moveCost, pushCost, and targetSeconds. Initially, your finger is on the digit startAt. Moving the finger above any specific digit costs moveCost units of fatigue. Pushing the digit below the finger once costs pushCost units of fatigue.

There can be multiple ways to set the microwave to cook for targetSeconds seconds but you are interested in the way with the minimum cost.Return the minimum cost to set targetSeconds seconds of cooking time.Remember that one minute consists of 60 seconds.

Example 1:

Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600 Output: 6 Explanation: The following are the possible ways to set the cooking time. - 1 0 0 0, interpreted as 10 minutes and 0 seconds. The finger is already on digit 1, pushes 1 (with cost 1), moves to 0 (with cost 2), pushes 0 (with cost 1), pushes 0 (with cost 1), and pushes 0 (with cost 1). The cost is: 1 + 2 + 1 + 1 + 1 = 6. This is the minimum cost. - 0 9 6 0, interpreted as 9 minutes and 60 seconds. That is also 600 seconds. The finger moves to 0 (with cost 2), pushes 0 (with cost 1), moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1). The cost is: 2 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12. normalized as 0960 and interpreted as 9 minutes and 60 seconds. The finger moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1). The cost is: 2 + 1 + 2 + 1 + 2 + 1 = 9.Copy the code

Example 2:

Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
Output: 6
Explanation: The optimal way is to push two digits: 7 6, interpreted as 76 seconds.
The finger moves to 7 (with cost 1), pushes 7 (with cost 2), moves to 6 (with cost 1), and pushes 6 (with cost 2). The total cost is: 1 + 2 + 1 + 2 = 6
Note other possible ways are 0076, 076, 0116, and 116, but none of them produces the minimum cost.
Copy the code

Note:

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

parsing

The universal microwave oven supports a cooking time of at least 1 second and a maximum of 99 minutes and 99 seconds. To set the cooking time, press up to four digits, and the microwave automatically normalizes the set time to four digits by adding a zero. The first two digits represent minutes, and the last two digits represent seconds. Then add them up for the cooking time.

Integers startAt, moveCost, pushCost, and targetSeconds are also given. You start with your finger on the number startAt. Moving your finger over any particular number costs moveCost energy, and pressing the button once costs pushCost energy. There are several ways we can set the microwave to targetSeconds, but we want to return the minimum energy units.

This question is very close to the actual application, so it is more interesting, I don’t feel what is being tested, it may be examining the ability to understand the question.

Let’s first consider how to calculate the amount of energy expended, assuming that we have a time target, which is relatively simple. Let’s define a function cost, which takes s as a string of time, and initialize result to be 0, which represents the total amount of energy expended. When our hand starts at startAt, You don’t have to expend the energy to move your hand, otherwise you calculate the ability to move your hand, and then you add the ability to press a button. If the current number is equal to the previous number, then we save the ability to move the hand and calculate the ability to press the button directly. Otherwise, we add the energy to move the hand and the energy to press the button, and return result.

The above function to calculate the energy is relatively simple, but the trouble is that the microwave has a different representation of targetSeconds. Max M=targetSeconds // 60, traversing range(M, -1, -1), if targetSeconds -i * 60 < 100, the min + seconds is valid. We normalize them to the available modes and add them to the list NUMs, otherwise we just jump out of the loop and iterate through the various forms in NUMS to find the value that consumes the least energy.

answer

class Solution(object):
    def minCostSetTime(self, startAt, moveCost, pushCost, targetSeconds):
        """
        :type startAt: int
        :type moveCost: int
        :type pushCost: int
        :type targetSeconds: int
        :rtype: int
        """
        def cost(s):
            result = 0
            if startAt == int(s[0]):
                result += 0
            else:
                result += moveCost
            result += pushCost
            for i in range(1, len(s)):
                if s[i - 1] == s[i]:
                    result += pushCost
                else:
                    result += moveCost
                    result += pushCost
            return result

        M = targetSeconds // 60
        nums = []
        for i in range(M , -1, -1):
            if targetSeconds - i * 60 < 100:
                a = str(i)
                b = str(targetSeconds - i * 60)
                if b == '0':
                    r = a + '00'
                elif len(b) == 1:
                    r = a + '0' + b
                else:
                    r = a + b
                if len(r)<=4:
                    nums.append(r.lstrip('0'))
            else:
                break
        result = float('inf')

        for r in nums:
            result = min(result, cost(r))
        return result
		
Copy the code

The results

225/225 Test cases passed. Status: Accepted Runtime: 26 MS Memory Usage: 13.3 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation