算法 part 3
day 11
题目一：合并两个有序链表 21
解答一
就数据结构书上的解，双指针，刻在DNA里了。
注意
最后那里可以用三元逻辑来写，会更短 ? :
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null && list2==null) return null;
if(list1==null) return list2;
if(list2==null) return list1;
//头结点
ListNode head = new ListNode();
if(list1.val<list2.val) {
head = list1;
list1=list1.next;
}
else {
head = list2;
list2=list2.next;
}
ListNode p =head;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
p.next=list1;
list1=list1.next;
}
else{
p.next=list2;
list2=list2.next;
}
p=p.next;
}
if(list1!=null) p.next=list1;
if(list2!=null) p.next=list2;
return head;
}
}
效果：100%，56%
没想到的：递归解
直接上代码
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
效果：100%，19%
* 题目二： 翻转链表 206
出现了一个大问题：我上了头插法的当了。不需要头插，只需要记住新链表的头结点就可以了，直接把它接在新头后面就行了。题目很简单，但是做的过程很折腾，其实是对Java的语法理解出了问题，回去翻书总结了。
解法一：递归，头插
就是新建一个head,然后递归得头插。很简单的思想，不知道为什么折腾了很久；
总结
- 单链表要注意没有前驱指针，不要想着指针往前走；
- 对java的参数传值调用不太清楚，出bug的时候很犹豫；
always call by value
- 方法不能改变参数内容，也不能让对象参数引用一个新的对象；
- 得到的只是拷贝，参数变量只存在与方法过程中;
方法参数的类型
- 基本类型：不可改变;
int a = 1; int b = 2; swap(a,b);- 对象引用：可以改变；
但是不用误以为java对对象采用引用调用，而是拷贝了类变量，成为了对象的引用。一个经典的反例：
//结果a仍然是白猫，b是黄猫; Cat a = new Cat("waite"); Cat b = new Cat("Yellow"); swap(a,b);
渣代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null) return null;
ListNode newHead = new ListNode();
addToHead(head,newHead);
return newHead.next;
}
public void addToHead(ListNode head,ListNode newHead){
if(head==null) return;
ListNode p = head;
head=head.next;
p.next=null;
p.next = newHead.next;
newHead.next = p;
addToHead(head,newHead);
}
}
总觉得很丑。效果：100%，5%
解法二 迭代
开始用循环直接获取尾结点，并计算结点个数。用个数了控制插入次数
总结
对象变量不是对象本身，只是“对象型指针”。一个对象变量并没有包含一个对象，而仅仅是引用。在java中，每个对象变量都是对存储在另一个地方的对象的引用。new操作符返回值也是一个引用。java的对象都存储在堆中。
深拷贝和浅拷贝 没细看的参考资料
代码
疑问：为什么每次新建结点的内存消耗还小于每次只是改变结点指针的内存消耗，是因为数据量太小了吗？
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null) return null;
ListNode tail = head;
int size = 1;
while(head.next!=null){
head=head.next;
size++;
}
for(int i = 0;i<size-1;i++){
ListNode p = new ListNode(tail.val,null);
if(head.next!=null) p.next = head.next;
head.next =p;
tail = tail.next;
}
return head;
}
}
效果：100% 82%
Day 12
*组合 77
一道没做出来题。很适合用来学习回溯；
解一：回溯
类似决策树，穷举所有可以性，可以用适当的剪枝来优化。脑子里有那棵树就好了；
回溯算法:是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
注意：
- 工作数组temp在每次加入result时，不能直接
result.add(temp)，因为java数组是类似引用传递的，需要result.add(new ArrayList<Integer>(temp))新建一个arrayList加进去，否则temp会在接下来的每次递归时改变，结果最后都是一模一样的数组。 - 剪枝和得到结果时都要return;
代码
class Solution {
ArrayList<Integer> temp = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n,k);
return result;
}
public void dfs(int cur,int k){
//剪枝
if(temp.size()+cur<k || cur<0) return;
//记录答案
if(temp.size()==k) {
result.add(new ArrayList<Integer>(temp));
return;
}
// 考虑当前
temp.add(cur);
dfs(cur-1,k);
temp.remove(temp.size()-1);
dfs(cur-1,k);
}
}
效果：100%，64%
解法二：利用二进制枚举
看的这篇文章学的，原来是利用二进制来实现全枚举，而不用递归。
注意：
- 注意位运算，& 得到的不是boolean，而是类似 1000,用的时候别
(i&(1<<j))==1而是用>或者!0; - 用
Integer.bitCount(i) == k统计1的数量就行了。。。不用逐位遍历累加，好傻。
代码
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
int elements[] = new int[n];
for (int i = 0; i < n; i++) {
elements[i] = i + 1;
}
for (int i = 0; i < (1 << n); i++) {
if (Integer.bitCount(i) == k) {
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
temp.add(elements[j]);
}
}
result.add(temp);
}
}
return result;
}
}
