# 【周赛】第153场-2019-9-8

1-Distance Between Bus Stops-easy。数组

2-Day of the Week-easy。数学

3-Maximum Subarray Sum with One Deletion-medium。数组、前缀和

4-Make Array Strictly Increasing-hard。数组、DP

## 1-Distance Between Bus Stops-easy。数组

A bus has `n` stops numbered from `0` to `n - 1` that form a circle. We know the distance between all pairs of neighboring stops where `distance[i]` is the distance between the stops number `i` and `(i + 1) % n`.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given `start` and `destination` stops.

Example 1: ` `Input: distance = [1,2,3,4], start = 0, destination = 1 Output: 1 Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.``

Example 2: ` `Input: distance = [1,2,3,4], start = 0, destination = 2 Output: 3 Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.``

` `class Solution:     def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:         if not distance:             return 0          clockwise = 0         counter_clkwise = 0         n = len(distance)         # key point 1，提前去掉一些Corner cases         if start%n == destination%n:             return 0         # key point 2，为了便于计算，默认start比destination小，把所有情况转化成这样         start, destination = min(start, destination), max(start, destination)         # 顺时针         for i in range(start, destination):             clockwise += distance[i]         # 逆时针         for i in range(start):             counter_clkwise += distance[i]         for i in range(destination, n):             counter_clkwise += distance[i]         return min(clockwise, counter_clkwise)       # 简洁一点的写法 class Solution:     def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:         if not distance:             return 0          clockwise = 0         n = len(distance)         if start%n == destination%n:             return 0         start, destination = min(start, destination), max(start, destination)         # 顺时针         for i in range(start, destination):             clockwise += distance[i]         # 逆时针         counter_clkwise = sum(distance) - clockwise         return min(clockwise, counter_clkwise)     ``

## 2-Day of the Week-easy。数学

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the `day``month` and `year` respectively.

Return the answer as one of the following values `{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}`.

Example 1:

` `Input: day = 31, month = 8, year = 2019 Output: "Saturday" ``

Example 2:

` `Input: day = 18, month = 7, year = 1999 Output: "Sunday" ``

Example 3:

` `Input: day = 15, month = 8, year = 1993 Output: "Sunday" ``

Constraints:

• The given dates are valid dates between the years `1971` and `2100`.

` `class Solution {     public String dayOfTheWeek(int d, int m, int y) {         if (m == 1 || m == 2) {             m += 12;             y--;         }         int iWeek = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;         String res = "";         switch (iWeek) {             case 0:                 res = "Monday";                 break;             case 1:                 res = "Tuesday";                 break;             case 2:                 res = "Wednesday";                 break;             case 3:                 res = "Thursday";                 break;             case 4:                 res = "Friday";                 break;             case 5:                 res = "Saturday";                 break;             case 6:                 res = "Sunday";                 break;         }         return res;     } }``

## 3-Maximum Subarray Sum with One Deletion-medium。数组、前缀和

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

` `Input: arr = [1,-2,0,3] Output: 4 Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.``

Example 2:

` `Input: arr = [1,-2,-2,3] Output: 3 Explanation: We just choose  and it's the maximum sum. ``

Example 3:

` `Input: arr = [-1,-1,-1,-1] Output: -1 Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.``

饶有趣味的一道题。看了别的oj上的solution才明白O(n)的解法的套路。这道题其实问的就是对于元素i，除开它，它左边的最大连续和和右边的连续和的和的最大值。所以是前缀和类型的问题。这里计算前缀和、后缀和的时候必须是包含i的

` `class Solution:     def maximumSum(self, arr: List[int]) -> int:         if len(arr) < 2:             return sum(arr)         n = len(arr)         forward = *n         backward = *n         # forward[i]表示截至（包括）i的最大连续和         cur_max = max_so_far = forward = arr         for i in range(1, n):             cur_max = max(cur_max + arr[i], arr[i])             max_so_far = max(max_so_far, cur_max)             forward[i] = cur_max                      # backward[i]表示i之后（包括）i的最大连续和         cur_max = max_so_far = backward[-1] = arr[-1]         for i in range(n-2, -1, -1):             cur_max = max(cur_max + arr[i], arr[i])             max_so_far = max(max_so_far, cur_max)             backward[i] = cur_max                  # 去掉arr[i]后的最大连续和         res = max_so_far         for i in range(1, n-1):             res = max(res, forward[i-1] + backward[i+1])         return res``

## 4-Make Array Strictly Increasing-hard。数组、DP

Given two integer arrays `arr1` and `arr2`, return the minimum number of operations (possibly zero) needed to make `arr1` strictly increasing.

In one operation, you can choose two indices `0 <= i < arr1.length` and `0 <= j < arr2.length` and do the assignment `arr1[i] = arr2[j]`.

If there is no way to make `arr1` strictly increasing, return `-1`.

Example 1:

` `Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] Output: 1 Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7]. ``

Example 2:

` `Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7]. ``

Example 3:

` `Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3] Output: -1 Explanation: You can't make arr1 strictly increasing.``

` `const int INF = 1e9 + 5;  class Solution { public:     int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {         sort(arr2.begin(), arr2.end());         arr2.resize(unique(arr2.begin(), arr2.end()) - arr2.begin());         int N = arr1.size(), M = arr2.size();         vector<vector<int>> dp(N + 1, vector<int>(M + 1, INF));         dp[M] = 0;          for (int i = 0; i < M; i++)             dp[i] = 1;          for (int i = 1; i < N; i++) {             if (arr1[i - 1] < arr1[i])                 dp[i + 1][M] = min(dp[i + 1][M], dp[i][M]);              for (int j = 0; j < M; j++) {                 if (arr1[i - 1] < arr2[j])                     dp[i + 1][j] = min(dp[i + 1][j], dp[i][M] + 1);                  if (arr2[j] < arr1[i])                     dp[i + 1][M] = min(dp[i + 1][M], dp[i][j]);             }              int minimum = INF;              for (int j = 0; j < M; j++) {                 dp[i + 1][j] = min(dp[i + 1][j], minimum + 1);                 minimum = min(minimum, dp[i][j]);             }         }          int answer = *min_element(dp[N].begin(), dp[N].end());         return answer < INF ? answer : -1;     } };``

• 点赞
• 收藏
• 分享

• 文章举报  ### 联系我们

#### 13687733322 