逆流的博客

字典序介绍所谓字典序，就是按照字典的排列顺序进行排列。首先，先按照首字符进行排序，如果首字符相同，则按照第二个字符进行排序，以此类推。比如一系列由abc三个字符组成的字符串的字典序的排列：abc，acb，bac，bca，cab，cba 字典序算法字典序算法的目的是为了找一个字符串的下一个字典序。例如：有一系列字符串是由abcdefg组成的，他们按照字典顺序排列。求字符串abcdgef的下一个排序，这类问题。 这里可以看下leetcode的一道题目：31. 下一个排列 - 力扣（Leetcode） 过程主要步骤： i从字符串末尾向前进行遍历，找到一个字符s[i] < s[i + 1] j从字符串末尾向前进行遍历，找到一个字符s[j] > s[i] 交换s[i]和s[j] 对i位置以后的字符进行倒转（不包括i） 这样的到的结果就是原字符串的下一个排序了。 实现这里以这道题为例：31. 下一个排列 - 力扣（Leetcode） 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3] ...

检验图中是否有环判断图中是否有环一共有三种方法： 拓扑排序 DFS 并查集 下面所有代码都是实现一个方法： 12345678class Solution { //检验图中是否有环，edges用来存储边，[2,3]表示2节点到3节点有一条有向或无向边 //该图是一个连通图 // n为节点数目 // 节点的标识在[0,n)之间 public boolean isLoop(int[][] edges,int n) { }} 拓扑排序有向图过程对于有向图，循环遍历图中所有入度为0的顶点并去除，直到最终没有顶点可以去除。如果还有顶点剩下，则剩下的就是环路。如果没有顶点剩下，则不存在环。 假如有一个有向图 入度为0的顶点有1顶点，则第一步先去除1顶点 现在入度为0的顶点有4顶点和2顶点，依次去除4顶点和2顶点 没有可去除的顶点了，该图有环路，顶点3、5、6形成环 代码实现1234567891011121314151617181920212223242526272829303132333435363738394 ...

并查集概述并查集是一种树性的数据结构，主要用于解决一些集合的合并，查询的问题。比如将多个元素合并到一个集合里；查询两个元素是否属于同一个集合。 实际运用：(看题就知道了) 547. 省份数量 - 力扣（Leetcode） 399. 除法求值 - 力扣（Leetcode） 684. 冗余连接 - 力扣（Leetcode） 工作原理基本原理先用一个数组来存储元素，数组的索引代表元素，值存储着该元素的父亲的下标。如果两个元素的老祖宗是一样的，那么这两个元素属于同一个集合。 初始情况： 初始情况，所有人的父亲都指向自己，也意味这自己属于一个集合。 现在，我们0所在集合归并到1所在集合中去。只需要让0的父亲指向1即可。即让0认1做爹，然后他们就属于一个家族了。 假如我们现在又想让3所在集合合并到4所在集合。那么只需要将3的父亲指向4即可。即让3认4做爹，然后他们就属于一个家族了。 假如，我们现在又想让0所在家族合并到3所在家族。那么我们只需要让0的父亲指向3的父亲即可。即让0的父亲认3的父亲做爹。那么他们就都属于一个家族了。（我们这里一定让0的父亲认3的父亲做爹才能合并成一个更大的家族， ...

欧拉回路介绍 七桥问题 18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。这就是所谓的七桥问题 后来大数学家欧拉把它转化成一个几何问题【一笔画问题】，并解决了该问题。思路就是把岸，岛，想象成一个点。把桥想象成一个边。 这样，七桥问题就转换成了，如何一笔走过图中的所有路径。 一些定义 对于一个图的一条路径，可以经过所有的边，且只通过一次，那么这个路径就称为欧拉路径。 对于一个图的一条路径，可以经过所有的边，且只通过一次，并能回到出发点，那么这个路径也称为欧拉回路 对于一个图，如果含有欧拉回路，则称这个图为欧拉图 对于一个图，如果含有欧拉路径而无欧拉回路，则称这个图为半欧拉图 判断是否存在欧拉回路对于无向图结论： 如果一个图所有的顶点所连接的边都是偶数，那么该图存在欧拉回路。如果含有顶点连接的边数为奇数，那么该图不存在欧拉回路。 对于这图，点A，B，C，D所连接的的边都是奇数，所以并不存在欧拉回路。及七桥问题的答案就是不存在一条这样的路径。 ...

求字的最大公约数辗转相除法 java代码实现 12345678private static int gcd(int a, int b) { while (a % b != 0) { int z = a % b; a = b; b = z; } return b;} 求多个数的最大公约数对于多个数的最大公约数，大概是这么一个情况 先求出前面的数的最大公约数，得到的结果和后面的数继续求最大公约数 代码实现 12345678910111213141516private static int gcd(int[] nums) { int num = nums[0]; for (int i = 1; i < nums.length; i++) { num = gcd(num, nums[i]); } return num;}private static int gcd(int a, int b) { ...

并发工具线程池 ThreadPoolExecutor线程池状态ThreadPoolExecutor使用int的高三位来表示线程池状态，低29为表示线程数量 状态名 高3位 接收新任务 处理阻塞队列任务 说明 running 111 Y Y shutdown 000 N N 不会接收新任务，但会处理阻塞队列剩余任务 stop 001 N N 会中断正在执行的任务，并抛弃阻塞队列任务 tidying 010 - - 任务全部执行完毕，活动线程为0即将进入终结 terminated 011 - - 终结状态 构造方法1234567public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<R ...

无锁CAS原子操作系统提供一个原子操作CAS(compare and swap 或 Compare And Set)比较并交换，需要传递三个值，数据所在地址，数据过去的值，数据需要更新的值。 cpu会先比较传入数据原来的值是否和内存中当前的值是否相等，如果相等才更新内存中的值，否则操作失败。使用cas(&i, i, i + 1)替代获取锁，那么如果操作失败了，那就循环重新再来一次，直到成功while(! cas(&i,i, i+1)); ABACAS会出现的一个经典问题就是ABA了，比如说： 一个线程1获取到内存中a的值为A 然后线程2把a改为了B 然后线程2又把a改为了A 最后线程A再调用CAS，它以为a变量没有被改过。执行成功 解决方法：版本号 对不仅需要传递值，还需要传递版本号，只有值相等且版本号相等才认为该值没有被修改过 原子类原子整数 AtomicBoolean AtomicInteger AtomicLong 1234567891011121314151617181920// AtomicIntegerAtomicInteger integer = ...