Java编程

动脑学院javavip

快速排序是最经典的排序算法,在这一章,我们将由浅入深,从最基本的快排算法开始讲解,逐步掌握快速排序的基本思想。

叉树是数据结构中难度最大的没有之一,如何实现一个二叉树结构并对它遍历难于上青天,学完这个章节会让你牢牢掌握二叉树的基础知识。

课程主要包括的内容有:线性表,栈与队列,字符串,二叉树,树,图,排序(内排序,外排序),检索,索引,高级数据结构、以及数据结构应用。课程持续16周(分为两个部分,每个8周),学习者每周在本课程上需要投入4-8小时。在第一部分学完了线性表、栈与队列、字符串、二叉树、树和图这些基础数据结构之后,第二部分我们将深入学习排序、检索、索引、高级数据结构以及数据结构应用等内容。涉及快速排序、外排序等各种经典排序算法,集合、散列、位图等检索方法,B/B+树、Trie树等索引结构,广义表、多维数组等高级线性结构,AVL、红黑树、伸展树等平衡二叉树。第二部分课程持续8周,学习者每周在本课程上需要投入4-8小时。本课程的本次开设得到Google研究经费支持。

动脑学院javavip

算法 – Algorithms排序算法:快速排序、归并排序、计数排序搜索算法:回溯、递归、剪枝技巧图论:最短路、最小生成树、网络流建模动态规划:背包问题、最长子序列、计数问题基础技巧:分治、倍增、二分、贪心数据结构 – Data Structures数组与链表:单 / 双向链表、跳舞链栈与队列树与图:最近公共祖先、并查集哈希表堆:大 / 小根堆、可并堆字符串:字典树、后缀树对于上面总结的这部分内容,力扣(LeetCode)已经为大家准备好了相关专题,等待大家来练习啦。

冒泡排序(Bubble Sort)冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法和复杂优化:这对理解我们的机器学习算法的计算效率和可扩展性以及利用我们的数据集中稀疏性很重要。需要的知识有数据结构(二叉树、散列、堆、栈等)、动态规划、随机和子线性算法、图论、梯度/随机下降和原始对偶方法。

推荐理由:本书首先介绍了JavaScript语言的基础知识,接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构,之后探讨了各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索,还介绍了动态规划和贪心算法等常用的高级算法及相关知识。

另外,我们在时间复杂度分析的时候也了解到,有时序列已经排列好了,但是冒泡排序还在重复地遍历,而这时的遍历是不必要的。我们设想一下,如果在当前这趟遍历时,没有元素发生交换,那就说明排序已经完成,因此后面就不需要再进行排序了。通过设置标记或旗帜的方法来改进的思路如下:

在这一周,我们将接触两个最基础的排序算法:选择排序法和插入排序法。虽然这两个排序算法很简单,但在这一周,我们将巩固我们之前学习的知识,将循环不变量的思路和复杂度分析应用在这些算法中。

/** [530] 二叉搜索树的最小绝对差* 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。* 示例 :* 输入:** ⁠ 1* ⁠ \* ⁠ 3* ⁠ /* ⁠ 2** 输出:* 解释:* 最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。* 注意: 树中至少有2个节点。*/class Solution {public int getMinimumDifference(TreeNode root) {// 中序输出之后,就是从小到大的排序数组inOrder(root);// 遍历数组,找出相邻结点差值最小的值,即是题目所求的值int min = Integer.MAX_VALUE;for (int i = 0; i < list.size() - 1; i++) {if (Math.abs(list.get(i + 1) - list.get(i)) < min)min = Math.abs(list.get(i + 1) - list.get(i));}return min;}ArrayList list = new ArrayList<>();// 中序遍历以node为根的二分搜索树, 递归算法private void inOrder(TreeNode node) {if (node == null)return;inOrder(node.left);list.add(node.val);inOrder(node.right);}}判定二叉树是否包含关系这里想到的是递归比较每个节点,还有个思路是把两个二叉树作层序遍历,如果是包含关系,那么被包含的二叉树的层序遍历结果一定是另一个二叉树层序遍历的子集。

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注