5197.最小绝对差
给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：
1
2
| 输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
|
示例 2：
1
2
| 输入：arr = [1,3,6,10,15]
输出：[[1,3]]
|
示例 3：
1
2
| 输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]
|
提示：
2 <= arr.length <= 10^5-10^6 <= arr[i] <= 10^6
解法1：暴力
先排序，然后找到差值最小的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
sort(arr.begin(),arr.end());
vector<vector<int>> res;
int n=arr.size();
int min=INT_MAX;
for(int i=1;i<n;i++)
{
int x=arr[i]-arr[i-1];
if(x>min)
{
continue;
}
else if(x<min)
{
res.clear();
min=x;
}
vector<int> temp;
temp.push_back(arr[i-1]);
temp.push_back(arr[i]);
res.push_back(temp);
}
return res;
}
};
|
5198.丑数 III
请你帮忙设计一个程序，用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数。
示例 1：
1
2
3
| 输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
|
示例 2：
1
2
3
| 输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
|
示例 3：
1
2
3
| 输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
|
示例 4：
1
2
| 输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984
|
提示：
1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18- 本题结果在
[1, 2 * 10^9] 的范围内
解法1：二分+容斥原理
1.采用二分，找到左边第一个个数符合n的数
2.求个数get_idx采用容斥原理mid/_a+mid/_b+mid/_c-mid/lcm(_a,_b)-mid/lcm(_a,_c)-mid/lcm(_b,_c)+mid/lcm(lcm(_a,_b),_c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
int _a;
int _b;
int _c;
public:
int nthUglyNumber(int n, int a, int b, int c) {
_a=a;
_b=b;
_c=c;
long long left=1,right=2*pow(10,9)+1;
while(left<right)
{
long long mid=left+(right-left)/2;
long long idx=get_idx(mid);
if(idx<n)
left=mid+1;
else
right=mid;
}
return left;
}
long long get_idx(long long mid)
{
return mid/_a+mid/_b+mid/_c-mid/lcm(_a,_b)-mid/lcm(_a,_c)-mid/lcm(_b,_c)+mid/lcm(lcm(_a,_b),_c);
}
long long lcm(long long a,long long b)
{
return (a/gcd(a,b))*b;
}
long long gcd(long long a,long long b)
{
if(a<b) return gcd(b,a);
long long r;
while(b)
{
r=a%b;
a=b;
b=r;
}
return a;
}
};
|
5199.交换字符串中的元素
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
1
2
3
4
5
| 输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
|
示例 2：
1
2
3
4
5
6
| 输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
|
示例 3：
1
2
3
4
5
6
| 输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
|
提示：
1 <= s.length <= 10^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengths 中只含有小写英文字母
解法1：并查集
注意采用n复杂度交换元素，采用n^2会超限
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| class Solution {
private:
vector<int> pre;
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n=pairs.size();
int len=s.size();
vector<int> _pre(len,-1);
for(int i=0;i<len;i++)
{
_pre[i]=i;
}
this->pre=_pre;
for(vector<int> pair:pairs)
{
int x,y;
x=find(pair[0]);
y=find(pair[1]);
if(x!=y)
{
pre[x]=y;
}
}
map<int,vector<char>> strs;
map<int,vector<int>> idxs;
unordered_set<int> unique_pre(pre.begin(),pre.end());
for(int i=0;i<len;i++)
{
int u_p=find(i);
idxs[u_p].push_back(i);
strs[u_p].push_back(s[i]);
}
for(map<int,vector<char>>::iterator ite=strs.begin();ite!=strs.end();ite++)
{
int k=ite->first;
sort(strs[k].begin(),strs[k].end());
}
for(map<int,vector<int>>::iterator ite=idxs.begin();ite!=idxs.end();ite++)
{
int k=ite->first;
for(int i=0;i<idxs[k].size();i++)
{
s[idxs[k][i]]=strs[k][i];
}
}
return s;
}
int find(int root)
{
int son=root,temp;
while(root!=pre[root])
root=pre[root];
while(son!=root)
{
temp=pre[son];
pre[son]=root;
son=temp;
}
return root;
}
};
|