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;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394186.html
標籤：其他