algorithm

前言参与度算法是用在计算多个节点之间的参与情况的算法，也就是说在多个已经确认的节点个数之间的一种算法。 说人话就是假设有10个节点，这10个节点都正常工作参与度就是100%，如果挂了一个节点，参与度就是：90%。是不是有点感觉了。 在分布式场景下，参与度是个重要的指标，尤其是各种分布式应用，那用的更是多。比如有一堆reids集群，挂了几个还可以工作，这就是一个参与度的阀值。在DPOS共识的区块链的场景下，这个值就可以起到一个参考指标的作用。 实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293package com.liukai.blockchain.labs;import java.util.Arrays;import java.util.HashMap;import java.ut ...

slot机制Slot 机制，大白话，就是分片机制。可以把时间或空间分成一个个槽，通过一定算法使用这些槽的机制。 有什么用？作用是可以把数据平均分存放到某个槽空间内，比如Hash环中使用的Hash Slot。再比如数组，可以再解为是一种槽机制。这是空间是的槽机制，在时间维度，可以把时间分片，每隔一段时间，就是一个时间槽位。比如：一分钟有60秒，每2秒划分一个槽位就有30个槽，那就可以执行30次；比如：一天有86400秒，每3秒划分一个槽位就有28800个槽。 这里实现一个简单的时间槽机制，分布式场景下，通过这个机制在，去中心化的场景下，让不同的机制按照一定时间槽机制进行运作。 实现要求必须保证是精准的3秒间隔，中间代码处理业务逻辑的时间必须也要计算在内。比如，执行业务逻辑使用100毫秒，那么到下一个3秒的间隔就是2900毫秒；如果，执行业务逻辑使用500毫秒，那么到下一个3秒的间隔就是2500毫秒；如果，执行业务逻辑使用2900毫秒，那么到下一个3秒的间隔就是100毫秒；保证完整的3秒，不多不少。 思路这样的话，就要记录计算所有时间： 标记当前开始时间 记录业务逻辑处理的时间 计算出 ...

相当于是使用 for 进行交换的一个小技巧的练习，后面会给出一些算法的小技巧，都是总结的一些算法的小技巧。给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例 输入: [0,1,0,3,12]输出: [1,3,12,0,0] 说明必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。 1234567891011121314151617public class Test { public static void main(String[] args) { Integer[] arr = {1, 3, 5, 0, 7, 0, 0, 0, 8, 9}; int j = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] != 0) { int temp = arr[j]; arr[j] = arr ...

整数反转给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。 示例 1： 12输入：x = 123输出：321 示例 2： 12输入：x = -123输出：-321 示例 3： 12输入：x = 120输出：21 示例 4： 12输入：x = 0输出：0 提示： -231 <= x <= 231 - 1 当所计算数字大于2^30 次方或等于2^31 次方但余下的数大于7或小于-2^30 次方或等于-2^31 次方但余下的数小于-8时，只要再计算一次就溢出。 解题方式1234567891011121314151617181920public static int reverse(int x) { int pop; int res = 0; while (x != 0) { pop = x % 10; ...

用栈实现队列这个是 Leetcode 232 题，用两个栈来实现一个先进先出的队列，实现了一个版本。 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 进阶 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。 示例： 12345678910111213输入：["MyQueue ...

跟网上的不同的是，我这种方式是以时间换空间的做法，不会一次性把数据全查出来再慢慢遍历，而是每次查询是否存在子级，有就递归下去查。数据量大时，查库的次数比较多，数据量少时对数据库查询次数少，压力较小，但是多次查询不会出现一次查询数据量很大卡住的情况。 思路 先获取一级菜单，对每个一级菜单设子区域。 如果子区域还有子区域，就递归查询，直到查不到子区域返回。 递归的核心就是在方法中设置一个返回条件，防止无限递归下去。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 * @author liukai * @since 2019/6/12 16:14. */public class SignTree { private static RegionDao regi ...

LeetCode 的344 题。 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 提示: 1 <= s.length <= 105 s[i] 都是 ASCII 码表中的可打印字符 示例1: 12输入：["h","e","l","l","o"]输出：["o","l","l","e","h"] 示例2: 12输入：["H","a","n","n","a","h"]输出：["h","a","n","n","a","H& ...

多生产消费者模式真正的开发环境下，不可能只有两条线程在跑，但是也有特殊情况，就是只需要两条线程来处理。比如一个线程生产，一个线程消费。这是一种线程协作，这种情场景下，生产者 和 消费者会操作同一个共享变量。看到这里的小伙伴应该是对线程的基本用法有一定了解，这里就直接开始明确几个概念 生产者 生产数据的线程，比如产生订单 消费者 处理生产者产生的订单 实际环境中，生产数据的速度要大于消费的速度，这个现象在很多场景中都存在。 共享变量 会被多个线程共同访问的变量 生产者、消费者模式本质是，通过严格控制两个线程的交替执行，来实现一个生产、一个消费的模式，数据存储在共享变量中。 可以再扩展一下，比如常用的MQ，也是一种生产者消费者模式，Producer 生产消费，Consumer消费消息。 主要资源12345678910111213141516171819202122232425262728293031323334/** * @author liukai * @since 2017/2/18. */public class Resource { private bool ...

要求要不使用第三个变量的前题下且原地修改变量位置，将两个数组元素交易位置。 思路不使用第三个变量的话，只能在原来的两上变量在动心思。这两个变量没说不能变，那么就使用数学的方式将两个变量交换一下。只需要把两个变量中的其中一个借用来存储当前的变量即可，最后再还原回去。步骤： 借变量 交换元素 其实公式也很好记，变量位置不变，只是变了符号： a + ba - ba - b 123456789101112131415161718192021222324252627282930package com.liukai.algorithm.sort;/** * Created by liu kai on 16/9/8. * 交换数组两个元素位置 */public class Change { public static void main(String[] args) { int x = 3, y = 5; int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; test( ...

说明这段代码的思路是使用两个循环来对数组进行去重操作，并将结果重新封装到一个新的数组中。整体思路是通过两个循环遍历数组，将重复出现的元素标记为 -1，然后根据标记的情况创建一个新的数组来存储去重后的结果。 代码的时间复杂度为 O(n^2)，其中 n 是输入数组的长度。外层循环从 0 到 n-2 进行迭代，内层循环从外层循环的下一个元素开始迭代到 n-1。因此，内层循环的迭代次数会逐渐减少。在最坏情况下，即数组中没有重复元素时，内层循环将完全执行 n-1 + n-2 + ... + 1 = (n-1)n/2 次。这是一个等差数列求和公式。然而，在内层循环中，当发现重复元素时，会将重复元素标记为 -1，并增加 len 计数器。内层循环在后续迭代中会跳过被标记为 -1 的元素。因此，当数组中有 k 个重复元素时，内层循环的迭代次数将会减少 k 次。最后，创建新数组的循环将迭代 n 次，其中 n 是输入数组的长度。 因此，总体来说，该代码的时间复杂度为 O(n^2)。在最坏情况下，即数组中没有重复元素时，时间复杂度为 O(n^2)。在最好情况下，即数组中所有元素都是重复的，时间复杂度为 O(n ...