线段树节点数据结构： class SegmentTree{ int l,r; //每个区间的左右端点 int sum; //区间数据 //其他附加信息 } 建树以完全二叉树建树，可以使用父子二倍标记法，子节点下标为父节点下标值的两倍。 //递归建树 //p:当前父节点，sak为节点数组 void build(int p,int l,int r){ sak[p].l=l;sak[p].r=r; if(l==r){ sak[p].sum=a[l]; return; } int mid = (l+r)/2; //依次建立左右子树 build(2*p,l,mid); build(2*p+1,mid+1,r); sak[p].sum = sak[2*p].sum+sak[2*p+1].sum; } 单点修改每次操作都是从根节点开始遍历，递归找到需要修改的节点。 //p:当前节点 x:目标节点 val:修改值 void change(int p,i

并查集并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。可以求解一些图相关的问题（连通分量）。 并查集森林是一种将每一个集合以树的形式表示的数据结构，其中每个结点都保存着到他父节点的引用。在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。 class UnionSet{ int[] parent; //初始化并查集,每个结点自成一个集合 void UnionSet(int n){ parent=new int[n]; for(int i=0;i<n;i++){ parent[i]=i; } } //递归查找根节点 int find(int x){ if(parent[x]==x) return x; else return find(parent[x]); }

11月一直在准备考试和各种结课作业，停滞了很长时间没有学习新技术了。最近在stackoverflow上看到一些有趣的问题，就自己做了相关总结。 https://stackoverflow.com/questions/41107/how-to-generate-a-random-alpha-numeric-string 问题：生成伪随机的字母-数字字符串。For example, a generated string of length 12 might look something like "AEYGF7K0DM1X". 类的逻辑较为简单，不过使用了一些之前没接触过的库函数。 1、java.util.concurrent.ThreadLocalRandom Random虽然是线程安全的，但是在多线程环境下效率很低，而且Random产生的随机数序列可以预测，顾不适合作为验证码类随机数产生。（思考：图片验证码产生是不是根据产生的随机数从数据库中选出相应的图片作为验证码？） System.out.println("-----------产生1到10之间的随机数

断言断言机制允许在测试期间向代码中插入一些检查语句，当代码发布时，这些插入的检测语句会被自动地移走。Java语言引入了关键字assert，有两种形式： assert 条件; assert 条件:表达式; 这两种形式都会对条件进行检测， 如果结果为false, 则抛出一个AssertionError 异常。在第二种形式中，表达式将被传人AssertionError 的构造器， 并转换成一个消息字符串。 在默认情况下， 断言被禁用。可以在运行程序时启用断言，断言的启用和禁用不必重新编译程序。启用或禁用断言是类加载器( class loader ) 的功能。当断言被禁用时， 类加载器将跳过断言代码， 因此，不会降低程序运行的速度。 java -enableassertions MyApp不应该使用断言向程序的其他部分通告发生了可恢复性的错误， 或者，不应该作为程序向用户通告问题的手段。断言只应该用于在测试阶段确定程序内部的错误位置。 日志日志可以替换测试代码中使用的System.out.println()，不像输出语句测试完还需要删除。 //基本日志 Logger.getGlobal().i

lambda表达式lambda表达式形式：参数，箭头(->)以及一个表达式，也可以将操作放在代码块{}中。 (String first,String second)-> { if(first.length()>second.length()) return 1; else if(first.length()<second.length()) return -1; else return 0; } () -> System.out.pringln("i"); 对于只有一个抽象方法的接口，需要这种接口的对象时，就可以提供一个lambda表达式。这种接口称为函数式接口。Comparator 就是只有一个方法的接口， 所以可以提供一个lambda 表达式： 函数式接口中可以包含静态方法（已经实现了的方法），默认方法（default），java.lang.Object里的public方法。 Arrays.sort (words , (first , second) -> first.length() - s

split()String类下的split()方法在根据正则表达式对字符串进行分割时会产生空字符串，在处理时需要进行判断。 //1、空字符串不会被解析 public class test { public static void main(String[] args) { String str = "1,2,3,4,,,"; String[] arr = str.split(","); for (String string : arr) { System.out.println("str"+string); } System.out.println(arr.length); } } //输出：str1,str2,str3,str4 4 //2、最后一个分隔符被分的字符串不为空时，其余空字符串可被解析。 public class test { public static void main(St

java的PriorityQueue是基于堆的优先队列。下面是其构造方法： //如果Collection已排序，则根据它的顺序进行排序 PriorityQueue(Collection<? extends E> c) //自定义一个比较器，根据比较器进行优先级判断 PriorityQueue(Comparator<? super E> comparator) 第二种构造方法使用的较多，比较器的创建可以使用匿名内部类的方法指定。通过重写Comparator的compare方法来实现。下面通过例子来解释： https://leetcode-cn.com/problems/top-k-frequent-elements/ public List<Integer> topKFrequent(int[] nums, int k) { List<Integer> list=new ArrayList<>(); if(nums.length==1){ list.add(nums[0]

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/ 给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。 递归：我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。通过递归构建所有的子树。 public List<TreeNode> generateTrees(int n) { if(n==0) return new ArrayList<TreeNode>(); return createTree(1,n); } //每次递归应该返回可能的子树列表 List<TreeNode> createTree(int start,int end){ List<TreeNode> list=new ArrayList<>(); if(start>end){ list.add(null); return