- 综合排序
- 最热优先
- 最新优先
- 来自专栏mathor
Morris遍历
Morris算法遍历一棵二叉树，时间复杂度O(n)，但是空间复杂度却只用神奇的O(1)，下面说一下Morris遍历的流程，首先规定来到的当前结点即为cur 如果cur无左孩子(cur.left == cur = cur.left) 如果mostRight的右孩子指向cur，则让其指向null(mostRight.right = null)，同时cur向右移动(cur = cur.right) 先序Morris mostRight.right = null; } cur = cur.right; } System.out.println(); } 中序Morris System.out.println(cur.value + " "); cur = cur.right; } System.out.println(); } 后序Morris
51210发布于 2018-08-17 - 来自专栏ccf19881030的博客
KMP（Knuth Morris Pratt）算法的Go语言实现
字符串匹配 BF(Brute force)算法 实现：每次向后移动一位进行匹配 RK(Rabin-Karp)算法 实现：将每组要匹配长度的字符串进行hash，再hash后的元素里找 BM(Boyer-Moore )算法 有两部分组成：并且是由大到小，倒着匹配 坏前缀：普通匹配只一位一位移动，移动规则为 si(坏字符的位置) xi(坏字符在匹配字符最后出现的位置) 都没有xi=-1 移动距离等于si-xi KMP（Knuth Morris Pratt）算法 实现：关键部分next数组，失效函数。next数据就是匹配串字符串最长匹配前缀和最长匹配后缀的关系。 KMP算法的Go语言实现代码如下： package main import "fmt" func main() { a := "ababaeabacaaaaaddfdfdfdfdf"
1.1K40发布于 2020-10-28 - 来自专栏听雨堂
Morris图表使用小记
挺好用的，碰到几个问题，有的是瞎试解决了的： 1、我想折线图能够响应单击事件，即点击某个节点后，就能加载进一步的信息，帮助没找到，参照另外一个地方的写法，居然支持事件 Morris.Line JSON.parse(data) loadMonth(obj.mon) }}); }); 2、 文字大小调整，hoverFontSize，设置了不太管用，有些浏览器支持有些不行，关键是，微信小程序的浏览器不行，于是改了两个地方： 1）morris.css中的样式，改了似乎用处不大 2）分析页面，找到样式 ，直接用jquery设置 $(".morris-hover morris-default-style").css({"font-size":"24px"}); 大概效果如下，手机中看起来不错。
1K80发布于 2018-01-23 - 来自专栏c++与qt学习
二叉树遍历高级算法之Morris---莫里斯算法
莫里斯算法与线索二叉树有异曲同工之妙，建议先了解线索二叉树，再来学习 ---- Morris算法 莫里斯算法思想 前序遍历 中序遍历 后序遍历 ---- 莫里斯算法思想 mirror遍历用到了线索二叉树的思想 ,在Morris方法中不需要为每个节点额外分配指针指向其前(predecessor）和后继节点（successor）,只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了 。 Morris的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接 我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕 到此为止，左子树部分就已经处理完毕了，下面右子树 总结: 连接过程:先连接后左移 复原过程：先右移后斩断，若斩断位置到位，立刻执行斩断，如果位置不到位，通过while循环到达指定位置 前序遍历 Morris 比如返回到 ２，此时打印 ４ 比如返回到 １，此时打印 ５ ２ 比如返回到 ３，此时打印 ６ 那么我们只需要将这个单链表逆序输出即可。
1.3K30发布于 2021-11-15 - 来自专栏golang算法架构leetcode技术php
golang 刷leetcode：Morris 遍历
示例 1： 输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [1] 输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 空间复杂度O（1）完成中序遍历Morries遍历 过程： 1，如果左孩子非空，让左孩子的最右节点指向根节点得到左孩子的最右节点 2，如果最右节点的右孩子节点是null，说明是第一次遍历，把它的右孩子指向根节点
28110编辑于 2022-08-02 - 来自专栏深度学习
【数据结构】数组和字符串（十五）：字符串匹配2：KMP算法（Knuth-Morris-Pratt）
字符串匹配可以采用多种算法，包括朴素模式匹配算法、KMP（Knuth-Morris-Pratt）算法、Boyer-Moore算法等。 在最坏情况下，该算法要匹配n-m+1次，每次匹配要做m次比较。本文将介绍更高效的模式匹配算法——KMP算法 1. ADL语言 2. KMP算法分析 待完善 3. result2 = kmpPatternMatching(S, P, &comparisons); if (result2 ! = -1) { printf("KMP算法：模式串在目标串中的位置: %d\n", result2); } else { printf("未找到匹配\n"); 失败函数答案 例2 例3
23810编辑于 2024-07-30 【Leetcode】144.二叉树的前序遍历（非递归，Morris算法）
Morris算法 这个算法每个结点需要遍历2次，所以时间复杂度要比之前两种高一些，但是空间复杂度仅为 O(1) 。 盗了一张示意图，出处见水印。 算法核心为：每个结点要经过两遍，第一次经过要找出当前结点左子树的最右结点的位置，然后把它的右指针指向自己；第二次经过时会发现它左子树的最右结点已经指向了自己，说明左子树已经全部遍历完，通过最右结点的右指针走了回来
28410编辑于 2025-08-27深入解析 Knuth-Morris-Pratt 算法：字符串匹配的高效解决方案
kmp算法 这篇文章主要是总结一下kmp算法。所以就不写暴力遍历的逻辑了。 首先，kmp算法主要是用来判断模式串是否在文本串中出现过，如果出现过，则返回最早出现的位置的经典算法。 该算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，算法也是由这三人姓氏进行命名。 我们就可以总结一个规律，不仅前面是0，如果前面一个字符的next值是1，那么我们就把当前字符与子串第二个字符进行比较，因为前面的是1，说明前面的字符已经和第一个相等了，如果这个又与第二个相等了，说明对称程度就是2了 比如上面agctag，倒数第二个a的next是1，说明它和第一个a对称了，接着我们就把最后一个g与第二个g比较，又相等，自然对称程度就累加了，就是2了。
49420编辑于 2024-07-29- 来自专栏LeetCode
二叉树的Morris遍历
一、中序遍历 public static void morrisIn(TreeNode root) { if (root == null) return; TreeNode cur = root; TreeNode mostRight = null; while (cur != null){ if (cur.left != null){ mostRight = cur.left; while (mostRight
46230发布于 2019-02-25 - 来自专栏思考与总结
Golang实现一个可存放重复元素的二叉搜索树，结合Morris算法
在学习二叉树的遍历的时候，有一个大名鼎鼎的Morris算法，使用双指针就可以实现二叉树的前中后序遍历，并且时间复杂度是O(N)，空间复杂度是O(1)，于是我使用Golang实现一个可存放重复元素的二叉搜索树 ，并且结合Morris算法进行查找。 res.Val) return node } // 获取中序遍历的结果, 就知道是否是有序的 func (this *Bst_1) GetSortedSequence() []int { // Morris 算法 res := []int{} p1 := this.root var p2 *TreeNode for p1 ! = nil { p2 = p1.Left if p2 != nil { for p2.Right != nil && p2.Right !
42110编辑于 2024-03-06 - 来自专栏技术总结
算法（2）
有两个算法 A 和 B ，假设两个算法的输入规模都是 n，算法 A 要做 2n+3 次操作，算法 B 要做 3n+1 次操作。觉得谁快？看下图： ? 而当 n = 2 时，两者效率相同；当 n > 2时，算法 A 就开始优于算法 B 了，随着 n 的增加， 算法 A 比算法 B 越来越好了，得出结论，算法 A 好过 算法 B 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略 2、在修改后的运行次数函数中，只保留最高阶项。 3、如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶 3、常数阶 高斯算法，时间复杂度不是O(3)，而是O(1)。 //第二种算法 int sum = 0, n = 100; /*执行1次*/ sum = (1 + n) * n/2; /*执行1次*/ printf( 也就是说，有多少个2相乘后大于n,则会退出循环。由2× = n ，得到 x = ㏒2n (2缩小)。所以这个循环的时间复杂度为O(㏒n)。
1.1K90发布于 2018-05-22 - 来自专栏AngelNI
排序算法-2
start++] =arr[p]; } } void mergesort(ll *A,ll start,ll end) { if(start<end) { ll mid = (start+end)/2; = a[i]; a[i] = a[j]; a[j] = t; } void heapify(ll *tree,ll n,ll i) { if(i>=n) return ; ll c1 = 2* i+1; ll c2 = 2*i+2; ll max = i; if(c1<n&&tree[c1]>tree[max]) { max = c1; } if(c2<n&&tree[c2]> tree[max]) { max = c2; } if(max ! = i) { swap(tree,max,i); heapify(tree,n,max); } } void heapsort(ll *a,ll n) { for(ll i =n/2-1;
30610发布于 2020-04-14 - 来自专栏修也的进阶日记
算法手记2
NC296 最小花费爬楼梯 牛客网题目链接(点击即可跳转):NC296 最小花费爬楼梯 题目详情: 本题详情如下图: 题目思路: 本题解题思路如下: 基础动态规划,1.写出动态转换方程2. vector<int>& cost) { vector<int> dp; dp.resize(cost.size()+1); for(int i=2; i<=cost.size();i++) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); return dp[cost.size ()]; } }; 结语 说点啥好呢...不断修补细节然后提高效率,不断学习算法并应用出肌肉记忆.
13200编辑于 2025-03-14 - 来自专栏Article
算法 Day 2
冒泡排序 平均时间复杂度 O(n2) 空间复杂度 O(1) function bubbleSort(arr) { var i = arr.length; var position =
13010编辑于 2022-06-14 - 来自专栏云深之无迹
Python 算法.2
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合? + b**2 == c**2 and a+b+c == 1000: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time + b**2 == c**2: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time = time.time() print("elapsed (nlogn) < O(n2) < O(n3) < O(2n) < O(n!) = Timer("test2()", "from __main__ import test2") print("append ", t2.timeit(number=1000), "seconds")
57630发布于 2021-04-28 - 来自专栏数据云团
算法篇-python排序算法-2
让指定的元素归位，就是放到它应该放的位置（左边元素比它小，右边元素比他大），然后对每个元素归位，完成排序。
65330发布于 2019-07-18 - 来自专栏码农帮派
LeetCode中级算法-回溯算法（2）
子集 [题目] 给定一个不包含重复元素的数组，返回该数组所有可能的子集 [输入] [1,2,3] [返回] [[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]] [解法 所以我们在回溯index元素的时候，可以根据这两种状态分别进行回溯 [代码实现] package main import "fmt" func main() { input := []int {1,2,3 [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"], ] [输入1] "ABCCED" [返回1] true [输入2] "ABCS" [返回2] false [解法] 这个题目的解点是第i个元素的上下左右是不是下一个元素，遍历整个字符串，当遍历到第i个字符串的时候，需要在上一个字母的坐标周围(上下左右)找到第i个字母
48620发布于 2021-01-12 - 来自专栏强化学习专栏
聚类算法（2）--- ISODATA算法
文章分类在AI学习笔记： AI学习笔记（8）---《聚类算法（2）--- ISODATA算法》 聚类算法（2）--- ISODATA算法 一、 ISODATA算法 ISODATA 其他聚类算法见： 聚类算法（1）---最大最小距离、C-均值算法 1.1算法原理 SODATA算法采用迭代的方式动态地更新簇的数目和簇的中心，根据设定的参数来调整簇的数量以及样本点与簇之间的距离等 （4）簇分裂：重复执行步骤2和步骤3，直至满足终止条件（如簇中心不再发生大的变化、达到最大迭代次数等）。 算法注意事项 ISODATA算法相比于传统的K-means算法增加了簇合并和簇分裂的步骤，这使得算法能够动态地调整簇的数量和形状，适应数据的复杂性。 三、 ISODATA算法实验结果 相关参数设置： 参数类型 数值 预期的聚类数 2 初始聚类中心个数 3 每类的最小样本数 3 标准差阈值 0.1 最小中心距离 2 每次可合并的最多对数 3 迭代次数
51910编辑于 2024-12-03 《算法导论》第 2 章 - 算法基础
大家好，今天我们来一起学习《算法导论》的第 2 章 —— 算法基础。 2.2 分析算法 分析算法的目的是预测算法的资源消耗，以便比较不同算法的性能。在大多数情况下，我们最关心的是算法的运行时间。 算法分析： 求解递归式 T (n) = 3T (n/2) + n^2 求解递归式 T (n) = T (2n/3) + 1 实践题： 实现一个版本的归并排序，当子数组的规模小于某个阈值时，改用插入排序 理解不同算法的优缺点和适用场景，是成为一名优秀程序员的重要一步。 希望这篇学习笔记能帮助你更好地理解《算法导论》第 2 章的内容。 以上就是《算法导论》第 2 章的全部学习内容。通过理论学习和代码实践相结合的方式，相信大家已经对算法基础有了更深入的理解。
10510编辑于 2026-01-21- 来自专栏Initial programming
初识算法 · 分治(2)
库存管理 III - 力扣（LeetCode） 题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。 那么直接进入算法原理部分咯。 算法原理 在前文我们知道，我们利用三个指针，将数组划分成了三个区域，分别是小于K的，等于K的，大于K的，那么我们要在该区域里面查找到第K个最大的元素，其实当我们划分好了区域之后，我们不妨分情况讨论，对于第三个区域 算法编写 class Solution { public: int GetRandom(vector<int>& v, int left, int right) { 题目的基本思路都是一样的，我们直接进入算法原理部分吧， 算法原理 其实对于这道题的解法非常多的，可以直接排序，然后返回，时间复杂度是N* LogN，也可以使用大小堆，时间复杂度是N * logK，但是都没有
23910编辑于 2024-11-26
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号