Posts

何为线段树 线段树是基于要研究的数组而构建的数据结构，呈二叉树状。线段树的叶子结点就是所要研究的数组，非叶子节点表示数组的一段区间的某个性质的值。比如此区间的和，或者最大值最小值等等。 为什么需要线段树呢？试想你需要设计一个功能，给定一个数组，需要你提供两个操作，一是更改某个元素，而是索引某个区间的和，或者最大值，或者最小值，这里以和举例。最直接也是最简单做法当然是直接在数组上操作，O(1)更新，O(N)索引和，N为区间长度。 class NumArray { public NumArray(int[] nums) { //TODO } // Updates nums[index] = val. public void update(int index, int val) { //TODO} // Gets sum of nums[left ... right]. public int query(int left, int right) { //TODO } } 再进一步，如果需要更新一个区间的元素呢，比如，nums[i] += val, for left <= i <= right。 class NumArray { // ... // Add val, for nums[i] with left <= i <= right public int add(int left, int right, int val) { //TODO } } 继续以上方法，就是遍历区间，一一更新，与索引相同复杂度:O(N)。...

何为BIT BIT是一种数据结构，名为树其实用数组即可表达。其主要作用是给定了一个数组(或多维数组)，BIT可用来： O(logN)的复杂度计算给定范围的和,也就是求sum(low, high) O(logN)的复杂度更新数组的一个元素 其构造方法巧妙但简单，可谓大道至简。 给定一个数组a[0 ... N-1],长度N。 BIT表示为indexes[0 ... N],长度N+1。indexes[i]=sum(g(i) ... i], g(i)=i-i&(-i)，注意是左开右闭区间。i&(-i)得到的是一个数字的二进制表示中只留下最右的1后的数字，比如12=[1100],则12&(-12)只留下最右的1就成了4=[0100]。 注意到indexes[]从1开始计数，所以始终有indexes[0]=0。为了说明方便，在数组a[]前面添加了个元素0。 看图说话，如此构造后，原数组的和sum[0 ... i]就可以通过把能覆盖range[0 ... i]的indexes[]加起来得到。比如求sum[0 ... 14]，步骤如下，辅以图示。 先加上indexes[14]，覆盖了a[14], a[13]。 14=[1110],最右1留下后是2=[10],减去后得到12,加上indexes[12]。 12=[1100],最右1留下后是4=[100],减去后得到8,加上indexes[8]。 8=[1000],最右1留下后是8=[1000],减去后得到0，结束。 所以何为BIT,其本质是通过原数组构造一个新数组indexes[]，其中每个元素表示原数组中一段连续子数组的和。范围求和就从线性遍历原数组(O(N))，变成了在indexes[]中快速查找(O(logN))能覆盖所求范围的那几个元素。 而更新则是与求和相反的一个过程,原数组一个元素a[i]更新后，首先需要更新indexes[i]，然后要不停向上，更新每个覆盖了a[i]的indexes元素。比如,a[9]=2 -> a[9]=10,则有： 计算一个更新delta, delta=10-2，更新indexes[9]+=delta, 9=[1001],最右1留下后是1=[0001],加上后得到10,更新indexes[10] += delta。 10=[1010],最右1留下后是2=[0010],加上后得到12,更新indexes[12] += delta。 12=[1100],最右1留下后是4=[0100],加上后得到16,更新indexes[16] += delta。 代码如下: class BIT { private int[] indexes; private int[] nums; public BIT(int[] nums) { this.nums = nums; indexes = new int[nums.length + 1]; for (int i = 0; i < nums....

归并排序基于分治思想，基本步骤是把数组一分为二，分别排序，然后将两个排序好的数组合并，合并两个排序好的数组可以在O(N)的复杂度完成。根据T(N) = 2T(2/N) + N,可以推导出时间复杂度为O(NlogN)。代码如下： public void sort(int[] nums) { mergeSort(nums, 0, nums.length - 1); } private void mergeSort(int[] nums, int start, int end) { if (start >= end) { return; } int mid = start + (end - start) / 2; // Step 1: sort nums[start ... mid]. mergeSort(nums, start, mid); // Step 2: sort nums[mid+1 ... end]. mergeSort(nums, mid + 1, end); // Step 3: merge two sorted sub-arrays....

What’s Union Find? Union Find is useful in finding connected components. The idea behind UF is quite simple. You have N items initially. Each item forms its own group by setting parent to pointing to itself, i.e., parents[i] = i. Then you can union two items if they are connected or share some common properties in your problem definition. E.g., union(1,3) will connect item 1 and 3 and make their parents both pointing to the same item....

此一年波谲云诡，世事多艰，终于今宵。纵困苦艰难，江河依旧辽阔。新年至，昂首向前，爆竹声中，品人间烟火。 庚子弥年多诡谲，今岁今日终今宵。 寒随一夜冬雪去，暖入春风催竹梢。 稚齿犹恋除夕夜，三更欲等雄鸡叫。 家别万里相思浓，一柱清香扫尘嚣。