個(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è)是慢指針佃蚜,先讓快指針向前移動∮褂椤k-1 次,也就是移動到 第⌒乘恪k 個(gè)元素熟尉,然后讓 慢指針開始移動,這樣的話當(dāng)快指針指到末尾的時(shí)候洲脂,慢指針指向的剛好是 倒數(shù)第〗锒k 個(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)擊此處