8 Storm-Shadow

尚未进行身份认证

我要认证

道法自然

等级
TA的排名 1w+

在接近有序的数组中查找指定元素

给定一个排好序的整型数组,将数组中的个别相邻的两个元素互换,如元素arr[i]只能和arr[i-1]或arr[i+1]互换,现要求在打乱顺序后的数组中查找指定元素。例如Input: arr[] = {10, 3, 40, 20, 50, 80, 70}, key = 40Output: 2 Output is index of 40 in given arrayInput: arr[] = {10, 3, 40, 20, 50, 80, 70}, key = 90Output:

2020-09-15 14:11:22

字符串的模式匹配 KMP Algorithm

本章讨论的是基于KMP算法(KMP即Knuth-Morris-Pratt)的串的模式匹配问题,什么是模式匹配,请参考前一章字符串的模式匹配 Pattern Searching。查找算法实例让我们用一个实例来演示这个算法。在任意给定时间,本算法被两个整数m和i所决定:m代表主文字符串S内匹配字符串W的当前查找位置, i代表匹配字符串W当前做比较的字符位置。图示如下:我们从W与S的开头比较起。我们比对到S[3](=' ')时,发现W[3](='D')与其不符。接着并不是从..

2020-09-15 14:07:10

字符串的模式匹配 Pattern Searching

字符串的模式匹配是计算机中应用非常广泛的一个问题,在浏览器、数据库等查询中,都需要用到模式匹配。问题描述:给定两个字符串txt[0..n-1]和pat[0..m-1],试查找txt中pat子串所在的所有位置,假设n>m。例如:Input: txt[] = "THIS IS A TEST TEXT" pat[] = "TEST"Output: Pattern found at index 10Input: txt[] = "AABAACAADAABAABA"

2020-09-15 13:56:25

用户隐私政策

你的隐私对我们而言至关重要。因此,我们制定了本隐私政策,其中说明了我们如何收集、使用、披露、转让和存储你的信息。请你仔细阅读我们的隐私政策,如有任何问题,请告知我们。个人信息的收集和使用个人信息是可用于唯一地识别或联系某人的数据。你与我们或某一我们关联公司联系时,可能会被要求提供你的个人信息。我们及其关联公司可互相分享此个人信息,并按本隐私政策使用该信息。我们及其关联公司还可将此信息与其他信息合并在一起,用于提供和改进我们的产品、服务、内容和广告宣传。下文是我们可能收集的个人信息的类型.

2020-08-23 15:47:08

把二叉树转化成BST

给定一棵二叉树,请把它转化成 Binary Search Tree(BST),且不能改变原二叉树的形状。如下是两个转化示例解:我们可以通过三大步骤完成转化(1)创建一个辅助数组 arr[],然后中序遍历原二叉树,把各节点存放到 arr[] 中,这一步时间复杂度为 O(n);(2)对 arr[] 进行升序排序,这一步的时间复杂度和具体的排序算法有关,快速排序是 O(n^2),堆排序或归并排序是 O(nLogn);(3)再次中序遍历原二叉树,在遍历的过程中,把数组 arr[] 中的元素依

2020-08-10 16:38:23

在BST中删除指定范围之外的节点

给定一棵 Binary Search Tree(BST)和一个范围 [min, max],请把 BST 上所有在 [min, max] 范围之外的节点都删除掉,且保持删除节点后的新树仍是 BST。如下是一棵 BST,给定范围为 [-10, 13]在删除掉所有在 [-10, 13] 范围之外的节点后,得到的新 BST 如下解:对 BST 上的每个节点,有两种情况(1)节点在给定范围外,这种情况还可再细分两种情况(a)节点小于 min;(b)节点大于 max;(2)节点在给.

2020-08-10 15:50:01

在BST中查找节点最多的子BST

给定一棵二叉树,试设计算法在这棵二叉树中寻找节点最多的 BST(Binary Search Tree),如果整棵二叉树本身就是一棵 BST,那么返回整棵树的节点数量。如下是几个例子解法一:可以从根节点开始遍历整棵二叉树,对每个节点,检查以它为根的子树是否是 BST,如果是,那么返回其节点数量,否则递归遍历其左、右子树并返回其左、右子树中节点最多的 BST。这种算法复杂度为 O(n^2),关键算法如下/* max() returns maximum of two integers

2020-08-10 15:45:35

求BST中第K个最小的元素

给定一棵 BST,请在这棵 BST 上查找其对应的升序序列中的第 k 个元素(即第 k 小元素)。如下图的 BST,如果 k=3,那么所求节点为 10,如果 k=5,那么所求节点为 14。解法一:中序遍历法,我们用一个栈作为辅助进行中序遍历,在遍历过程中,对出栈次数进行计数,出栈 k 次时即找到我们要的节点。算法复杂度为 O(n),n 为树的节点总数,算法描述如下:/* initialization */pCrawl = rootset initial stack element

2020-07-16 13:47:43

中序遍历BST的算法及实现

问题描述:在二叉树中,一个节点的后续是在中序遍历过程中,在它之后访问的下一个节点,如果某节点是中序遍历的最后一个节点,那么它的后续为 NULL。在 BST 中,给定节点的后续节点就是大于该节点的最小结点,这个性质对于查找比某元素大的下一个元素时非常有用。如上图,8 的后续是 10,10 的后续是 12,14 的后续是 20。现给定一个节点,请设计算法查找中序遍历中,该节点的后续节点。解法一:使用双亲指针这种解法需要每个节点都有指向双亲的指针,算法可分成两种情况来处理:(1).

2020-07-15 15:59:38

在树中求两个结点的最近共同祖先(LCA,即Lowest Common Ancestor)

问题描述:首先定义一个术语 LCA(Lowest Common Ancestor):设 T 为一棵树,n1 和 n2 都存在于 T 中,n1 和 n2 的 LCA 为离它们两最近的共同祖先(一个节点的祖先可以是它自己)。n1 和 n2 的最近共同祖先,也是它们的共同祖先中,离树根最远的那个节点。如下图是一棵二叉树图中,10 和 14 的 LCA 是 12,8 和 14 的 LCA 是 8。两节点的 LCA 是非常有用的,例如两节点 n1 和 n2 的距离,等于根节点到 n1 的距离加上等于根

2020-07-15 09:36:40

在BST树中查找指定 key 的中序遍历的先驱和后续节点

问题描述:给定一棵 BST,其根节点指针为 root,节点结构如下:struct Node{ int key; struct Node *left, *right ;};现要求在这棵 BST 查找指定 key 的中序遍历的先驱和后续节点,如果不存在,那么请返求 key 应该位于哪两个节点之间。解:下面是解决这个问题的算法描述Input: root node, keyoutput: predecessor node, successor node1. I.

2020-07-15 09:31:15

二叉搜索树(Binary Search Tree)的删除操作及实现代码

本节我们主要讨论 BST 中的一个基本操作 Delete,在进行删除操作的时候,会遇到以下三种情况:(1)要删除的叶子节点,这种情况,我们只需要直接的把节点删除掉即可。(2)要删除的节点有且仅有一个孩子节点,这种情况,我们把要删除节点的孩子节点的内容复制到要删除的节点上(即替换要删除节点的内容),然后再把孩子节点删除掉即可。(3)要删除的节点既有左孩子,又有右孩子,这种情况,我们要先找到中序遍历时,要删除节点的后续节点(也可以用先驱节点),然后把这个后续节点的内容复制到要删除节点上.

2020-07-09 16:31:54

二叉查找树即Binary Search Tree的查找和插入

我们简单讨论了 BST 的基本特性和操作。本章我们主要讨论 BST 中的两个基本操作 Search、Insertion。1. Search a key在 BST 中查找指定的 key,我们先把要查找的 key 和 root 节点比较,如果相等,则返回 root,否则如果 key 大于 root,那么我们递归的在右子树中查找,否则递归的在左子树中查找。C 实现struct node* search(struct node* root, int key){ // Bas.

2020-07-06 17:09:06

二叉搜索树(Binary Search Tree)

1.二叉查找树简介二叉查找树,即 BST(Binary Search Tree),也称二叉搜索树、有序二叉树(rdered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:(1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)任意节点的左、右子树也分别为二叉查找树;(4)没有键值相等的节点。二叉查找树相比于其他数据结.

2020-07-03 17:23:31

使用 AES 对称加密算法对视频文件进行加密解密(C++ 及 Java 实现)

因为项目需要,最近学习了一下 AES 加密算法,并分别用 C++ 和 Java 实现了这个算法。用 Java 实现是因为在 Android 项目上,需要对视频文件进行 AES 加密解密,用 C++ 实现是因为服务器需要对被加密过的视频进行解密。对视频文件进行加密解密的规则非常简单,加密时以 byte[] 的形式读取视频文件开头的一小段数据,一般 256byte 就足够了,然后对这个 byte[] 进行 AES 加密,把得到的密文替换到视频文件开头的 256byte 就可以了。因为视频文件的头被加密了,所

2020-07-03 10:09:07

十一、FFmpeg视频播放时的缩放

视频播放画面的缩放主要是通过libswscale这个库来实现。我们将用来缩放的基本函数是sws_scale。但一开始,我们必需定义一个SwsContext的结构体,然后把它传递给sws_scale函数。类似于在SQL中的预备阶段或者是在Python中编译的规则表达式regexp。要获取这个SwsContext,我们得通过sws_getContext函数,它的参数有:源的宽度和高度,我们想要的宽度和高度,源的格式和想要转换成的格式,同时还有一些其它的参数和标志。然后我们像使用img_convert一样来使

2020-06-25 14:30:54

十、FFmpeg视频播放之快进快退

1、处理快进快退(seek)命令本章我将给大家讲解怎么给我们的播放器添加快进、快退、定位功能,这也是几乎所有播放器都有的功能。为实现此功能,我们要用到av_seek_frame函数,这个函数非常简单易用。我们用键盘上的左右键分别表示向前和向后跳转一小段,类似的用向上和向下键表示跳转一大段。 这里的一小段是10 秒,一大段是60 秒。为此要在主循环监听键盘事件。但是在捕捉到键盘事件后不能直接调用av_seek_frame函数,我们要在主要的解码循环,decode_thread循环中处理这些事件

2020-06-25 14:16:29

八、FFmpeg把音频流同步到视频流

1、同步音频现在我们已经有了一个比较像样的播放器了,最后让我们再来看一下剩下的一些简单的细节。在上章中我们说过也可以把音频同步到视频的,本章我们就来实现这个功能。这和把视频同步到音频是类似的:用一个内部视频时钟记录视频线程播放了多久,然后把音频同步到这个时钟上。最后我们再会进一步推广,把音频和视频都同步到外部时钟。2、实现视频时钟首先我们要实现一个类似音频时钟的视频时钟:一个给出当前视频播放时间的变量。可能你觉得这和使用上一帧的PTS来更新定时器一样简单。但是要注意了,当我们把视频帧间的时.

2020-06-25 13:54:13

七、FFmpeg把视频流同步到音频流

1、如何同步视频直到现在,我们的视频播放器还几乎无法正常工作,虽然它能播放视频,也能播放声音,但是声音和视频还没同步。那么现在我们要怎么做呢?2、PTS和DTS的作用音频流和视频流信息里面,都有一些信息用于表明应该以多快速度和什么时间来播放它们。音频流有采样率,视频流有帧率。但是如果只是简单的通过数帧和乘以帧率的方式来同步视频,那么同步很可能会出问题。为了可以实现同步,在流中的数据包中有解码时间戳(DTS)和显示时间戳(PTS)。要理解这两个参数的作用,得先了解电影的存储方式。像MPEG等.

2020-06-25 13:16:47

六、FFmpeg-优化音频解码播放流程

一、音频解码播放概述前面我们用SDL处理了音频流,SDL会启动一个线程监听音频回调函数。本章中,我们仿照音频的处理方式来处理视频的显示。这样会使得代码更加模块化,易于开发维护。到我们对音视频进行同步时,这种模块化会使得同步的实现会非常方便。那我们从哪开始呢? 现在主函数处理的事情太多了:事件循环、读数据包、解码视频等。所以我们首先要做的是把这些处理抽离出来:创建一个专门用于解码数据包的线程,然后根据数据包的类型,把它们写入音频或视频队列中,再由相应的音频和视频线程读取。音频处理线程我们已经实现过了。

2020-06-25 12:34:55

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享宗师
    分享宗师
    成功上传21个资源即可获取