链表的题目刷的七七八八，然后看算法第一章第四小节。真的，看到课后习题我真的忍不住说一句MMP，1.4.14和1.4.15是在LeetCode做到过的3-sum和4-sum(好吧还是有点区别的，leetcode需要返回所有符合的值)，然后1.4.24居然特么的是扔鸡蛋问题，经典的动态规划，之前我一朋友还分给我享过原题= =。
OK，第一章第四小节讲的是算法复杂度，过了一遍依然很朴素的认为对于一个长度为N的输入，有n层全遍历的嵌套循环就是Nn，对于一些分治的算法，比如快速排序，就是NlogN，logN就是一次遍历一部分比如二分查找，至于2n，暂时还不是很清楚。
对于对象的内存消耗一般是(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)是个N2，就是每次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--;
}
}
网友评论