- 博客(276)
- 收藏
- 关注
RSS订阅原创 345. 反转字符串中的元音字母
题目编写一个函数，以字符串作为输入，反转该字符串中的元音字母。示例1输入：“hello”输出：“holle”示例2输入：“leetcode”输出：“leotcede”题解1将元音字母的大小写放在set中,类比二分法class Solution {public: string reverseVowels(string s) { int left = 0; int right = s.size()-1; set<char
2021-02-21 15:43:27
363
原创 648 单词替换
题目在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。你需要输出替换之后的句子。示例1输入：dictionary = [“cat”,“bat”,“rat”], sentence
2021-02-15 17:46:46
285
原创 DFS（深度优先遍历）
声明：参考labuladong的算法小抄回溯算法框架vector<string>result;void backtrack(路径，选择列表）{ if （满足结束条件） { result.push_back(); return; } for(auto 选择：选择列表）//这里的for循环不是必要的 { 做选择 backtrack(路径，选择列表）
2021-01-24 16:57:02
323
原创 139 单词拆分I
题目给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例1输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。示例2输入: s = “applepenapple”, wordDict = [
2021-01-24 16:27:22
152
原创 5 最长回文子串
在这里插入代码片@TOC内容给你一个字符串 s，找到 s 中最长的回文子串。示例1输入：s = “babad”输出：“bab”解释：“aba” 同样是符合题意的答案。示例 2：输入：s = “cbbd”输出：“bb”示例 3：输入：s = “a”输出：“a”示例 4：输入：s = “ac”输出：“a”思路一、暴力解法首先肯定都会想到暴力解法，如果使用暴力解法这道题就很简单了两层循环就可以找到答案，但是这样其 时间复杂度很高O(n^3) ，由于只用到了常数
2021-01-23 17:39:59
93
2
原创 内联函数和类内定义
一、内联函数关键字：inlineinline void test(){ cout<<"fun"<<endl;}特点：1、为了解决程序中函数调用的效率问题，以空间换时间。 在程序中，调用内联函数时，该函数在编译时被替代，而不是像一般函数那样在运行时被调用，如下图所示：2、内联函数中的局部static对象，在不同cpp文件中访问时共享二、类/结构体/联合体 内定义即在/结构体/联合体 里面定义成员函数class P...
2020-09-05 13:49:54
1411
原创 51 上一个排列、下一个排列
给定一个整数数组来表示排列，找出其上一个排列。样例给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]给出排列[1,2,3,4]，其上一个排列是[4,3,2,1] 思路：1、上一个排列就是所有全排列按照升序排列后的上一个排列2、如数字排列63624578，其上一个排列为63587642由于是在所有升序排列中找到上一个排列，所以对于某一个排列，我们假设从某一位开始，后面...
2018-08-20 18:08:31
952
转载 socket阻塞与非阻塞，同步与异步、I/O模型
https://blog.csdn.net/hguisu/article/details/7453390
2018-08-16 20:52:41
250
原创 服务器编程框架
虽然服务器种类很多，但编程框架基本相同，不同之处在于逻辑处理 I/O处理单元是服务器管理客户连接的模块。完成以下工作： 等待并接受新的客户连接，接收客户数据，将服务器响应数据返回给客户端 但数据的收发不一定在I/O处理单元中执行，也可能在逻辑单元中执行，具体在何处执行，取决于事件处理方式一个逻辑单元...
2018-08-16 20:32:34
367
原创 高性能服务器程序框架
服务器主要包括如下三个主要模块：I/O处理单元，四种I/O模型和两种高效事件处理方式逻辑单元，逻辑单元的高效并发方式存储单元，服务器的可选模块服务器模型C/S模型：所有客户端都通过访问服务器来获取所需的资源C/S模型的运行逻辑：服务器启动后，首先创建一个或多个监听socket,并调用bind函数将其绑定到服务器感兴趣的端口上，然后调用listen函数等待客户连接。...
2018-08-16 20:10:28
248
原创 两种高效的事件处理方式
Reactor模式它要求主线程（I/O处理单元）只负责监听文件描述符上是否有事件发生，有的话就立即将该事件通知工作线程（逻辑单元）除此之外主线程不做其他实质性的工作，读写数据以及接受新的连接，以及处理客户请求均在客户线程中完成。使用同步I/O模型（以epoll_wait为例）实现的Reactor模式的工作流程：1）主线程往epoll内核事件表中注册socket上的读就绪事件。2）...
2018-08-16 19:45:50
410
转载 内存分配的三种方式
把所有的点都说到，才能说明你有足够的项目经验，在实际工作的时候不会因为一些小问题而产生一些严重的bug，也证明了你有实力胜任这份工作。要回答这个问题，我们必须先要理解C++的内存管理方式，需要站在内存四区的角度去审视一下代码，这样整个理解了内存分配的方式，回答的时候就只需要注意一些细节了。写一个例子然后画一下内存示意图。int getmem(char **myp,int length)/...
2018-08-14 14:57:58
18622
原创 智能指针
智能指针是行为类似于指针的类对象。为什么需要智能指针？ 为了避免当系统异常退出的时候避免资源泄漏（内存）创建指向str的指针ps。有一个问题。如果函数异常终止，则本地变量将从栈内存中删除——因此ps占据的内存将被释放，如果ps指向的内存也被释放了，则就不需要后面的智能指针了。或者如果ps有一个析构函数，当ps过期时，调用它的析构函数删除它指向的内存就行。可惜，没有。原因是ps是一个常...
2018-08-14 11:08:30
185
转载 c++线程中的几种锁
这个是在中兴面试中被面试问到的一个题“你知道线程中的自旋锁么？”，我当时一脸懵逼，不知道。回来后整理下，在这里对线程中的锁进行一个学习。线程之间的锁有：互斥锁、条件锁、自旋锁、读写锁、递归锁。一般而言，锁的功能越强大，性能就会越低。1、互斥锁互斥锁用于控制多个线程对他们之间共享资源互斥访问的一个信号量。也就是说是为了避免多个线程在某一时刻同时操作一个共享资源。例如线程池中的有多个空闲线...
2018-08-12 20:20:42
246
转载 有关线程池的面试题
（1）因为我的项目中写到一个项目：简单线程池的实现，那么面试官就问我“如何保证线程池是线程安全的”。首先给大家普及下线程池的知识。我写的线程池是使用POSIX写的。线程池整个项目中包括两个类：一个是Task类，用于描述执行一个任务的方法（一个函数）和执行这个任务所需要的参数（函数的参数）。另外一个类就是我们的线程池类ThreadPool类，在线程池中主要有两个队列，一个是Task类队列，用于...
2018-08-12 20:17:19
10280
原创 STL之vector
容器、结构与分类 容器 ：所有的容器都维护着两个迭代器，分别指向头和尾STL容器是将运用最广的数据结构实现出来根据数据在容器中的排列特性，将这些数据结构分为序列式和关联式两种序列式容器（advlsqp）array\deque\vector\list\queue\priority-queueArray连续空间，其迭代器就是指针。 VectorVector&l...
2018-08-12 16:31:22
572
原创 STL之（底层哈希表）hash_set、hash_multiset、hash_map,hash_multimap
hash_set与hash_multiset：实值就是键值以hashtable为底层机制，所以几乎所有的hash_set行为，都是转调hashtable的操作行为。 与set、multiset相比，hash_set、hash_multiset没有自动排序功能。 hash_set与set一样，实值就是键值。使用方式与set完全相同插入元素操作采用底层机制hashtable...
2018-08-12 16:20:07
523
原创 STL之(哈希表）hashtable
容器hashtable(哈希表）：另外一种底层机制其基本原理是：使用一个下标范围比较大的数组来存储元素。把关键字Key通过一个固定的算法函数即所谓的哈希函数（散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的list空间里。也可以简单的理解为，按照关键字key为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地...
2018-08-12 16:07:30
5457
原创 STL之（底层红黑树）set、multiset、map、multimap
set、multset容器set/multiset是以rb_tree为底层机构，因此有元素自动排序的特性。 排序的依据是key，而set/multiset的value和key合一：value就是key，其中value由key和data组成。 set/multiset提供遍历操作和迭代器，按正常规则（++iter）遍历，便能获得排序状态（sorted） 我们无法使用set/multiset...
2018-08-12 15:55:54
4208
转载 STL之关联式容器----红黑树
标准STL关联式容器分为set(集合)和map(映射表)两大类以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器的底层机制均以RB-tree红黑树完成。它也是一个独立容器，但不开放给外界用 不在标准规格之列的关联式容器hash table(散列表/哈希表),和以hash table为底层机制的hash_set(散列集合)、hash_map(散列...
2018-08-12 10:13:45
729
原创 STL之stack、queue、priority_queue
栈的底层结构：以缺省情况下的deque作为其底层容器（封闭底端出口和入口，利用deque的成员函数完成stack成员函数的定义），list也可以作为其底层容器一种先进后出的数据结构，只能在最顶端新增、移除、取出元素。即不能遍历，所以stack没有迭代器 队列的底层结构：以缺省情况下的deque作为其底层容器（封闭deque的底端出口和顶端入口，利用deque的成员函...
2018-08-12 09:09:33
298
转载 STL面试题
1、说说std::vector的底层（存储）机制。（如何实现vector）vector维护的是一个连续线性空间（动态数组），它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围（注意finish指向的是最后一个元素后面那个元素）并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。 当我们以push_back()将新元素插入于vec...
2018-08-11 22:34:30
433
原创 STL容器迭代器失效情况分析、总结
当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效，因此我们为了避免危险，应该获取insert或者erase返回的迭代器，以便用重新获取的新的有效的迭代器进行正确的操作 iter=vec.insert(iter);iter=vec.erase(iter); 迭代器失效的类型： 1.由于插入元素，使得容器元素整体“迁移”导致存放原容器元素...
2018-08-11 22:27:42
9249
3
原创 STL之deque
deque的底层实现vector是单向开口的连续线性空间,deque则是一种双向开口的由一段一段的定量连续空间组成，即可以在头尾两端分别做元素的插入和删除操作。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间而我们也知道vector的头部操作效率非常差。 deque采用一块map（不是STL中的map）作为主控。这里的map是一小块连续空间，其中每个元素（此处称为...
2018-08-11 22:05:19
524
原创 STL之list
list的设计list由三部分构成：list节点、list迭代器、list本身特点：每次插入或删除一个元素，就配置或释放一个空间。对空间的运用不浪费对于任何位置的元素插入或元素移除，list永远是常数时间list节点list是一个双向链表，所以其list结点中有前后两个指针,当然还有值。如下：//组成list的结点template<typename T>s...
2018-08-11 20:25:37
138
原创 有关笔试题，输入输出格式的几个特殊例子
题目描述老师想知道从某某同学当中，分数最高的是多少，现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩.输入描述:输入包括多组测试数据。每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。学生ID编号从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i个...
2018-08-11 18:33:35
863
原创 剑指offer 1 赋值运算符函数
题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数class CMyString{ public: CMyString(char*pData=NULL); CMyString(const CMyString&str);//拷贝构造 CMyString&operator=(const CMyString&str)...
2018-08-09 21:15:22
157
原创 剑指offer 47 礼物的最大价值
题目描述 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘1 10 3 8 12 2 9 6 5 7 4 11 3 7 16 5 礼物的最大价值为 1+12+5+7+7+16+5=53。剑指offer答案： 思路：动态规划...
2018-08-09 19:59:04
538
原创 剑指offer 48 最长无重复字符的子字符串
给定一个字符串，请找出其中无重复字符的最长子字符串。样例例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为3。对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。挑战O(n) 时间分析：这里是子串，不是子序列，所以必须是连续的。如果给一个例子中的例子"abcbd"，让你手动找无重复字符的子串，该怎么找。我们肯定会一个字...
2018-08-09 18:19:25
309
原创 剑指offer 44 数字序列中某一位的数字(类似题43）
题目描述 数字以01234567891011121314…的格式序列化到一个字符序列中。在这个序列中，第5位是5（从0开始），第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。分析：最直观的方法就是从0开始逐一枚举每个数字。每枚举一个数字，就求出该数字是几位数，并把该数字的位数和前面所有数字的位数累加。如果位数之和仍然小于或者等于输入n，则继续枚举下一...
2018-08-09 16:56:58
447
原创 剑指offer 把数字转换成字符串（动态规划）
题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成“a”，1翻译成“b”，·······，25翻译成“z”。一个数字可能有多个翻译。例如，12258有5种不同的翻译，分别是“bccfi”、"bwfi"、"bczi"、"mcfi"和"mzi"。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。思想：本题可以用自上而下（即从前往后递归的方式），将12258分为1, 2258...
2018-08-08 22:37:41
418
转载 面试题：C++有了malloc/free，为什么还需要new、delete？
1、面试宝典面试题（P81）：C++有了malloc/free，为什么还需要new、delete？malloc与free是C、C++语言的标准库函数，new/delete是C++的运算符。他们都用于申请动态内存和释放内存。对于非内部数据类型的对象而言，只用malloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/f...
2018-08-08 11:12:39
843
原创 剑指offer 不用加减乘除做加法
题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。输入：输入可能包含多个测试样例。对于每个测试案例，输入为两个整数m和n(1<=m,n<=1000000)。分析：（1）十进制加法分三步：(以5+17=22为例)1. 只做各位相加不进位，此时相加结果为12(个位数5和7相加不进位是2，十位数0和1相加结果是1)；2. 做...
2018-08-06 19:43:26
195
原创 剑指offer 求1+2+3+......+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。class Solution {private: int result=0;public: int Sum_Solution(int n) { if(n==0) return 0; ...
2018-08-06 16:21:23
149
转载 IO多路转接—select 、poll、epoll
多路（多个文件描述符）I/O(输入输出）转接（将多个文件描述符交给select监控）调用select函数，直到描述符表中有一个描述符准备好进入I/O时，该函数才返回，通过select的返回值告知进程哪些描述符已经准备好进入I/O。三种模型性能分析 select1.select能监听的文件描述符个数受限于FD_SETSIZE,一般为1024，单纯改变进程打开的文件描述符个数并不能改变...
2018-07-28 22:25:32
228
转载 Linux 线程同步的三种方法
线程的最大特点是资源的共享性，但资源共享中的同步问题是多线程编程的难点。linux下提供了多种方式来处理线程同步，最常用的是互斥锁、条件变量和信号量。一、互斥锁(mutex)通过锁机制实现线程间的同步。初始化锁。在Linux下，线程的互斥量数据类型是pthread_mutex_t。在使用前,要对它进行初始化。 静态分配：pthread_mutex_t mutex = PTHREAD_...
2018-07-27 17:29:35
93
转载 Posix 信号量与System v信号量的区别
在回答这个问题之前，首先要先了解什么是Posix，什么又是System V。简要的说，Posix是“可移植操作系统接口（Portable Operating System Interface ）的首字母简写，但它并不是一个单一的标准，而是一个电气与电子工程学会即IEEE开发的一系列标准，它还是由ISO（国际标准化组织）和IEC（国际电工委员会）采纳的国际标准。而System v是Unix操作系...
2018-07-27 16:31:01
698
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人