方法二：位运算
Integer.numberOfTrailingZeros(m)表示m的二进制串中，最低为1后面0的个数
举例
nums1 = [1， 3]， nums2 = [2, 3]
mask1 = 1010, mask2 = 1100
m = mask1 & mask2 = 1000
Integer.numberOfTrailingZeros(m) = 3
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int minNumber(int[] nums1, int[] nums2) {
int mask1 = 0, mask2 = 0;
for (int x : nums1) mask1 |= 1 << x;
for (int x : nums2) mask2 |= 1 << x;
int m = mask1 & mask2;
if (m > 0)
return Integer.numberOfTrailingZeros(m);
int x = Integer.numberOfTrailingZeros(mask1), y = Integer.numberOfTrailingZeros(mask2);
return Math.min(x * 10 + y, x + y * 10);
}
}
|
方法一：排序 + HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int minNumber(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int res = nums1[0] < nums2[0] ? nums1[0] * 10 + nums2[0] : nums2[0] * 10 + nums1[0];
Set<Integer> set = new HashSet<>();
for (int x : nums1)
set.add(x);
for (int x : nums2)
if (set.contains(x))
return x;
return res;
}
}
|
方法一：最大子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int maximumCostSubstring(String s, String chars, int[] vals) {
int[] map = new int[26];
for (int i = 0; i < 26; ++i)
map[i] = i + 1;
for (int i = 0; i < chars.length(); ++i) {
char ch = chars.charAt(i);
int val = vals[i];
map[ch - 'a'] = val;
}
int res = 0, sum = 0;
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
int val = map[ch - 'a'];
sum += val;
res = Math.max(res, sum);
if (sum < 0)
sum = 0;
}
return res;
}
}
|
方法一：【转换】中位数贪心+裴蜀定理（Python/Java/C++/Go）
不需要Visited数组
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
| class Solution {
public int findShortestCycle(int n, int[][] edges) {
List<Integer>[] g = new List[n];
Arrays.setAll(g, o -> new ArrayList<>());
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
g[from].add(to);
g[to].add(from);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i)
res = Math.min(res, bfs(i, n, g));
return res == Integer.MAX_VALUE ? -1 : res;
}
public int bfs(int i, int n, List<Integer>[] g) {
int res = Integer.MAX_VALUE;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, -1});
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[i] = 0;
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int node = arr[0], pre = arr[1];
for (int next : g[node]) {
if (dist[next] == -1) {
dist[next] = dist[node] + 1;
queue.offer(new int[]{next, node});
}
else if (next != pre)
res = Math.min(res, dist[next] + dist[node] + 1);
}
}
return res;
}
}
|
方法一：BFS
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
| class Solution {
public int findShortestCycle(int n, int[][] edges) {
List<Integer>[] g = new List[n];
Arrays.setAll(g, o -> new ArrayList<>());
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
g[from].add(to);
g[to].add(from);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, -1});
Set<Integer> visited= new HashSet<>();
int[] dist = new int[n];
dist[i] = 0;
visited.add(i);
while (!queue.isEmpty()) {
int size = queue.size();
for (int j = 0; j < size; ++j) {
int[] arr = queue.poll();
int node = arr[0], pre = arr[1];
for (int next : g[node]) {
if (next == pre)
continue;
if (visited.contains(next)) {
res = Math.min(res, dist[next] + dist[node] + 1);
break;
}
visited.add(next);
queue.offer(new int[]{next, node});
dist[next] = dist[node] + 1;
}
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
|