解法1：位运算
0 1 2 3 4 5 6
“” 0 1 00 01 10 11
找规律就完事了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
string encode(int num) {
int k=0;
int temp=1;
string res="";
while(num>=temp)
{
num-=temp;
temp=temp<<1;
k++;
}
char c;
while(k--)
{
c=(num&1)+'0';
res+=c;
num=num>>1;
}
reverse(res.begin(),res.end());
return res;
}
};
|
解法:map+set
将每个的父区域记录。
然后找region1，和region2的父区域，若两者相同直接返回，若不相同将找到的父区域记录，同时找父区域的父区域，直到找到，返回。
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
| class Solution {
public:
string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
int n=regions.size();
map<string,string> pre;
for(int i=0;i<n;i++)
{
string f=regions[i][0];
for(int j=1;j<regions[i].size();j++)
{
pre[regions[i][j]]=f;
}
}
set<string> temp;
temp.insert(region1);
temp.insert(region2);
while(pre[region1]!=pre[region2])
{
region1=pre[region1];
region2=pre[region2];
cout<<region1<<" "<<region2<<endl;
if(temp.find(region1)!=temp.end())
{
return region1;
}
if(temp.find(region2)!=temp.end())
{
cout<<"!";
return region2;
}
if(region1!="")
temp.insert(region1);
if(region2!="")
temp.insert(region2);
}
return pre[region1];
}
};
|
解法：并查集+DFS
注：题目被限制会员才能看了，没权限，没法提交，先用二哥的题解，有机会了写个c++版
from：小白二号
先把所有的近义词集合求出来。题目中 AA 是 BB 的近义词，如果 AA 是 BB 的近义词，AA 是 CC 的近义词，那么 AA，BB，CC 都是近义词，这一步如果数据量大需要用到并查集，数据量小，瞎搞搞咯
然后再dfs，把句子中每个词的近义词都拿出来计算一次。。。
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
| import java.util.*;
class Solution {
private void dfs(Map<String, Set<String>> map, String[] col, List<String> result, int index) {
if (index == col.length) {
result.add(String.join(" ", col));
return;
}
if (map.containsKey(col[index])) {
String s = col[index];
for (String sub: map.get(col[index])) {
col[index] = sub;
dfs(map, col, result, index + 1);
}
col[index] = s;
} else {
dfs(map, col, result, index + 1);
}
}
public List<String> generateSentences(List<List<String>> synonyms, String text) {
Map<String, Set<String>> map = new HashMap<>();
for (List<String> synonym: synonyms) {
Set<String> s1 = map.getOrDefault(synonym.get(0), new HashSet<>());
Set<String> s2 = map.getOrDefault(synonym.get(1), new HashSet<>());
if (s1 == s2) {
continue;
}
HashSet<String> ret = new HashSet<>();
ret.addAll(s1);
ret.addAll(s2);
ret.add(synonym.get(0));
ret.add(synonym.get(1));
for (String sub: ret) {
map.put(sub, ret);
}
}
String[] col = text.split(" ");
List<String> result = new ArrayList<>();
dfs(map, col, result, 0);
Collections.sort(result);
return result;
}
}
|
作者：小白二号
链接：https://leetcode-cn.com/circle/discuss/4bcTK1/view/j97Wxb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法：卡特兰数
卡特兰数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int numberOfWays(int num_people) {
vector<long long> h(1010,0);
h[0]=1;h[1]=1;
int mod=pow(10,9)+7;
for(int i=2;i<=500;i++)
{
int res=0;
for(int j=0;j<i;j++)
{
res+=h[j]*h[i-j-1]%mod;
res%=mod;
}
h[i]=res;
}
return h[num_people/2];
}
};
|