leetcode周赛 239

A:水题，直接枚举即可。

 1 class Solution {
 2 public:
 3     int getMinDistance(vector<int>& nums, int target, int start) {
 4         int res=0,seq=INT_MAX;
 5         for(int i=0;i<nums.size();i++){
 6             if(nums[i]==target&&abs(i-start)<seq){
 7                 seq=abs(i-start);
 8                 res=i;
 9             }
10         }
11         return abs(start-res);
12     } 
13 };

B:直接枚举每一段有多少个字母就好了时间（2e19），不过得注意有19位，所以得用ULL来存。

考试写的dfs版本：

 1 typedef unsigned long long LL;
 2 class Solution {
 3 public:
 4     bool res=false;
 5     LL get(LL l,LL r,string s){
 6         LL res=0;
 7         for(LL i=l;i<=r;i++){
 8             res=res*10+s[i]-'0';
 9         }
10         return res;
11     }
12     void dfs(LL now,LL pre,string& s,LL cnt){
13         if(now>=s.size()&&cnt>=2){
14             res=true;
15             return ;
16         }
17         for(LL i=now;i<s.size();i++){
18             LL num=get(now,i,s);
19             if((now==0&&num<pre)||num==pre-1){
20                 dfs(i+1,num,s,cnt+1);
21             }
22         }
23 
24     }
25     bool splitString(string s) {
26         dfs(0,0x3f3f3f3f3f3f3f3f,s,0);
27         return res;
28     }
29 };

二进制枚举版本：

 1 typedef unsigned long long LL;
 2 class Solution {
 3 public:
 4     bool splitString(string s) {
 5         int n=s.size();
 6         for(int i=1;i < 1<<(n-1);i++){//i是四位，从1开始是至少有一个分割线
 7             unsigned long long x=s[0]-'0';
 8             unsigned long long pre=-1;//补码，全一
 9             bool flag=true;
10             for(int j=0;j<n-1;j++){
11                 if(i>>j&1){
12                     if(pre!=-1&&x!=pre-1){
13                         flag=false;
14                         break;
15                     }
16                     pre=x;
17                     x=s[j+1]-'0';
18                 }else{
19                     x=x*10+s[j+1]-'0';
20                 }
21             }
22             if(x!=pre-1) flag=false;
23             if(flag) return true;
24         }
25         return false;
26     }
27 };

C:考试的时候想的并不是很明白，复习的时候发现考察逆序对的问题，考试的时候阴差阳错的用冒泡的思想解决了。

考试的时候的代码：

 1 class Solution {
 2 public:
 3     int getMinSwaps(string num, int k) {
 4         string tnum=num;
 5         for(int i=0;i<k;i++)
 6             next_permutation(tnum.begin(),tnum.end());
 7         int res=0;
 8         for(int i=0;i<num.size();i++){
 9             if(num[i]!=tnum[i]){
10                 int tar=i+1;
11                 while(num[i]!=tnum[tar]) tar++;
12                 for(int j=tar;j>i;j--){
13                     swap(tnum[tar],tnum[tar-1]);
14                     tar--;
15                     res++;
16                 }
17             }
18         }
19         return res;
20     }
21 };

补题时候的代码：

还存在一个问题就是如果存在两个相同的元素的话如何对应。

因为只能交换相邻元素，显而易见是第一种，第二种会多出2*s的交换次数。

 1 class Solution {
 2 public:
 3     int getMinSwaps(string a, int k) {
 4         string b=a;
 5         for(int i=0;i<k;i++)
 6             next_permutation(b.begin(),b.end());
 7         int n=b.size();
 8         vector<int> c(n);//存储a中的元素在b中的位置
 9         vector<bool> vis(n);
10         for(int i=0;i<n;i++){
11             char ca=a[i];
12             for(int j=0;j<n;j++){
13                 if(!vis[j]&&ca==b[j]){
14                     c[i]=j;
15                     vis[j]=true;
16                     break;
17                 }
18             }
19         }
20         //目的：把c变成正序
21         //因为n=1e3,冒泡排序即可，若n过大的话，得用归并
22         int res=0;
23         for(int i=0;i<n;i++){
24             for(int j=0;j<n-i-1;j++){
25                 if(c[j]>c[j+1]){
26                     swap(c[j],c[j+1]);
27                     res++;
28                 }
29             }
30         }
31         return res;
32     }
33 };

D：可以用并查集做，这是个经典模型（参考AcWing疯狂的馒头）

并查集初始化之后，我们将优先级高的先操作，本题优先级高的就是区间长度短的。

每次区间操作之后将一个区间删除（方法是让每一个都指向他的后一个元素），同时记录每一个元素对应的答案。

class Solution {
public:
    vector<int> p,w;
    vector<int> minInterval(vector<vector<int>>& segs, vector<int>& queries) {
        sort(segs.begin(),segs.end(),[](vector<int>&a,vector<int>&b){
            return a[1]-a[0]+1 < b[1]-b[0]+1;
        });
        const int n=1e7+10;
        p.resize(n+1);
        w.resize(n+1,-1);
        for(int i=0;i<=n;i++) p[i]=i;
        for(auto& s:segs){
            int l=s[0],r=s[1];
            int len=s[1]-s[0]+1;
            while(find(l)<=r){
                l=find(l);
                w[l]=len;
                p[l]=l+1;
            }
        }
        vector<int> res;
        for(auto& q:queries){
            res.push_back(w[q]);
        }
        return res;
    }
    int find(int x){
        if(p[x]!=x)
            p[x]=find(p[x]);
        return p[x];
    }
};

但是因为本题n为1e7，时间复杂度为nlogn，会超时

观察到区间数目和查询数目只有1e5，可以用离散化优化

 1 class Solution {
 2 public:
 3     vector<int> xs;
 4     vector<int> p,w;
 5     vector<int> minInterval(vector<vector<int>>& segs, vector<int>& queries) {
 6         for(auto& s:segs) xs.push_back(s[0]),xs.push_back(s[1]);
 7         for(auto& q:queries) xs.push_back(q);
 8         sort(xs.begin(),xs.end());
 9         xs.erase(unique(xs.begin(),xs.end()),xs.end());
10         //以上为离散化
11         sort(segs.begin(),segs.end(),[](vector<int>&a,vector<int>&b){
12             return a[1]-a[0]+1 < b[1]-b[0]+1;
13         });
14         int n=xs.size();
15         p.resize(n+1);
16         w.resize(n+1,-1);
17         for(int i=0;i<=n;i++) p[i]=i;
18         for(auto& s:segs){
19             int l=get(s[0]),r=get(s[1]);
20             int len=s[1]-s[0]+1;
21             while(find(l)<=r){
22                 l=find(l);
23                 w[l]=len;
24                 p[l]=l+1;
25             }
26         }
27         vector<int> res;
28         for(auto& q:queries){
29             res.push_back(w[get(q)]);
30         }
31         return res;
32     }
33     int find(int x){
34         if(p[x]!=x)
35             p[x]=find(p[x]);
36         return p[x];
37     }
38     int get(int x){
39         return lower_bound(xs.begin(),xs.end(),x)-xs.begin();
40     }
41 };