算法第四版笔记(复杂度&union-find)

链表的题目刷的七七八八，然后看算法第一章第四小节。真的，看到课后习题我真的忍不住说一句MMP，1.4.14和1.4.15是在LeetCode做到过的3-sum和4-sum(好吧还是有点区别的，leetcode需要返回所有符合的值)，然后1.4.24居然特么的是扔鸡蛋问题，经典的动态规划，之前我一朋友还分给我享过原题= =。
OK，第一章第四小节讲的是算法复杂度，过了一遍依然很朴素的认为对于一个长度为N的输入，有n层全遍历的嵌套循环就是Nⁿ，对于一些分治的算法，比如快速排序，就是NlogN，logN就是一次遍历一部分比如二分查找，至于2ⁿ，暂时还不是很清楚。
对于对象的内存消耗一般是(64位环境下)：16字节对象开销+内部成员开销(类型为对象则固定8字节)+填充字节(需要填充至8的倍数)
这章的一些习题：

1：2-sum，3-sum，4-sum

书上题目只需要数组中含有符合条件的值就返回true。那么对于2-sum，除了遍历之外有两个优化。一个是使用hash表保存所有值(这里是对hash的一些记录)，然后查找。一个是在一次循环中使用搜索。
对于leetcode里面的题目，需要返回所有符合的结果集，这个其实解法就不一样了。

1.1：3-sum

将数组排序之后，用双指针来做。

 public static List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
             //偷个懒，使用set来存放结果用于消除重复
             Set<List<Integer>> sets = new HashSet<>();
            for(int i=0;i<nums.length-2;i++){
                //因为排过序，所以如果num[i]>0那么后面的就一定也大于0就不用遍历了。
                if (nums[i]>0)break;
                int target = 0-nums[i];
                int j = i+1;int k = nums.length-1;
                while (j<k){
                    if (nums[j]+nums[k] == target){
                        List<Integer> set = new ArrayList<>();
                        set.add(nums[i]);set.add(nums[j]);set.add(nums[k]);
                        sets.add(set);
                        j++;k--;
                    }
                    else if (nums[j]+nums[k]<target){
                        j++;
                    }
                    else {
                        k--;
                    }
                }
            }
            List<List<Integer>> lists = new ArrayList<>(sets);
            return lists;
        }

1.1：4-sum

4-sum可以用和3-sum一模一样的双指针来做，不过是多了一层循环。

 public List<List<Integer>> fourSum(int[] nums, int target) {
        Set<List<Integer>> sets = new HashSet<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++) {
            for(int j=i+1;j<nums.length-2;j++) {
                int low = j+1;int high = nums.length-1;
                while(low<high) {
                    int sum = nums[i]+nums[j]+nums[low]+nums[high];
                    if ( sum == target) {
                        sets.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
                        low++;high--;
                    }
                    else if(sum<target) {
                        low++;
                    }else {
                        high--;
                    }
                }
            }
        }
        List<List<Integer>> result = new ArrayList<>(sets);
        return result;
    }

然后leetcode上面有人总结了这种k-sum的做法，我就不抄一遍了。链接如下：
kSums in JAVA

2：Union-Find

这个算法讲的是给一个连通分量集(书上用一个数组表示)，设计一个算法将这个分量集中的分量合并，以及查找节点的分量。
leetcode上面打上union-find tag的题目不多，而其中Middle题里面，我一眼看出来能用union-find做的题目只有下面这两题。
547. Friend Circles
200. Number of Islands
吐个槽，书上这种表达方式引起我的极度不适，建个新的节点类多好啊，直接用数组表示我真的日了狗。
API如下，注释掉的是我觉得比较好理解的表达方式:

class Point{
    int index;  
}
public class UnionFind {
    private int[] id;
    private int count;
    
    public UnionFind(int N) {
        count =N;
        id = new int[N];
        for(int i=0;i<N;i++) {
            
        }
    }
    public int count() {
        return count;
    }
    /*public boolean connected(Point p,Point q) {
        return find(p) == find(q);
    }
    public int find(Point p) {
        
    }
    public void union(Point p,Point q) {
        
    }*/
    public int find(int p) {
        //TODO
        return 0;
    }
    public void union(int p,int q) {
        //TODO
    }
}

2.1：quick-find

这个没什么好说的，这个的思路是只要两个节点的id相同则算为连通分量。find方法下可以return id[point.index]，union方法下遍历整个数组，将两者id统一。
对于N对数据就需要遍历N次数组，这个算法一看就拉闸。

    public int find(Point p) {
        return id[p.index];
    }
    public void union(Point p,Point q) {
        int qID=find(q);
        int pID=find(p);
        if (pID==qID) {
            return;
        }
        for(int index = 0;index<id.length;index++) {
            if (id[index] == pID) {
                id[index] = qID;
            }
        }
        count--;
    }

2.1：quick-union

这个的思路就不一样了，quick-union的判定：某个point的id值为另一个point的index，那么这两个point连通。这样的话所有分量中的节点就连成一棵树，根是那个指向自身的节点，连接方向朝上。

public int find(int p) {
        while(p!=id[p]) p=id[p];
        return p;
    }
    public void union(int p,int q) {
        int qRoot=find(q);
        int pRoot=find(p);
        if (qRoot==pRoot) {
            return;
        }
        id[pRoot] = qRoot;
        count--;
    }

这个方法的最坏输入的次数为：3+5+......+(2N-1)是个N²，就是每次union的时候都把大树连到小树上面导致大树的叶子在find的时候耗时更多，情况大致如下:

最坏情况

改进方法是记录树的大小，然后每次union的时候总是将小树添加到大树的根节点。

2.1：WeightedQuickUnion

class WeightedQuickUnionUF{
    private int[] id;
    private int[] size;
    private int count;
    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        size = new int[N];
        for(int i=0;i<N;i++) {
            id[i] = i;
        }
        for(int i =0;i<N;i++) {
            size[i] = 1;
        }
    }
    public int count() {
        return count;
    }
    public boolean connected(int p,int q) {
        return find(p) == find(q);
    }
    public int find(int p) {
        while(p!=id[p]) p=id[p];
        return p;
    }
    public void union(int p,int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (size[pRoot]<size[qRoot]) {
            id[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }else {
            id[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }
        count--;
    }
}