前言

常用java算法有哪些？就好比問(wèn)，漢語(yǔ)中常用寫(xiě)作方法有多少種，怎么分類(lèi)。算法按用途分，體現(xiàn)設(shè)計(jì)目的、有什么特點(diǎn)算法按實(shí)現(xiàn)方式分，有遞歸、迭代、平行、序列、過(guò)程、確定、不確定等等算法按設(shè)計(jì)范型分，有分治、動(dòng)態(tài)、貪心、線性、圖論、簡(jiǎn)化等等作為圖靈完備的語(yǔ)言，理論上”Java語(yǔ)言“可以實(shí)現(xiàn)所有算法。“Java的標(biāo)準(zhǔn)庫(kù)‘中用了一些常用數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法。像apache common這樣的java庫(kù)中又提供了一些通用的算法

最常見(jiàn)10大算法類(lèi)型

下文總結(jié)了程序員在代碼面試中最常遇到的10大算法類(lèi)型，想要真正了解這些算法的原理，還需程序員們花些功夫。

1.String/Array/Matrix 在Java中，

String是一個(gè)包含char數(shù)組和其它字段、方法的類(lèi)。如果沒(méi)有IDE自動(dòng)完成代碼，下面這個(gè)方法大家應(yīng)該記?。?/p>

toCharArray（） //get char array of a String

Arrays.sort（） //sort an array

Arrays.toString（char［］ a） //convert to string

charAt（int x） //get a char at the specific index

length（） //string length

length //array size

substring（int beginIndex）

substring（int beginIndex， int endIndex）

Integer.valueOf（）//string to integer

String.valueOf（）/integer to string

String/arrays很容易理解，但與它們有關(guān)的問(wèn)題常常需要高級(jí)的算法去解決，例如動(dòng)態(tài)編程、遞歸等。

下面列出一些需要高級(jí)算法才能解決的經(jīng)典問(wèn)題：

· Evaluate Reverse Polish Notation ·

Longest Palindromic Substring ·

單詞分割 ·

字梯

· Median of Two Sorted Arrays ·

正則表達(dá)式匹配

· 合并間隔 ·

插入間隔

· Two Sum ·

3Sum

4Sum ·

3Sum Closest ·

String to Integer ·

合并排序數(shù)組

· Valid Parentheses ·

實(shí)現(xiàn)strStr（） ·

Set Matrix Zeroes ·

搜索插入位置 ·

Longest Consecutive Sequence

· Valid Palindrome ·

螺旋矩陣

· 搜索一個(gè)二維矩陣

旋轉(zhuǎn)圖像 ·

三角形

· Distinct Subsequences Total ·

Maximum Subarray ·

刪除重復(fù)的排序數(shù)組

· 刪除重復(fù)的排序數(shù)組2 ·

查找沒(méi)有重復(fù)的最長(zhǎng)子串 ·

包含兩個(gè)獨(dú)特字符的最長(zhǎng)子串

· Palindrome Partitioning

2. 鏈表

在Java中實(shí)現(xiàn)鏈表是非常簡(jiǎn)單的，每個(gè)節(jié)點(diǎn)都有一個(gè)值，然后把它鏈接到下一個(gè)節(jié)點(diǎn)。 class Node {

int val;

Node next;

Node（int x） {

val = x;

next = null; }

}

比較流行的兩個(gè)鏈表例子就是棧和隊(duì)列。 棧（Stack）

class Stack{ Node top;

public Node peek（）{

if（top ！= null）{

return top;

}

return null; }

public Node pop（）{

if（top == null）{

return null;

}else{

Node temp = new Node（top.val）;

top = top.next;

return temp;

} }

public void push（Node n）{

if（n ！= null）{

n.next = top;

top = n;

}

}

}

隊(duì)列（Queue）

class Queue{

Node first， last;

public void enqueue（Node n）{

if（first == null）{

first = n;

last = first;

}else{

last.next = n;

last = n;

}

}

public Node dequeue（）{

if（first == null）{

return null;

}else{

Node temp = new Node（first.val）;

first = first.next;

return temp;

}

} }

值得一提的是，Java標(biāo)準(zhǔn)庫(kù)中已經(jīng)包含一個(gè)叫做Stack的類(lèi)，鏈表也可以作為一個(gè)隊(duì)列使用（add（）和remove（））。（鏈表實(shí)現(xiàn)隊(duì)列接口）如果你在面試過(guò)程中，需要用到棧或隊(duì)列解決問(wèn)題時(shí)，你可以直接使用它們。

在實(shí)際中，需要用到鏈表的算法有：

· 插入兩個(gè)數(shù)字 ·

重新排序列表 ·

鏈表周期

Copy List with Random Pointer

· 合并兩個(gè)有序列表 ·

合并多個(gè)排序列表 ·

從排序列表中刪除重復(fù)的 ·

分區(qū)列表 ·

LRU緩存

3.樹(shù)&堆

這里的樹(shù)通常是指二叉樹(shù)。

class TreeNode{

int value; TreeNode left; TreeNode right;

}

下面是一些與二叉樹(shù)有關(guān)的概念：

· 二叉樹(shù)搜索：對(duì)于所有節(jié)點(diǎn)，順序是：left children 《= current node 《= right children； ·

平衡vs.非平衡：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，

并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)； ·

滿二叉樹(shù)：除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)；

· 完美二叉樹(shù)（Perfect Binary Tree）：一個(gè)滿二叉樹(shù)，所有葉子都在同一個(gè)深度或同一級(jí)，并且每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)； ·

完全二叉樹(shù)：若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 （1～h-1） 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。 堆（Heap）是一個(gè)基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)，也可以稱為優(yōu)先隊(duì)列（ PriorityQueue），在隊(duì)列中，調(diào)度程序反復(fù)提取隊(duì)列中第一個(gè)作業(yè)并運(yùn)行，因而實(shí)際情況中某些時(shí)間較短的任務(wù)將等待很長(zhǎng)時(shí)間才能結(jié)束，或者某些不短小，但具有重要性的作業(yè)，同樣應(yīng)當(dāng)具有優(yōu)先權(quán)。堆即為解決此類(lèi)問(wèn)題設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。

下面列出一些基于二叉樹(shù)和堆的算法：

· 二叉樹(shù)前序遍歷

· 二叉樹(shù)中序遍歷

· 二叉樹(shù)后序遍歷

字梯 ·

驗(yàn)證二叉查找樹(shù) ·

把二叉樹(shù)變平放到鏈表里

· 二叉樹(shù)路徑和 ·

從前序和后序構(gòu)建二叉樹(shù) ·

把有序數(shù)組轉(zhuǎn)換為二叉查找樹(shù) ·

把有序列表轉(zhuǎn)為二叉查找樹(shù)

· 最小深度二叉樹(shù) ·

二叉樹(shù)最大路徑和

· 平衡二叉樹(shù)

4.Graph

與Graph相關(guān)的問(wèn)題主要集中在深度優(yōu)先搜索和寬度優(yōu)先搜索。深度優(yōu)先搜索非常簡(jiǎn)單，你可以從根節(jié)點(diǎn)開(kāi)始循環(huán)整個(gè)鄰居節(jié)點(diǎn)。下面是一個(gè)非常簡(jiǎn)單的寬度優(yōu)先搜索例子，核心是用隊(duì)列去存儲(chǔ)節(jié)點(diǎn)。

?

第一步，定義一個(gè)GraphNode

class GraphNode{

int val;

GraphNode next;

GraphNode［］ neighbors;

boolean visited;

GraphNode（int x） {

val = x;

}

GraphNode（int x， GraphNode［］ n）{

val = x;

neighbors = n;

}

public String toString（）{ return “value： ”+ this.val; } }

第二步，定義一個(gè)隊(duì)列

class Queue{

GraphNode first， last;

public void enqueue（GraphNode n）{

if（first == null）{

first = n;

last = first;

}else{

last.next = n;

last = n;

}

}

public GraphNode dequeue（）{

if（first == null）{

return null;

}else{

GraphNode temp = new GraphNode（first.val， first.neighbors）; first = first.next; return temp;

}

}

}

第三步，使用隊(duì)列進(jìn)行寬度優(yōu)先搜索

public class GraphTest {

public static void main（String［］ args） {

GraphNode n1 = new GraphNode（1）;

GraphNode n2 = new GraphNode（2）;

GraphNode n3 = new GraphNode（3）;

GraphNode n4 = new GraphNode（4）;

GraphNode n5 = new GraphNode（5）;

n1.neighbors = new GraphNode［］{n2，n3，n5};

n2.neighbors = new GraphNode［］{n1，n4};

n3.neighbors = new GraphNode［］{n1，n4，n5};

n4.neighbors = new GraphNode［］{n2，n3，n5};

n5.neighbors = new GraphNode［］{n1，n3，n4};

breathFirstSearch（n1， 5）;

}

Public static void breathFirstSearch（GraphNode root， int x）{

if（root.val == x）

System.out.println（“find in root”）;

Queue queue = new Queue（）;

root.visited = true;

queue.enqueue（root）;

while（queue.first ！= null）{

GraphNode c = （GraphNode） queue.dequeue（）;

for（GraphNode n： c.neighbors）{

if（！n.visited）{

System.out.print（n + “ ”）;

n.visited = true;

if（n.val == x）

System.out.println（“Find ”+n）;

queue.enqueue（n）;

}

}

}

} }

輸出結(jié)果：

value： 2 value： 3 value： 5 Find value： 5

value： 4

實(shí)際中，基于Graph需要經(jīng)常用到的算法：

克隆Graph