朱酱酱的学习博客

计组-05-数据的表示(浮点数)

前言

• 定点数的局限性

  • 在位数有限的情况下，无法增加数的表示范围

• 浮点数

  • 在位数有限的情况下，既扩大了数的表示范围，又保持了数的有效精度

• 本章节基本要点

1. 浮点数的表示形式

Leetcode-027-移除元素

题目描述

• 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
• 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
• 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

1
2
3
4
5
6
7
8
9
10
11

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。


示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

方法一 ： 双指针

• 由于题目要求删除数组中等于val 的元素，因此输出数组的长度一定小于等于输入数组的长度，可以把输出的数组直接写在输入数组上。可以使用双指针：右指针fast 指向当前将要处理的元素，左指针slow指向下一个将要赋值的位置。
  • 如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
  • 如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。
• 整个过程保持不变的性质是：区间[0,slow) 中的元素都不等于 val。当左右指针遍历完输入数组以后，slow的值就是输出数组的长度。
• 这样的算法在最坏情况下（输入数组中没有元素等于 val），左右指针各遍历了数组一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int removeElement(int[] nums, int val) {
        // 1. 变量初始化及特判
        int n = nums.length;
        int slow = 0;                                   // 慢指针
        int fast = 0;                                   // 快指针

        // 2. 处理逻辑
        while(fast < n){
            if(val != nums[fast]){                      // 这种情况说明该快指针指向的元素需要被保留
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;                                     // 说明元素需要删除的，跳过该元素
        }
        // 3. 返回处理后的末尾元素
        return slow;
    }
}

复杂度分析

• 时间复杂度：O(n) ，遍历一遍数组
• 空间复杂度：O(1) ， 原地修改

Leetcode-220-存在重复元素 III

题目描述

• 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t，同时又满足 abs(i - j) <= k 。
• 如果存在则返回true，不存在返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

0 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^4
0 <= t <= 2^31 - 1

RabbitMQ-13-分布式事务

1. 前言

• 分布式事务指事务的操作位于不同的节点上，需要保证事务的AICD 特性。

• 例如在下单场景下，库存和订单如果不在同一个节点上，就涉及分布式事务。

• 在分布式系统中，要实现分布式事务，无外乎那几种解决方案。

RabbitMQ-12-集群搭建

1. 前言

• RabbitMQ这款消息队列中间件产品本身是基于Erlang编写，Erlang语言天生具备分布式特性（通过同步Erlang集群各节点的magic cookie来实现）。因此，RabbitMQ天然支持Clustering。这使得RabbitMQ本身不需要像ActiveMQ、Kafka那样通过ZooKeeper分别来实现HA方案和保存集群的元数据。
• 集群是保证可靠性的一种方式，同时可以通过水平扩展以达到增加消息吞吐量能力的目的。
• 在实际使用过程中多采取多机多实例部署方式，为了便于同学们练习搭建，有时候你不得不在一台机器上去搭建一个rabbitmq集群，本章主要针对单机多实例这种方式来进行开展。

注意：

• 主要参考官方文档：https://www.rabbitmq.com/clustering.html

RabbitMQ-11-存储机制

1. 存储机制

• 持久化消息
  • RabbitMQ的持久化队列分为：
    1：队列持久化
    2：消息持久化
    3：交换机持久化
• 非持久消息：是指当内存不够用的时候，会把消息和数据转移到磁盘，但是重启以后非持久化队列消息就丢失。

Leetcode-LCP002-分式化简

题目描述

• 有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。

输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。


示例 1：

输入：cont = [3, 2, 0, 2]
输出：[13, 4]
解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。

示例 2：

输入：cont = [0, 0, 3]
输出：[3, 1]
解释：如果答案是整数，令分母为1即可。

• 提示：

  • cont[i] >=0
    1 <= cont的长度 <= 10
cont最后一个元素不等于0

  • 答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。

RabbitMQ-10-死信队列

1. 死信产生的原因

• DLX，全称为Dead-Letter-Exchange , 可以称之为死信交换机，也有人称之为死信邮箱。

• 当消息在一个队列中变成死信(dead message)之后，它能被重新发送到另一个交换机中，这个交换机就是DLX ，绑定DLX的队列就称之为死信队列。

• 消息变成死信，可能是由于以下的原因：

  • 消息被拒绝
  • 消息过期
  • 队列达到最大长度

• DLX也是一个正常的交换机，和一般的交换机没有区别，它能在任何的队列上被指定，实际上就是设置某一个队列的属性。

  • 当这个队列中存在死信时，Rabbitmq就会自动地将这个消息重新发布到设置的DLX上去，进而被路由到另一个队列，即死信队列。
  • 要想使用死信队列，只需要在定义队列的时候设置队列参数 x-dead-letter-exchange 指定交换机即可。

RabbitMQ-09-过期时间TTL

1. TTL的概念

• 过期时间TTL表示可以对消息设置预期的时间，在这个时间内都可以被消费者接收获取；过了之后消息将自动被删除。

• RabbitMQ可以对消息和队列设置TTL。目前有两种方法可以设置。

  • 第一种方法是通过队列属性设置，队列中所有消息都有相同的过期时间。
  • 第二种方法是对消息进行单独设置，每条消息TTL可以不同。

• 如果上述两种方法同时使用，则消息的过期时间以两者之间TTL较小的那个数值为准。

• 消息在队列的生存时间一旦超过设置的TTL值，就称为dead message被投递到死信队列， 消费者将无法再收到该消息。

TTL的标识

Leetcode-080- 删除有序数组中的重复项 II

题目描述

• 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
• 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

1
2
3
4
5
6
7
8
9
10
11

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

方法一 ： 双指针

• 因为给定数组是有序的，所以相同元素必然连续。我们可以使用双指针解决本题，遍历数组检查每一个元素是否应该被保留，如果应该被保留，就将其移动到指定位置。

• 具体地，我们定义两个指针slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度

  • nums[fast] : 为第一个待检查的元素
  • nums[slow−1] 为上一个应该被保留的元素所移动到的指定位置。

• 本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2]是否和当前待检查元素nums[fast] 相同。

  • 若nums[slow - 2] == nums[fast] 则当前元素不应该被保留
  • 当前nums[slow−2]=nums[slow−1]=nums[fast]

最后slow即为数组的长度

特别地，

数组的前两个数必然可以被保留，因此对于长度不超过 2 的数组，我们无需进行任何处理，

对于长度超过 2 的数组，我们直接将双指针的初始值设为 2 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int removeDuplicates(int[] nums) {
        // 1. 特判及初始化 : 长度小于等于二直接满足条件
        int len = nums.length;
        if(len <= 2){
            return len;
        }

        // 2. 双指针逻辑 : 从下标为2开始检查
        int fast = 2;                               // fast代表待检查的元素
        int slow = 2;                               // slow代表已经检查完的长度
        while(fast < len){
            if(nums[slow - 2] != nums[fast]){        // 说明中间产生了重复元素
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        // 3. 返回值
        return slow + 1;
    }
}

复杂度分析

• 时间复杂度：O(n) ，遍历一遍数组
• 空间复杂度：O(1) ， 原地修改