個(gè)人認(rèn)為，算法是程序員的內(nèi)功锌订，不管你是能把 Java 或是 C # 玩出花來，也是需要注意提升一下內(nèi)在修煉的画株。畢竟辆飘，只有深厚的內(nèi)功才能把招式發(fā)揮到極致。以下算法谓传，可能咋一看覺得很簡單蜈项，自己也能實(shí)現(xiàn)，但是要知道能實(shí)現(xiàn)功能固然重要续挟，但算法的效率更值得研究紧卒。紙上得來終覺淺，相信如果你能把以下算法都親手實(shí)現(xiàn)一遍诗祸，必定會有收獲跑芳，至少我個(gè)人是這樣。
想要實(shí)現(xiàn)以下將介紹算法直颅，首先需要自己實(shí)現(xiàn)一個(gè) 鏈表博个，下面粘貼上我利用前插法寫的鏈表。
public class MyList {
private Node first;
public MyList(){
}
public class Node {
Node next;
int data;
public Node(Node next, int data) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
this.next = null;
}
public Node(){
}
}
public void add(int data) {
first = add(first, data);
}
private Node add(Node x, int data) {
if (x == null)
return new Node(data);
return new Node(x, data);
}
public Node getFirst() {
return first;
}
}
2.1 編寫代碼功偿，移除未排序鏈表中的重復(fù)結(jié)點(diǎn)盆佣。如果不能使用緩沖區(qū)，又該怎么解決械荷？
// 借用臨時(shí)緩沖區(qū)的解法
public static void deleteSame(MyList list) {
MyList.Node current = list.getFirst();
MyList.Node pre = null;
Hashtable<Integer, Boolean> hashtable = new Hashtable<>();
while (current != null) {
if (hashtable.containsKey(current.data)) {
pre.next = current.next;
} else {
hashtable.put(current.data, true);
pre = current;
}
current = current.next;
}
}
// 不借用臨時(shí)緩沖區(qū)
public static void deleteSameTwo(MyList list) {
MyList.Node current = list.getFirst();
MyList.Node runner;
while (current != null) {
runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
}
runner = runner.next;
}
current = current.next;
}
}
2.2 實(shí)現(xiàn)一個(gè)算法共耍，找出單鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn)．
// 只打印該元素，不返回該元素
private static int findOne(MyList.Node node, int k) {
if (node == null)
return 0;
int i = findOne(node.next, k) + 1;
if (i == k)
System.out.println(node.data);
return i;
}
// 基于以上方法 利用 IntWrapper返回該元素
private class IntWrapper {
public int value = 0;
}
private static MyList.Node findTwo(MyList.Node node, int k, IntWrapper i) {
if (node == null)
return null;
MyList.Node t = findTwo(node.next, k, i);
i.value = i.value + 1;
if (i.value == k) {
return node;
}
return t;
}
注意除了以上兩種算法吨瞎，還有一種方法痹兜，就是設(shè)置兩個(gè)指針，一個(gè)是快指針关拒，一個(gè)是慢指針佃蚜，先讓快指針向前移動∮褂椤ｋ－１ 次，也就是移動到 第⌒乘恪ｋ 個(gè)元素熟尉，然后讓 慢指針開始移動，這樣的話當(dāng)快指針指到末尾的時(shí)候洲脂，慢指針指向的剛好是 倒數(shù)第〗锒ｋ 個(gè)元素。
2.3 實(shí)現(xiàn)一個(gè)算法恐锦，刪除單向鏈表中間的某個(gè)結(jié)點(diǎn)往果，假定你只能訪問該結(jié)點(diǎn)。
private static void delete(Node root) {
// 如果當(dāng)前節(jié)點(diǎn)為空或者當(dāng)前節(jié)點(diǎn)為尾節(jié)點(diǎn)的時(shí)候直接退出
if (root == null || root.next == null) {
return;
}
Node next = root.next;
root.data = next.data;
root.next = next.next;
}
2.4 編寫代碼一铅，以給定值 x 為基準(zhǔn)將鏈表分割成兩部分陕贮，所有小于 x 的結(jié)點(diǎn)排在大于或等于 x 的節(jié)點(diǎn)之前。
public static Node divide(Node root, int x) {
MyList mins = new MyList();
MyList maxs = new MyList();
while (root != null) {
if (root.data < x) {
mins.add(root.data);
} else {
maxs.add(root.data);
}
root = root.next;
}
Node minRoot = mins.getFirst();
Node maxRoot = maxs.getFirst();
if (minRoot == null) {
return maxRoot;
}
Node temp = minRoot;
while (minRoot.next != null)
minRoot = minRoot.next;
minRoot.next = maxRoot;
return temp;
}
2.5 給定兩個(gè)用鏈表表示的整數(shù)潘飘，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)位肮之。這些數(shù)位是反向存放的，也就是個(gè)位排在鏈表首部卜录。編寫函數(shù)對兩個(gè)整數(shù)求和戈擒，并用鏈表形式返回結(jié)果。
public static Node addLists(Node n1, Node n2, int carry) {
if (n1 == null && n2 == null && carry == 0) {
return null;
}
Node result = new MyList().new Node();
int value = carry;
if (n1 != null) {
value += n1.data;
}
if (n2 != null) {
value += n2.data;
}
result.data = value % 10;
Node more = addLists(n1 == null ? null : n1.next, n2 == null ? null : n2.next, value / 10);
result.next = more;
return result;
}
2.6 編寫一個(gè)函數(shù)艰毒，檢查鏈表是否為回文筐高。
public static boolean isPalindrome(Node root) {
Node fast = root;
Node slow = root;
Stack<Integer> stack = new Stack<>();
while (fast != null && fast.next != null) {
stack.push(slow.data);
slow = slow.next;
fast = fast.next.next;
}
// 說明有奇數(shù)個(gè)元素，跳過中間元素
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
int top = stack.pop().intValue();
if (top != slow.data)
return false;
slow = slow.next;
}
return true;
}
以上代碼實(shí)現(xiàn)都是核心代碼丑瞧，需要完整代碼的 點(diǎn)擊此處
