Leetcode 第273场周赛题解
Leetcode 第273场周赛题解(C++版)
Problem A - 反转两次的数字
题意
问一个数反转两次是否等于原数
思路
只有最后有0和该数为0符合
代码
class Solution {
public:
bool isSameAfterReversals(int num) {
return (num%10||num==0);
}
};
Problem B - 执行所有后缀指令
题意
给定一个n*n网格图和一个起点、一个移动序列，问对于该序列的每一个后缀，能在网格范围内移动几步？
思路
我们注意到移动序列的长度m和图的大小n都是
[
1
,
500
]
[1,500]
[1,500]，那么直接对每个后缀暴力模拟即可。
代码
class Solution {
public:
int sol(int n, vector<int>& startPos, string s){
int x=startPos[0],y=startPos[1];
int m=s.size();
for(int i=0;i<m;i++){
if(s[i]=='L') y--;
if(s[i]=='R') y++;
if(s[i]=='U') x--;
if(s[i]=='D') x++;
if(x<0||y<0||x>=n||y>=n) return i;
}
return m;
}
vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
int m=s.size();
vector<int> ans;
vector<string> str(m);
for(int i=0;i<m;i++) str[i]=s[m-1-i]+(i?str[i-1]:"");
for(int i=m-1;i>=0;i--) ans.push_back(sol(n,startPos,str[i]));
return ans;
}
};
Problem C - 相同元素的间隔之和
题意
给定一个数组，对于每个元素，求该元素到数组中所有其它与他等值元素的距离之和。
思路
对于数组中的每个值，记录其所有下标的和、每个值出现的总次数；那么对于每个位置now，其答案ans[now]就是
a
n
s
[
n
o
w
]
=
∑
(
i
=
0
)
&
&
(
a
r
r
[
i
]
=
=
a
r
r
[
n
o
w
]
)
n
∣
i
−
n
o
w
∣
ans[now]=sum_{(i=0) && (arr[i]==arr[now])}^{n}{|i-now|}
ans[now]=(i=0)&&(arr[i]==arr[now])∑n∣i−now∣
显然，我们对其进行去绝对值的操作，可以将答案分为在now左侧和在now右侧两种情况，可以化简为：
a
n
s
[
n
o
w
]
=
(
当
前
值
已
计
算
数
量
(
左
侧
)
−
未
计
算
数
量
(
右
侧
)
)
∗
n
o
w
+
(
(
总
下
标
和
−
n
o
w
)
(
右
侧
)
−
已
计
算
的
下
标
和
(
左
侧
)
)
ans[now]=(当前值已计算数量(左侧)-未计算数量(右侧))*now\+((总下标和-now) (右侧)-已计算的下标和(左侧))
ans[now]=(当前值已计算数量(左侧)−未计算数量(右侧))∗now+((总下标和−now)(右侧)−已计算的下标和(左侧))
从化简后的式子我们可以看出：需要记录当前已经计算了多少个值为arr[now]的数以及arr[now]这个值已出现的下标总和，我们可以想到利用前缀和来记录这个值，即使用数组cnt2记录到当前位置arr[now]这个值出现了多少次，数组sum2记录到当前位置所有值与arr[now]相等的元素出现的下标之和，同时，使用数组sum记录当前值所有下标总和，cnt记录当前值总共出现多少次，用代码表述也就是：
a
n
s
[
n
o
w
]
=
(
c
n
t
2
[
a
r
r
[
n
o
w
]
]
−
(
c
n
t
[
a
r
r
[
n
o
w
]
]
−
1
−
c
n
t
2
[
a
r
r
[
n
o
w
]
]
)
)
∗
n
o
w
+
(
(
s
u
m
[
a
r
r
[
n
o
w
]
]
−
s
u
m
2
[
a
r
r
[
n
o
w
]
]
−
n
o
w
)
−
s
u
m
2
[
a
r
r
[
i
]
]
)
)
ans[now]= (cnt2[arr[now]]-(cnt[arr[now]]-1-cnt2[arr[now]]))*now\ +((sum[arr[now]]-sum2[arr[now]]-now)-sum2[arr[i]]))
ans[now]=(cnt2[arr[now]]−(cnt[arr[now]]−1−cnt2[arr[now]]))∗now+((sum[arr[now]]−sum2[arr[now]]−now)−sum2[arr[i]]))
代码
class Solution {
public:
vector<long long> getDistances(vector<int>& arr) {
long long sum[100005]={0},sum2[100005],cnt[100005],cnt2[100006];
vector<long long> ans;
int n=arr.size();
for(int i=0;i<n;i++){
sum[arr[i]]=0;//每个值的下标总和
sum2[arr[i]]=0;//当前已计算的“下标和”的前缀
cnt[arr[i]]=0;//每个值出现的次数
cnt2[arr[i]]=0;//每个值已计算的下标数量
}
for(int i=0;i<n;i++){
cnt[arr[i]]++;
sum[arr[i]]+=i;
}
for(int i=0;i<n;i++){
int m=cnt[arr[i]];
//cout<<cnt[arr[i]]<<' '<<(m-1-cnt[arr[i]])<<' '<<sum[arr[i]]-sum2[arr[i]]-i<<' '<<sum2[arr[i]]<<endl;
ans.push_back( (cnt2[arr[i]]/*左侧*/-(m-1-cnt2[arr[i]])/*右侧*/)*i+((sum[arr[i]]-sum2[arr[i]]-i)/*右侧*/-sum2[arr[i]]/*左侧*/));
sum2[arr[i]]+=i;
cnt2[arr[i]]++;
//cout<<i<<' '<<arr[i]<<' '<<ans[i]<<endl;
}
return ans;
}
};
Problem D - 还原原数组
题意
原有三个数组arr,lower,higher。
对每个满足
0
≤
i
<
n
0 le i < n
0≤i<n 的下标
i，lower[i] = arr[i] - k
对每个满足0
≤
i
<
n
0 le i < n
0≤i<n 的下标
i，higher[i] = arr[i] + k
以上k为正整数
现在将lower和higher混在一起打乱(称为nums数组)，让你复原arr数组(保证有答案)
1
≤
n
≤
1000
1 le n le 1000
1≤n≤1000
1
≤
n
u
m
s
[
i
]
≤
1
0
9
1 le nums[i] le 10^9
1≤nums[i]≤109
思路
最初，我想到在双重循环中枚举K，对于每个K，使用multiset存储和查询是否有满足条件的n个数对，找到一个删除一个，以此保证每个数仅会被扫到一次，此时的理论复杂度仍然是
O
(
n
3
)
O(n^3)
O(n3)。
但是我们注意到，由于保证有答案，那么一个arr的元素就对应了两个nums的元素，也就是说，我们要将nums中的元素两两配对，我们显然可以固定选取nums[0]，枚举与其配对的另一个元素，同时计算出
K
K
K，计算出
K
K
K后，反过来使用这个
K
K
K进行两两配对，这个过程也是
O
(
n
)
O(n)
O(n)的，于是最后我们能够在
O
(
n
2
)
O(n^2)
O(n2)的时间复杂度内解决该问题。
代码
class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
multiset<int> se;
for(auto i:nums) se.insert(i);
int n=nums.size();
for(int i=1;i<n;i++){
if((nums[0]+nums[i])%2==0){
int k=abs(nums[0]-nums[i])/2;
if(k<=0) continue;
vector<int> tmp;
multiset<int> s1=se;
while(!s1.empty()){
auto a=s1.begin();
auto b=s1.find(*a+2*k);
if(b!=s1.end()){
tmp.push_back(*a+k);
s1.erase(a);
s1.erase(b);
}
else break;
}
if(tmp.size()==n/2) return tmp;
}
}
vector<int> ans;//不会走到这一步
return ans;
}
};