方法一：模拟
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public long findTheArrayConcVal(int[] nums) {
int n = nums.length;
long res = 0;
for (int i = 0; i < n / 2; ++i) {
String s = String.valueOf(nums[i]) + String.valueOf(nums[n - i - 1]);
res += Long.parseLong(s);
}
res += n % 2 == 1 ? Long.parseLong(String.valueOf(nums[n / 2])) : 0;
return res;
}
}
|
方法一：二分查找
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 long countFairPairs(int[] nums, int lower, int upper) {
long res = 0;
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; ++i) {
int ceiling = ceiling(nums, lower - nums[i], i + 1);
int floor = floor(nums, upper - nums[i], i + 1);
res += floor - ceiling + 1;
}
return res;
}
private int floor(int[] nums, int x, int i) {
int l = i, r = nums.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (nums[mid] <= x)
l = mid + 1;
else
r = mid - 1;
}
return r;
}
private int ceiling(int[] nums, int x, int i) {
int l = i, r = nums.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (nums[mid] >= x)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
}
|
方法一：位运算预处理 s 中的所有数字
当x不存在map中或者当前子串长度小于之前存的子串长度，更新map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[][] substringXorQueries(String s, int[][] queries) {
int n = s.length(), m = queries.length;
Map<Integer, int[]> map = new HashMap<>();
for (int i = 0; i < n; ++i) {
int x = 0;
for (int j = i; j < Math.min(i + 30, n); ++j) {
x = x << 1 | (s.charAt(j) - '0');
if (!map.containsKey(x) || map.get(x)[1] - map.get(x)[0] > j - i)
map.put(x, new int[]{i, j});
}
}
int[][] res = new int[m][2];
int[] NOTFOUND = new int[]{-1, -1};
for (int i = 0; i < m; ++i) {
int val = queries[i][0] ^ queries[i][1];
res[i] = map.getOrDefault(val, NOTFOUND);
}
return res;
}
}
|