- 博客(369)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 图的拓扑排序
图的基本算法-拓扑序列拓扑排序拓扑排序基本算法代码示例拓扑排序对于一个有向无环图，简称DAG（Directed Acyclic Graph），进行拓扑排序就是将图中所有的定点排成一个线性序列，使得图中任意一对定点u和v，若边<u,v>则u在拓扑排序中出现在v之前。这样的序列成为满足拓扑次序的序列成为拓扑排序。拓扑排序基本算法对于一个有向无环图：找到入度为0的顶点，可能有多个...
2020-03-29 18:11:44
453
原创 什么是CPU上下文切换
什么是CPU上下文切换系统任务进程上下文切换系统调用系统调用的步骤进程上下文切换步骤进程上下文切换代价进程上下文切换的时机进程调度场景线程上下文切换线程和进程最大区别线程上下文切换的两种情况总结中断上下问切换中断和进程上下文区别总结系统任务系统中有三种任务：线程进程硬件触发信号，导致中断处理根据任务不同，上下文切换也分为三种：5. 线程上下文切换6. 进程上下文切换7. 中断...
2019-04-24 11:42:45
763
原创 怎么理解平均负载
uptime查看系统负载$ uptime17:43 up 13 days, 6:02, 2 users, load averages: 2.72 1.85 1.7917:43 // 当前时间up 13 days, 6:02 // 系统运行时间2 users // 正在登陆的用户最后三个数据：1分钟、5分钟、15分钟的平均负载平均负载平均负载的含义平均负载是指单位时间内，...
2019-04-20 15:09:07
585
原创 go服务的内存优化总结
go服务的内存优化总结go的内存分配方式新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入go的内存分配方式...
2019-04-20 14:39:58
1128
原创 数字转化为16进制数
leetcode：https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/思路1：数组hash存储string hex=“0123456789abcdef”;排除0先考虑num大于0的数，实现非常简单考虑num小于0的数，负数存储最高为1，且INT_MIN的绝对值等于INT_MAX+1，那么需要对INT_MIN做...
2019-04-16 22:12:28
3798
原创 数组初始化引起的性能问题
数组初始化// array.cint main(){ char a1[1024] = ""; char a2[1024] = {0}; char a3[1024] = {'\0'}; char a4[1024]; a4[0] = '\0'; return 0;}如上代码所示，前三种都是数组初始化的方法，a4仅仅初始化第一个元素。// gcc 版本：
2017-08-21 21:24:20
1067
原创 linux中buffer和cache的区别
free命令$free -h total used free shared buffers cachedMem: 62G 62G 739M 1.7M 11M 9.0G-/+ buffers/cache: 53G 9.
2017-08-08 10:07:04
986
原创 DP-House Robber
House RobberHouse Robber 题目大意： 一个小偷准备偷窃一条街道上的房屋，但这些房屋中任意相邻的房屋在同一夜被偷盗，那么就会自动报警。每个房屋中可偷盗的物品价值不一样，如果你是一名窃贼，怎么在同一夜中偷窃物品价值最大而不触发报警装置？分析什么样的最优化问题适合使用DP如何判断一个问题是否可用动态规划算法求解？下面是引用《算法导论》中什么问题才能使用DP的论述： 《算法导
2016-11-26 16:26:26
691
原创 基础算法-计数排序
计数排序计数排序要求所有元素都是0到k之间的整数（注：必须确定知道最大值k）。基本思想数列中小于等于元素a的个数为n，则直接把a放到第n-1个位置（注：索引从0开始）。代码/* * src[] : int, 待排序的整型数组 * dst[] : int, 返回已排序的整型数组 * size : int, src和dst数组的大小 * k : int, src数组中最大值k*/ void
2016-11-22 17:23:01
686
原创 关于滚动数组
Minimum Path SumGiven a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.普通的DP解决方案 DP的4个基本要素： 状态（State）
2016-11-19 21:16:10
908
原创 实现一个简单的HashTable
实现一个简单的HashTable，包括以下三个接口：put，get ，delete。基本原理哈希表的基本概念哈希表就是一种以 键-值(key-indexed) 存储数据的结构，只要输入待查找的值即key，即可查找到其对应的值。哈希函数是一种映射f(key) = index，多个key可以映射到一个index上，这在哈希表存储时产生冲突。哈希函数可以迅速计算出key对应哈希表数组中的索引，但无法避免冲
2016-11-15 16:40:42
2973
原创 实现push,pop,max为O(1)的栈
原理使用两个栈来实现要求: 栈的push,pop,max都为O(1)。一个栈用来保存入栈数据中的最大值另一个栈用来正常保存入栈和出栈的数据，它max方法用来调用第一个栈保存的当前最大值实现辅助栈作用：用于保存当前最大值的栈template<typename T>class stackMax{public: stackMax():size(0), capacity(1), data
2016-11-10 20:08:12
1379
原创 重建二叉树
重建二叉树根据前序遍历序列和中序遍历序列重建二叉树/* * 二叉树重建辅助函数 * preorder: vector<int>,前序序列 * inorder : vector<int>,中序序列 * idx : int, 当前树的根节点的在前序序列中的索引 * start : int, 当前树在中序序列中开始的索引 * end : int, 当前树在中序学列中结束的
2016-11-08 10:08:31
726
原创 LRU cache 算法的实现
#什么是LRULRU Cache是一个Cache置换算法，含义是“最近最少使用”，当Cache满（没有空闲的cache块）时，把满足“最近最少使用”的数据从Cache中置换出去，并且保证Cache中第一个数据是最近刚刚访问的。由“局部性原理”，这样的数据更有可能被接下来的程序访问。
2016-11-07 15:16:32
6189
原创 给定一个字符串，求出其最长的重复子串的长度
题目来源：这是编程珠玑上的一道题目概念字符串的前缀和后缀例如字符串 s =“abcdeabc” 则s的前缀： “a”，“ab”，“abc”，“abcd”，“abcde”，“abcdea”，“abcdeab”，“abcdeabc”其中除了s字符串本身（“abcdeabc”）之外，其他的前缀为s的真前缀。s的后缀： “abcdeabc”,“bcdeabc”，“cdeabc”，“deabc”，“ea
2016-11-05 11:55:55
17963
2
原创 数据库隔离级别的理解
数据库的隔离级别数据库中每个事务都要占用一些资源，比如对表/数据共享操作权限，事务的隔离级别描述了事务对资源共享程度。数据库的事务的隔离级别和解决的问题 隔离级别 出现的问题 原因 READ-UNCOMMITED 脏读 其他事务（线程）可以读取到当前事务修改但未提交的数据 READ-COMMITTED 不可重复读 设置数据库的隔离级别为READ-COMMITTED后
2016-11-03 10:07:31
777
原创 DFS、BFS和Backtracking模板
搜索问题的解法DFS（深度优先搜索）BFS（广度优先搜索）backtracking（回溯）DFS模板void dfs(...) { // 结束递归的条件 if (...) { ..... // 把“当前结果” 加入 “结果集容器” 中 return; } // 继续递归，里面可能有回溯，也可能没有 if (...) {
2016-11-01 11:33:20
2228
原创 约瑟夫环
约瑟夫环约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后[1] 结果+1即为原问题的解。一般的解决方法直观上，通过循环链表非常的简单，只需要循环删除指定节点就
2016-10-31 15:41:38
866
原创 实现C库函数strcpy
1 实现c库的函数strcpy原型声明：char* strcpy(char* dst, const char* src);普通版本的strcpy//strcpy 实现没有检查dst和src内存重叠问题char* strcpy(char *dst, const char *src) //const约束，内容不可变{ assert((src != NULL) && (dst != NULL)
2016-10-18 22:33:15
2445
原创 字符串-回文判断
回文判断回文的两种解法解法1从字符串的两边向中间判断字符串是否是回文。bool isPalindrome(string s) { if (s.empty()) return false; int l = 0, r = s.size()-1; while (l < r) { if (s[l] != s[r]) return false
2016-10-17 22:56:35
699
原创 贪心算法
找零钱问题the problem of “Making Change”.Coins available are:dollars (100 cents) quarters (25 cents) dimes (10 cents) nickels (5 cents) pennies (1 cent)#include #include #include using names
2016-10-17 10:14:24
663
原创 赛车进站问题
假设一场赛车比赛中需要跑 n 圈，而某赛车最多跑 3 圈就需要进站加油继续跑，请问有多少种进站策略。分析跑 n 圈加油的策略函数getCount(n)如下：当 n = 0 时，返回值为 0；赛车不跑圈，则没有进站策略。当 n = 1 时，返回值为 1；赛车跑1圈，则进站加油和不加油都可以，其策略只能为1。当 n = 2 时，返回值为 2；赛车跑2圈，第1圈跑完进站加油或不加油两种选择，跑完第2
2016-10-09 22:02:00
796
原创 二进制位的应用
问题1100瓶药水中有且仅有1瓶有毒，小白鼠喝毒药后24h内死亡。要在24h内查出有毒药瓶，至少需要多少只鼠？思路使用100只老鼠一定可以检测出哪瓶药有毒，分别给100只老鼠编号从1到100，并且给100瓶药编号从1到100；那么编号为1的老鼠喂编号为1的那瓶药，编号为2老鼠喂编号为2瓶药，…., 编号为100的老鼠喂编号为100的那瓶药。24小时过后，查看编号几的老鼠死亡，则编号为几的那瓶药有毒（
2016-10-01 20:16:15
1202
转载 Linux的进程间通信-消息队列
前言Linux系统给我们提供了一种可以发送格式化数据流的通信手段，这就是消息队列。使用消息队列无疑在某些场景的应用下可以大大减少工作量，相同的工作如果使用共享内存，除了需要自己手工构造一个可能不够高效的队列外，我们还要自己处理竞争条件和临界区代码。而内核给我们提供的消息队列，无疑大大方便了我们的工作。Linux环境提供了XSI和POSIX两套消息队列，本文将帮助您掌握以下内容：如何使用XSI消息队
2016-09-30 11:26:21
1404
原创 加锁和锁的粒度的思考
多线程下（或多进程）下访问共享资源的情况1 进程1和进程2并发读取test文件的数据： 线程（进程）的ID 读 写 数据状态 1 ~ 不变 2 ~ 不变2 进程1读取test文件的数据，进程2向test文件写入新的数据 进程（线程）的ID 读 写 数据状态 1 ~ 读
2016-09-20 19:50:36
6464
原创 BFS的应用
BFS在二叉树上的应用二叉树的层次遍历// 一颗二叉树 1 / \ 2 3 / \ / \ 4 5 6 7 // 按照层次遍历的要求，把结果输出到一行中void levelTraverse(BTree tree){ queue<BTree> qTree; if (tree)
2016-09-13 09:44:23
775
原创 Merge Two Sorted Lists-满满的套路
leetcode-21Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists不带头结点的版本实现/** 1. Definition for singly-linked lis
2016-09-03 17:23:42
427
原创 全排列
全排列给出一个字符串或整数数组，对这个字符串或整数数组进行全排列 例如：{1， 2， 3} 数组，对这个整数数组进行全排列。递归实现实现template <typename T> inline void swap(T* array, unsigned int i, unsigned int j) { T t = array[i]; array[i] = array[
2016-09-03 11:53:14
1017
转载 Linux的进程间通信-信号量
前言信号量又叫信号灯，也有人把它叫做信号集，本文遵循《UNIX环境高级编程》的叫法，仍称其为信号量。它的英文是semaphores，本意是“旗语”“信号”的意思。由于其叫法中包含“信号”这个关键字，所以容易跟另一个信号signal搞混。在这里首先强调一下，Linux系统中的semaphore信号量和signal信号是完全不同的两个概念。我们将在其它文章中详细讲解信号signal。本文可以帮你学会：
2016-08-31 13:04:22
936
转载 Linux IO模式及 select、poll、epoll详解
注：本文是对众多博客的学习和总结，可能存在理解错误。请带着怀疑的眼光，同时如果有错误希望能指出。同步IO和异步IO，阻塞IO和非阻塞IO分别是什么，到底有什么区别？不同的人在不同的上下文下给出的答案是不同的。所以先限定一下本文的上下文。本文讨论的背景是Linux环境下的network IO。一 概念说明在进行解释之前，首先要说明几个概念：用户空间和内核空间进程切换进程的阻塞文件描述符缓存
2016-08-10 10:43:28
699
原创 Linux的write调用
linux的write调用const char *buf = "My ship is solid";ssize_t nr;/* write the string in 'buf' to 'fd' */nr = write(fd, buf, strlen(buf));if (nr == -1) /* error */当write()调用返回时，内核已经把数据从提供的缓冲区拷贝到内核缓冲
2016-08-09 09:27:03
3071
转载 Linux进程间通信-共享内存
前言本文主要说明在Linux环境上如何使用共享内存。阅读本文可以帮你解决以下问题：什么是共享内存和为什么要有共享内存？ 如何使用mmap进行共享内存？ 如何使用XSI共享内存？ 如何使用POSIX共享内存？如何使用hugepage共享内存以及共享内存的相关限制如何配置？ 共享内存都是如何实现的？使用文件或管道进行进程间通信会有很多局限性，比如效率问题以及数据处理使用文件描述符而不如内存
2016-08-08 11:45:50
1771
原创 Ubuntu的GONME桌面中网络连接图标消失？
问题在Ubuntu的GONME桌面使用过程中经常遇到网络连接图标消失，没有网络连接的情况？分析这是由于Ubuntu桌面系统的网络管理服务程序NetworkManager服务退出导致的网络不可连接。解决方案重新启动NetworkManager服务即可，如下所示：// 查看network-manager服务的几种使用方法# service network-managerUsage: /etc/ini
2016-08-06 21:10:40
2192
转载 数据库的最简单实现
所有应用软件之中，数据库可能是最复杂的。MySQL的手册有3000多页，PostgreSQL的手册有2000多页，Oracle的手册更是比它们相加还要厚。但是，自己写一个最简单的数据库，做起来并不难。Reddit上面有一个帖子，只用了几百个字，就把原理讲清楚了。下面是我根据这个帖子整理的内容。一、数据以文本形式保存第一步，就是将所要保存的数据，写入文本文件。这个文本文件就是你的数据库。为了方便读取，
2016-08-05 15:51:33
303
转载 为什么主引导记录的内存地址是0x7C00？
《计算机原理》课本说，启动时，主引导记录会存入内存地址0x7C00。这个奇怪的地址，是怎么来的，课本就不解释了。我一直有疑问，为什么不存入内存的头部、尾部、或者其他位置，而偏偏存入这个比 32KB 小1024字节的地方？ 昨天，我读到一篇文章，终于解开了这个谜。首先，如果你不知道，主引导记录（Master boot record，缩写为MBR）是什么，可以先读《计算机是如何启动的？》。 简单说，
2016-08-05 15:26:24
557
转载 Linux的进程间通信-文件和文件锁
前言使用文件进行进程间通信应该是最先学会的一种IPC方式。任何编程语言中，文件IO都是很重要的知识，所以使用文件进行进程间通信就成了很自然被学会的一种手段。考虑到系统对文件本身存在缓存机制，使用文件进行IPC的效率在某些多读少写的情况下并不低下。但是大家似乎经常忘记IPC的机制可以包括“文件”这一选项。我们首先引入文件进行IPC，试图先使用文件进行通信引入一个竞争条件的概念，然后使用文件锁解决这个问
2016-08-03 08:46:22
3047
原创 判断字符串有重复字符
题目判断英文字符串中有重复字符代码#define BOOL int#define TRUE 1#define FALSE 0int arr[256] = {0};BOOL check1(char *str){ size_t len = strlen(str); if (len > 256) return TRUE; size_t i; fo
2016-07-30 17:11:32
1341
转载 Linux内存寻址之分段机制
前言最近在学习Linux内核，读到《深入理解Linux内核》的内存寻址一章。原本以为自己对分段分页机制已经理解了，结果发现其实是一知半解。于是，查找了很多资料，最终理顺了内存寻址的知识。现在把我的理解记录下来，希望对内核学习者有一定帮助，也希望大家指出错误之处。分段到底是怎么回事相信学过操作系统课程的人都知道分段分页，但是奇怪的是书上基本没提分段分页是怎么产生的，这就导致我们知其然不知其所以然。下面
2016-07-30 10:30:01
765
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人