- 博客(47)
- 收藏
- 关注
RSS订阅原创 二叉树的直径
二叉树的解题技巧是，首先判断问题能否划分为子问题、应当划分为什么样的子问题。二叉树直径实际上就是二叉树中的最长路径，我们是可以划分出子问题的：二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,经过根结点的最长路径}其中左子树的最长路径和右子树的最长路径是两个可以递归求解的子问题，那么经过根结点的最长路径如何计算呢？是左子树的深度加上右子树的深度。代入上面的式子得到：二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,左子树的深度+右子树的深度}子树的最大直径、子树的最大深度。这
2020-06-03 19:21:51
314
1
原创 腐烂的橘子
DFS（深度优先搜索）和 BFS（广度优先搜索）。它们各有不同的适应场景。题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS，应该是毫无疑问的了这道题的主要思路是：1.一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。2.然后进行 BFS 遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点，注意判断结点位于网格边界的特殊情况。3.由于可能存在无法被污染的橘子，我们需要记录新鲜橘子的数量。
2020-06-03 19:06:31
176
原创 II 和为S的连续正数序列
了解滑动窗口：滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。对于这道题来说，数组就是正整数序列 。我们设滑动窗口的左边界为 i，右边界为j ，则滑动窗口框起来的是一个左闭右开区间 。注意，为了编程的方便，滑动窗口一般表示成一个左闭右开区间。在一开始，i=1，j=1.滑动窗口位于序列的最左侧，窗口大小为零.滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能
2020-06-02 19:15:21
157
原创 旋转数组问题
先将整个数组反转，再将数组的前后两半（前 k 个数和后 k 个数）分别反转，就可以实现数组的旋转了。三次反转（reverse）操作的过程如下图所示：public void rotate(int[] nums, int k){ int N = nums.length; reverse(nums, 0, N); reverse(nums, 0, k); reverse(nums, k, N);};void reverse(int[] nums, int begin, in
2020-06-02 18:51:17
159
原创 链表排序
总体思想为以上三部分。下面分别讲述：1.划分：这个操作实际上可以拆分为两个基本操作：a.寻找链表的中点b.删除链表中点左侧的指针，将链表断开寻找链表中点的操作，我们在链表快慢指针的文章中讲过，使用一快一慢两个指针遍历链表即可。删除链表指针，实际上和删除链表结点类似。我们在链表遍历框架的文章中讲过，使用相邻的两个指针一同遍历链表即可。ListNode split(ListNode head){ ListNode fast = head; ListNode slow = he.
2020-06-01 19:40:10
97
原创 判断链表中是否存在环
如果链表中不存在环的话，快指针则不会和慢指针指向同一个结点，而是会走到链表结尾。依照这个思路我们可以得到以下的题解代码public boolean hasCycle(ListNode head){ ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = s
2020-05-31 20:44:59
117
原创 寻找链表的倒数第 k 个元素
思路：快慢指针，两个指针速度相同，只是间隔一定距离。快指针先前进 k个元素，然后两个指针同样速度前进。这样当快指针到达链表尾部时，慢指针正好到达链表的倒数第k 个元素public ListNode removeNthFromEnd(ListNode head, int k){ ListNode fast = head; for（int i = 0; i < k; i++）{ fast=fast.next; } ListNode curr = head;
2020-05-31 20:41:13
113
原创 寻找链表中点
链表数据类型的特点决定了它只能单向顺序访问，而不能逆向遍历或随机访问（按下标访问）。很多时候，我们需要使用快慢指针的技巧来实现一定程序的逆向遍历，或者减少遍历的次数。这就是为什么快慢指针常用于链表问题。快指针一次前进两个结点，速度是慢指针的两倍。这样当快指针到达链表尾部时，慢指针正好到达的链表的中部。过程如下方动图所示。public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = h
2020-05-30 21:52:22
452
原创 盛最多水的容器
如果选择固定一根柱子，另外一根变化，水的面积会有什么变化吗？推测结论：1.当前柱子是最两侧的柱子，水的宽度 为最大，其他的组合，水的宽度都比这个小。左边柱子较短，决定了水的高度为 3。2.如果移动左边的柱子，新的水面高度不确定，一定不会超过右边的柱子高度 7。3.如果移动右边的柱子，新的水面高度一定不会超过左边的柱子高度 3，也就是不会超过现在的水面高度结论：由此可见，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。这个时候，左边的柱子和任意.
2020-05-30 21:45:03
131
原创 给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数（不可以重复使用同一个数）
有序这个条件，你可能首先想到的是二分查找。但是仔细一想，需要固定一个数，对另一个数进行二分查找样时间复杂度是较高。使用双指针解法：public int[] twoSum(int[] nums, int target) {int i=0;int j=nums.length-1; while(i<j){ int sum=nums[i]+nums[j]; if(sum < target){ i++; } else if((sum >
2020-05-28 21:55:40
1273
原创 回溯算法
二叉树的遍历过程：以 Path Sum 为例为了最终输出所有可能的路径，我们需要在遍历时记录当前路径，当发现路径满足条件时，就将路径保存下来。路径遍历的顺序实际上就是 DFS 的顺序。当 DFS 进入一个结点时，路径中就增加一个结点；当 DFS 从一个结点退出时，路径中就减少一个结点。下面的 GIF 动图展示了这个过程。回溯算法的递归与遍历策略回溯（backtracking） 实际上就是“撤回一步”的意思。而在二叉树的 DFS 遍历中，从一个结点退出就是一种回溯。回溯法和 DFS 是息息相关的。例如
2020-05-27 21:51:52
249
原创 给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶结点的路径
题目：给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶结点的路径，这条路径上所有结点值相加等于目标和。返回 true 或者 false。1.了解二叉树的遍历框架说到二叉树的遍历框架，很多人的脑海里立马蹦出来的就是前序、中序和后序遍历。但是机械地记住前中后序遍历没有太大意义，我们首先要掌握的是二叉树的递归思想递归有两大要点：反复调用自身终止条件二叉树结构上进行递归，则这两大要点变为：递归调用自己两个子树在叶结点处终止递归调用子树的部分是重点。我们需要保证在子树上求解的是与原问题相同
2020-05-26 19:48:29
2503
原创 反转一个单链表
1.单链表这样一个相对“简陋”的数据结构，实际上就是为了考察面试者指针操作的基本功。2.如何才能简洁明了地解决单链表问题呢？实际上很多链表题目都是类型化的，都可以归结为链表的遍历，以及在遍历中做插入和删除操作。我们可以使用链表遍历的框架来解题a.了解链表遍历框架：当删除链表结点时，既需要访问当前结点，也需要访问前一个结点。既然这样，我们不妨使用两个指针来遍历链表，curr 指针指向当前结点，prev 指针指向前一个结点。这样两个指针的语义明确，也让你写出的代码更易理解。b.单步操作是“反转 pre
2020-05-26 19:33:39
142
转载 Linux的文件操作命令
修改文件时间或创建新文件——touch命令格式touch [参数选项] 文件名例子：新建一个空的文件并查看时间命令参数1）-a 或–time=atime或–time=access或–time=use：仅更改访问时间。2）-c 或–no-create ：仅修改文件时间，不创建任何文档3）-m 或–time=mtime或–time=modify ：只更改变动时间。查看文件的时间参数 ：注：A、modification time（mtime）：更新文件的修改时间.。B、access ti
2020-05-22 10:18:18
123
原创 静态库和动态库
静态库静态库的命名方式：“libxxx.a”，其中“xxx”为库名，库名前加“lib”，后缀用“.a”工作过程 ：在编译过程中，静态库的所有数据都被载进目标文件里。程序运行的时候就不再需要静态库优点 ：编译后的执行程序不需要外部函数库支持缺点 ：1.静态函数库编译成的文件占用的内存比较大。2.当静态库改变时，程序必须重新编译静态库的生成与使用命令介绍静态库的生成和使用过程中需要用到ar命令。ar是Linux系统的一个备份压缩命令，用于创建、修改备存文件（archive），或从备存文件
2020-05-22 09:46:40
175
转载 硬连接和软连接
Linux下的两种连接文件及创建方式在Linux下面的连接文件有两种——软连接和硬连接，虽然都是连接文件，但两者却有很大的区别：一种是类似于Windows的快捷方式功能的文件（或目录），这种连接称为软连接；另一种则是通过文件系统的inode连接来产生新文件名，而不是产生新文件，这种称为硬连接创建连接文件的方法非常简单，就是使用ln命令，ln file1 file2，则创建硬连接，file2为file1的硬连接，ln -s file1 file2，则创建软连接，file2为file1的软连接。详述硬
2020-05-21 18:30:54
709
原创 数据流重定向
数据流重定向概念在说数据流重定向之前，先来说说数据流的概念吧。数据流分为三种：标准输入（stdin），标准输出（stdout）和标准错误输出（stderr）。简单来说，标准输出指的是命令执行所回传的正确信息，而标准错误输出指的是命令执行失败后，所回传的错误信息。这些信息默认是打印在屏幕上的什么时数据流重定向呢？从字面上理解就是改变数据流的流向，使之流向指定的文件或设备。例如，把执行命令所回传的正确信息（标准输出信息）流向一个文件，而将所回传的错误信息（标准错误输出）流向别一个文件，并把这两个文件的信
2020-05-21 15:34:08
384
转载 linux环境变量
环境变量的概念含义：环境变量一般是指操作系统中指定操作系统运行环境的一些参数。它相当于一个指针，想要查看变量的值，需要加上“$”。分类：按作用的范围分类：在Linux中的变量，可以分为环境变量和本地变量：1）环境变量：相当于全局变量，存在于所有的Shell中，具有继承性；2）本地变量：相当于局部变量只存在当前Shell中，本地变量包含环境变量，非环境变量不具有继承性。按生存周期分类：1）永久：需要修改配置文件，变量永久生效；2）暂时：使用export定义，关闭Shell后失效。环境变量的
2020-05-21 11:46:05
319
原创 LINUX进程状态
两状态进程模型在任何时刻，一个进程要么正在执行，要么没有执行，因而可以构成最简单的模型。一个进程可以处于以下两种状态之一：运行态或未运行态。在任何一种情况下，分配器都会从队列中选择一个进程来执行。进程的创建和终止进程创建的原因：（1）新的批处理作业；（2）交互登录；（3）操作系统因为提供一项服务而创建；（4）由现有的进程派生。一个应用程序进程可以产生另一个进程，以接收应用程序产生的数据，并将数据组织成适合以后分析的格式。当一个进程派生另一个进程时，前一个称为父进程，被派生的进程称做子进程
2020-05-21 10:32:37
404
原创 POSIX信号量
概念POSIX信号量与SYSTEM信号量的作用相同，都同步操作，达到无冲突地访问共享资源。但是不同的是，POSIX信号量可以用于线程间同步。其实，POSIX信号量是具有等待队列的计数器，它的相关函数存放在“semaphore.h”文件中。初始化信号量int sem_init(sem_t *sem, int pshared, unsigned int value);参数：pshared：0表示线程间共享，非0表示进程间共享。value：信号量初始值，表示可用资源的数量。销毁信号量int se
2020-05-21 09:51:50
107
原创 进程替换
替换原理用fork创建子进程后执行的是和父进程相同的程序，也有可能执行不同的代码分支，子进程往往要调用一种exec函数以执行另一个程序。当进程调用一种exec函数时，该进程的用户空间代码和数据完全被新进程替换，从新程序的启动例程（main函数）开始执行。记住：调用exec并不创建新进程，所以调用exec前后该进程的id并为改变。exec只是用磁盘上的一个新程序替换了当前进程的正文段、数据段、堆段和栈段。替换函数其实，有六种以exec开头的函数，统称exec函数#include<unistd.
2020-05-20 09:17:44
86
转载 linux进程控制
进程创建fork函数是非常重要的函数，它从已存在的进程中创建一个新进程。这样，新进程为子进程，原进程为父进程。1）调用fork函数的格式#include <unistd.h>#include <sys/types.h>pid_t fork(void);//返回值：子进程返回0；父进程返回子进程的PID；出错返回-1。调用fork函数后，内核的工作：a.分配新的内存块和内核数据结构给子进程。b.将父进程的部分数据结构内容拷贝至子进程。c.添加子进程到系统进程列表中。
2020-05-19 22:31:06
101
转载 linux线程等待与分离
线程等待原因已经退出的线程，其空间没有被释放，仍然在进程的地址空间内。创建新的线程不会复用刚才退出线程的地址空间。线程等待函数：pthread_join（1）功能：等待线程结束（2）原型：int pthread_join(pthread_t pthread, void **value_ptr);（3）参数：a.thread：线程ID；b.Value_ptr：它指向一个指针，后者指向线程的返回值。（4）返回值：成功返回0；失败返回错误码线程终止状态调用pthread_join函数的线程将挂
2020-05-19 20:59:27
193
转载 c++动态内存管理
介绍malloc、calloc和realloc1.malloc函数，其原型如下void *malloc（size_t size）；malloc所分配的是一块连续的内存，其参数就是需要分配的内存字节数。如果分配成功，则返回指向这块内存的指针；如果分配失败，则返回NULL指针2.calloc函数，其原型如下void *calloc（size_t num_elements, size_t size_element）；calloc函数也是分配内存的，其参数包含所需元素的个数和每个元素的字节大小，将对分配
2020-05-19 20:51:24
252
原创 c++类与对象2
隐含的this指针性质：每个成员函数都有一个指针形参，它的名字是固定的，称为this指针，this指针是隐式的（为何构造函数除外？）。成员函数隐含指针形参，是编译器自己处理的，不能在成员函数的形参中添加this指针的参数定义，也不能在调用时显示传递对象的地址给this指针。传递方式：对象地址作为实参传递给成员函数的第一个形参this指针。存放位置：this指针在对象调用成员函数前创建，在成员函数调用结束后销毁，所以this指针存放在栈上。类的默认成员函数1、构造函数有参和无参的构造函数clas
2020-05-19 17:08:02
107
翻译 线程之互斥量
概念互斥量从本质来说是一把锁，在访问共享资源前对互斥量进行设置（加锁），在访问完成后释放（解锁）互斥量。对互斥量进行加锁以后，任何其他试图再次对互斥量加锁的线程都会被阻塞，直到当前线程释放该互斥锁。如果解锁前有一个以上的线程阻塞，那么解锁后这些线程就变为运行状态，直到其中一个线程重新对互斥量加锁，这时其他线程又变为阻塞状态。互斥量的作用大部分情况，线程使用的数据都是局部变量，变量的地址空间在线程栈空间内，这种情况变量归属单个线程，其他线程无法获得变量。但有的时候，线程间需要共享很多变量，通过数据的共
2020-05-19 15:47:36
170
转载 Linux网络编程之套接字
预备知识1、了解IP地址1）IP协议有两个版本，IPv4和IPv6，现在用得比较多的是IPv4。2）IP地址是在IP协议中用来标识网络中不同主机的地址。3）对于IPv4版本来说，IP地址是一个4字节，32位的整数。4）通常使用“点分十进制”的字符串表示IP地址，例如：“192.168.181.129”，其中用点分割的每一个数字表示一个字节，范围为0-255。5）在IP数据报头部，有两个IP地址，分别叫做原IP地址和目的IP地址。IP地址能够把信息发送到对方的机器上，但是还需要一个其他的标识符来
2020-05-19 15:12:44
636
原创 c++之迭代器
迭代器的概念提供一种方法，使之能够依次寻访某个容器所包含的所有元素，而又无需暴露该容器底层的结构。迭代器的本质迭代器实际是一种行为类似指针的对象，因此指针的所有操作迭代器都支持，使用迭代器时向使用指针一样去使用。比如：指针的解引用、成员访问、前置/后置++、前置/后置–、==、!=等迭代器支持，但是迭代器是一种行为类似指针的新类型，因此迭代器的实际只需将指针的上述操作在类中重载即可（以后补充代码示例）迭代器的实现迭代器是算法和容器的粘合剂，同一个算法可以操作不同类型的容器，而容器类型不同，意味
2020-05-17 20:45:54
222
原创 C++类与对象
类的概念类是一种复杂的数据类型，它是将成员变量成员函数）封装在一起的集合体。这与C语言中的结构体相似对象的概念对象指的是类的实例。将对象作为程序的基本单元，将数据和程序封装在一起，以提高软件的重用性、灵活性、和扩展性面向对象的三大特性封装性、继承性、多态性访问限定符 1. public成员可从类外部直接访问，private/protected成员不能从类外部直接访问。 2. protected限定的函数和数据，只有继承者和受保护的成员可以使用 3. private限定的函数和数据，
2020-05-17 19:38:39
157
转载 word插入公式（2）：告别空格 ，公式居中，编号自动右对齐（适用于论文）
声明：本文为CSDN博主「OSUfish」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/OSUfish/article/details/84568601
2020-05-17 17:57:00
290
原创 类的默认成员函数
类默认生成的成员函数有六个： 构造函数、 拷贝构造函数、 析构函数、 赋值操作符重载、 取地址操作符重载 const修饰的取地址操作符重载构造函数1.概念：初始化对象，有且仅在定义一个对象时自动执行一次的函数，就称为构造函数。2.特性a.函数名与类名相同。b.无返回值。c.实例化对象时系统会自动调用对应的构造函数。d.构造函数可以重载。e.构造函数可以在类内定义，也可以在类外定义。在类外定义时的格式：类名+“::”+函数名。f.如果...
2020-05-16 15:43:21
981
1
原创 c++引用与指针
引用概念引用不是定义一个变量，而是给一个已经定义的变量重新起一个别名引用的定义格式：类型&引用变量名=已定义过的变量名。引用的特点：1）一个变量可用多个别名；2）引用必须初始化；3）引用只能在初始化的时候引用一次，不能改变为再引用其他的变量。代码：#include<iostream>using namespace std;int main(){ int a = 10; int b = 11; int& c = a; int&
2020-05-16 11:01:05
122
原创 c++函数重载
概念在C++程序中，将在同一作用域内，语义、功能相似具有相同函数名字，不同参数列表（参数的个数，顺序和类型不同）的函数。函数重载的实现名字修饰概念因为最终的二进制可执行程序是不允许有同名函数出现的。作为语言实现的编译器必须为每一个被重载的函数生成唯一的内部变量首先了解程序运行经历的几个阶段：预处理、编译、汇编、链接。名字修饰即就是一种在编译过程中，将函数、变量名称重新改编的机制。C语言的名字修饰只是在函数名字前面添加了下划线。比如，对于以下代码，在最后链接时就会出错：C++的名字修饰C+
2020-05-16 10:10:10
210
原创 c++静态成员
概念声明为static的类成员称为类的静态成员，用static修饰的成员变量称为静态成员变量，用static修饰的函数称为静态成员函数。特性1）静态成员为所有类对象所共享，不属于某个具体的实例；2）静态成员变量要在类外定义，定义时不加static关键字；3）访问静态成员的方式：类名：：静态成员；4）静态成员函数没有隐藏的this指针，不能访问任何非静态成员；5）静态成员和类的普通成员一样，有public、protected、private访问级别，有返回值，可被const修饰。6）静态成员变
2020-05-15 16:27:39
89
转载 c++之深浅拷贝
看了别人的博客的理解如图有这样一个类：主函数：运行结果：看看p和p2指向的地址：两者指向同一块地址,那么析构释放内存，就会出错。解决方式：深拷贝再来看看两个指针指向再举一个例子#include<iostream>#include<stdlib.h>using namespace std;class String{public: //构造函数 String(const char* str) :_str(new char[strlen(st
2020-05-15 16:00:35
109
转载 c++进阶之多态
多态概念多态的字面意思：一个事物有多种形态。按统实现的角度分类：静态多态、动态的多态静态多态：函数的重载和运算符的重载都属于静态的多态，在程序编译时系统就能决定调用的是哪一个函数，因此静态的多态又称为编译时的多态性。动态的多态：在程序运行过程中才动态的确定操作所针对的对象，因此又称为运行时的多态。动态的多态性是通过虚函数实现的。构成多态的条件1）必须要使用关键字virtual修饰基类的成员函数，指明该函数是虚函数；2）并且在派生类里面要重新实现，才能实现动态的多态重写的条件：1.要形成重写
2020-05-15 12:18:49
164
原创 c++入门string标准库操作
string对象的定义和初始化代码示例：#include <iostream>#include <string>using namespace std;int main(){ string s1 = "a"; cout << "s1 = " << s1 << endl; //s1 = a string s2(s1); //将 s2 初始化为 s1 的一个副本 cout << "s2 = "
2020-05-14 11:31:40
99
原创 c++入门vector标准库操作
使用 vector 之前，必须包含相应的头文件，vector 属于 std 命名域的，因此需要通过命名限定： #include<vector> using std::vector; //using namespace std;vector 对象的定义和初始化vector<int> a;vector<int> b(a);vector<string> a(6,'a');vector<int> a(10);常见操作#inc
2020-05-14 10:56:55
379
转载 Linux线程创建与终止
线程概念线程指程序的一个执行流，也可理解为是进程内部的一个控制序列，任何进程都至少含有一个线程。如下图所示：在许多经典的操作系统教科书中，总是把进程定义为程序的执行实例，它并不执行什么, 只是维护应用程序所需的各种资源，而线程则是真正的执行实体。为了让进程完成一定的工作，进程必须至少包含一个线程。进程，直观点说，保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，这个内存体有自己的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统会以进程为单位，分配系统资源，所以我们也说，进程是
2020-05-13 17:43:43
277
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人