153th Weekly Contest

标签 ： Leetcode Weekly Contest

5181.公交站间的距离

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

示例 1：

image_1dk7j3dto1qpbgm0rpi1j26joo9.png-21.1kB

输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。

示例 2：

image_1dk7j4fn5o5dkqu187ssd57pgm.png-22.8kB

输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。

示例 3：

image_1dk7j5fdi18la1kgg5ge11uf1uo213.png-21.5kB

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

提示：

  • 1 <= n <= 10^4
  • distance.length == n
  • 0 <= start, destination < n
  • 0 <= distance[i] <= 10^4

Solutions:
Answer 1:

// CopyRight By liouzhou_101
class Solution {
public:
    int distanceBetweenBusStops(vector<int>& d, int start, int destination) {
        int sum = 0;
        int n = d.size();
        for (int i = 0; i < n; ++ i) sum += d[i];
        int ret = 0;
        for (int i = start; i != destination; i = (i+1)%n) ret += d[i];
        return min(ret, sum-ret);
    }
};

Answer 2:

// CopyRight By darrenhp
class Solution {
public:
  int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    vector<int> P(1);
    partial_sum(distance.begin(), distance.end(), back_inserter(P));
    if (start > destination) swap(start, destination);
    int k = P[destination] - P[start];
    return min(P.back() - k, k);
  }
};

Answer 3:

// CopyRight By wnjxyk
class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int n=distance.size(), sum=0, forw=0;
        
        for (int i=0; i<n; i++) sum+=distance[i];
        
        while(start!=destination){
            forw+=distance[start];
            start=(start+1)%n;
        }
        
        return min(sum-forw, forw);
    }
};

Answer 4:

// CopyRight By ghost-37
class Solution(object):
    def distanceBetweenBusStops(self, distance, start, destination):
        if start > destination:
            start,destination = destination,start
        sum_d = sum(distance)
        cur_sum = 0
        for i in range(start,destination):
            cur_sum += distance[i]
        return min(cur_sum,sum_d-cur_sum)

5183. 一周中的第几天

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

示例 2：

输入：day = 18, month = 7, year = 1999
输出："Sunday"

示例 3：

输入：day = 15, month = 8, year = 1993
输出："Sunday"

提示：

  • 给出的日期一定是在 1971 到 2100 年之间的有效日期。
    Answer 1:

    class Solution:
  def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
      import time
      import datetime

      #str 转 datetime
      string = str(year) + '-' + str(month) + '-' + str(day)
      date_time = datetime.datetime.strptime(string,'%Y-%m-%d')

      from datetime import datetime

      dayOfWeek = date_time.isoweekday() ###返回数字1-7代表周一到周日

      dict = {1:"Monday", 2: "Tuesday", 3: "Wednesday", 4: "Thursday", 5: "Friday", 6: "Saturday", 7: "Sunday"}
      return dict[dayOfWeek]

    Answer 2:

    // CopyRight By darrenhp
class Solution {
public:
bool isLeap(int y) {
  return y % 400 == 0 || (y % 100 != 0 && y % 4 == 0);
}

string dayOfTheWeek(int day, int month, int year) {
  vector<int> md = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  vector<string> ds = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
  int tot = 3;
  for (int y = 1970; y < year; y++) {
    tot += isLeap(y)?366:365; 
  }
  for (int m = 1; m < month; m++) {
    if (isLeap(year) && m == 2) tot += 29;
    else tot += md[m];
  }
  tot += day;
  return ds[tot % 7];
}
};

    Answer 3:

    class Solution {
public:
  string ans[7]={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
  string dayOfTheWeek(int day, int month, int year) {
      if (month<3) { --year; month+=12; }
      int c=year/100, y=year%100;
      int w=(c/4-2*c+y+y/4+13*(month+1)/5+day-1)%7;
      return ans[(w+7)%7];
  }
};

    Answer 4:

    import java.util.*;
class Solution {
String b[]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
  public String dayOfTheWeek(int day, int month, int year) {
      Calendar time = Calendar.getInstance();
      time.set(year, month-1, day);
      int day1=time.get(Calendar.DAY_OF_WEEK);
      return b[day1-1];
  }
}

    Answer 5:

    from datetime import datetime
class Solution(object):
  def dayOfTheWeek(self, day, month, year):
      ml = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday","Sunday"]
      x = datetime(year,month,day)
      return ml[x.weekday()]

5182. 删除一次得到子数组最大和

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。

换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

请看示例：

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

提示：

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i] <= 10^4

Answer 1:

// CopyRight By jfantasy
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        const int n = arr.size();
        vector<int> f(n, 0), g(n, 0);
        for (int i = 0; i < n; ++i) {
            f[i] = arr[i];
            if (i > 0 && f[i - 1] > 0) f[i] += f[i - 1];
        }
        for (int i = n - 1; i >= 0; --i) {
            g[i] = arr[i];
            if (i < n - 1 && g[i + 1] > 0) g[i] += g[i + 1];
        }
        int ans = f[0];
        for (int i = 0; i < n; ++i) {
            ans = max(ans, max(f[i], g[i]));
            if (i + 1 < n) ans = max(ans, f[i] + g[i + 1]);
            if (i + 2 < n) ans = max(ans, f[i] + g[i + 2]);
        }
        return ans;
    }
};

Answer 2:

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int l = arr.size(), ans = -2e9;
        vector<int> f(l);
        for (int i = 0, sum = 0; i < l; ++i) {
            sum = max(sum + arr[i], arr[i]);
            f[i] = sum;
        }
        for (int i = l - 1, sum = 0; i >= 0; --i) {
            sum = max(sum + arr[i], arr[i]);
            ans = max(ans, max<int>(sum, i - 2 >= 0 ? sum + f[i - 2] : -2e9));
        }
        return ans;
    }
};

Answer 3:

class Solution(object):
    def maximumSum(self, arr):
        import numpy as np
        n = len(arr)
        if ( n == 1 ):
            return arr[0]
        if (max(arr) < 0):
            return max(arr)
        left = np.zeros((n,),dtype=np.int32)
        right = np.zeros((n,),dtype=np.int32)
        left[0] = max(0,arr[0])
        for i in range(1,n):
            left[i] = max(0,left[i-1]+arr[i])
        right[n-1] = max(0,arr[n-1])
        for i in range(n-2,-1,-1):
            right[i] = max(0,right[i+1]+arr[i])
        ans = 0
        for i in range(1,n-1):
            ans = max(ans,left[i-1]+right[i+1]+max(0,arr[i]))
        ans = max(ans,right[1]+max(0,arr[0]))
        ans = max(ans,left[n-2]+max(0,arr[n-1]))
        return ans

5184. 使数组严格递增

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

示例 2：

输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

示例 3：

输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。

提示：

  • 1 <= arr1.length, arr2.length <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

Answer 1:

// CopyRight By wnjxyk
int pool[2050];
int dp[2050][2050];
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n=arr1.size(), m=arr2.size();
        
        for (int i=0; i<m; i++) pool[i]=arr2[i];
        sort(pool, pool+m);
        m=unique(pool, pool+m)-pool;
        memset(dp, -1, sizeof(dp));
        dp[0][m]=0; for (int i=0; i<m; i++) dp[0][i]=1;
        for (int i=0; i<n-1; i++){
            for (int j=0; j<=m; j++){
                if (dp[i][j]==-1) continue;
                int now_v=(j==m?arr1[i]:pool[j]);
                // Don't
                if (arr1[i+1]>now_v){
                    if (dp[i+1][m]==-1 || dp[i+1][m]>dp[i][j]) dp[i+1][m]=dp[i][j];
                }
                // Modify
                int nxt_p=upper_bound(pool, pool+m, now_v)-pool;
                if (nxt_p<m){
                    // printf("Change(%d) %d->%d\n", i, arr1[i], pool[nxt_p]);
                    if (dp[i+1][nxt_p]==-1 || dp[i+1][nxt_p]>dp[i][j]+1) dp[i+1][nxt_p]=dp[i][j]+1;
                }
            }
        }
        int ans=-1;
        for (int i=0; i<=m; i++){
            if (dp[n-1][i]==-1) continue;
            if (ans==-1 || ans>dp[n-1][i]) ans=dp[n-1][i];
        }
        return ans;
    }
};

Answer 2:

# ghost-37
class Solution(object):
    def makeArrayIncreasing(self, arr1, arr2):
        import bisect
        n1 = len(arr1)
        n2 = len(arr2)
        arr2 = sorted(arr2)
        dp = [{} for i in range(n1)]
        if min(arr2) < arr1[0]:
            dp[0][min(arr2)] = 1
        dp[0][arr1[0]] = 0
        for i in range(1,n1):
            for k,v in dp[i-1].items():
                if arr1[i] > k:
                    if not arr1[i] in dp[i]:
                        dp[i][arr1[i]] = 10000
                    dp[i][arr1[i]] = min(dp[i][arr1[i]],v)
                nv = bisect.bisect_right(arr2,k)
                if nv == n2: continue
                nv = arr2[nv]
                if not nv in dp[i]:
                    dp[i][nv] = 10000
                dp[i][nv] = min(dp[i][nv],v+1)
        ans = 10000
        for k,v in dp[n1-1].items():
            ans = min(ans,v)
        if ans >= 10000: ans = -1
        return ans
Last modification：September 8, 2019
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏