Y~哈哈哈的博客

原创 goroutine基础

一、goroutine是什么？是go里的一种轻量级线程-协程1、相对线程，协程的优势在于它非常轻量级，进行上下文切换的代价非常小2、相对于一个goroutine，每个结构中有一个sched的属性就是用来保存它上下文的，这样，goroutine就可以很轻易的来回切换3、由于其上下文切换在用户态下发生，根本不必进入内核态，所以速度很快。而且只有当前goroutine的pc,sp等少量信息需要保存4、在go语言中，每一个并发的执行单元为一个goroutinego语言中的goroutine并发

翻译 OAuth 2.0授权框架

背景介绍：OAuth2.0授权框架支持第三方应用程序以获取对HTTP服务的有限访问权，通过协调批准交互来代表资源所有者，在资源所有者和HTTP服务之间，或者通过允许第三方应用程序代表自己获取访问权限。这个规范取代并淘汰了所描述的OAuth1.0协议一、传统模式的身份验证模型在传统的客户端-服务器身份验证模型中，客户端请求对服务器进行访问限制的资源（受保护的资源）通过使用资源所有者的服务器向服务器进行身份验证证书。为了提供第三方应用程序访问受限制的资源，资源所有者与第三方。这会带来一些问题和局限性

原创 RPC原理

1、什么是RPCRPC指进程间通信。就是允许程序调用另一个地址空间（通常是共享网络的一台机器上）的过程或函数，且不需要显示编码这个远程调用的细节。2、为什么需要RPC目前大厂内部系统由大大小小的许多服务组成，服务部署在不同的机器上，如果服务间的调用都是走网络通信，未免也太过复杂，服务消费方每调用一个服务都要写一部分网络通信的代码，太过繁琐且容易出错。如果能像本地调用一个去调用远程连接这样就非常方便了，这种方式就是RPC远程调用。但是很多人可能会有以下几个疑惑点：（1）远程问题如何通信？客

原创 Docker

Doceker是一种操作系统层面的虚拟化技术，可以在操作系统和应用程序之间进行隔离，也称之为容器。Docker可以在一台物理服务器上快速运行一个或多个实例，例如，启动一个Cent OS操作系统，并在其内部命令执行指令后结束，整个过程就像自己在操作系统一样高效...

原创 树中两个结点的最低公共祖先

遇到这个题要分几种情况1、该树是一棵二叉搜索树： 由于二叉搜索树是排序过的，位于左子树的结点都比父节点小，而位于右子树的结点都比父节点大，我们只需要从树的根节点开始和两个输入的结点进行比较。如果当前结点的值都比两个结点的值大，那么最低的共同父节点一定是在当前结点的左子树中，于是下一步遍历当前结点的左结点。如果当前结点的值都比两个节点的值小，那么最低共同父节点一定在当前结点的右子树中，...

原创 秋招面经总结（持续更新中）

大华：（一面8月12，二面8月15）一面：（25分钟）1、自我介绍2、博客都是关于哪些技术的3、fork源码的剖析（只是简单的剖析吗？有没有将其替换掉使用）4、select、poll、epoll的区别5、raw_socket的原理以及和TCP/UDP中socket的区别6、libevent的工作原理7、在TCP/IP五层传输协议中，数据传输的方式还有给数据加头加的是...

原创 leetcode—— 不同路径I II

/*一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？*/思路：从起点 (x=0,y=0)(x=0,y=0)(x=0,y=0) 出发，下一步只能向右或者向下到达第二点，向右则为 (x+1，y)(x+1，y)(x+1...

原创 把字符串转换成整数

注意： atoi通过区分一个全局变量来区分当字符串为空的时候返回的0和输入的字符串是“0”的时候返回值的0，如果是非法输入，返回0并把这个全局变量设为一个特殊的标记。如果输入是“0”，则返回0，不会设置全局变量。这样当atio的调用者得到返回值0的时候，可以通过检查全局变量得知输入究竟是非法输入还是字符串“0”所以在下面代码中，如果是正常的转换，输入都是合法的，那么会在最后将这个全局变量置...

原创 C++中类的初始化列表

这个初始化列表严格来说，应该叫做构造函数的初始化列表，一个对象的完整构造顺序顺序应该是：先按照成员变量的定义顺序依次构造成成员变量，最后再调用当前类的构造函数构造一个新的对象，因此当构造函数调用时，说明成员变量（或者成员对象）早已初始化（或者构造）完成，那么成员变量（或者成员对象）如果没有默认的初始化或者构造方式的话，就在当前类构造函数的初始化列表当中初始化举例：class A{...

原创 丑数

题目：我们把只包含因子 2、3、5的数称为是丑数，求按从小到大的顺序的第n个丑数。看不懂的可以私聊我,虽然是书上的代码和思路，但还是以自己弄懂为主int Min(int number1, int number2, int number3){ int min = (number1 < number2) ? number1:number2; min = (min < num...

原创 Linux中线程安全问题

一、线程安全的介绍 在目前的计算机科学中，线程是操作系统调度的最小单元，进程是资源分配的最小单元。在大多数操作系统中，一个进程可以同时派生出多个线程。这些线程独立执行，共享进程的资源。在单处理器系统中，多线程通过分时复用技术，处理器在不同的线程间切换，从而更高效地利用系统 CPU资源。在多处理器和多核系统中，线程实际上可以同时运行，也就是每个处理器可以运行一个线程，系统的运算能力相对于...

原创 在数组中查找丢失的一个数据

最简单的算法：开辟一个数组，然后遍历原数组，读到哪个数就给新开辟的那个数组对应位置写成true,遍历完之后再对对新开的数组遍历一遍找到为false的那个位置，它对应的下标就是丢失的数据时间复杂度：O（n）空间复杂度O(n+1)int missing(int *arr, int len){ if(NULL == arr) return -1; int*brr = (int *)mal...

原创 qsort函数和bsearch函数

头文件<stdlib.h>一、qsort()是用来排序的，原型如下：void qsort(void *base, size_t num, size_t size, int(*compare)(const void*,const void*));void *base：任意类型的数组 size_t size：指数组元素的个数 size_t size：每一个元素的大小 最...

原创 线段树

题目：对一个数组重复的随机的找一段连续数据进行求和（query）以及重复的随机的改(updata)某一个位置处的值第一种解法：再开一个数组，这个数组用来存和，图如下：void Sum_arr(int *arr,int len1, int *sum_arr){ int i=0,j=0; while(i < len1) { if(i == 0)...

原创 堆排序

堆排序分为两步：建初始堆和交换堆顶元素和末尾元素并重建堆（ 排序） 时间复杂度为O（n） + O(nlgn)即等于O(nlgn)一、建堆：时间复杂度：O(n)堆我们正好可以用一个数组来存储，那么它将有如下的关系：i 表示第i个结点parent = (i-1) / 2;Lchild = 2*i + 1;Rchild = 2*i + 2;堆建立的时候有两点很重要：1...

原创 把一个数组中的0全部移到数组的最后边或者数组的最前边

把所有为0的数移到数组的最后边思想：从前往后遍历一遍数组，将数组中的零全部用一个整型变量 ZeroNum记录下来，当碰到一个非零的数据，就让这个数向前移动ZeroNum个单位，即arr[i-ZeroNum] = arr[i]; 把数组遍历完成之后，为0个个数就全部统计出来了，那么就将数组的后ZeroNum个位置全都改为0即可代码如下：时间复杂度：O（n），空间复杂度：O（1）voi...

原创 斐波那契 跟 动态规划的联系

上图画出了斐波那契的运算关系，我们发现 fib(4)、fib(3) 都是重复计算了，那么按照这样的方式计算完之后效率就很低很低了，时间复杂度为 O(2^n)，如果我们把faib(4)n的值先保存起来，下次直接用是相比前面的重复计算是不是效率就高了很多呢，因为提供下面的一种方法int arr[] = {1,1,2,3,4,5,6}; 下标： 0 1 2 3 4 5 6我...

原创 int *const p和const int *p区别

const int *p;上面这条语句中，const修饰的是p指向的内存的值不能被修改，但是p本身是可以修改的int *const p;上面这条语句中，const修饰的是p本身是常量，不能被修改，但是p指向的内存是可以被修改的下面给出几种错误的类型转换const int *p ==> int *q;int **p ==> const int **q;con...

原创 C++this指针干什么用的

class Test{public: void func(){ cout<<"mvalue:"<<mvalue<<endl; }private: int mvalue;};int main(){ Test t1,t2; t1.func(); t2.func(); return...

原创 set的底层实现实现为什么不用哈希表而使用红黑树

1、set中元素是经过排序的，红黑树也是有序的，哈希是无序的2、如果只是单纯的查找元素的话，那么肯定要选哈希表了，因为哈希表在的最好查找时间复杂度为O(1)，并且如果用到set中那么查找时间复杂度的一直是O（1），因为set中是不允许有元素重复的。而红黑树的查找时间复杂度为O(lgn)...

原创 如何实现一个类定义的对象不能进行拷贝构造和赋值呢

可以实现一个基类，把这个基类的拷贝构造和operator=赋值函数私有化，那么任何这个基类继承的派生类，都不能拷贝和operator=了还有一种办法：把这个类的拷贝构造和operator=赋值函数私有化，这样做完全可以，但是对于每一个类的进行更改，代码修改量比较大，所以还是建议使用上面的方法...

原创 如何实现一个不可以被继承的类

由于派生类对象的构造，要先构造基类部分，而且派生类可以继承基类的private成员，但是却不能访问，因此可以把基类的构造函数实现成private私有的构造函数，那么任何一个派生类在继承这个基类的时候，都会由于无法调用基类的私有构造函数，而导致这个基类不能被任何派生类继承...

原创 关于迭代器失效的几种情况

一、序列式容器迭代器失效 1、顺序容器：vector：向量容器。底层是动态开辟的一维数组，内存可增长，每次增长2倍 deque：双端队列容器。底层是动态开辟的二维数组，一位数组里全部存的是指针，二维数组是动态开辟的，所以说deque的底层是一个部分连续整体不 连续的结构 list：列表容器。底层是带头节点的双向链表容器2、对于序列式容器vector、deque 当当前元...

原创 用O(1)事件复杂度删除第K个结点

删除第K个结点其实主要就是删除这个结点中的值，即可以删除第K+1个结点，然后把它的它拿来放在第K个节点处就行了Node **deleteKNode(Node **head, int k){ if((*head) == NULL) { return NULL; } Node *p = (*head); int len = 0; while(p) { p = p->...

原创 动态规划——背包问题

原创 动态规划——连续子段和

一、动态规划的递归式：n是这组数的长度公式意义：当以第 i-1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第 i 个数累加，得到的结果比第 i 个数字本身还要小，所以这种情况下以第 i 个数字结尾的子数组就是第 i 个数字本身。如果以第 i-1 个数字结尾的子数组中所有数字的和大于0，与第 i 个数字累加就得到以第 i个数字结尾的子数组中所有数字的和二、时间复杂度：O(...

原创 二叉搜索树转换成排序双向链表

因为二叉树中，每个结点都有两个指向子节点的指针。在双向链表中也有两个指针，它们分别指向前一个和后一个结点。由于这两种结点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此在理论上可能实现二叉搜索树和排序链表的双向链表的转换。 在搜索二叉树中，左子节点的值总小于父节点的值，右子节点的值总是大于父节点的值（所以使用中序遍历）。因此在转换成排序链表的时候，原先指向左子节点的指针调...

原创 数组与二叉树的转换

1、利用数组转换成二叉树——后序的方式TreeNode *Array_Tree(int *arr,int i, int n){ TreeNode *ptr = NULL; if(i > n || NULL == arr) { return ptr; } if(i < n) { ptr = BuyNode(); ptr->Lchild = Array...

原创 同步/异步在不同的模型中含义不相同以及阻塞、非阻塞

一、I/O模型中的同步/异步1、在I/O模型中，同步I/O是说I/O的读写操作，是在I/O事件发生之后，由应用程序来完成的。对于异步I/O来说，它可以直接对I/O执行读写操作，这些操作告诉用户内核缓冲区的位置，以及I/O操作完成之后内核通知应用程序的方式2、异步I/O总是立即返回的，因为真正的读写操作已经由内核接管。同步I/O的读写操作由应用程序自己完成。换言之，同步I/O内核通知的是就...

原创 大端小端问题总结及相关面试题

参考https://blog.csdn.net/lishitao_578/article/details/72956312

原创 delete和delete[]的区别以及什么时候用new[]申请可以用delete来释放

一、什么时候用new[]申请，可以用delete释放 1、在C++中，把单个元素的内存开辟释放和数组的内存开辟释放是分开的。因为在C++里面，开辟内存和构造对象是一起发生的，析构对象和释放内存是一起发生的int *a = new int; //delete a 或 delete[] 都可以int *p = new int[]; //delete p 或 delete p[] 都可以...

原创 new和 malloc区别以及delete和free的区别

一、new和malloc的区别其实new的底层也是使用malloc来实现的，只不过在类类型中比malloc多了一个调用构造函数来初始化的功能1、返回值new开辟内存需要指定类型，返回指定类型的指针，因此不需要进行强转 malloc的返回值是一个指针，指向一段可用内存的起始地址。因此malloc的返回值需要强转成指定类型的地址2、内存开辟与初始化malloc只负责开辟内存，内有初...

原创 Linux环境下段错误产生原因及调试方法

一、段错误是什么？ 段错误指访问的内存超出了系统给这个程序设定的内存空间，例如访问了不存在的内存地址，访问了系统保护的内存地址，访问了只读的内存地址等二、一一举例说明访问不存在的内存地址#include<stdio.h>void mian(){ int *ptr = NULL; *ptr = 0;}访问系统受保护的内存地址#inclu...

原创 Shell程序设计

一、为什么要使用shell编程呢？（1）是可以快速、简单地完成编程（2）如果你有一个简单的构想则可以通过它来检查自己的想法是否可行（3）shell非常适合于编写一些执行相对简单的任务的小工具，因为它们更强调的是易于配置、易于维护和可移植性，而不是看重执行效率（4）可以使用shell对进程控制进行组织，使命令按照预定顺序在前一阶段命令成功的前提下顺序执行缺陷：shell不适合用来...

原创 Linux下共享内存的应用场景以及三种共享内存的方式

一、应用场景1、进程间通讯——生产者消费者模式 一个现场负责产生数据，一个现场负责处理数据，那么我们可以用主线程作为生产者，从键盘获取数据写入共享缓冲区，另一个线程作为消费者，从共享缓冲区读取数据，并打印。当然，这里要解决互斥的问题2、父子进程间通讯 由fork()产生的子进程和父进程不共享内存区，所以父子进程间的通讯也可以共享内存，以POSAX共享内存为例：父进程启动后使用...

原创 Send和Recv两个调用的底层原理以及UDP中recvfrom和sendto接收和发送数据的方式

send和recv是利用建立好的TCP连接进行数据据的发送和接收的系统调用。send负责将要发送的数据写入对应套接字文件描述符的发送缓冲区中，send成功并不代表数据就成功的发送到了对端，其实send的返回值是实际写入发送缓冲区的字节数，什么时候发送给对端由底层协议完成。如果缓冲区满则有可能阻塞send.send在内核中最终通过_sock_sendmsg，将数据写入相应的缓冲区中。recv是...

原创 fread/write和 fwrite/write的区别

1、fread是带缓冲区的，read不带缓冲区2、fwrite属于库函数，write属于系统掉头3、fread可以读一个机构，read在Linux/unix中读二进制与普通文件没有区别4、fopen不能指定要创建文件的权限，open可以指定权限5、fopen返回指针，open返回文件描述符（整数）举例：如果文件的大小是8k，你如果用read/write，且只分配了2K的缓存，则...

原创 二叉树的性质

1、在二叉树的第i层上至多有2^(i-1)个节点（i >= 1）2、深度为k的二叉树之多有2^k -1个节点（i >= 1）3、对任意一颗二叉树T，如果其终端节点数为 a，度为2的节点数为 b，则 a=b+14、具有n个结点的完全二叉树的深度为lgn +15、如果对一棵有n个结点的完全二叉树...

原创 有关多线程中fork()的问题

问题1：如果一个多线程程序的某个线程调用了fork函数，那么新创建的子进程是否将自动创建和父进程相同数量的线程呢？答案：否。子进程只拥有一个执行线程，它是调用fork的那个线程的完整复制。并且子进程将自动继承父进程中互斥锁（条件变量与之类似）的状态。也就是说，父进程中已经被加锁的互斥锁在子进程中也是被锁住的问题二：子进程可能不清楚从父进程继承而来的互斥锁的具体状态（是加锁还是解...

原创 线程和信号

1、进程中的所有线程共享该进程的信号，所以线程库将根据线程掩码决定把信号发送给那个具体的线程。因此，如果我们在每个子线程中都单都设置信号掩码，就很容易导致逻辑错误。此外，所有线程共享信号处理函数。也就是说，当我们在一个线程中设置了某个信号的信号处理函数后，它将覆盖其他线程为同一个信号设置的处理函数。这两点都说明，我们应该定义一个专门的线程来处理所有的信号2、如果父进程希望和子进程共享地址空间，...