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

发表于 | 分类于

题目

给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

实现 NumArray 类：

  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val) 将 nums[index] 的值更新为 val
  • int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], …, nums[right]）

示例：

输入：
[“NumArray”, “sumRange”, “update”, “sumRange”]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

阅读全文 »

线段树

发表于 | 分类于

线段树

动态求数组的区间和

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/**
 * 线段树
 * arr[] = {1, 3, 5, 7, 9, 11}
 * tree[] = {36,9,27,4,5,16,11,1,3,0,0,7,9,0,0}
 *                   36 [0-5]
 *    [0-2]  9                  27[3-5]
 * [0-1] 4      5[2]       16[3-4]    11[5]
 *   1     3             7    9
 *  [0]    [1]          [3]   [4]
 */
public class segmentTree {

    private static void buildTree(int[] arr, int[] tree, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int leftNode = 2 * node + 1;
            int rightNode = 2 * node + 2;

            int mid = start + (end - start) / 2;
            buildTree(arr, tree, leftNode, start, mid);
            buildTree(arr, tree, rightNode, mid + 1, end);
            tree[node] = tree[leftNode] + tree[rightNode];
        }
    }

    // 将arr[]的idx下标改成val值
    private static void update(int[] arr, int[] tree, int node, int start, int end, int idx, int val) {
        if (start == end) {
            arr[idx] = val;
            tree[node] = val;
        } else {
            int leftNode = 2 * node + 1;
            int rightNode = 2 * node + 2;
            int mid = start + (end - start) / 2;
            if (idx >= start && idx <= mid) {
                update(arr, tree, leftNode, start, mid, idx, val);
            } else {
                update(arr, tree, rightNode, mid + 1, end, idx, val);
            }
            tree[node] = tree[leftNode] + tree[rightNode];
        }
    }

    // 求arr数组中下标left到right的和
    private static int query(int[] arr, int[] tree, int node, int start, int end, int left, int right) {
        if (left > end || right < start) {
            return 0;
        } else if (start >= left && end <= right) {
            return tree[node];
        } else if (left == right) {
            return tree[node];
        }
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        int mid = start + (end - start) / 2;
        int leftSum = query(arr, tree, leftNode, start, mid, left, right);
        int rightSum = query(arr, tree, rightNode, mid + 1, end, left, right);
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int[] tree = new int[1000];
        buildTree(arr, tree, 0, 0, arr.length - 1);
        for (int i = 0; i < 15; i++) {
            System.out.print(tree[i] + "  ");
        }
        System.out.println();

        int sum1 = query(arr, tree, 0, 0, arr.length - 1, 2, 5);
        System.out.println(sum1);

        update(arr, tree, 0, 0, arr.length - 1, 4, 6);
        for (int i = 0; i < 15; i++) {
            System.out.print(tree[i] + "  ");
        }
        System.out.println();
        int sum2 = query(arr, tree, 0, 0, arr.length - 1, 2, 5);
        System.out.println(sum2);
    }
}

巧妙的思想

发表于 | 更新于

redis之hash扩容的渐进式哈希

哈希表是一个很常用的数据结构，哈希冲突也是非常常见的。常见的解决哈希冲突的方法有开放地址法、链地址法等。redis的hash采用的就是链地址法，同java的hashmap一样。

关于扩容，redis也有一个负载因子，当redis不在进行BGSAVE或这ReWriteAOF时，负载因子超过1就进行扩容；当redis在进行BGSAVE或者ReWriteAOF时，负载因子为5。扩容后的表大小为当前的2倍。

redis是单线程的，为了避免哈希表过大导致扩容阻塞，redis采取渐进式哈希，将表的扩容分发到表的增删改查操作中，redis的dict结构维护两个哈希表，一个用来存放数据，另一个用来扩容。并且redis的哈希表结构dict维护一个rehashidx，记录当前表的哈希位置。

redis的hash的实现结构

redis之intset的整数类型升级

树

发表于 | 更新于 | 分类于

二叉树的遍历

前序遍历

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
    public void before_dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.println(node.val);
        before_dfs(node.left);
        before_dfs(node.right);
    }

// 非递归的方式。
    public void before(TreeNode node) {
        if (node == null) {
            return;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        while (node != null || !queue.isEmpty()) {
            while (node != null) {
                System.out.println(node.val);
                queue.addFirst(node);
                node = node.left;
            }

            if (!queue.isEmpty()) {
                node = queue.removeFirst();
                node = node.right;
            }
        }
    }
阅读全文 »

链表

发表于 | 分类于

链表的题目，主要有两大要点，其一是思路，其二是编码。

LeetCode206:反转一个单链表

维护三个指针，prev, current, next，从前往后，以此反转

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

LeetCode24:两两交换链表中的节点

思路1：维护三个指针，prev、next1、next2，以prev为遍历中心，操作prev、next1、next2、next3的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode next1 = prev.next;
        ListNode next2 = next1.next;
        ListNode next3 = next2.next;
        
        prev.next = next2;
        next1.next = next3;
        next2.next =next1;
        
        prev = next1;
    }
    return dummy.next;
}

思路2：递归反转，维护next1，next2两个指针

1
2
3
4
5
6
7
8
9
10
11
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode next1 = head.next;
    ListNode next2 = next1.next;
    next1.next = head;
    head.next = swapPairs(next2);
    return next1;
}
阅读全文 »

Tomcat源码导入IDEA

发表于 | 分类于

前不久，公司的项目正在从基于OSGI的karaf框架切换到tomcat平台，借此机会，想研究一下tomcat源码，对应用底层的运行机制进一步理解，提升自己的能力。

Tomcat源码下载

tomcat官网

点击左侧Download下面的最新版本 Tomcat 9,可以看到tomcat分为Binary Distributions与Source Code Distributions两种发行方式，这里选择Source Code Distributions源码发行版。

下载，解压。

jdk、maven安装以及本地环境变量的配置，网上很多。

准备完毕。

阅读全文 »

谈人生

发表于 | 分类于

什么是人生？ 这个话题，在我这二十几年中，我已经不止一次的思考过。

工作

18年7月，我结束了学生生涯，来到华为，工作的节奏太快，没有时间去发泄大学毕业的感伤，这让我想起了大一时候我对高中的感伤。我没时间去思考自己，没时间去思考以后的生活，麻木的匆忙的工作把我彻头彻尾的改造成一个机器，我体会到时间的飞快，体会到人生的短暂，工作眨眼半年了，真的是一眨眼的功夫。

阅读全文 »

网络技术与应用--数据交换方式

发表于

数据交换

网络的目标是实现网络上终端之间的数据通信，需要实现两个机制。一是建立连接在网络上的任何两个终端之间的数据传输通路的机制，二是控制数据沿着源终端至目的终端传输通路完成传输过程的机制。

信道即信号传输通道，发送端将数据转换成信号，信号经过信道传播到达接收端，接收端将信号还原成数据。

电路交换

由电路交换机按需在两个终端之间动态建立信道的过程称为电路交换过程，两个终端之间的信道建立方式称为电路交换方式。

为什么是按需动态建立信道呢？

如果采用两两互连的方式，信道固定，终端之间随时可以传输数据，并且终端可以同时与其他所有终端通信。但是如果终端之间存在双向信道，n个终端需要n*(n-1)个信道。
考虑在实际通信过程中，每一个终端同时与所有其他终端通信的可能性几乎没有，n个终端同时需要互相之间两两通信的可能性页几乎没有，所以采取通过设备互连终端，由设备按需建立终端之间的信道，这里的设备就是电路交换机！

阅读全文 »