总结
其他的内容都可以按照路线图里面整理出来的知识点逐一去熟悉，学习，消化，不建议你去看书学习，最好是多看一些视频，把不懂地方反复看，学习了一节视频内容第二天一定要去复习，并总结成思维导图，形成树状知识网络结构，方便日后复习。
这里还有一份很不错的《Java基础核心总结笔记》，特意跟大家分享出来
目录：
部分内容截图：
本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录
需要这份系统化的资料的朋友，可以点击这里获取
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
算法二：堆排序算法
=====================================
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
1.创建一个堆H[0…n-1]
2.把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1
代码实现：
public class HeapSort {
public static void main(String[] args) {
int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
myHeapSort(a);
for (int i : a)
System.out.print(i + " ");
}
public static void myHeapSort(int[] arr) {
int i;
int len = arr.length;
// 构建一个最小堆
for (i = len / 2 - 1; i >= 0; i–) {
adjustment(arr, i, len);
}
// 每次将顶点与最后一个节点交换，然后重新调整顶点即可
for (i = len - 1; i >= 0; i–) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
adjustment(arr, 0, i);
}
}
public static void adjustment(int[] arr, int pos, int len) {
int child = 2 * pos + 1;
// 若pos的右节点存在，则child指向左右节点值较小的那个节点
if (child + 1 < len && arr[child] > arr[child + 1]) {
child++;
}
// 将pos节点的值取其与子节点中的最小值，然后继续调整
if (child < len && arr[pos] > arr[child]) {
int tmp = arr[pos];
arr[pos] = arr[child];
arr[child] = tmp;
adjustment(arr, child, len);
}
}
}
算法三：归并排序
====================================
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
代码实现：
public class Main {
public static void main(String[] args) {
int[] arr = {11,44,23,67,88,65,34,48,9,12};
int[] tmp = new int[arr.length]; //新建一个临时数组存放
mergeSort(arr,0,arr.length-1,tmp);
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static void merge(int[] arr,int low,int mid,int high,int[] tmp){
int i = 0;
int j = low,k = mid+1; //左边序列和右边序列起始索引
while(j <= mid && k <= high){
if(arr[j] < arr[k]){
tmp[i++] = arr[j++];
}else{
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余，则将其全部拷贝进tmp[]中
while(j <= mid){
tmp[i++] = arr[j++];
}
while(k <= high){
tmp[i++] = arr[k++];
}
for(int t=0;t<i;t++){
arr[low+t] = tmp[t];
}
}
public static void mergeSort(int[] arr,int low,int high,int[] tmp){
if(low<high){
int mid = (low+high)/2;
mergeSort(arr,low,mid,tmp); //对左边序列进行归并排序
mergeSort(arr,mid+1,high,tmp); //对右边序列进行归并排序
merge(arr,low,mid,high,tmp); //合并两个有序序列
}
}
}
算法四：二分查找算法
======================================
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。
public class BinarySearch
{
private static int rCount=0;
private static int lCount=0;
/
- 获取递归的次数
- @return
*/
public int getrCount() {
return rCount;
}
/
- 获取循环的次数
- @return
*/
public int getlCount() {
return lCount;
}
/
- 执行递归二分查找，返回第一次出现该值的位置
- @param arrays 已排序的数组
- @param start 开始位置
- @param end 结束位置
- @param findValue 需要找的值
- @return 值在数组中的位置，从0开始。找不到返回-1
*/
public static int searchRecursive(int[] arrays,int start,int end,int findValue)
{
rCount++;
if(start<=end)
{
//中间位置
int middle = (start + end) >> 1;
//中值
int middleValue = arrays[middle];
if(findValue == middleValue)
{
//等于中值直接返回
return middle;
}else if(findValue < middleValue)
{
//小于中值时在中值前面找
return searchRecursive(arrays,start,middle-1,findValue);
}else
{
//大于中值在中值后面找
return searchRecursive(arrays,middle+1,end,findValue);
}
}else
{
//找不到
return -1;
}
}
/
- 循环二分查找，返回第一次出现该值的位置
- @param arrays 已排序的数组
- @param findValue 需要找的值
- @return 值在数组中的位置，从0开始。找不到返回-1
*/
public int searchLoop(int[] arrays,int findValue)
{
int start=0;
int end=arrays.length-1;
while(start<=end)
{
lCount++;
//中间位置
int middle=(start+end)>>1; //相当于(start+end)/2
//中值
int middleValue=arrays[middle];
if(findValue==middleValue)
算法基础之十大算法java
{
//等于中值直接返回
return middle;
}
else if(findValue<middleValue)
{
//小于中值时在中值前面找
end=middle-1;
}
else
{
//大于中值在中值后面找
start=middle+1;
}
}
//找不到
return -1;
}
}
算法五：BFPRT（线性查找算法）
=============================================
BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。
算法步骤：
1. 将n个元素每5个一组，分成n/5(上界)组。
2. 取出每一组的中位数，任意排序方法，比如排序。
3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。
代码实现：
/
- Created by ganjun on 2017/5/3.
*/
import java.util.*;
public class BFPRT {
public final int MAXN = ;
public static void swap(int [] x , int i , int j){
int tmp = x[i];
x[i] = x[j]; x[j] = tmp;
}
public static void sort(int [] x , int l , int r){
for(int i=l ; i<=r ; i++){
for(int j=i+1 ; j<=r ; j++){
if(x[j]<x[i]) swap(x , i , j);
}
}
}
public int findMedian(int []x , int l , int r){
int i , index;
for(i=l , index=0 ; i+4<=r ; i+=5 , index++){
sort(x , i , i+4);
swap(x , l+index , i+2);
}
//处理5个一分组多余的数字
if(i<=r){
sort(x , i , r);
swap(x , l+index , i+(r-i+1)/2);
index++;
}
if(index == 1) return x[l+index];
else return findMedian(x , l , l+index-1);
}
//寻找x数组中[l,r]区间内第k小元素
public int findKthMin(int [] x , int l , int r , int k){
int median = findMedian(x , l , r);
// 类似快速排序的方式，确定一个pivot为这个中位数的值x[l]，然后小的数放左边，大的数放右边
// 填坑法，最开始的数字x[l]上l位置是空出来的，
// 那么每一轮都从右边位置j找到一个较小的数填到i上（最开始i=l)，然后i上空出来了位置，
// 就再从左侧开始找到一个较大的数填回j上，直到i>=j
int mediemVal = x[l];
int i=l , j=r;
while(i<j){
while(i<j && x[j]>mediemVal) j–;
if(i<j) x[i] = x[j];
while(i<j && x[i]<mediemVal) i++;
if(i<j) x[j] = x[i];
}
x[i] = mediemVal;
if(i-l+1 == k) return x[i];
else if(i-l+1 > k) return findKthMin(x , l , i-1 , k);
else return findKthMin(x , i+1 , r , k-(i-l+1));
}
public static void main(String [] args){
int []x = {2,3,6,5,7,9,4};
BFPRT sol = new BFPRT();
//int val = sol.findMidiem(x , 0 , 6);
int val = sol.findKthMin(x , 0 , x.length-1 , 3);
System.out.println(val);
}
}
算法六：DFS（深度优先搜索）
===========================================
深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
深度优先遍历图算法步骤：
1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
上述描述可能比较抽象，举个实例：
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
代码实现：
import java.util.Stack;
public class DFSTest {
// 存储节点信息
private char[] vertices;
// 存储边信息（邻接矩阵）
private int[][] arcs;
// 图的节点数
private int vexnum;
// 记录节点是否已被遍历
private boolean[] visited;
// 初始化
public DFSTest(int n) {
vexnum = n;
vertices = new char[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
}
}
// 添加边(无向图)
public void addEdge(int i, int j) {
// 边的头尾不能为同一节点
if (i == j)return;
arcs[i][j] = 1;
arcs[j][i] = 1;
}
// 设置节点集
public void setVertices(char[] vertices) {
this.vertices = vertices;
}
// 设置节点访问标记
public void setVisited(boolean[] visited) {
this.visited = visited;
}
// 打印遍历节点
public void visit(int i){
System.out.print(vertices[i] + " ");
}
// 从第i个节点开始深度优先遍历
private void traverse(int i){
// 标记第i个节点已遍历
visited[i] = true;
// 打印当前遍历的节点
visit(i);
// 遍历邻接矩阵中第i个节点的直接联通关系
for(int j=0;j<vexnum;j++){
// 目标节点与当前节点直接联通，并且该节点还没有被访问，递归
if(arcs[i][j]==1 && visited[j]==false){
traverse(j);
}
}
}
// 图的深度优先遍历（递归）
public void DFSTraverse(){
// 初始化节点遍历标记
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
// 从没有被遍历的节点开始深度遍历
for(int i=0;i<vexnum;i++){
if(visited[i]==false){
// 若是连通图，只会执行一次
traverse(i);
}
}
}
// 图的深度优先遍历（非递归）
public void DFSTraverse2(){
// 初始化节点遍历标记
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
Stack s = new Stack();
for(int i=0;i<vexnum;i++){
if(!visited[i]){
//连通子图起始节点
s.add(i);
do{
// 出栈
int curr = s.pop();
// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈
if(visited[curr]==false){
// 遍历并打印
visit(curr);
visited[curr] = true;
// 没遍历的子节点入栈
for(int j=vexnum-1; j>=0 ; j-- ){
if(arcs[curr][j]==1 && visited[j]==false){
s.add(j);
}
}
}
}while(!s.isEmpty());
}
}
}
public static void main(String[] args) {
DFSTest g = new DFSTest(9);
char[] vertices = {‘A’,‘B’,‘C’,‘D’,‘E’,‘F’,‘G’,‘H’,‘I’};
g.setVertices(vertices);
g.addEdge(0, 1);
g.addEdge(0, 5);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(1, 6);
g.addEdge(1, 8);
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 8);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(3, 6);
g.addEdge(3, 7);
g.addEdge(3, 8);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(4, 7);
g.addEdge(5, 0);
g.addEdge(5, 4);
g.addEdge(5, 6);
g.addEdge(6, 1);
g.addEdge(6, 3);
g.addEdge(6, 5);
g.addEdge(6, 7);
g.addEdge(7, 3);
g.addEdge(7, 4);
g.addEdge(7, 6);
g.addEdge(8, 1);
g.addEdge(8, 2);
g.addEdge(8, 3);
System.out.print(“深度优先遍历（递归）：”);
g.DFSTraverse();
System.out.println();
System.out.print(“深度优先遍历（非递归）：”);
g.DFSTraverse2();
}
}
算法七：BFS（广度优先搜索）
===========================================
广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。
算法步骤：
1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜寻并回传结果。
- 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。
代码实现：
package com.liuzhen.chapterThree;
public class BreadthFirstSearch {
public int count = 0; //计算广度优先遍历总次数，初始化为0
/*
- adjMatrix是待遍历图的邻接矩阵
- value是待遍历图顶点用于是否被遍历的判断依据，0代表未遍历，非0代表已被遍历，其最终具体结果代表该顶点在最终遍历顺序中的位置
- result用于存放广度优先遍历的顶点顺序
*/
public void bfs(int[][] adjMatrix,int[] value,char[] result){
for(int i = 0;i < value.length;i++){
if(value[i] == 0){ //当该顶点未被遍历时
char temp = (char) (‘a’ + i);
result[count] = temp;
System.out.println();
System.out.println(“出发点：”+temp+“地”);
bfsVisit(adjMatrix,value,result,i); //使用迭代遍历该顶点周边所有邻接顶点
}
}
}
/*
- adjMatrix是待遍历图的邻接矩阵
- value是待遍历图顶点用于是否被遍历的判断依据，0代表未遍历，非0代表已被遍历，其最终具体结果代表该顶点在最终遍历顺序中的位置
- result用于存放广度优先遍历的顶点顺序
- number是当前正在遍历的顶点在邻接矩阵中的数组下标编号
*/
public void bfsVisit(int[][] adjMatrix,int[] value,char[] result,int number){
value[number] = ++count; //出发顶点已被遍历，其在遍历结果中最终位置为++count
for(int i = 0;i < value.length;i++){
if(adjMatrix[number][i] == 1 && value[i] == 0){ //当改顶点与出发顶点相邻且未被遍历时
char temp = (char) (‘a’ + i);
result[count] = temp;
System.out.print(“到达”+temp+“地”+“ ”);
value[i] = ++count; //当前被遍历顶点，其在遍历结果中最终位置为++count
}
}
}
public static void main(String[] args){
int[] value = new int[10]; //初始化后，各元素均为0
char[] result = new char[10];
char[] result1 = new char[10];
int[][] adjMatrix = {{0,0,1,1,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{1,0,0,1,0,1,0,0,0,0},
{1,0,1,0,0,0,0,0,0,0},
{1,1,0,0,0,1,0,0,0,0},
{0,1,1,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,1,0,1,0},
{0,0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,1,0,1,0}};
BreadthFirstSearch test = new BreadthFirstSearch();
test.bfs(adjMatrix, value, result);
System.out.println();
System.out.println(“判断节点是否被遍历结果（0代表未遍历，非0代表已被遍历）：”);
for(int i = 0;i < value.length;i++)
System.out.print(" "+value[i]);
//依据具体顶点在遍历结果顺序中最终位置，计算其具体遍历顺序为result1数组序列
for(int i = 0;i < value.length;i++){
result1[value[i]-1] = (char) (‘a’ + i);
}
System.out.println();
System.out.println(“判断节点是否被遍历结果（0代表未遍历，非0代表已被遍历，其具体数字代表其原地点在被遍历结果中所处位置：）：”);
for(int i = 0;i < value.length;i++)
System.out.print(" "+result1[i]);
System.out.println();
System.out.println(“广度优先查找遍历顺序如下：”);
for(int i = 0;i < result.length;i++)
System.out.print(" "+result[i]);
}
}
算法八：Dijkstra算法
==========================================
戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。
算法步骤：
1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
代码实现：
package com.liuzhen.chapter9;
public class Dijkstra {
/*
- 参数adjMatrix:为图的权重矩阵，权值为-1的两个顶点表示不能直接相连
- 函数功能：返回顶点0到其它所有顶点的最短距离，其中顶点0到顶点0的最短距离为0
*/
public int[] getShortestPaths(int[][] adjMatrix) {
int[] result = new int[adjMatrix.length]; //用于存放顶点0到其它顶点的最短距离
boolean[] used = new boolean[adjMatrix.length]; //用于判断顶点是否被遍历
used[0] = true; //表示顶点0已被遍历
for(int i = 1;i < adjMatrix.length;i++) {
result[i] = adjMatrix[0][i];
used[i] = false;
}
for(int i = 1;i < adjMatrix.length;i++) {
int min = Integer.MAX_VALUE; //用于暂时存放顶点0到i的最短距离，初始化为Integer型最大值
int k = 0;
for(int j = 1;j < adjMatrix.length;j++) { //找到顶点0到其它顶点中距离最小的一个顶点
if(!used[j] && result[j] != -1 && min > result[j]) {
min = result[j];
k = j;
}
}
used[k] = true; //将距离最小的顶点，记为已遍历
for(int j = 1;j < adjMatrix.length;j++) { //然后，将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较，更新最短距离
if(!used[j]) { //当顶点j未被遍历时
//首先，顶点k到顶点j要能通行；这时，当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时，更新顶点0到顶点j的最短距离
if(adjMatrix[k][j] != -1 && (result[j] > min + adjMatrix[k][j] || result[j] == -1))
result[j] = min + adjMatrix[k][j];
}
}
}
return result;
}
public static void main(String[] args) {
Dijkstra test = new Dijkstra();
int[][] adjMatrix = {{0,6,3,-1,-1,-1},
{6,0,2,5,-1,-1},
{3,2,0,3,4,-1},
{-1,5,3,0,2,3},
{-1,-1,4,2,0,5},
{-1,-1,-1,3,5,0}};
int[] result = test.getShortestPaths(adjMatrix);
System.out.println(“顶点0到图中所有顶点之间的最短距离为：”);
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+" ");
}
}
结果：
顶点0到图中所有顶点之间的最短距离为：
0 5 3 6 7 9
算法九：动态规划算法
======================================
动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
关于动态规划最经典的问题当属背包问题。
算法步骤：
1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
代码实现：
package com.hust0328;
import java.util.Scanner;
/
- Created by huststl on 2018/3/28 14:24
- 动态规划题01
*/
public class Dp01 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long max = 0;
int[][] dp = new int[n][n];
dp[0][0] = scan.nextInt();
for(int i=1;i<n;i++){
for(int j=0;j<=i;j++){
int num = scan.nextInt();
if(j==0){
dp[i][j] = dp[i-1][j] + num;
}else {
dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;
}
max = Math.max(dp[i][j],max);
}
}
System.out.println(max);
}
}
算法十：朴素贝叶斯分类算法
=========================================
朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。
朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。
代码实现：
package com.example.psbys;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.net.URL;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;
/
- 朴素贝叶斯
- @author Dyl
*/
public class PSbys {
Vector vector;
int testTotal = 0;// 训练样本数量
int predictTotal = 0;// 测试样本的数据
int predictSucess = 0;// 预测成功的数量
String[] ClassValueName = { “unacc”, “acc”, “good”, “vgood” };
// 数量
int[] ClassValueTotal = new int[4];// unacc-0 acc-1 good-2 vgood-3
int[][] buying_Vlaue = new int[4][4]; // 前面是自己的属性，后面是value的属性
int[][] maint_Value = new int[4][4];
int[][] doors_Value = new int[4][4];
int[][] persons_Value = new int[3][4];
int[][] lugboot_Value = new int[3][4];
int[][] safety_Value = new int[3][4];
// 概率///节约空间
float[] ClassValueTotal_gl = new float[4];// unacc-0 acc-1 good-2 vgood-3
float[][] buying_Vlaue_gl = new float[4][4]; // 前面是自己的属性，后面是value的属性
float[][] maint_Value_gl = new float[4][4];
float[][] doors_Value_gl = new float[4][4];
float[][] persons_Value_gl = new float[3][4];
float[][] lugboot_Value_gl = new float[3][4];
float[][] safety_Value_gl = new float[3][4];
public PSbys() {
vector = new Vector();
}
public static void main(String[] args) throws Exception {
最后
这份文档从构建一个键值数据库的关键架构入手，不仅带你建立起全局观，还帮你迅速抓住核心主线。除此之外，还会具体讲解数据结构、线程模型、网络框架、持久化、主从同步和切片集群等，帮你搞懂底层原理。相信这对于所有层次的Redis使用者都是一份非常完美的教程了。
整理不易，觉得有帮助的朋友可以帮忙点赞分享支持一下小编~
你的支持，我的动力；祝各位前程似锦，offer不断！！！
本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录
需要这份系统化的资料的朋友，可以点击这里获取
.net.URL;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;
/
- 朴素贝叶斯
- @author Dyl
*/
public class PSbys {
Vector vector;
int testTotal = 0;// 训练样本数量
int predictTotal = 0;// 测试样本的数据
int predictSucess = 0;// 预测成功的数量
String[] ClassValueName = { “unacc”, “acc”, “good”, “vgood” };
// 数量
int[] ClassValueTotal = new int[4];// unacc-0 acc-1 good-2 vgood-3
int[][] buying_Vlaue = new int[4][4]; // 前面是自己的属性，后面是value的属性
int[][] maint_Value = new int[4][4];
int[][] doors_Value = new int[4][4];
int[][] persons_Value = new int[3][4];
int[][] lugboot_Value = new int[3][4];
int[][] safety_Value = new int[3][4];
// 概率///节约空间
float[] ClassValueTotal_gl = new float[4];// unacc-0 acc-1 good-2 vgood-3
float[][] buying_Vlaue_gl = new float[4][4]; // 前面是自己的属性，后面是value的属性
float[][] maint_Value_gl = new float[4][4];
float[][] doors_Value_gl = new float[4][4];
float[][] persons_Value_gl = new float[3][4];
float[][] lugboot_Value_gl = new float[3][4];
float[][] safety_Value_gl = new float[3][4];
public PSbys() {
vector = new Vector();
}
public static void main(String[] args) throws Exception {
最后
这份文档从构建一个键值数据库的关键架构入手，不仅带你建立起全局观，还帮你迅速抓住核心主线。除此之外，还会具体讲解数据结构、线程模型、网络框架、持久化、主从同步和切片集群等，帮你搞懂底层原理。相信这对于所有层次的Redis使用者都是一份非常完美的教程了。
[外链图片转存中…(img-mHvHsuCN-08)]
整理不易，觉得有帮助的朋友可以帮忙点赞分享支持一下小编~
你的支持，我的动力；祝各位前程似锦，offer不断！！！
本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/25695.html