AlgorithmClassfication4

Algorithm6

区间的前缀和,可以考虑前缀数组,查询O(1),但是更新会变为O(n)

树状数组是一种可以动态维护序列前缀和的数据结构(序列下标从 11 开始)

线段树,更新和查询都是O(logn)

前缀和

前缀和,就是用一个前缀和数组,将前面的数值,都求和求起来。

209. 长度最小的子数组

前缀和 + 二分法

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 {
// 使用前缀和 + 二分查找的方法
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int[] sums = new int[n];
sums[0] = nums[0];
for (int i=1; i<n; i++) {
sums[i] = nums[i] + sums[i-1];
}

int ans = Integer.MAX_VALUE;

for (int i = 0; i < n; i++) {
int right = i, left = 0, t = sums[i] - target;

// 若小于0,表示不存在大于等于的连续自数字和
if (t < 0) {
continue;
}

// 找出sums[mid]中第一个小于等于的
while (left <= right) {
int mid = (left + (right - left >> 1));

if (sums[mid] == t) {
left = right = mid;
break;
} else if (sums[mid] > t) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 此处的mid是的sum是不算在里面的
// 所以如果right为-1,代表刚好是0~right,因为如果0~right的不满足的,上面判断去掉了
ans = Math.min(ans, i - right);
}

return ans == Integer.MAX_VALUE ? 0 : ans;
}
}

剑指 Offer II 010. 和为 k 的子数组

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 subarraySum(int[] nums, int k) {
int n = nums.length;
int[] preSums = new int[n+1];
int ans = 0;

Map<Integer, Integer> map = new HashMap<>();

map.put(0, 1); // 就是如果从0开始到i都要,所以这个也要包括
for (int i=1; i<=n; i++) { // 注意,此处就是<=n了
preSums[i] = nums[i-1] + preSums[i-1]; // 这个前缀和,prenums[i]表示的是,从0~i-1的nums的和

// 注意,此处这个一定要写在这里,后面的再存,后面的会算上我当前的答案,但是我把所有的存了,再去找答案的话,会有重复。
// 就是说,要在[0, i]中,找sum数组中有多少个sums[i+1] - k的数。
ans += map.getOrDefault(preSums[i] - k, 0);
map.put(preSums[i], map.getOrDefault(preSums[i], 0) + 1);
}

return ans;
}
}

187. 重复的DNA序列

这个自己利用前缀和的思想,得到区间串的hash,还是没太懂理解。

TSGOwkMsEDChPA4

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
class Solution {
int N = (int)10e5 + 10;
int[] h = new int[N], p = new int[N];
// 131313试出来的,131不能通过全部案例
int P = 131313;
public List<String> findRepeatedDnaSequences(String s) {
int n = s.length();
List<String> ans = new ArrayList<>();
p[0] = 1; // 注意是p0

// 跟前缀和类似,从第1个开始,0不算
for (int i = 1; i <= n; i++) {
h[i] = h[i-1] * P + s.charAt(i-1);
p[i] = p[i-1] * P;
}

// 存储长度为10的字符串的hash和个数,而不是用长度为10的String作为key
// 此hash计算是O(1)的,而长度为10的String的hashcode计算为O(10)
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i + 10 - 1 <= n; i++) {
int j = i + 10 - 1;
// 下面这个hash的计算是为什么?最优右边那个不就输p10么
int hash = h[j] - h[i-1] * p[j-i+1];
int cnt = map.getOrDefault(hash, 0);
if (cnt == 1) {
ans.add(s.substring(i-1, j));
}
map.put(hash, cnt + 1);
}

return ans;
}
}

树状数组

树状数组 java_树状数组详解

树状数组与前缀和差分数组以及二维树状数组

1395. 统计作战单位数

树状数组

WofEDMm4TkYhPI9

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
class Solution {
// 因为rating的个数最多为10e5
int N = (int)10e5 + 10;
int[] tr = new int[N];

// 计算这个数二进制,从右到左第一个1的位置(从0开始),奇数得到的结果总为0
int lowbit(int x) {
return x & (-x);
}
// 给第x个数据更新v,就是加上v的意思
// 由于rating x后面的tr终会有它,所以从x往后
void update(int x, int v) {
for (int i = x; i < N; i += lowbit(i)) {
tr[i] += v;
}
}
// 查询前x个数据的和
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}

// 注意,这里面树状数组,存储的是元素的个数信息,以元素值为下标,个数为值
public int numTeams(int[] rating) {
int n = rating.length, ans = 0;

for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
// 遍历i与k之间的那个值有多少
int a = rating[i], c = rating[k];

if (a > c) {
// 需要找到大于c,小于a的,而且query(c)是包含c的,所以减去就是不包含了
ans += query(a - 1) - query(c);
} else {
ans += query(c - 1) - query(a);
}

// 这个要加在后面,品一下
update(c, 1); // c这个数增加1
}
for (int k = i + 1; k < n; k++) {
update(rating[k], -1);
}
}

return ans;
}
}

双树状数组优化-枚举终点

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
class Solution {
// 因为rating的个数最多为10e5
int N = (int)10e5 + 10;

// 计算这个数二进制,从右到左第一个1的位置(从0开始),奇数得到的结果总为0
int lowbit(int x) {
return x & (-x);
}
// 给第x个数据更新v,就是加上v的意思
// 由于rating x后面的tr终会有它,所以从x往后
void update(int[] tr, int x, int v) {
for (int i = x; i < N; i += lowbit(i)) {
tr[i] += v;
}
}
// 查询前x个数据的和,注意这个x在这里面是下标的意思
int query(int[] tr, int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}

// 注意,这里面树状数组,存储的是元素的个数信息,以元素值为下标,个数为值,稍有不同
public int numTeams(int[] rating) {
int n = rating.length, ans = 0;
int[] trLeft = new int[N], trRight = new int[N];

for (int num : rating) {
update(trRight, num, 1);
}
for (int i = 0; i < n; i++) {
// 注意,刚来的时候,当前数字不算在右边,所以剪掉
update(trRight, rating[i], -1);

// 左边小,右边大
ans += query(trLeft, rating[i] - 1) * (query(trRight, N - 1) - query(trRight, rating[i]));
// 左边大,右边小
ans += query(trRight, rating[i] - 1) * (query(trLeft, N - 1) - query(trLeft, rating[i]));
// 注意,刚来的时候,当前数字不算在左边边,所以不加,昨晚才加
update(trLeft, rating[i], 1);
}

return ans;
}
}

树状数组离散化

树状数组+离散化

Treeset排序 + 去重 map重新编号

做法,说白了,就是将值域的数字,去掉不存在的压缩。

首先用treeset将值域存在的都放进去,因为排好序了,然后一个个编号(map),这样肯定就缩小了呀。后面每一个数组就用该编号代替了。

327. 区间和的个数

只能说细节挺多的。

EqAvdbBR1zFSN7e

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
63
64
65
66
class Solution {
// 使用离散化树状数组,遍历到nums[j],(前面的都加入树状数组),寻找在sums[i]-upper~sums[i]-lower的个数
int N = 0; // 离散化之后才知道有多少
int[] tr; // 离散化之后才能创建

public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n+1];

// 前缀和
for (int i=1; i<=n; i++) {
sums[i] = sums[i-1] + nums[i-1];
}

// 离散化,1 首先将所有可能的值域放入Treeset中
Set<Long> set = new TreeSet<>();
set.add(0l); // 注意需要存0
for (long sum: sums) {
set.add(sum);
set.add(sum - upper);
set.add(sum - lower);
}
// 2 然后将这些离散的值域编号
Map<Long, Integer> map = new HashMap<>();
int index = 1; // 注意此处index要从1开始,从0的话不对,update循环都出不来
for (long sum: set) {
map.put(sum, index++);
}
// 3 根据离散化的大小,创建树状数组大小
N = index + 10;
tr = new int[N];

// 然后就是树状数组的问题了
int ans = 0;
update(map.get(0l), 1); // 注意,0一定要记得放啊,就是初始sums一个都没有的时候也需要放入,因为num[j]遍历的时候,可以是0~j。
for (int i=0; i<n; i++) {
// 后者也要包括,所以-1
ans += preSum(map.get(sums[i+1] - lower)) - preSum(map.get(sums[i+1] - upper) - 1);

// 注意,一定是这个update在后面
// 因为一开始进来,nums[i]跟别的比,sums的比
update(map.get(sums[i+1]), 1);
}

return ans;
}

// 树状数组
int lowbit(int x) {
return x & (-x);
}

void update(int x, int value) {
for (int i=x; i < N; i += lowbit(i)) {
tr[i] += value;
}
}

int preSum(int x) {
int ans = 0;
for (int i=x; i>0; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}
}

拟合:三元组ai>aj, ai=ak

【2022-08-20】网易秋招笔试四道编程题

由于a的值太大,所以考虑离散化

两个数组分别存放左边开始,右边开始的对应值的个数。如l[i]表示在0~当前下标中,i出现的个数。

然后用树状数组维护相同数字的个数的乘积。

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
63
64
65
66
67
// 未验证
import java.util.*;
import java.util.stream.Collectors;

public class SanYuanZu {
// 注意,要从1开始,0的话,+lowbit(0)上不去,死循环了
static int N = 1;
static int[] tr;
static int lowbit(int x) {
return x & (-x);
}

static void update(int x, int value) {
for (int i = x; i < N; i += lowbit(i)) {
tr[i] += value;
}
}

static int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(x)) {
ans += tr[i];
}
return ans;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

// 离散化,1 treeset排序去重
Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toCollection(() -> new TreeSet<>((a, b) -> b - a)));
// 2 map编号,这里没有用stream是因为,编号递增不能放入lambda表达式,因为他需要final的量
Map<Integer, Integer> map = new HashMap<>();
for (Integer num : set) {
map.put(num, N++);
}

// 3 然后根据编号,反映给原始数组nums,此处完整的lambda表达式为 num -> { return map.get(num);}
nums = Arrays.stream(nums).map(map::get).toArray();

int[] l = new int[N+10], r = new int[N + 10];
tr = new int[N + 10];
// 右边的,需要先全部放进去
for (int num : nums) {
r[num] += 1;
}

int ans = 0;
// 注意,这个num是离散化之后映射的结果了
for (int num : nums) {
// set是从大到小排序的
// 遍历到该num的时候,这个数是先不算的,需要找到他的左右两边比他大的,相等的
// query的时候,由于是严格大于,所以需要-1。
ans += query(num-1);

// 之前的去掉
update(num, -l[num] * r[num]);
l[num] += 1;
r[num] -= 1;
// 放入新的
update(num, l[num] * r[num]);
}

System.out.println(ans);
}
}

307. 区域和检索 - 数组可修改

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
class NumArray {
// 使用树状数组
// 前缀和更新区间需要O(n),不划算
// 由于值小,不需要离散化,而且个数也不多
int[] tr;
int[] nums;
int n;

int lowbit(int x) {
return x & (-x);
}

void add(int x, int value) {
// 不能从0开始,所以从1开始
x += 1;
// 注意,是lowbit(i),而不是lowbit(x)
for (int i = x; i <= n; i += lowbit(i)) {
tr[i] += value;
}
}

int query(int x) {
// 不能从0开始,所以从1开始
x += 1;
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}

public NumArray(int[] nums) {
this.nums = nums;
n = nums.length;
tr = new int[n + 10];

for (int i = 0; i < nums.length; i++) {
add(i, nums[i]);
}
}

public void update(int index, int val) {
add(index, val - nums[index]);
nums[index] = val;
}

public int sumRange(int left, int right) {
return query(right) - query(left-1);
}
}

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(index,val);
* int param_2 = obj.sumRange(left,right);
*/

线段树

线段树(java)

线段树详解

731. 我的日程安排表 II

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
// 这个是用红黑树做的
class MyCalendarTwo {
// 打算使用TreeMap,来实现

TreeMap<Integer, Integer> map;
public MyCalendarTwo() {
map = new TreeMap<>();
}

public boolean book(int start, int end) {
Integer pre = map.floorKey(start), next = map.ceilingKey(end);
// 注意,最好用包装类型接受,因为如果返回null,拆箱的话会nullpointexception的
if ((pre == null || map.get(pre) <= start) && (next == null || map.get(next) >= end)) {
return true;
}

return false;
}
}

/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/

// 线段树

732. 我的日程安排表 III

本来需要开辟一个数组存储连续的数据,但是连续的数组中有些不会存储到,那么考虑使用TreeMap

307. 区域和检索 - 数组可修改

区间的前缀和,可以考虑前缀数组,查询O(1),但是更新会变为O(n)

树状数组是一种可以动态维护序列前缀和的数据结构(序列下标从 11 开始)

线段树,更新和查询都是O(logn)

拓扑排序

802. 找到最终的安全状态

找到没有环的节点,首先将入与出翻转,那么入度为0的,原来出度是0,肯定不会出现环,然后用拓扑思想遍历下去。

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
class Solution {
/**
* 此处使用反向图 + 拓扑排序的方式
* 使用邻接表存储图
*/
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
List<Integer>[] revGraph = new ArrayList[n];
int[] cnts = new int[n];

for (int i = 0; i < n; i++) {
revGraph[i] = new ArrayList<>();
}

for (int u=0; u < n; u++) {
for (int v: graph[u]) {
// 反向,所以是i的入度+1
cnts[u] += 1;
revGraph[v].add(u);
}
}

// 所有入度为0的入队,他们是安全的
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (cnts[i] == 0) {
queue.offerLast(i);
}
}

while (!queue.isEmpty()) {
int v = queue.pollFirst();
// 每次从队列中拿出一个,遍历它指向的,它们的入度-1
// 如果是0了,安全无环,入队
for (int u: revGraph[v]) {
cnts[u] -= 1;
if (cnts[u] == 0) {
queue.offerLast(u);
}
}
}

// 返回cnt为0,拓扑一遍后,入度为0的点
return IntStream.range(0, cnts.length).filter(index -> cnts[index] == 0).boxed().collect(Collectors.toList());
}
}

Author: Jcwang

Permalink: http://example.com/2022/07/23/AlgorithmClassfication4/