- 博客(747)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 #pragma once 和 #ifndef 的联系和区别？
组织头文件的时候，编译时经常会遇到重复定义的error，这个问题的根源在于一个文件被include多次，如何解决这个问题呢？有下面两种方式1 #ifndef方式比如： #ifndef __SOMEFILE_H__ #define __SOMEFILE_H__ ... ... // 一些声明语句 #endif2 #pragma once方式比如：#pragma on...
2019-08-04 13:04:32
374
原创 select、poll、epoll等
POSIX概述 同步IO、异步IO、阻塞IO、非阻塞IO，这几个词常见于各种各样的与网络相关的文章之中，往往不同上下文中它们的意思是不一样的，以致于我在很长一段时间对此感到困惑，所以想写一篇文章整理一下。 POSIX(可移植操作系统接口)把同步IO操作定义为导致进程阻塞直到IO完成的操作，反之则是异步IO。 按POSIX的描述似乎把同步和阻塞划等号，异步和非阻塞划等号...
2019-07-21 00:49:47
411
原创 Socket编程学习总结
读书的时候，每当遇到需要网路通信的时候，总是随便百度一下，然后就随便写写就过去了，对于socket本身并没有太深的认识。因为目前的工作中用到了网络通信，并且在过去写的socket通信一般都是阻塞的，这在项目中是无法忍受的。 因此，本文主要参考网上的多篇博客，然后系统的总结了socket的概念，并给出了编程实例，不喜勿喷。网络通信概念 网络层的ip地址可以唯一标...
2019-07-20 08:12:31
1860
原创 为什么用成员初始化列表会快一些？
首先把数据成员按类型分类 1。内置数据类型，复合类型（指针，引用） 2。用户定义类型（类类型）分情况说明： 对于类型1，在成员初始化列表和构造函数体内进行，在性能和结果上都是一样的 对于类型2，结果上相同，但是性能上存在很大的差别因为类类型的数据成员对象在进入函数体是已经构造完成，也就是说在成员初始化列表处进行构造对象的工作，这是调用一个构造函数，在进入函数体之后，进行的是 对已经...
2018-09-10 15:27:54
3700
原创 C++ 自定义二元谓词函数的写法
写的方法struct cmp { bool operator()(pair<int, int>& a, pair<int, int>& b) { if (a.first == b.first) return a.sec
2018-09-08 15:15:25
1810
原创 增长一下姿势：什么是彩虹表？
https://blog.csdn.net/nie19940803/article/details/76641498https://www.cnblogs.com/yushuo1990/p/6007068.htmlhttps://blog.csdn.net/gscaiyucheng/article/details/17113073
2018-09-05 13:39:06
398
原创 虚基类调用顺序 + 不能继承的类
https://blog.csdn.net/owen7500/article/details/52432970 https://www.cnblogs.com/haoyuanyuan/archive/2013/04/25/3041250.html
2018-09-05 13:36:24
1018
原创 PDD笔试题：最小字符串
直接递归即可需要注意的地方是set是有序的，所以DFS得到第一个结果one就是最终答案代码如下：#include <iostream>#include <vector>#include <map>#include <set>#include <queue>#
2018-08-30 19:55:54
2664
原创 LeetCode上一道经典的面试题-O（1）实现LRU Cache
参考这个博客这里写链接内容 思路： 每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度） 这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动。 当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满时，淘汰链表最后的位置就是了。 还有这个博客简单的LRU Ca...
2018-08-09 15:42:12
732
原创 0交换排序
长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成以下函数#include <iostream>#include <vector>#include <map>#include <unordered_map>#include <set>#include &a
2018-07-01 18:52:46
1773
原创 C++ 虚函数表指针以及虚函数指针的确定
【摘要】很多教材上都有介绍到虚指针、虚函数与虚函数表，有的说类对象共享一个虚函数表，有的说，一个类对象拥有一个虚函数表；还有的说，无论用户声明了多少个类对象，但是，这个VTABLE虚函数表只有一个；也有的在说，每个具有虚函数的类的对象里面都有一个VPTR虚函数指针，这个指针指向VTABLE的首地址，每个类的对象都有这么一种指针。今天，我们就来解决这个问题，同一个类的不同对象，是不是拥有“相同”...
2018-06-14 14:30:05
2824
1
原创 this指针到底存放到哪里
那么C++中类成员函数是如何知道哪个对象调用了它？并正确显示调用它的对象的数据呢？当一个对象调用某成员函数时会隐式传入一个参数， 这个参数就是this指针。this指针中存放的就是这个对象的首地址。 这和C中通过向函数传递结构体变量的地址是不是很像？只是传参形式不一样罢了！ 在C中我们是手工把结构体变量和函数关联起来的，而C++则是编译器帮我们把类数据和成员函数关联起来的并通过名称粉碎和编译...
2018-06-13 15:09:55
4290
原创 程序员面试金典习题集锦04
参考这个链接如何测量上下文切换时间 首先明白大的数字有什么特点，大的数字= 两个数字的和 - 小的数字，较大的数字。可以用绝对值的做法来做的，构造差值。 令result = (|a+b| + |a-b|) / 2; 那么，如果a > b ,则有: result = a;符合要求 这道题需要注意的地方就是全部是负数的情况 遇到这种题就要...
2018-05-05 14:46:06
443
原创 程序员面试金典习题集锦03
最直接的方法就是递归，参考这个博客算出有几种括号的放法可使该表达式得出result值 参考这个链接给定一个排序后的数组，包含n个整数，但这个数组已被旋转过多次，找出数组中的某个元素 这样的情况很有可能是两点： 1）使用C风格字符串，导致指针越界访问：严格检查使用c风格字符串 2）使用随机数，导致不同情况下的bug不一样：在log中打印seed，然后复现bug再去排除...
2018-05-05 10:21:35
359
原创 程序员面试金典习题集锦02
寻找二进制1的个数相等的最大和最小值 最笨的方法，就是暴力求解， 可以通过分析二进制字符串来实现寻找 直接异或，然后求解1的数量即可 我想到的最笨的方法就是直接相加，然后数组求和即可。 感觉应该是可以通过位运算来做的，下面是智力题： ...
2018-05-04 20:39:21
337
原创 程序员面试金典习题集锦01
这道题很简单，但是不一定可以转换到这个思路上来。 如何使用一个数组实现三个栈？ 还有一道关于MinStack的题，这也值得学习， leetcode 155. Min Stack 最小栈的实现 寻找二叉查找树的下一个结点： 寻找二叉树子树的存在与否？ ...
2018-05-03 09:45:19
326
原创 汉诺塔问题
汉诺塔比较经典的实现是利用递归，但也可以利用堆栈。题意理解：有A,B,C三个柱子，将A柱子上的N个盘子（从大到小排列）移到C柱子上，每次只允许移动一个盘子，并且保证每个柱子上的盘子的排列都是从大到小。1、递归实现 假设只有一个盘子，那么只需实现 A->C 这个动作； 如果有两个盘子，那么需要 (1)A->B; (2)A->C; (3)B-&g...
2018-05-02 11:08:19
487
原创 队列的实现
就是考察如何实现一个队列这道题考察的是细节代码如下：#ifndef QUEUE_H#define QUEUE_H#include<cassert>#include<iostream>using namespace std;template<typename T>class Queue{public: Queue(int m...
2018-05-01 20:28:57
301
原创 动态求解中位数
题意是这样的，给你一个序列寻找中位数？其实这个可以转化为TopK问题，但是假如这个数组不断的变化呢？这个时候可以考虑使用堆来解决。这是一个很经典的问题，值得反思和学习。参考这一道题leetcode 295. Find Median from Data Stream 双优先级队列 + 中位数查找代码如下：#include <iostream>#include <...
2018-05-01 20:05:58
949
原创 字典树Trie树 + 深度优先遍历DFS
字典树是非常藏剑的数据结构，一定要学会使用。这个时一定要学会手写的代码！！！！！C++版本如下：class TrieNode {public: // Initialize your data structure here. TrieNode *child[26]; bool isWord; TrieNode() : isWord(false) ...
2018-05-01 19:30:26
2965
原创 老鼠与毒药问题
大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右...
2018-04-05 13:47:36
995
转载 经典图算法：二分图匹配——匈牙利算法和KM算法 + 我觉得这个算法要背下来
二分图的概念二分图又称作二部图，是图论中的一种特殊模型。 设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。 二分图的性质定理：当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。如果无回路，相当于任一回路的次数为0，故也视为二分图。二分图的判定如果一个图是...
2018-04-02 10:49:41
547
原创 面经笔记+来自腾讯后台开发内推2019
线程里面有什么是独立的？进程包含代码数据文件，这个是进程内的所有线程共享，但是线程有自己的线程ID、程序计数器、寄存器和栈独立的资源。一个进程一定要有一个线程吗？没有线程的进程是什么？协程是什么？协程是在线程之上由“用户”构建的并发单元，对OS来说无感知，协程的切换由用户自己管理和调度。（这里的用户是相较于内核而言的，一些通用库这里也理解为用户）同步和互斥是怎么做的...
2018-03-25 21:00:39
689
原创 20180324今日头条编程测试题：拼接数组 + Majicc操作
师兄的做法很棒，这道题的思路是这样的，假如可以均分成i份，那么可以直接执行第二种操作i-1次，否者的话执行第一种操作。#include <iostream>using namespace std;int main(){ int n; cin>>n; int res=0; for(int i=2;i<=n;) {...
2018-03-24 21:11:50
532
原创 2018腾讯游戏面试总结
关于岗位我首先报了腾讯游戏的提前批，刚好有一个师兄在深圳总部的光子实验室，所以我直接申请的是后台开发岗位。这个提前批是无需笔试的。第一次电话面试这次面了一个小时，其中前半个小时都在询问项目的情况，这个就略过了，其余的都是一些基础的知识。关于C++：C++的三大特性？多态是什么实现的？指针和引用的区别？const有什么用法？内存泄漏、数组越界问题、指针非法...
2018-03-21 11:19:38
8471
1
原创 2018拼多多内推编程题：带key的迷宫+很棒的做法
链接：https://www.nowcoder.com/questionTerminal/e3fc4f8094964a589735d640424b6a47 来源：牛客网 作者：超蓝の悟空时间限制：1秒 空间限制：131072K假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上...
2018-03-20 17:00:45
2284
1
原创 leetcode 179. Largest Number 数组可以组成最大的数
Given a list of non negative integers, arrange them such that they form the largest number.For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.Note: The result may be very l...
2018-03-14 13:19:49
633
原创 C++ 多态面试题
什么是多态？有哪些分类？答：多态是面向对象的重要特性之一，它是一种行为的封装，是同一种事物所表现出的多种形态，简单地说是”一个接口多种实现“ 有两种类型的多态性： 编译时的多态性。编译时的多态性是通过重载来实现的。 运行时的多态性。运行时的多态性是通过虚成员实现的。构造函数为什么不能是虚函数？1.从存储空间角度。 虚函数对应一个vtable，这个vtable其实是存储在对象的...
2018-03-11 21:12:01
2951
1
原创 C++ 随手笔记
C++成员变量初始化顺序成员变量在使用初始化列表初始化时，与构造函数中初始化成员列表的顺序无关，只与定义成员变量的顺序有关。因为成员变量的初始化次序是根据变量在内存中次序有关，而内存中的排列顺序早在编译期就根据变量的定义次序决定了。这点在EffectiveC++中有详细介绍。如果不使用初始化列表初始化，在构造函数内初始化时，此时与成员变量在构造函数中的位置有关。注意：类成员在定义时，是不...
2018-03-10 14:56:48
206
原创 剑指offer读书笔记：第六章，面试中的各项个能力02
问题01 N个骰子的点数 基于递归求骰子点数，时间效率不够高。先把骰子分成两堆，第一堆只有一个，第二堆有n-1个，单独的那一个可能出现1到6的点数，我们需要计算从1-6的每一种点数和剩下的n-1个骰子来计算点数和。还是把n-1个那部分分成两堆，上一轮的单独骰子点数和这一轮的单独骰子点数相加，然后再和剩下的n-2个骰子来计算点数和。不难发现这是一种递归的思路。定义一个长度为6n-...
2018-03-10 14:28:53
302
原创 剑指offer读书笔记：第六章，面试中的各项个能力01
问题01 数字在排序数字中的数量 最笨的方法使用Map统计遍历，但是题目是有序数组，所以必然是二分查找，可以去寻找key的上一个元素和下一个元素，时间都是O(lon(n))，然后计算范围即可。问题02 二叉树的深度这个实在是太简单了，直接DFS深度优先遍历即可问题03 数组中只出现一次的数字 先考虑一个数组里只有一个数出现一次，其他两个数都出现两...
2018-03-09 21:42:36
249
原创 剑指offer读书笔记：第五章，优化时间和空间效率
问题01 数组中出现次数超过一半的数字 对于一个数组超过一半的数字就是众数，直接摩尔投票方法，其他的方法都是渣渣。参考这个博客找出数组中出现次数超过一半的数+ 寻找众数 + 摩尔投票法 问题02 最小的k个数 这道题和求第k小的数的做法是一样的，直接快排的思想去做即可。其实还可以这么做 问题03 连续子数组的最大和 典型的动态规划DP...
2018-03-09 20:42:17
580
原创 剑指offer读书笔记：第四章，解决面试题的思路02
问题01 二叉树中和为某一值的路径 直接DFS深度优先遍历即可问题02 复杂链表的复制 方法1是通过链表查找来得到pSibling指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：复制原始链表上的每个结点N创建N’，然后把这些创建出来的结点用pNext连接起来。同时把问题0...
2018-03-09 17:45:51
267
原创 剑指offer读书笔记：第四章，解决面试题的思路01
问题01 二叉树的镜像–>反转二叉树 这个就是著名的反转二叉树问题void exchangeBTree(BTRee *root){ BTRee *t; if(root) { t=root->rChild; root->rChild=root->lChild; root->l...
2018-03-09 16:58:15
253
原创 剑指offer读书笔记：第三章，高质量的代码
问题01 代码的全面性在写代码的时候要注意各种情况的考虑，一般分为三个方面：功能测试：这个主要测试可以不可以完成函数的功能，边界测试：这个尽量要考虑各种极端的case，比如循环条件的边界判断、数据溢出的考虑等等负面测试：这个主要是各种错误的输入，靠考虑系统的鲁棒性，比如指针为null应该怎么考虑，等等。 - 问题02 数值的整数次方 对于这道题，要考虑四种情...
2018-03-09 16:08:24
245
原创 剑指offer读书笔记：第二章，面试基本知识03
问题01 排序算法 && 旋转数组 上面的做法是基于统计来实现排序。 很明显最直接的方法就是暴力遍历，复杂度是O(n)，但是这显然不是面试官想要的做法，这明显是考察二分查找。可以看出每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。这个才是解决本问题的关键的地方，那么可以得到如下的流程：...
2018-03-09 14:32:10
217
原创 2018阿里巴巴算法岗位实习面试总结（朋友的面试）
编程题给一个圆盘分成N个扇形有M个颜色，要求同色不可以相邻，文有多少种做法。 一面他报的是算法岗位是，所以问了一个算法题，题目是这样的：给你一个浮点数的集合，随机取出两个数做乘积，求乘积的最大值。最笨的方法就是O(n*n)去做乘积，然后遍历得到最大值。存在O(n)的做法，遍历数组把元素按照整数负数分开，假如只存在正数那么计算前两大的值去做乘积；假如只存在负数去前量小的去...
2018-03-09 09:14:44
8736
原创 剑指offer读书笔记：第二章，面试基本知识02
问题1 有序矩阵+右上角查找方法有二暴力查找右上角查找问题变形：寻找第k小的数据方法有二 - 暴力遍历然后排序 - 右上角查找+二分查找参考这个链接leetcode 668. Kth Smallest Number in Multiplication Table 有序矩阵搜索 + 右上角二分搜索 问题02 字符串地址 str1和str2会自...
2018-03-08 20:47:06
237
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人