- 博客(67)
- 收藏
- 关注
RSS订阅原创 C++面试宝典：类的大小（sizeof）
类的大小空类的大小 sizeof = 1因为实例化就是为内存中开辟一个独一无二的地址，至少是一个字节，所以一个字节大小其实就是占位置的一个字节。class node {};int main() { node *tmp = new node(); cout<<sizeof(tmp)<<endl; // output = 4，指针的大小是4 cout<<sizeof(*tmp)<<endl; // output = 1，
2020-05-28 01:00:34
223
原创 腾讯精选练习：231. 2的幂（位运算，lowbit）
231. 2的幂给定一个整数，编写一个函数来判断它是否是 2 的幂次方。示例 1:输入: 1输出: true解释: 20 = 1示例 2:输入: 16输出: true解释: 24 = 16分析1如果是2的幂，那么取以2为底的log会得到一个整数精度要自己设定。class Solution {public: bool isPowerOfTwo(int n) { if(n<=0) return false; double lg = log
2020-05-24 21:41:27
206
原创 腾讯精选练习：142. 环形链表 II（数论同余，逻辑）
142. 环形链表 II给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。示例 1：输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。示例 2：输入：head = [1,2]
2020-05-24 12:40:12
163
原创 腾讯精选练习：16. 最接近的三数之和
16. 最接近的三数之和给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).分析这类题目一般都排个序，先固定一个数，然后用双指针去找另外数字。注意就是要遍历所有的数，作为被固定的那个数，这样才能枚举所有的
2020-05-23 21:57:09
149
原创 腾讯精选练习：89. 格雷编码（找规律做位运算）
89. 格雷编码格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以 0 开头。示例 1:输入: 2输出: [0,1,3,2]解释：00 - 001 - 111 - 310 - 2对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1示例 2:
2020-05-23 21:51:31
195
原创 腾讯面试精选：122. 买卖股票的最佳时机 II（贪心，逻辑题）
122. 买卖股票的最佳时机 II给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候
2020-05-23 17:34:42
379
原创 腾讯精选练习：求数列的所有的子集（dfs，位运算 ）
78. 子集给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]解法1用dfs去实现一种暴力求解。我们可以从左到右遍历数组nums，对于每一个数，我们只需要考虑将它加入已有的集合中，构成一个新的集合，还是让它单独作为一个集合。所以我们得出以下操作：遍历答案集合里面所有的子集，然后把
2020-05-23 17:03:11
379
转载 C++面试宝典：线程同步的方式（临界区critical section，互斥量mutex&lock）
线程同步临界区临界区（Critical Section）是一段独占对某些共享资源访问的代码，在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。临界区在使用时以CRITICAL_SECTION结构对象保护共享资源，并分别用EnterCriticalSection（）和LeaveCriticalSecti
2020-05-21 13:59:07
481
转载 C++面试宝典：线程通信（C++的promise和future）
线程通信：C++的promise和future通过使用 std::promise 和 std::future，就有了task的全部控制权。std::promise允许设置一个值，一个消息，或者一个异常。该结果可以延迟由promise提供。std::future可以从promise获取值，请求性获取，值可用的话就可获取到了。等待promise的消息通知。等待可以使用一个相对持续时间或绝对时间点来完成=>替代了条件变量。创建一个共享future (std::shared_future).
2020-05-21 13:01:30
497
转载 C++面试宝典：内核态和用户态
操作系统为什么要分用户态和内核态在CPU的所有指令中，有一些指令是非常危险的，如果错用，将导致整个系统崩溃。比如：清内存、设置时钟等。如果所有的程序都能使用这些指令，那么你的系统一天死机n回就不足为奇了。所以，CPU将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统及其相关模块使用，普通的应用程序只能使用那些不会造成灾难的指令。Intel的CPU将特权级别分为4个级别：RING0,RING1,RING2,RING3。linux的内核是一个有机的整体。每一个用户进程运行时都好像有一份内核的
2020-05-19 20:51:16
614
原创 腾讯精选练习：LRU缓存机制（unordered_map+hash）
LRU缓存机制运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶:你是否可以
2020-05-18 15:34:21
125
转载 乐观锁与悲观锁
悲观锁总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁。共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现。乐观锁总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判
2020-05-15 15:35:10
105
原创 剑指offer：面试题60. n个骰子的点数（概率DP）
面试题60. n个骰子的点数把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例 1:输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例 2:输入: 2输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.138
2020-05-11 18:06:12
208
原创 剑指offer：面试题59 - II. 队列的最大值（单调队列）
面试题59 - II. 队列的最大值请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1示例 1：输入:[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”][[],[1],[2],[],[],[]]输出:[null,n
2020-05-11 15:58:43
140
原创 剑指offer：面试题57 - II. 和为s的连续正数序列（前缀和+二分）
面试题57 - II. 和为s的连续正数序列输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。示例 1：输入：target = 9输出：[[2,3,4],[4,5]]解法一：前缀和+二分首先求前缀和，枚举每一个前缀和sum[i]，在0~i 之间二分另外一个前缀和sum[mid]，使得sum[i] - sum[mid] == target。class Solution {public:
2020-05-11 14:25:12
146
原创 剑指offer：面试题56 - II. 数组中数字出现的次数 II（异或+取模求出现一次的数）
面试题56 - II. 数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。示例 1：输入：nums = [3,4,3,3]输出：4分析遍历每一个数的每个二进制位，统计所有数字第 i 位出现 1 的个数，如果该二进制位上 1 的个数不能被 3 整除，那么只出现一次的那个数字在这个二进制位上为1。class Solution {public: int cnt[32]; int singleNumber(
2020-05-11 12:58:12
152
原创 剑指offer：面试题56 - I. 数组中数字出现的次数（分组异或）
面试题56 - I. 数组中数字出现的次数一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。示例 1：输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]分析如果我们可以把所有数字分成两组，使得：两个只出现一次的数字在不同的组中；相同的数字会被分到相同的组中。那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。那么如何实现这样的分组呢？记这两
2020-05-11 12:37:37
170
原创 剑指offer：面试题66. 构建乘积数组
面试题66. 构建乘积数组给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24]提示：所有元素乘积之和不会溢出 32 位整数a.length <= 100000看题目给的B[i]计算方法，B[i]是A数组里除了A[i]以外所有元素的乘积。**除了A[i]**这个关键词很
2020-05-11 11:25:24
176
原创 剑指offer：面试题65. 不用加减乘除做加法（位运算）
面试题65. 不用加减乘除做加法写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。示例:输入: a = 1, b = 1输出: 2提示：a, b 均可能是负数或 0结果不会溢出 32 位整数分两部分来求：1、没有进位的加法a ^ b二者异或仅仅是考虑了该位相加，不能处理进位2、求加法的进位((unsigned int)(a & b) << 1);二者相与的结果为1，说明该位会向前进位，左移 1 即可求得进位的
2020-05-11 10:35:48
148
原创 剑指offer：面试题53 - II. 0～n-1中缺失的数字（查找左边界）
面试题53 - II. 0～n-1中缺失的数字一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例 1:输入: [0,1,3]输出: 2示例 2:（这个样例很特别）输入: [0,1,2]输出: 3class Solution {public: int missingNumber(vector<int>& nums) { if(!n
2020-05-10 21:54:21
83
原创 剑指offer：面试题53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: 0限制：0 <= 数组长度 <= 50000排序里面查找数字，首先就想到是二分，查出现次数，显然是找左边界和右边界，模板题。class Solution {public: int search(vector<int>& nums
2020-05-10 21:14:56
173
原创 剑指offer：面试题52. 两个链表的第一个公共节点
面试题52. 两个链表的第一个公共节点输入两个链表，找出它们的第一个公共节点。我的做法是先分别算出两个链表的长度，记长度的差值是dis，然后让长的链表先走dis步，然后再两个一起走。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */cl
2020-05-10 20:37:20
116
原创 剑指offer：面试题46 把数字翻译成字符串
面试题46 把数字翻译成字符串给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。示例 1:输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”提示：0≤num<2310 \leq num < 2^{31}0≤nu
2020-05-10 02:35:18
393
原创 剑指offer：面试题45 把数组排成最小的数
面试题45 把数组排成最小的数输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2]输出: “102”示例 2:输入: [3,30,34,5,9]输出: “3033459”排个序就可以了。class Solution {public: static int cmp(int a, int b){ string sab = to_string(a) + to_string(b); st
2020-05-09 23:55:06
176
原创 剑指offer：面试题44 数字序列中某一位的数字
面试题44 数字序列中某一位的数字数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。示例 1：输入：n = 3输出：3示例 2：输入：n = 11输出：0限制：0 <= n < 2^31分析这道题下标从0开始，第一个0是占下标0用的，不必考虑。主要是考虑了一位数（1-9）占了9位，两位数（10-99）占了180位，以此类推
2020-05-09 22:52:16
107
原创 剑指offer：面试题47 礼物的最大价值（一维DP）
面试题47 礼物的最大价值在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？class Solution {public: int dp[205]; int maxValue(vector<vector<int>>& grid) { int m =
2020-05-09 17:15:57
94
原创 剑指offer：面试题43 1～n整数中1出现的次数（数位DP）
面试题43. 1～n整数中1出现的次数这道题我很喜欢，有用的知识增加了。首先明确这道题可以用数位DP来做：先上一个数位DP模板：#include <bits/stdc++.h>using namespace std;//问：在区间[a,b]中不含49的数字有多少个int a, b, shu[20], dp[20][2]; //shu数组存储各位上的数 dp[i][1] 表示第i+1位为4，剩余数字长度为i的数字的个数//dp[i][0] 意思第i+1
2020-05-09 17:13:54
219
原创 剑指offer：面试题48 最长不含重复字符的子字符串
面试题48 最长不含重复字符的子字符串请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。显然是滑动窗口class Solution {public: int vis[300]; int lengthOfLongestSubstring(string s) { int cnt = 0; int max = 0; int startPos = 0; for(int i=0; i<300; i
2020-05-08 23:05:47
131
原创 剑指offer：面试题40 最小的k个数
面试题40 最小的k个数输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。示例 1：输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1]示例 2：输入：arr = [0,1,2,1], k = 1输出：[0]分析这是一道非常经典的题目，有三种做法：1、直接sort排序取前K大2、堆排序3、快排思想第一种解法太无聊不说了2、堆排序堆就是根节点大于孩子结点，兄弟结点不区
2020-05-08 21:01:09
84
原创 剑指offer：面试题36 二叉搜索树与双向链表
二叉搜索树与双向链表输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。leetcode真的狗，一份好好的代码交了十几次过不了，去牛客网一次就过了，呸呸呸。#include<bits/stdc++.h>using namespace std;// Definition for a TreeNode.class...
2020-05-08 15:37:34
188
原创 C++面试宝典：大端小端以及判定方法
一、概念1、大端模式2、小端模式二、怎么判断是大端还是小端int main(){ union{ short i; char a[2]; } u; u.a[0] = 0x11; u.a[1] = 0x22; printf ("0x%x\n", u.i); // 0x2211 为小端 0x1122 为大端}...
2020-05-06 17:35:19
287
原创 C++面试宝典：static和虚函数表
一、类里面的 static 内存分布static修饰的是1、全局变量 2、局部变量 3、类里面的数据成员 4、类里面的成员函数对于类里面的成员变量来说，对于所有的类来说都是可以被使用的，在类对象实例化之前就已经存在，存在全局数据区。对于类里面的成员函数来说，静态成员函数不和任何的对象相关联，在text段（代码段）分配内存。二、类里面的 virtual 内存分布对于virtual来说，虚...
2020-05-06 15:59:53
247
原创 阿里巴巴面试 2020.5.5
面试前准备面试官在面试之前给我发了两本书，分别叫做《代码整洁之道》和《敏捷软件开发》，然后出了一道编程题，编程题如下：编程题目：出租车起步价14元，含3公里起步价之后，每公里2.5元晚上11点之后（含），次日6点前（不含）起步价18元，含3公里。计价以上车时间为准，不考虑乘坐期间从白天到晚上的情况。晚上起步价之后，每公里3元。10公里之后，白天每公里3.5元，晚上每公里4.7元。外...
2020-05-05 15:38:00
347
1
原创 阿里巴巴面试准备 学习《代码整洁之道》
第2章 有意义的命名重载构造器的时，使用描述参数的静态方法名。例如：Complex fulcrumPoint = Complex.FromRealNumber(23.0);通常好于Complex fulcrumPoint = new Complex(23.0)第3章 函数3.1 短小函数越短越好，最好不要超过20行3.2 只做一件事要判断函数是不是只做了一件事，就是看是否能再...
2020-05-05 09:21:26
180
原创 C++面试宝典：http1.0和2.0的区别
一、HTTP1.0 HTTP 1.1主要区别1.1 长连接HTTP 1.0需要使用keep-alive参数来告知服务器端要建立一个长连接，而HTTP1.1默认支持长连接。HTTP是基于TCP/IP协议的，创建一个TCP连接是需要经过三次握手的,有一定的开销，如果每次通讯都要重新建立连接的话，对性能有影响。因此最好能维持一个长连接，可以用个长连接来发多个请求。1.2 节约带宽HTTP 1....
2020-05-02 15:58:24
442
原创 C++面试宝典：http中cookie的作用（http是无状态协议）
cookie是什么Cookie总是保存在客户端中，也就是服务器暂存电脑里的一个文件（.txt），让服务器用来辨认你的计算机。当你在浏览器网站的时候，Cookie会帮你在网站上所打的文字或是一些选择都记录下来。当下次你再访问同一个网站，Web服务器会先看看有没有之前在该网站保存的Cookie资料，有的话，就会依据Cookie里的内容来判断使用者，送出特定的网页内容给你。cookie的作用：c...
2020-05-02 14:40:46
547
原创 C++面试宝典：HTTP概述
1、http协议的定义http(Hypertext transfer protocol)超文本传输协议，通过浏览器和服务器进行数据交互，进行超文本（文本、图片、视频等）传输的规定。也就是说，http协议规定了超文本传输所要遵守的规则。2、http的报文头部有什么内容当你在浏览器地址栏里键入一个url，你的浏览器将会类似如下的http请求：GET /tutorials/other/top-...
2020-05-02 13:50:02
370
原创 C++面试宝典：TCP可靠性的保证机制总结
TCP保证可靠性主要依靠下面7种机制：1、序列号、确认应答、超时重传TCP将每个字节的数据都进行了编号，这就是序列号。数据到达接收方，接收方需要发出一个确认应答（ACK），表示已经收到该数据段，并且确认序号（ack number）会说明了它下一次需要接收的数据序列号。如果发送发迟迟未收到确认应答，那么可能是发送的数据丢失，也可能是确认应答丢失，这时发送方在等待一定时间后会进行重传。这个时间一...
2020-05-02 12:40:29
360
转载 C++面试宝典：map与unordered_map的区别
map和unordered_map的差别需要引入的头文件不同map: #include < map >unordered_map: #include < unordered_map >内部实现机理不同map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑...
2020-05-02 11:31:23
383
原创 C++面试宝典：进程间通讯方式概述
1、管道我们来看一条 Linux 的语句netstat -tulnp | grep 8080学过 Linux 命名的估计都懂这条语句的含义，其中”|“是管道的意思，它的作用就是把前一条命令的输出作为后一条命令的输入。在这里就是把 netstat -tulnp 的输出结果作为 grep 8080 这条命令的输入。如果两个进程要进行通信的话，就可以用这种管道来进行通信了，并且我们可以知道这条竖线...
2020-05-02 11:31:11
513
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人