3112、访问消失节点的最小时间

5181. 公交站间的距离 显示英文描述

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

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

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

case1：

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

提示：

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

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int mindis = 0;
        int sum  = 0;
        if (start == destination) {
            return 0;
        }
        for (int i = 0;i < distance.length;i++) {
            sum += distance[i];
        }
        if (start > destination) {
            start = start^destination;
            destination = start^destination;
            start = start^destination;
        }
        for (int i = start;i < destination;i++) {
            mindis += distance[i];
        }
        if (sum > mindis*2) {
            return mindis;
        } else {
            return sum - mindis;
        }
    }
}

• 全球第一的答案

class Solution {
  template <typename T>
  vector<T> dijkstra(int s,vector<vector<pair<int, T> > > & G){
    const T INF = numeric_limits<T>::max();
    using P = pair<T, int>;
    int n=G.size();
    vector<T> d(n,INF);
    vector<int> b(n,-1);
    priority_queue<P,vector<P>,greater<P> > q;
    d[s]=0;
    q.emplace(d[s],s);
    while(!q.empty()){
      P p=q.top();q.pop();
      int v=p.second;
      if(d[v]<p.first) continue;
      for(auto& e:G[v]){
        int u=e.first;
        T c=e.second;
        if(d[u]>d[v]+c){
          d[u]=d[v]+c;
          b[u]=v;
          q.emplace(d[u],u);
        }
      }
    }
    return d;
  }

  //INSERT ABOVE HERE
public:
  int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    int n=distance.size();
    using P = pair<int, int>;
    vector< vector<P> > G(n);
    for(int i=0;i<n;i++){
      int j=(i+1)%n;
      G[i].emplace_back(j,distance[i]);
      G[j].emplace_back(i,distance[i]);
    }
    return dijkstra(start,G)[destination];
  }
};

// 国内第一
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);
  }
};

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 年之间的有效日期。

// 
im
class Solution {
public:
    string dayOfTheWeek(int day, int month, int y) {
     if (month < 3) {
         y--;
         month += 12;
     }
     int w = (y + y / 4 - y / 100 + y / 400 + (13 * month + 8) / 5 + day) % 7;
     return S[w];
    }
};

class Solution {
public:
    int m[2][13] = {
        {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
        {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    };
    bool is_leap(int y) {
        return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
    }
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> A = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        // 2019/9/8 Sunday
        // int C = year / 100, Y = year % 100;
        // int ret = (day + (26 * month - 2) / 10 - 2 * C + Y + Y / 4 + C / 4) % 7;
        // return A[ret];
        int ret = 4;
        // 天数累加
        for (int i = 1971; i < year; ++i) {
            int k = is_leap(i);
            for (int j = 1; j <= 12; ++j) ret += m[k][j];
        }
        int k = is_leap(year);
        for (int i = 1; i < month; ++i) {
            ret += m[k][i];b
        }
        ret += day;
        ret %= 7;
        return A[ret];
    }
};

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];
  }
};

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

动态规划

我们定义f ( i ) 和 g ( i )，

• 其中 f( i ) 表示不删除元素的情况下最大子数组和（区间为[0，i]），
• g( i ) 代表删除元素的情况下的最大子数组和（区间为[0，i]）。

f(i) = Math.max(f(i-1)+arr[i],arr[i]) //要么是当前元素累加之前的和，要么是重新从当前元素开始
g(i) = Math.max(g(i-1)+arr[i],f(i-1)) 
//要么是加上当前元素，也就是维持之前删除某个元素的情形，即g[i-1]+arr[i]
//要么是删除当前这个元素，那么区间[0, i-1]就是不删除元素的情况，即f(i-1)+0（注意是f不是g！！）

问题在于初始化：

f(0)= arr[0] //因为必须要有元素，不能为 0 个元素

g(0) = 什么呢？

• 举个例子，假设我们要计算g(1)：

g(1) = Math.max(g(0)+arr[1],f(0))//题目提到至少保留一个元素，所以必须要选f(0)，即g(0)要足够小
// g(0) + arr[1] < arr[0]
// g(0) < arr[0] - arr[1]
// 因为 - 10^4 <= arr[i] <= 10^4，所以arr[0]-arr[1] >= -2 * 10^4，即g(0)取-20001即可

最后遍历一遍 f 数组和 g 数组找出最大值即可。

• 具体代码如下：

class Solution {
    public int maximumSum(int[] arr) {
        int len = arr.length;
        int[] f = new int[len];
        int[] g = new int[len];
        f[0] = arr[0];
        g[0] = -200001;
        for(int i=1;i<len;i++){
            f[i] = Math.max(f[i-1]+arr[i],arr[i]);//其实就是f(i-1)是否<0
            g[i] = Math.max(g[i-1]+arr[i],f[i-1]);
        }
        int res = Integer.MIN_VALUE; 
        for(int i=0;i<len;i++){
            res = Math.max(res,Math.max(f[i],g[i]));
        }
        return res;
    }
}

作者：xiaoxinganlinganim
链接：https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion/solution/bi-jiao-tong-su-yi-dong-de-dp-by-xiaoxinganlingani/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// class Main {
public:
  int maximumSum(vector<int>& arr) {
    int _max = *max_element(arr.begin(), arr.end());
    if (_max <= 0) return _max;
    int N = arr.size();
    int cur = 0;
    vector<int> L(N);
    for (int i = 0; i < arr.size(); i++) {
      cur += arr[i];
      if (cur < 0) cur = 0;
      L[i] = cur;
    }
    int _max2 = *max_element(L.begin(), L.end());
    cur = 0;
    vector<int> R(N);
    for (int i = arr.size() - 1; i >= 0; i--) {
      cur += arr[i];
      if (cur < 0) cur = 0;
      R[i] = cur;
    }
    int t = 0;
    for (int i = 0; i < arr.size(); i++) {
      int l = i - 1 >= 0? L[i - 1]: 0;
      int r = i + 1 <  arr.size()? R[i + 1]: 0;
      t = max(t, l+r);
    }
    return max(_max2, t);
  }
// };

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

class Solution {
  template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
  template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


  template<typename V>
  V compress(V v){
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    return v;
  }
  template<typename T>
  map<T, int> dict(const vector<T> &v){
    map<T, int> res;
    for(int i=0;i<(int)v.size();i++)
      res[v[i]]=i;
    return res;
  }
  map<char, int> dict(const string &v){
    return dict(vector<char>(v.begin(),v.end()));
  }

  //INSERT ABOVE HERE
public:
  int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    vector<int> as=arr1,bs=arr2;
    bs=compress(bs);

    int n=as.size(),m=bs.size();

    // dp[m] is for as[i]
    vector<int> dp(m+1,1);
    dp[m]=0;

    for(int i=1;i<n;i++){
      const int INF = 1e9;
      vector<int> nx(m+1,INF);

      for(int j=0;j+1<m;j++)
        chmin(nx[j+1],dp[j]+1);

      for(int j=0;j<m;j++)
        if(bs[j]<as[i]) chmin(nx[m],dp[j]);

      for(int j=0;j<m;j++)
        if(as[i-1]<bs[j]) chmin(nx[j],dp[m]+1);

      if(as[i-1]<as[i]) chmin(nx[m],dp[m]);
        
      swap(dp,nx);
    }

    int ans=*min_element(dp.begin(),dp.end());
    if(ans>n) ans=-1;
    return ans;
  }
};


// 
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        std::vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
        
        /*intial*/
        dp[0][0] = -1;
        sort(arr2.begin(),arr2.end());
        
        for(int i = 1; i <= n; ++i){
            for(int j = 0;j <= i; ++j){
                if(arr1[i-1] > dp[j][i-1]){
                    dp[j][i] = arr1[i-1];
                }
                
                if(j > 0){
                    auto it = upper_bound(arr2.begin(),arr2.end(),dp[j-1][i-1]);
                    if(it != arr2.end()){
                        dp[j][i] = min(dp[j][i],*it);
                    }
                }
                if( i == n && dp[j][i] != INT_MAX){
                    return j;
                }
            }
        }
        
        return -1;
    }
};

// 作者：mike-meng
// 链接：https://leetcode-cn.com/problems/make-array-strictly-increasing/solution/dp-on2-by-mike-meng/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
         //特殊情况处理
        if (arr1 == null || arr1.length == 0) return -1;
        // 只有一个元素
        if (arr1.length == 1) return 0;
        // 处理arr2，去重，排序
        TreeSet<Integer> ts = new TreeSet<>();
        if (arr2 != null) {
            for (int i = 0; i < arr2.length; i++) ts.add(arr2[i]);
        }
        // 局部解存储，初始化
        int[][] dp = new int[arr1.length + 1][arr1.length + 1];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][0] = Integer.MIN_VALUE;
        
        // 算法
        for (int j = 1; j < dp.length; j++) {
            for (int i = 0; i <= j; i++) {
                if (arr1[j - 1] > dp[i][j - 1]) {
                    dp[i][j] = arr1[j - 1];
                }
                // TreeSet 方法 higher，查找第一个大于目标元素的元素
                if (i > 0 && ts.higher(dp[i - 1][j - 1]) != null) {
                    dp[i][j] = Math.min(dp[i][j], ts.higher(dp[i - 1][j - 1]));
                }
                // 返回结果，最小的交换次数
                if (j == dp.length - 1 && dp[i][j] != Integer.MAX_VALUE) return i; 
            } 
        }
        return -1;
    }
}
// 作者：mike-meng
// 链接：https://leetcode-cn.com/problems/make-array-strictly-increasing/solution/dp-on2-by-mike-meng/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com