欢迎
首页 标签 归档 友链 Page

AlgorithmClassfication4

2022-06-10

AlgorithmClassfication4

区间的前缀和，可以考虑前缀数组，查询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/06/10/AlgorithmClassfication4/

updated at 2022-10-15

Previous Post
Algorithm多次写的
Next Post
AlgorithmClassfication3