一开始看这本书的目录发现连动态规划都没有的，当时觉得有点坑爹，后来想想我这种基础烂到家的码畜也没什么资格觉得这玩意儿能坑爹。
断断续续的看到现在其实做了第一章的数据结构的链表背包题目，发现其实书上讲的挺多的，题目大多都是让自己构造一个简单的容器，实现API。
除了书上的题目，对于链表的练习这里推荐几个LeetCode里面的题目，都是仅与链表本身操作相关，不涉及其他算法。
2. Add Two Numbers
19. Remove Nth Node From End of List
82. Remove Duplicates from Sorted List II
86. Partition List
19. Remove Nth Node From End of List
25. Reverse Nodes in k-Group
做链表题感觉最需要注意的就是NullPointException，如果能在循环里规避就最好了，实在不行呢，在循环里面写个判断。最开始甚至写过while(node!=null){if(node.next.val!=1){}}这样的蠢东西。
1.几个简单的算法
1.1翻转链表
//其实很简单，主要致敬一下轮子哥之前的一个回答= =
//第一个方法是：一个个遍历链表，并且将节点插入新链表头
Node reserves(Node node){
Node first = node;
Node temp = null;
while(first!=null){
Node next = first.next;
first.next = temp;
temp = first;
first = next;
}
return temp;
}
//第二个方法是：一个个将链表中的节点倒转
//1->2->3->4->5 => 2->1->3->4->5这样的
Node reserves(Node node){
Node current= node;
Node temp= node;
while(current.next!=null){
Node second = current.next;
current.next = second.next;
second.next = temp;
temp = second;
}
return temp;
}
反正个人觉得链表的东西就是疯狂创建指针就完事儿了(似乎还专门有种说法叫双指针？)。更多的练习可以上leetcode去专门找linked list做。
1.2随机选取
书上某一题需要用数组实现一个随机队列其中一个接口要求随机返回并删除某一个元素，但是书上又没有现成方法咯。不过也很简单，就是从队列中随机取一个随机数据然后与尾数据交换，然后删除尾数据，用random类实现。
int[] a = new int[]{1,2,3,4,5,6,7,8,9,0};
int size = a.length;
while (size!=0){
int index = (int)(Math.random()*size);
int temp = a[index];
a[index] = a[--size];
a[size] = temp;
System.out.println(temp);
}
1.3栈的可生成性
emmmmmm，常见题了吧...就是给一个栈的操作(可能是pop也可能是push)序列，以及几串结果，问你下列几个结果哪个是生成不了的。就是 1-2-3-4-5的栈操作顺序问你5-4-1-2-3是不是可生成。
//将结果与操作逐个比对，如果有相同，则当成一个入栈出栈操作，跳过，否则将操作数压入栈
//最后栈不断pop并与剩余数比较，有不同则错。
//发现我怎么说都说不拎清，还是看代码吧....反正也简单
LinkedList<Integer> linkedList = new LinkedList<>();
int[] a = new int[]{1,2,3,4,5};
int[] b = new int[]{5,4,3,2,1};
int i=0,j=0;
while (i<a.length&&j<b.length){
if (a[i]!=b[j]){
linkedList.push(a[i++]);
}
else {
j++;i++;
}
}
while (j<b.length){
if (linkedList.pop()!=b[j]){
break;
}
j++;
}
System.out.println(linkedList.isEmpty());
2.构造数据结构以及一点点问题
首先自己实现数据结构API刚好书上有一套组合题。
1：实现双向队列。2：用双向队列实现两个栈。3：用两个栈实现一个缓冲区API。
说实话这些题目看着挺简单的，但是其中有很多值得思考的地方。
public class DulNode<T> {
T item;
DulNode<T> next;
DulNode<T> pre;
public DulNode(T item) {
this.item = item;
}
public DulNode(){}
}
//双向队列实现俩栈
public class DequeImp<Item> implements Deque<Item> {
private int size = 0;
private DulNode<Item> root = new DulNode<>();
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public void pushLeft(Item item) {
DulNode<Item> temp = root;
while (temp.pre != null) {
temp = temp.pre;
}
DulNode<Item> left = new DulNode<>(item);
temp.pre = left;
left.next = temp;
size++;
}
@Override
public void pushRight(Item item) {
DulNode<Item> temp = root;
while (temp.next != null) {
temp = temp.next;
}
DulNode<Item> right = new DulNode<>(item);
temp.next = right;
right.pre = temp;
size++;
}
@Override
public Item popLeft() {
DulNode<Item> temp = root;
if (temp.pre == null) {
return null;
}
while (temp.pre != null) {
temp = temp.pre;
}
Item result = temp.item;
temp.next.pre = null;
size--;
return result;
}
@Override
public Item popRight() {
DulNode<Item> temp = root;
if (temp.next == null) {
return null;
}
while (temp.next!=null) {
temp = temp.next;
}
Item result = temp.item;
temp.pre.next = null;
size--;
return result;
}
}
public class BufferImp implements Buffer{
private DequeImp<Character> stack;
public BufferImp(){
stack = new DequeImp<>();
}
@Override
public void insert(char c) {
stack.pushLeft(c);
}
@Override
public char delete() {
//这里有个问题，基础的char无法为null，但是容器又是泛型的
// 所以具体应该如何处理不抛出null的异常，有什么好的解决办法？
Character result = stack.popLeft();
return result==null?'\0':result;
}
@Override
public void left(int k) {
if (checkSize(k)){
while (k>0){
stack.pushRight(stack.popLeft());
k--;
}
}
}
@Override
public void right(int k) {
if (checkSize(k)){
while (k>0){
stack.pushLeft(stack.popRight());
k--;
}
}
}
@Override
public int size() {
return stack.size();
}
private boolean checkSize(int k){
if (size()<k){
System.out.println("can not do this operation");
return false;
}
return true;
}
}
其实非常建议看看JDK的容器代码，写得好而且代码文档详细，看着好舒服= =。
