leetcode周赛 239

本文主要是介绍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：待补充。。

这篇关于leetcode周赛 239的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！