Ciel's blog

Hi, this is Ciel!

Posted on Edited on In

  1. 首先django程序需要修改setting.py中的数据库配置的HOST

    IP通过在宿主机上通过ifconfig指令查看到docker0的IP地址，通常为172.17.0.1，宿主机访问docker的ip则是最后一位改为2，即172.17.0.2，宿主机和docker容器就是通过这个docker0网桥进行通信的。

  2. 配置mysql允许远程访问

编辑cnf文件，bind-address = 127.0.0.1改为bind-address = 0.0.0.0

1
vim /etc/mysql/mysql.conf.d/mysqld.cnf

进入mysql

1
2
3
> grant all on *.* to root@'%' identified by '你的密码' with grant option;
> flush privileges;    # 刷新权限
> exit

再重启mysql，即可以从外部计算机通过root用户连接到此mysql数据库

1
2
/etc/init.d/mysql stop
/etc/init.d/mysql start

Posted on Edited on In

链表的JAVA实现

在JAVA中，JAVA的集合(collection)实现了各种常用的数据结构，包括链表。

下面自己来实现简单的单链表。链表是由一个个的相互连接的结点组成，结点又由数据域和指针域组成，指针域指向下一个结点。

1
2
3
┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ A │ ●─┼──>│ B │ ●─┼──>│ C │ ●─┼──>│ D │   │
└───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘

JAVA没有struct结构体，所以用一个Node Class表示结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 结点
public class ListNode<E>{
	// 数据域
	private E data;
	// 指针域
	private ListNode<E> next = null;
	
	// 构造函数
	public ListNode(E data) {
		this.data = data;
	}
	// 构造函数
	public ListNode(E data, ListNode<E> next) {
        this.data = data;
        this.next=next;
    }
	
	public void setData(E data) {
		this.data = data;
	}
	
	public E getData() {
		return this.data;
	}
	
	public void setNext(ListNode<E> next) {
		this.next = next;
	}
	
	public ListNode<E> getNext() {
		return this.next;
	}
}

链表反转

面试题5 - 从尾到头打印链表并不算是真正的链表反转，它只是将链表中的元素放进到新的数组对象中去了。

对于链表的反转问题，可以新建链表及节点关系；也可以在原有列表的基础上进行指针的变换，这样考察点就在于指针的运用（pointer manipulation）。这里主要阐述在原有列表的基础上进行指针的变换的方法。

迭代法（Iterative）

迭代法是从前向后顺序地交换两个节点的相对位置。

我们需要三个指针：

  • pre pointer：存储上一个节点，因为是单链表，在迭代过程中，当链表头移动到下一个结点后，就无法访问上一个结点了。
  • cur pointer：指示我们当前的指向。
  • next pointer：当我们改变当前结点指向后，我们就会丢失原来的下一个结点，所以需要一个结点来储存，才能知道我们的下一次迭代的前进方向。

最后的结果（图片来自视频）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 迭代法
public static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
    if (listNode == null) {
        return listNode;
    }
    // 用于存储上一结点
    ListNode<Integer> pre = null;
    // 指向当前结点
    ListNode<Integer> cur = listNode;
    // 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
    ListNode<Integer> next = new ListNode<>(null);
    while (cur != null) {// 当前结点为null，说明位于尾结点
        // 存储下一节点
        next = cur.getNext();
        // 反转指针域的指向（指向前一节点）
        cur.setNext(pre);
        // 将本次迭代的当前节点，作为下次循环的前结点
        pre = cur;
        // 将存储的下一节点取出，作为下一次迭代的当前节点
        cur = next;
    }
    // 还回新链表的头结点，即原链表的尾结点
    return pre;
}

Time: O(n)
Space: O(1)

递归法（Recursive）

递归法是从后向前逆序地交换两c个节点的相对位置。递归即是借助了系统的”栈”。

每一次迭代就像是向另一个人发出了命令：将我（本节点，本此迭代的head）后面的所有结点反转，不包括我。

每一次迭代，我们有的资源是返回的反转后的剩下链表（rlh，reversed list head）以及本节点（head）；每一次迭代，执行的动作是，将rlh指向我自己，再将新的rlh返回到上一次迭代。

图片来自视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 递归法
public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
	// base case
	if (listNode == null || listNode.getNext() == null) {
			return listNode;// 若为空链或者当前结点在尾结点，则直接还回
		}
	// 先反转后续节点listNode.getNext()
	ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
	// 执行本次递归的指向更改
	// S1：让下一节点指向本结点
	listNode.getNext().setNext(listNode);
	// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
	listNode.setNext(null);
	// 反转后新链表的头结点
	return reHead;
   }

Time: O(n)
Space: O(n)

代码

ListNode.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Main {
	public static void main(String[] args) {
		ListNode<Integer> node0 = new ListNode<>(0);
		ListNode<Integer> node1 = new ListNode<>(1);
		ListNode<Integer> node2 = new ListNode<>(2);
		ListNode<Integer> node3 = new ListNode<>(3);
		node0.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		
		ListNode<Integer> h1 = node0;
		System.out.println("反转前的链表：");
		while (h1 != null) {
			System.out.println(h1.getData());
			h1 = h1.getNext();
		}
		
		node0 = LinkedListReverse1(node0);
//		node0 = LinkedListReverse2(node0);
		
		ListNode<Integer> h2 = node0;
		System.out.println("反转后的链表：");
		while (h2 != null) {
			System.out.println(h2.getData());
			h2 = h2.getNext();
		}
		
	}
	
	// 迭代法
	public static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
		if (listNode == null) {
			return listNode;
		}
		// 用于存储上一结点
		ListNode<Integer> pre = null;
		// 指向当前结点
		ListNode<Integer> cur = listNode;
		// 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
		ListNode<Integer> next = new ListNode<>(null);
		while (cur != null) {// 当前结点为null，说明位于尾结点
			// 存储下一节点
			next = cur.getNext();
			// 反转指针域的指向（指向前一节点）
			cur.setNext(pre);
			// 将本次迭代的当前节点，作为下次循环的前结点
			pre = cur;
			// 将存储的下一节点取出，作为下一次迭代的当前节点
			cur = next;
		}
		// 还回新链表的头结点，即原链表的尾结点
		return pre;
    }

	
	// 递归法
	public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
		// base case
		if (listNode == null || listNode.getNext() == null) {
				return listNode;// 若为空链或者当前结点在尾结点，则直接还回
			}
		// 先反转后续节点listNode.getNext()
		ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
		// 执行本次递归的指向更改
		// S1：让下一节点指向本结点
		listNode.getNext().setNext(listNode);
		// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
		listNode.setNext(null);
		// 反转后新链表的头结点
		return reHead;
    }

	
}

Main.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Main {
	public static void main(String[] args) {
		ListNode<Integer> node0 = new ListNode<>(0);
		ListNode<Integer> node1 = new ListNode<>(1);
		ListNode<Integer> node2 = new ListNode<>(2);
		ListNode<Integer> node3 = new ListNode<>(3);
		node0.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		
		ListNode<Integer> h1 = node0;
		System.out.println("反转前的链表：");
		while (h1 != null) {
			System.out.println(h1.getData());
			h1 = h1.getNext();
		}
		
		node0 = LinkedListReverse1(node0);
//		node0 = LinkedListReverse2(node0);
		
		ListNode<Integer> h2 = node0;
		System.out.println("反转后的链表：");
		while (h2 != null) {
			System.out.println(h2.getData());
			h2 = h2.getNext();
		}
		
	}
	
	// 迭代法
	public static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
		if (listNode == null) {
			return listNode;
		}
		// 用于存储上一结点
		ListNode<Integer> pre = null;
		// 指向当前结点
		ListNode<Integer> cur = listNode;
		// 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
		ListNode<Integer> next = new ListNode<>(null);
		while (cur != null) {// 当前结点为null，说明位于尾结点
			// 存储下一节点
			next = cur.getNext();
			// 反转指针域的指向（指向前一节点）
			cur.setNext(pre);
			// 将本次迭代的当前节点，作为下次循环的前结点
			pre = cur;
			// 将存储的下一节点取出，作为下一次迭代的当前节点
			cur = next;
		}
		// 还回新链表的头结点，即原链表的尾结点
		return pre;
    }

	
	// 递归法
	public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
		// base case
		if (listNode == null || listNode.getNext() == null) {
				return listNode;// 若为空链或者当前结点在尾结点，则直接还回
			}
		// 先反转后续节点listNode.getNext()
		ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
		// 执行本次递归的指向更改
		// S1：让下一节点指向本结点
		listNode.getNext().setNext(listNode);
		// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
		listNode.setNext(null);
		// 反转后新链表的头结点
		return reHead;
    }

	
}

References

一篇文章搞定面试中的链表题目(java实现)

Java单链表反转 详细过程

【LeetCode算法题详解】链表反转（已添加字幕）

Posted on Edited on In

题目

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

解题

这是一个单链表（singly linked list）反转问题。这道题要求返回一个ArrayList，所以需要新建一个ArrayList，让后放入链表元素，直接用ArrayList的方法，弱化了对指针的运用（pointer manipulation）的考察。

使用栈（Iterative）

问题与栈的“FILO”规则类似，所以可以使用栈，先遍历链表，逐一将节点压入栈，再出栈添加到新建的链表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.empty()) {
            list.add(stack.pop());
        }
        return list;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

add指定位置插入（Iterative）

也可以遍历链表，然后借助ArrayList的add函数将节点从前插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode != null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

递归法（Recursive）

递归法是从后向前逆序地插入节点。递归即是借助了系统的”栈”。

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Solution {
    ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 注意是if不是while循环
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

总结

  1. ArrayList源码中两个add方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 将指定的元素插入ArrayList中的指定位置
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

References

牛客网讨论与题解

Java学习笔记之ArrayList基本用法

0%