zzuRingo-CSDN博客

原创 [2017/08/22]高性能C/C++编程中的那些数据结构

本文首发于腾讯KM，如转载请注明作者，出处。偶然在k吧首页看到了luckyzuo的分享，因为自己一直对这方面很感兴趣，所以在工作之余对照ppt听了讲座录音，受益匪浅。这次分享提到了几种数据结构，我结合了自己的一些理解，写了这篇文章。写的时候查阅了许多资料，越发认识到自己基础知识的薄弱（还是要学习一个）。由于水平有限，若有错误，请各位指正。目录：一. 哈希表的弱点1.1 hash的硬伤 1.1.1

2017-08-22 17:31:53 1542

原创 [2017/07/12]后台检查cpu性能常用命令

1.uptime:平均负载输入uptime，显示以下数据：15:00:05 up 9 days, 5:06, 2 users, load average: 0.02, 0.04, 0.01 它依次显示下列信息：当前时间、系统已经运行了多长时间、目前有多少登陆用户、系统在过去的1分钟、5分钟和15分钟内的平均负载。2.vmstat：包括系统范围的CPU平均负载vmstat m n第一个参数

2017-07-12 15:46:11 813

原创 [2017/07/11]随手记setvbuf函数

今天看源码，看到一句setvbuf(stdout, NULL, _IONBF, 0);关于setvbuf接口，linux系统编程手册P195有介绍。其中对_IONBF这个参数，做以下解释：不对IO进行缓冲，每个stdio库函数立刻调用write()或read()，并且忽略buf和size。可以分别指定两个参数为NULL或者0.如stderr,可以保证错误立即输出。看得一脸懵逼。其实意思就是，

2017-07-11 11:04:22 792

现在才被面试，都是因为自己zz。。四月份网申的时候写的远程面试，忘了改面试地点，于是成功GG错过面试。谁知五月份的时候超凡学长突然告诉我鹅厂有实习生补招，要了我最新的简历。本来觉得没什么希望，结果前几天突然收到了面试电话。截止现在前两面都过了，来趁热写一写面试总结。一面一面其实略GG，很多会的东西都回答得不是很好。面试时长大概20min。面试官上来让自我介绍，于是把自己简历上的东西大概都说了一下。

2017-06-02 20:32:09 8586 22

原创 [2017/05/18]操作系统调度算法--最短剩余时间优先算法的模拟实现

看了看上次更博还是3月份。。可怕可怕。果然是因为最近沉迷于读书无法自拔啊qwq（明明是因为懒吧啊喂！）今天看到一道OS题，题目是这样的：设有四个进程，它们的到达时刻和处理时间如下所示: 进程到达时刻处理时间 P1 , 0 , 8 P2 , 3 , 6

2017-05-18 18:53:03 7436

原创 [2017/3/30] 游戏公司面试总结！

视频面，比较简单。面试官人很好，还关心我单手拿手机会不会累233。问题都是对照简历问的。第一个问题：自我介绍。我就把简历上的东西说了一遍。第二个问题：本科学过哪些计算机相关课程？就实话实说了。。计算机原理和数据结构。第三个问题：进程线程区别？简直是面试必问。幸亏学长之前以这道题为例子告诉了我正确答题的方法，答得很轻松~第四个问题：select epoll 的区别？把用途，底层实现和效率问题都答了一下

2017-03-30 17:35:14 1616

原创 [2017/3/13]阿里面试总结

晚上10点半正在运动的时候突然接到电话。。于是让对方等了五分钟，找了个安静的地方开始电面。感觉面试官姐姐挺辛苦，非工作时间还来面试实习生，不仅如此，在我比较水的情况下都能保持很好的态度，很感动！！首先： 1.介绍你自己 2.一个你印象比较深的项目 linux： find命令？多进程多线程区别？怎么创建进程？僵尸进程？孤儿进程？ epoll select比较？死锁是什么？

2017-03-13 23:32:57 1427

原创 [2017/2/24]stack smashing detected问题

今天遇到了这个问题，百度了一下，说是由于数组空间分配不足引起的。另外这个问题只在有问题的函数返回后才会出现。所以用printf大法锁定了问题函数，然后重点检查了char类型数组，果然有一个开小了。以前从来没有遇到过这种问题，所以就记下来。

2017-02-24 09:35:32 558

原创 [2017/2/14]简单快速幂

好久都没更博了qwq题意给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。思路1.exponent是int类型，所以可正可负可为0。 2.最简单的方法就是粗暴地直接乘，但是时间复杂度高。 3.所以应该用快速幂。关于快速幂exponent转二进制，二进制中每一位都是后一位的2倍。算式好麻烦。。不写了。如果不会可以百度关键字：快速幂。c

2017-02-14 10:44:55 353

原创 [2016/12/19]kmp算法

上学期上数据结构的时候就学了这个算法，可是没好好听（摊手）。这次刷题的时候遇到了一个字符串匹配题，于是学会了这个算法。看了这么多博客，觉得对原理讲得比较好的就是这篇：戳这里。如果想理解，重点还是前后缀的概念。还有中间怎么跳的，这个自己写两个字符串，模拟一下就行。下面的代码写得非常好，对理解很有帮助。为了帮助理解，加入了一些输出。#include <iostream>#include <stdio.

2016-12-19 15:03:16 364

原创 [2016/12/15]perl程序勘误

今天要用到处理结果了，发现有些aa之间的距离莫名大。。于是检查了一下脚本，错得太离谱了。。难怪昨天用这个数据写程序，代码没错，但跑起来不断提醒segmentation fault。程序就那么几行代码不是我写的，但是错误的地方都在那里orz 首先！！chain写成chian是什么鬼啊！！完全没看出来。。由于perl语言的特性，不用声明变量所以就没报错，只是把数据当0处理了。其次，字符串比较不应该

2016-12-15 10:00:09 355

原创 [2016/12/14]统计一个串里segment的个数

题目大意串被空格分成若干segment，求它们的个数。我的思路c的话就老老实实根据空格和其前后字母判断吧。。 python一行就行了，split后再求len。别人的代码（题目很简单。。但是我写得很麻烦。在下面看到了别人的代码，觉得非常简洁，巧妙，所以粘上来）class Solution {public: int countSegments(string s) { int

2016-12-14 16:27:15 427

原创 [不定时更新]看到的好文

经常看很多文章，但是有些文章很棒，所以屯在这里，以便日后再读。基于TCP的网络程序自己以前做过个差不多的，但是现在忘了好多。。这篇文章主要关于基础函数以及它们背后的原理。以前只懂瞎写代码。。现在学了一些基础知识，然后回过头看，发现原理什么的都很好理解了！把《编程珠玑》读薄看的速度比书快

2016-12-13 16:44:01 360

原创 [2016/12/8]happy number:application of Floyd's Cycle Detection Algorithm

题目大意求一个数是不是happy number（定义戳这里）我的思路数字如果不是happy number，就会一直被困在循环里，因为会出现同一个数字出现两次的情况。直接的思路是用set，如果一个数字出现了两次，就返回false。别人的思路我的做法空间复杂度略高。看了下面别人的解，空间复杂度仅为N1。大致就是设立快慢两个指针，如果存在环，两个指针一定会相遇。参考：Floyd’s Cycle Det

2016-12-08 19:15:19 401

原创 [2016/12/8]我的第一个perl程序

程序功能读入一系列文件，按照给出的条件计算特定链上两两氨基酸之间的距离。程序不足及吐槽头一次接触perl，竟然能写出来。。撒花！第一次学新语言，写的第一个程序不是hello world哈哈哈，感觉还不错。 perl真的比c慢很多啊。。用c写这个几很快跑出来了，计算量还是加倍的。但是明显perl方便很多，c处理内存处理得想掀桌。（不过perl的正则表达式也用得想掀桌。。）为了节省时间，没有多做优

2016-12-08 10:36:27 588

原创 [2016/12/7]我要用到的perl知识

玛雅。。被抓来用一晚上的时间用perl完成一个文本处理的工作。以前从来没接触过perl，把要用的都粘到这里了。正则表达式相关Perl入门（四）Perl的正则表达式Perl 正则表达式 [匹配实例]强大的Perl中的正则perl 判断有没有数字Perl正则表达式初步

2016-12-07 19:07:22 532

原创 [2016/12/6]计算两个大数的和

题目大意如题，两个数字都以字符串的形式被给出。返回值是字符串别人的代码觉得很简单直接就A了。。但是看了别人的方法，才发现自己的思路太繁琐，繁琐在细分了很多终止条件。其实这些条件一言以蔽之，就是下面代码while的循环条件。下面是大神的代码class Solution {public:string addStrings(string num1, string num2) { int i

2016-12-06 20:35:25 438

原创 [2016/12/5]判断一个int类型数是不是2的幂

题目大意如题。。记得某次实验室周赛的时候做过这道题。那个时候直接打表过的，因为最多只有31种可能。现在依然打表→_→ 但是看到了别人的一种特别巧妙的做法，就保存一下。代码class Solution {public: bool isPowerOfTwo(int n) { return n > 0 && !(n&(n-1)); }};算法原理如果一个数是2的幂（0除

2016-12-05 20:17:14 467

原创 [2016/12/5]不用第三个变量交换两个数字

记得以前看到过这个方法，不过一直没记住。今天做题的时候突然要用交换两个变量。所以就想用这种方法啦！题目很简单，就是求斐波那契数列和。代码如下：int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; int a = 1; int b = 2; for(int i = 3;i<=

2016-12-05 10:54:50 341

原创 [2016/12/4]ACM校赛后感受

虽然好长时间都没做算法题了还是厚着脸皮报名了。。啊哈哈哈比完之后虽然在对手都比较水的情况下，排名还比较辣鸡，但还是挺高兴的。写代码这么久了，不知道自己有什么进步。快五个月没打acm了，以同样的题目水准做对比，感觉这几个月的进步还是很大的。首先，思考速度快了很多，直接反应在手速上了，全程代码主力。每写一行代码，脑海中就会浮现出可能会出错的点，并在大脑中另开条线程一一排查，并不影响写下面的代码。

2016-12-04 19:23:54 498

原创 [2016/12/2]求一个32位二进制数中1的数量

思路直接位运算走起，没啥好说的。代码int hammingWeight(uint32_t n) { int num = 1; int count = 0; while(n){ if(num & n) count ++; n = n >> 1; } return count;}

2016-12-02 11:05:22 630

原创 [2016/12/2]求二叉查找树结点的最低共有祖先（LCA）

关于二叉查找树写这篇就是为了复习二叉查找树的相关概念啦！二叉查找树（Binary Search Tree）,又称二叉搜索树，二叉排序树。它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值. 它的左、右子树也分别为二叉排序树。题目思路刚开始做这道题一

2016-12-02 10:56:17 314

原创 [2016/12/1]python数据类型之字典

字典简介字典是无序的，它不能通过偏移来存取，只能通过键来存取。字典 = {‘key’:value} key：类似我们现实的钥匙，而value则是锁。一个钥匙开一个锁特点内部没有顺序，通过键来读取内容，可嵌套，方便我们组织多种数据结构，并且可以原地修改里面的内容，属于可变类型。（如何改变？）组成字典的键必须是不可变的数据类型，比如，数字，字符串，元组等，列表等可变对象不能作为键。创建字典inf

2016-12-01 15:27:12 268

原创 [2016/12/1]判断是否存在重复元素 -- c++ set的巧妙用法

题目大意给你一堆int型元素，判断里面是否有重复元素。有返回TRUE，没有则返回FALSE。我的思路sort一遍再遍历，找出重复元素后return true，其他return false。set方法把数组中的元素全部添加进set，然后比较数组大小和set大小。如果相等则return false，反之则return true.set代码bool containsDuplicate(vector<int

2016-12-01 11:34:04 8932 1

原创 [2016/11/30]python数据类型之元组和集合

元组特点1.有序的集合 2.通过偏移来取数据,支持切片。（查看支持方法，只需要 dir(变量）) 3.属于不可变的对象，不能在原地修改内容，没有排序，修改等操作。 “修改”方法：如果要修改，先用list把元组转成列表，再用tuple转换成list。或者，先生成一个tuple的拷贝（如何生成？），再按上面的方法改。那为什么有列表还要有元组呢？元组不可变的好处。保证数据的安全，比如我们

2016-11-30 15:36:34 311

原创 [2016/11/30]项目V1.0：计算两个氨基酸之间的中心碳原子距离和最近距离

代码功能给出若干文件，计算出文件中特定肽链中特定某几个氨基酸间的中心碳原子距离和最近距离，并输出到文件。（输出到文件这里，并不确定怎样的数据好处理，所以还没写完，想好了补上。另外，计算特定肽链这个功能，只能在代码里改，不好，日后完善。）缺点1.链表的数据存储方式简直不能再麻烦，线性表加链表的方式更好，如果有时间再完善这个。 2.一次算完所有肽链的数据，不好。应该一条一条算，算完释放内存，再接着

2016-11-30 12:18:42 2459 1

原创 [2016/11/28]判断一个数是否是回文数，但不能开多余空间

题目大意如题。所以转成字符串再判断显然不行。思路所以怎么做呢？思考回文数的特点。翻转所得到的数字还是原来的数。所以，如果能翻转这个数字，再把结果和原来的数比较，就可以得知这个数是不是回文数了。代码代码如下bool isPalindrome(int x) { if(x<0) return false; int val = x; int total = 0; int en

2016-11-28 17:08:50 437

原创 [2016/11/25]九宫格问题

题目大意数独规则点这里注意可以有格子是空的。空的格子用“.”表示。方法一.位运算知道了这个之后，就很好办啦。因为数字只有九个，而且不允许重复出现。直接想到位运算！表示当前数字，只需要把1向右移动当前数字位。然后设置一个状态变量，存储当前有多少数字出现过。把他们相与，如果为0说明此数字还没出现过，就更新这个状态变量，即把他们做或运算。计算3*3格子的时候参考了别人的代码，想法很巧妙，直接两重循

2016-11-25 16:44:37 676

原创 [2016/11/24]python数据类型之列表

列表特点 1.有序的集合 2.通过偏移来索引，从而读取数据 3.支持嵌套 4.可变的类型 (联想c中的数组，可以理解为数组和vector的升级版)####列表切片####>1.正向索引>2.反向索引>3.默认索引a = [1,2,3,4,5,6,7]a[0,4,1]#[1,2,3,4]#正向索引,从左向右取。第三个参数是步长，带方向。a[-1,-4,-1]

2016-11-25 10:54:46 480

原创 [2016/11/21]机智的算法：在长度为len的数组中找出出现次数大于len/2的元素

题意如标题所说。注意，默认此数组中有元素的出现次数为len/2。刚开始看到这道题，觉得简单到爆。直接sort一遍再取len/2处的元素不就行了嘛。这样的时间复杂度为nlogn。后来看了下面这种别人的做法，觉得十分巧妙。膜膜膜！这种算法叫majority vote algorithm，时间复杂度为n。大致思路是： As we sweep we maintain a pair consi

2016-11-21 18:18:13 583

原创 [2016/11/20]pyhton概览加数据类型

变量名区分大小写。尽量用字母或下划线开头，不要用数字开头。不要在中间加‘.’赋值赋值语句从右到左。按符号优先级走。圆括号>指数操作>除，取余，乘法>加减运算符其他类比c。除了**，是平方的意思。python特点一切数据皆对象.对象包括方法。一切变量都是对数据对象的一个引用，并没有存数据 python内部引用计数。sys.getrefcount(数据)。结合现象不负责任

2016-11-20 23:27:22 360

原创 [2016/11/18](补)计算机组成原理第三章笔记

第三课.指令系统体系结构一.X86体系结构 ①Intel 8086： 1.主要特点 16位通用寄存器，可以处理16位数据，也可以处理8位数据。对外：16根数据线，20根地址线。可寻址范围：2^20byte（1M字节单元）。物理地址形成采用段加偏移模式。2.8086寄存器模型：四种寄存器类型：指令指针寄存器，通用寄存器，标志寄存器，段寄存器。通用寄存器：数据寄存器

2016-11-18 18:06:53 569

原创 [2016/11/17](补)计算机组成原理第二章笔记

第二课.计算机概览一.概览 —— 基本计算机模型的两大部分 ①概览：把计算机模型比作餐馆，联想记忆。 ②两大部分：１.存储器２.控制器控制器的基本组成见图。两部分由控制总线，地址总线，数据总线相连。除此之外，控制器里还有内部总线此处的重点在于，记清每个部件的名字以及其作用二.执行指令的过程 ①指令的格式及意义就像 ADD R0,

2016-11-18 15:16:57 817

原创 [2016/11/17]翻转二叉树

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.内心复杂地做完了这道带有传奇色彩的题。。代码如下：struct TreeNode* invertTree(struct TreeNode*

2016-11-18 13:29:40 290

原创 [2016/11/17]不用加减号，求两个数的和

题目说不用普通运算符，首先想到的就是用位运算。那用位运算该怎么做呢？这时就拿起纸笔，看看你自己是怎么做二进制加法的。只要你明白了，就能告诉计算机该怎么做。首先发现，在做某位的加法时，单看这一位。如果两个数相同，得出的是0，反正为1。这不就是异或嘛！知道了这个，怎么处理进位呢？继续做，发现进位的特点是：都是进到下一位，且当且仅当两个加数都是1时，才可产生进位（明显是按位与啊）。把按位与得到的数

2016-11-17 11:27:45 1223

原创 [2016/11/16]求一棵树左叶子的和

不能一日不写代码！做题练手。这种情况肯定一下就想到递归啦。首先明确返回条件(是叶子节点)。然后，对于每一层递归，其主角都是以参数root为根节点的树。递归要做的，就是把这棵树左子树的左叶子和找出来，然后把这棵树右子树的左叶子和找出来，然后返回二者的和。代码如下：（数据是按层次遍历给出的。）/** * Definition for a binary tree node. * struct Tree

2016-11-16 16:47:40 834

原创 [2016/11/14]naive问题中异或的巧妙用法

一道简单题，大意是给你一个数组，除了一个数只出现一次，其他全部的数字都出现了两次。求那个数。正常人的思路都是先sort一遍，再写个step为2的for循环找。这样做时间复杂度nlogn+n，空间复杂度1。但是！！！下面这个做法用了相同的空间复杂度，时间复杂度仅为n。巧妙利用了按位异或的性质：一样为0，不一样为1。最后异或之后只剩下不同的数啦！粘了代码如下：int singleNumb

2016-11-14 10:51:34 326

原创 [2016/11/13]c语言的细节问题：malloc和char*

1.malloc：当malloc里参数为0时，系统还是会分配空间，并不会返回NULL。返回NULL的原因只有分配内存失败。2.’/0’的问题：用char*来为字符串分配空间时，如果串的长度为len，malloc函数里的参数为len+1，多分配的一个字节用来填写/0。不填在电脑上输出的时候没问题，在oj上就挂了。还是养成这样的习惯吧。今天遇到的这两个问题都是在做十分简单的题时出现的。平时coding时

2016-11-13 16:34:53 762

原创 [2016/11/1][http服务器开发]终于解决了一个为期一周的bug（开心脸

开心的同时嫌弃自己的智障orz。。遇到的bug是：client那边发出下载请求之后，发送请求的fd关闭。服务器在添加cache功能后，会出现bug：此后，server在用write发送了一个len的字节后，服务端直接崩溃退出，不产生core文件。但是，如果不从shared memory中读数据，而是直接open本地文件，从其中读数据，这种现象就不存在。因为从本地文件中读没有这个问题，所以一

2016-11-01 18:23:41 373

原创 [2016/11/1][tcpdump]本机抓包命令

sudo tcpdump -S -nn -vvv -i lo port 9838 > 1.txtsudo：虽然开了root但是不知道为什么，系统总是提示Operation not permitted（摊手），所以就加上了-i lo ：供本机抓包用port ：此处指定端口> 1.txt ：重定向输出，抓得数据可在本文件夹下1.txt中找到

2016-11-01 17:52:47 2755

空空如也

空空如也