[Swift]LeetCode983. 最低票价 | Minimum Cost For Tickets

25-03-05 13

对于[Swift]LeetCode983.最低票价|MinimumCostForTickets感兴趣的读者，本文将提供您所需要的所有信息，并且为您提供关于983.MinimumCostForTicke

对于[Swift]LeetCode983. 最低票价 | Minimum Cost For Tickets感兴趣的读者，本文将提供您所需要的所有信息，并且为您提供关于983. Minimum Cost For Tickets、LeetCode - Find minimum time to finish jobs in constraints、LeetCode 1167. Minimum Cost to Connect Sticks、LeetCode 712. Minimum ASCII Delete Sum for Two Strings的宝贵知识。

本文目录一览：

[Swift]LeetCode983. 最低票价 | Minimum Cost For Tickets
983. Minimum Cost For Tickets
LeetCode - Find minimum time to finish jobs in constraints
LeetCode 1167. Minimum Cost to Connect Sticks
LeetCode 712. Minimum ASCII Delete Sum for Two Strings

[Swift]LeetCode983. 最低票价 | Minimum Cost For Tickets

原文地址：https://www.cnblogs.com/strengthen/p/10326127.html

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

124ms

 1 class Solution {
 2     func mincostTickets(_ days: [Int], _ costs: [Int]) -> Int {
 3         var n:Int = days.count
 4         var dp:[Int] = [Int](repeating:Int.max / 2,count:n+1)
 5         dp[0] = 0
 6         for i in 1...n
 7         {
 8             dp[i] = dp[i-1] + costs[0]
 9             for j in (0...(i - 1)).reversed()
10             {
11                 if days[i-1] - days[j] + 1 <= 7
12                 {
13                     dp[i] = min(dp[i], dp[j] + costs[1])
14                 }
15                 if days[i-1] - days[j] + 1 <= 30
16                 {
17                     dp[i] = min(dp[i], dp[j] + costs[2])
18                 }
19             }
20         }
21         return dp[n]
22     }
23 }

983. Minimum Cost For Tickets

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

难度：medium

题目：
某国流行火车旅行，可以提前一年制订火车旅行计划。要出行的日子以数组的形式给出。出行的日子为1到365之间的整数。

火车票以3种形式出售：
1天通行票
7天通行票
30天通行票
通行票允许多天持续旅行。例如，如果在第2天购得7天通行票，那么在接下来的7天，第3天，4 天， 5 天， 6 天，7 天， 8天持续旅行。

返回所有旅行天数所用的最小的旅行花费。

思路：
动态规划
问题可以拆解，设当天为n, 则
daysCost(n) = costs(n) + Math.min(daysCost(n - 1), daysCost(n - 7), daysCost(n - 30)) (n为计划旅行日)
daysCost(n) = daysCost(n - 1) (n为非计划旅行日）

Runtime: 4 ms, faster than 100.00% of Java online submissions for Minimum Cost For Tickets.

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] dcs = new int [366];
        for (int i = 0; i < n; i++) {
            dcs[days[i]] = 1;
        }

        for (int i = 1; i < 366; i++) {
            if (0 == dcs[i]) {
                dcs[i] = dcs[i - 1];
            } else {
                dcs[i] = Math.min(costs[0] + dcs[i - 1], 
                                  Math.min(costs[1] + dcs[Math.max(0, i - 7)],
                                           costs[2] + dcs[Math.max(0, i - 30)]));
            }
        }
        
        return dcs[days[n - 1]];
    }
}

LeetCode - Find minimum time to finish jobs in constraints

非常值得看的一题啦！和 MIT Quiz 中的那个 network flow 题（Maze Marathonor，在 Algorithm - Network Flow 那篇博客里）过程很相似，过程都是：

1. 算出个最长的可能时间 maxTime。

2. 设计个 boolean isPossible（k）的函数，输入 k 是个时间值，意思是，这个函数用来检测 problem 可不可以在时间 k 内完成。

3. 在 [0, maxTime] 内进行 binary search，在 BS 的过程中每次都对 mid 进行 isPossible（mid），直到最后找到最小的可能时间。

Find minimum time to finish all jobs with given constraints

4.3

Given an array of jobs with different time requirements. There are K identical assignees available and we are also given how much time an assignee takes to do one unit of job. Find the minimum time to finish all jobs with following constraints.

An assignee can be assigned only contiguous jobs. For example, an assignee cannot be assigned jobs 1 and 3, but not 2.
Two assignees cannot share (or co-assigned) a job, i.e., a job cannot be partially assigned to one assignee and partially to other

// C++ program to find minimum time to finish all jobs with
// given number of assignees
#include<bits/stdc++.h>
using namespace std;
 
// Utility function to get maximum element in job[0..n-1]
int getMax(int arr[], int n)
{
   int result = arr[0];
   for (int i=1; i<n; i++)
      if (arr[i] > result)
         result = arr[i];
    return result;
}
 
// Returns true if it is possible to finish jobs[] within
// given time ''time''
bool isPossible(int time, int K, int job[], int n)
{
    // cnt is count of current assignees required for jobs
    int cnt = 1;
 
    int curr_time = 0; //  time assigned to current assignee
 
    for (int i = 0; i < n;)
    {
        // If time assigned to current assignee exceeds max,
        // increment count of assignees.
        if (curr_time + job[i] > time) {
            curr_time = 0;
            cnt++;
        }
        else { // Else add time of job to current time and move
               // to next job.
            curr_time += job[i];
            i++;
        }
    }
 
    // Returns true if count is smaller than k
    return (cnt <= K);
}
 
// Returns minimum time required to finish given array of jobs
// k --> number of assignees
// T --> Time required by every assignee to finish 1 unit
// m --> Number of jobs
int findMinTime(int K, int T, int job[], int n)
{
    // Set start and end for binary search
    // end provides an upper limit on time
    int end = 0, start = 0;
    for (int i = 0; i < n; ++i)
        end += job[i];
 
    int ans = end; // Initialize answer
 
    // Find the job that takes maximum time
    int job_max = getMax(job, n);
 
    // Do binary search for minimum feasible time
    while (start <= end)
    {
        int mid = (start + end) / 2;
 
        // If it is possible to finish jobs in mid time
        if (mid >= job_max && isPossible(mid, K, job, n))
        {
            ans = min(ans, mid);  // Update answer
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
 
    return (ans * T);
}
 
// Driver program
int main()
{
    int job[] =  {10, 7, 8, 12, 6, 8};
    int n = sizeof(job)/sizeof(job[0]);
    int k = 4, T = 5;
    cout << findMinTime(k, T, job, n) << endl;
    return 0;
}

LeetCode 1167. Minimum Cost to Connect Sticks

原题链接在这里：https://leetcode.com/problems/minimum-cost-to-connect-sticks/

题目：

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Constraints:

1 <= sticks.length <= 10^4
1 <= sticks[i] <= 10^4

题解：

Find the routine that add the two smallest first, then largest repeated the least times.

Use min heap to get two 2 smallest values, merge them and add merged back to min heap unitl there is only one stick in min heap.

Time Complexity: O(nlogn). n = sticks.length.

Space: O(n).

AC Java:

 1 class Solution {
 2     public int connectSticks(int[] sticks) {
 3         if(sticks == null || sticks.length < 2){
 4             return 0;
 5         }
 6         
 7         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 8         for(int num : sticks){
 9             minHeap.add(num);
10         }
11         
12         int res = 0;
13         while(minHeap.size() > 1){
14             int merge = minHeap.poll() + minHeap.poll();
15             res += merge;
16             minHeap.add(merge);
17         }
18         
19         return res;
20     }
21 }

LeetCode 712. Minimum ASCII Delete Sum for Two Strings

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

This is clearly a DP problem.

dp[i][j] is the cost for s1.substr(0,i) and s2.substr(0, j). Note s1[i], s2[j] not included in the substring.

Base case: dp[0][0] = 0
target: dp[m][n]

if s1[i-1] = s2[j-1]   // no deletion
    dp[i][j] = dp[i-1][j-1];
else   // delete either s1[i-1] or s2[j-1]
    dp[i][j] = min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);

We can use a 2D vector, or an optimized O(n) extra space. See below. The run time is O(mn).

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1]+s2[j-1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0]+s1[i-1];
            for (int j = 1; j <= n; j++) {
                if (s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else 
                    dp[i][j] = min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
            }
        }
        return dp[m][n];
    }
};

Optimized O(n) extra space

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<int> dp(n+1, 0);
        for (int j = 1; j <= n; j++)
            dp[j] = dp[j-1]+s2[j-1];
        for (int i = 1; i <= m; i++) {
            int t1 = dp[0];
            dp[0] += s1[i-1];
            for (int j = 1; j <= n; j++) {
                int t2 = dp[j];
                dp[j] = s1[i-1] == s2[j-1]? t1:min(dp[j]+s1[i-1], dp[j-1]+s2[j-1]);
                t1 = t2;
            }
        }
        return dp[n];
    }
};

关于[Swift]LeetCode983. 最低票价 | Minimum Cost For Tickets的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于983. Minimum Cost For Tickets、LeetCode - Find minimum time to finish jobs in constraints、LeetCode 1167. Minimum Cost to Connect Sticks、LeetCode 712. Minimum ASCII Delete Sum for Two Strings等相关内容，可以在本站寻找。

本文标签：