- 博客(92)
- 收藏
- 关注
RSS订阅原创 146. LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。// 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}// 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}// 缓存是 {1=1, 2=2}// 返回 -1 (未找到)lRUCache.get(1);// 返回 -1 (未找到)lRUCache.put(1, 1);// 缓存是 {1=1}lRUCache.get(1);
2023-11-17 07:48:22
717
原创 leetcode-28. 实现 strStr()-20220829-KMP算法
leetcode-28. 实现 strStr()-20220829-KMP算法
2022-08-29 23:37:05
994
原创 算法导论-----二叉搜索树
一 二叉搜索树定义二叉搜索树是一个二叉树，满足如下性质：对于二叉搜索树中一个随机非叶子结点x，其中x的关键值大于（等于）x的左孩子的关键值，x的关键值小于（等于）右孩子的关键值。二 二叉搜索树的遍历二叉搜索树的中序遍历是先遍历左子树，然后是根节点，然后是右子树。遍历结果是一个从小到大的顺序序列。三 查找最小结点和最大结点根据二叉搜索树的性质，最小节点是在结构的最左侧结点，最大节点是在结构的最右侧结点查找最小结点算法如下： FIND_MIN(T) r = T.root While(r.l
2021-09-27 08:28:37
190
原创 算法导论-----散列表
一 散列表产生背景散列表是根据数组可以直接随机访问的特性产生的。这样就可以在一定情况下，通过散列函数和很小的数组结构，对数据进行组织，实现在最坏情况下查找为O(n)，平均情况下O(1)的算法。二 散列表组成散列表是由散列函数和映射以后的数据存储结构组成的。散列函数先将原始数据通过计算得到一个散列值，然后再将散列值存储到存储结构中但是散列函数面对不同的原始值，可能计算出相同的散列值，这种情况成为冲突，解决冲突的办法有两种：1、链接法：将数据存储结构申请为指针数组，如果有相同的散列值，将相同的散列值
2021-09-19 10:28:08
139
原创 算法导论---基数排序和桶排序
一 基数排序1.1 算法思想对一个包含n个d位的输入数组A，我们需要输出它的某种排列顺序。此时我们对这个数组中所有的数按照从最低位开始，先将最低位的数排序一遍，然后是倒数第二低的数再排序一遍，依次循环，将所有的d位的数排序一遍以后，就可以得到排好序的输出序列。子过程对d位中某一位进行排序的时候，选择排序算法很重要，这个会影响整个基数排序算法的性能。二 桶排序2.1 桶排序思想首先，桶排序的先决条件是输入数组均匀分布或者大致均匀分布在某一个区间上。桶排序思想就是对输入数组中数分布的区间进行划分，
2021-09-16 07:52:26
111
原创 算法导论-----计数排序
一 计数排序预置条件首先知道待排序的所有元素中的最大值，同时待排序元素是正常的大于等于 0 的正整数二 计数排序算法思想排序算法就是要找到当前的待排序元素在输出数组中的位置在那，然后将待排序元素放到输出数组中即可所以计数排序的基本思想就是对一个元素，我通过计算的方式找到该元素在输出数组中的位置，然后放到输出数组中，这样排序就完成了。三 算法伪代码COUNTING-SORT(A, B, k) // 其中k 是A数组元素中的最大值 let C[0, k] be a new array for
2021-09-15 08:22:27
110
原创 算法导论----快速排序
一 快速排序思想基本思路还是根据分治法的思想得出的。首先给定一个数组，然后在数组中选择一个值作为划分标记，然后将数组中剩余的值与这个标记值进行比较，大于标记值的放到标记值右边，小于标记值的放到标记值左边，这个过程就是一次划分过程，然后对标记值左边小于标记值的子数组再进行上述划分，对右边大于标记值的子数组也进行上述划分，实际上就是递归过程，直到最后递归完成，那么快速排序也就完成了。二 快速排序算法实现2.1 总体算法实现 QUICKSORT(A, p, r) if (p < r
2021-09-14 08:27:16
273
原创 算法导论------堆排序
一 堆定义堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。如下所示：二 堆的性质假设堆是使用数组进行存储的，那么对于堆中的节点 i ，其对应的相关性质如下：PARENT(i) = i / 2 // 父节点计算LEFT(i) = i * 2 // 左孩子节点计算RIGHT(i) = i * 2 + 1 // 右孩子节点计算三 最大堆和最小堆3.1 最大堆性质最大堆的简单概括就是堆中任意一个节点的父节点，都比该任意节点的值要大。即：PA
2021-09-13 08:12:26
122
原创 19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */// 方法一 两趟循环 或者用栈也可以，栈和两趟循环类似，不多说了struct ListNode* removeNthFromEnd(struct ListNod
2021-08-13 08:24:03
57
原创 96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。这个题目是非常典型的动态规划题目，先不说官方题解中后面推导出来的什么数学上的卡特兰数，就前面的动态规划推导过程和思路讲解，我感觉就是非常好的一个解决思路，值得学习。代码实现比较简单，重点是前面的推导思路。推导思路：解题代码：int numTrees(int n){ if (n == 0 || n == 1) { return 1;
2021-07-10 17:44:10
54
原创 404. 左叶子之和
计算给定二叉树的所有左叶子之和。示例：3/ 9 20/ 15 7在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sum-of-left-leaves著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法：递归解法：/** * Definition for a binary tree node. * struct TreeNode {
2021-07-10 10:34:41
37
原创 64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。示例 2：输入：grid = [[1,2,3],[4,5,6]]输出：12来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-path-sum著作
2021-06-04 08:15:49
69
原创 62. 不同路径---动态规划
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7输出：28示例 2：输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。向右 -> 向下 -> 向下向下 -> 向下 -> 向右向下 -> 向右 ->
2021-05-28 08:06:25
146
原创 二叉树的遍历算法
题目：给定一个二叉树的根节点 root ，返回它的 中序 遍历中序遍历定义：给一个二叉树的节点，先遍历二叉树的左子树，然后遍历根节点，然后访问二叉树的右子树解法：1.递归遍历，隐形的维护了一个栈递归遍历算法比较简单，因为二叉树本身的建立也是通过递归进行建立的。所以二叉树的子树也是二叉树，根据这个思想，遍历算法如下：1）访问二叉树的左子树2）访问根节点3）访问二叉树的右子树伪代码如下：mid_printf_binary_tree(root) {mid_printf_binary_tree
2021-05-13 22:23:26
194
原创 Line 207: Char 3: runtime error: load of null pointer of type ‘int‘ [__Serializer__.c]
这个错误实在leetcode上刷题的时候出现的根因：由于返回了空指针，然后被用 free()函数释放了空指针，所以导致上面的问题出现解决方案：返回一个用malloc申请的指针变量即可解决
2021-05-11 21:41:50
1632
1
原创 linux设备驱动详解
第九章 异步通知机制主要说下代码：：我测试的内核环境是 5.4.311.globalfifo程序代码实现如下：#include <linux/module.h>#include <linux/types.h>#include <linux/fs.h>#include <linux/errno.h>#include <linux/mm.h>#include <linux/sched.h>#include <lin
2021-02-21 08:16:25
429
原创 linux设备驱动开发详解
第七章 linux设备驱动中的并发控制在linux驱动中，涉及两个应用程序读写一个进程设备的情况，这个时候就需要进行相关操作，因为设备是临界区资源，如果不进行相关保护，就可能出现错误。提供的保护就是设置对linux设备的并发控制。linux提供的并发控制如下：1.自旋锁自旋锁不能用于出现阻塞的情况下，容易出现死锁的问题。2.信号量信号量可以使用在大部分情况下，但是3....
2021-02-20 07:47:04
139
原创 第八章 linux设备驱动驱中的阻塞与非阻塞
1.驱动程序中的阻塞与非阻塞的概念阻塞机制：当当前设备不可用的时候，驱动程序设置当前进程进行休眠状态，同时添加当前进程当等待队列中去，然后让出CPU，让其他的进程进行执行。当当前进程执行的条件满足以后，通过一个唤醒信号，将等待队列中等待的进程唤醒，然后继续执行当前进程。非阻塞机制：当当前设备不可用的时候，驱动程序设置当前进程一直轮询当前的设备状态，一直到设备状态可以执行操作为止。这个里面要参照书里面关于阻塞和非阻塞的程序样例，书里面说的很重要，所以就要搞懂哪个样例。2.等待队列 参照书里面的内容即可
2021-02-20 07:43:06
197
原创 linux设备驱动开发详解
第六章 字符设备驱动cdev结构体是描述一个设备，同时该结构体用于设备注册,进行设备注册有专门的接口file_operations结构体是用来描述操作该设备驱动提供的操作接口的集合，linux所有文件操作，open,read,write和close最终都会调用到file_operations结构体中...
2021-01-08 07:21:55
352
原创 linux设备驱动开发详解
第五章 linux文件系统与设备文件系统1.linux系统提供的文件操作接口creat 是文件创建接口open 可以进行文件打开，打开文件以后返回文件操作符，也可以进行文件创建，创建成功以后返回创建成功的文件操作符，同时设置读写权限write 是通过文件操作符将内容写入文件read 是通过文件操作符读取文件中的内容lseek是进行文件读写位置定位close是通过文件操作符关闭文件2.C语言标准库中包含的文件操作接口fopen是可以打开指定文件或者创建指定文件，返回文件操作符，需要设置读写权
2020-12-25 07:16:46
522
原创 linux设备驱动开发详解
第四章 linux内核模块1.linux内核模块的优点1）模块可以不用编译linux内核，在开发调试的时候，通过动态加载命令加载进内核就可以运行，大大提升了开发调试效率，同时也控制了linux内核的大小2）模块一旦被加载，它就和linux内核其他的部分一样，直接运行。2.linux内核模块基本结构linux内核包含主要的几个基本功能函数和声明函数，具体如下：module_init()是模块的初始化(即加载)接口声明函数，通过传入自己编写的设备初始化接口，对模块进行初始化。module_exit
2020-12-23 07:47:09
1029
原创 linux 静态库.a 和 动态库.so总结
库文件指的是已经编译好的二进制代码文件，可以在程序中调用常见的库有：标准c语言库，数学函数库，线程库库文件分两种：静态库和动态库在linux系统环境中，静态库是以.a文件结尾的文件，动态库是以.so文件结尾的文件。静态库的特点：静态库是在文件编译的...
2020-12-23 07:04:39
365
转载 mit6.828实验环境配置步骤
这学期开了操作系统，所以跟着大名鼎鼎的MIT 6.828期望真的学到知识。配环境的时候跟着别人的博客和MIT首页的操作也捣鼓了很久，下面把具体的操作步骤和踩得坑记录一下。环境Ubuntu18.04实体环境步骤6.828首页，找到顶部栏 Labs，点击Labs，再点击次出现的Tools进入工具页面。我们首先在主目录下创建一个名叫6.828的文件夹，后面会clone一个qemu的文件夹装用来跑JOS系统的虚拟机，另外一个lab文件夹用来装JOS系统。创建目录就不说了。首先输入% objdump -
2020-11-04 22:52:22
1392
原创 110. 平衡二叉树
题目：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。解法思路：1）通过遍历每一个节点，然后返回节点对应的左右子树的高度来判断该节点是否是左右平衡的，采取从根节点开始的思路可以实现，但是该方法对于子树的高度计算存在重复计算（参考前序遍历）代码实现如下：/** * Definition for a binary tree node. * struct TreeNode { * int va
2020-07-28 22:23:07
117
原创 108. 将有序数组转换为二叉搜索树
题目：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例：解题思路：链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/代码试下：/** * Definitio
2020-07-28 21:41:44
55
原创 最大子序和
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-subarray著作权归领扣网络所有。商业转载请联系
2020-07-22 15:57:21
108
原创 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7],返回其自底向上的层次遍历为：[[15,7],[9,20],[3]]来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。二叉
2020-07-21 20:49:35
129
转载 先序序列和后序序列并不能唯一确定二叉树
数据结构的基础知识中重要的一点就是能否根据两种不同遍历序列的组合（有三种：先序+中序，先序+后序，中序+后序），唯一的确定一棵二叉树。然后就是根据二叉树的不同遍历序列（先序、中序、后序），重构二叉树。显然，这三种组合并不是都能唯一确定二叉树的，其中先序+后序就不能唯一确定一棵二叉树，其他两种组合可以唯一的确定一颗二叉树。由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
2020-07-21 16:04:29
10197
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人