Java版算法思想概览：从基础到高级

需积分: 13 107 浏览量更新于2024-07-18 收藏 1.07MB PDF 举报

"《算法思想Java版》是一份详尽的IT学习资料，主要针对编程爱好者和专业人员讲解了算法的基本概念和实践技巧，特别强调了在Java环境中应用这些算法的重要性。内容涵盖了广泛的主题，如： 1. 基础算法：包括二分查找、贪心算法（如快速选择和堆排序）、排序算法（如桶排序和排序算法的实现），以及搜索策略（广度优先搜索BFS和深度优先搜索DFS）。 2. 递归与回溯：Backtracking是一种解决复杂问题的策略，而动态规划则是解决优化问题的有效手段。分割整数和矩阵路径等问题也是在此部分讨论的。 3. 经典数列与问题：如斐波那契数列、最长递增子序列和最长公共子序列，以及经典的背包问题（0-1背包）和数组区间操作。 4. 数学基础知识：涉及素数、最大公约数、进制转换和阶乘等概念，以及字符串处理中的加法减法。 5. 数据结构：深入剖析了栈和队列、哈希表、字符串、数组与矩阵，以及特殊的数据结构如Trie（字典树）和二叉搜索树(BST)。 6. 图论与位运算：层次遍历、前中后序遍历，以及图的表示和操作，位运算在算法中的实用技巧也被提及。 7. 实战例子：如LeetCode中的实例，如求解开方问题(LeetCode第69题)，通过实际编程代码展示了算法在实际场景中的应用。 8. 参考资料：提供了一些权威的在线资源，便于读者进一步深入学习和实践。该资料不仅理论知识全面，而且注重实践，适合想要提升算法能力的Java开发者阅读，无论是初学者还是进阶者都能从中受益。通过这份笔记，读者能够更好地理解和掌握各种核心算法，并将其应用于日常开发工作中。"

2018/3/24 算法思想马克飞象专为印象笔记打造的Markdown编辑器

https://maxiang.io/# 16/120

深度优先搜索和广度优先搜索广泛运用于树和图中，但是它们的应用远远不止如此。

BFS

广度优先搜索的搜索过程有点像一层一层地进行遍历：从节点0出发，遍历到6、2、1和5这四

个新节点。继续从6开始遍历，得到节点4；从2开始遍历，没有下一个节点；从1开始遍历，

没有下一个节点；从5开始遍历，得到3和4节点。这一轮总共得到两个新节点：4和3。反复

从新节点出发进行上述的遍历操作。可以看到，每一轮遍历的节点都与根节点路径长度相同。设d

表示第i个节点与根节点的路径长度，推导出一个结论：对于先遍历的节点i与后遍历的节点j，有

d <=d 。利用这个结论，可以求解最短路径**最优解**问题：第一次遍历到目的节点，其所经过的

路径为最短路径，如果继续遍历，之后再遍历到目的节点，所经过的路径就不是最短路径。在程序

实现BFS时需要考虑以下问题：队列：用来存储每一轮遍历的节点标记：对于遍历过得节点，

应该将它标记，防止重复遍历；**计算在网格中从原点到特定点的最短路径长度**

[[1,1,0,1],

[1,0,1,0],

[1,1,1,1],

[1,0,1,1]]

public int minPathLength(int[][] grids, int tr, int tc) {

int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int m = grids.length, n = grids[0].length;

Queue<Position> queue = new LinkedList<>();

queue.add(new Position(0, 0, 1));

while (!queue.isEmpty()) {

Position pos = queue.poll();

for (int i = 0; i < 4; i++) {

Position nextPos = new Position(pos.r + next[i][0], pos.c + n

ext[i][1], pos.length + 1);

if (nextPos.r < 0 || nextPos.r >= m || nextPos.c < 0 || nextP

os.c >= n) continue;

if (grids[nextPos.r][nextPos.c] != 1) continue;

grids[nextPos.r][nextPos.c] = 0;

if (nextPos.r == tr && nextPos.c == tc) return nextPos.lengt

queue.add(nextPos);

}

return -1;

}

private class

Position

{

int r, c, length;

public Position(int r, int c, int length) {

this.r = r;

this.c = c;

i j

2018/3/24 算法思想马克飞象专为印象笔记打造的Markdown编辑器

https://maxiang.io/# 17/120

this.length = length;

}

DFS

广度优先搜索一层一层遍历，每一层遍历到的所有新节点，要用队列先存储起来以备下一层遍历的

时候再遍历；而深度优先搜索在遍历到一个新节点时立马对新节点进行遍历：从节点0出发开始遍

历，得到到新节点6时，立马对新节点6进行遍历，得到新节点4；如此反复以这种方式遍历新节

点，直到没有新节点了，此时返回。返回到根节点0的情况是，继续对根节点0进行遍历，得到新

节点2，然后继续以上步骤。从一个节点出发，使用DFS对一个图进行遍历时，能够遍历到的节

点都是从初始节点可达的，DFS常用来求解这种**可达性**问题。在程序实现DFS时需要考虑以

下问题：栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。也可以使

用递归栈。标记：和BFS一样同样需要对已经遍历过得节点进行标记。**查找最大的连通面积**

[Leetcode:695.MaxAreaofIsland(Easy)](https://leetcode.com/problems/maxareaof

island/description/)

[[0,0,1,0,0,0,0,1,0,0,0,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,1,1,0,1,0,0,0,0,0,0,0,0],

[0,1,0,0,1,1,0,0,1,0,1,0,0],

[0,1,0,0,1,1,0,0,1,1,1,0,0],

[0,0,0,0,0,0,0,0,0,0,1,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,0,0,0,0,0,0,1,1,0,0,0,0]]

public int maxAreaOfIsland(int[][] grid) {

int m = grid.length, n = grid[0].length;

int max = 0;

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

if(grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));

}

return max;

}

private int dfs(int[][] grid, int i, int j){

int m = grid.length, n = grid[0].length;

if(i < 0 || i >= m || j < 0 || j >= n) return 0;

if(grid[i][j] == 0) return 0;

grid[i][j] = 0;

return dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j +

1) + dfs(grid, i, j - 1) + 1;

}

剩余119页未读，继续阅读

csdnuser405

粉丝: 0
资源: 1

Java版算法思想概览：从基础到高级

概率算法简介 舍伍德算法

图解算法小册-Java版

多态蚁群算法——java版

数据结构与算法-java版本

JAVA版数据结构与算法(JAVA语言版解密)

SVM 算法 java版本

java算法思想-第五章.pdf

K均值聚类算法的Java版实现代码示例

java代码-BM算法java版本

常用排序算法JAVA版

最新资源

概率算法简介舍伍德算法