- 博客(127)
- 资源 (5)
- 收藏
- 关注
RSS订阅
原创 C++记录(二）
1.算术移位和逻辑移位。逻辑移位是只补0，算术移位是看符号，负数补1，正数补0（讨论的是右移的情况下）。负数一般不左移，无实际意义，如果遇到位运算的相关题目需要对int变量进行左移而且不知道正负，那么先强制类型准换为unsigned再进行移位操作。2.constexpr意义是字面值常量，即在编译期就可以将其计算出结果。constexpr修饰函数名是高速编译器放心大胆的将该函数计算出结果（要...
2019-11-04 20:18:45
177
原创 C++记录（一）
1extern 符表示该变量不是当前作用域定义的，用于声明。如extern i;表示i不是当前作用域里的，是其他某个include的cpp文件里的变量。2int *p=0;相当于初始化p为空指针。3指针是对象，引用不是对象。所以可以取指针的指针或者指针的引用，但不可以取引用的指针。指针一定要指向对象。4const int x=1;const int *p=&x; //p...
2019-09-28 01:04:06
325
原创 剑指offer 面试题52. 两个链表的第一个公共节点
这题之前leetcode做过，权当复习首先这题没说是否一定有公共节点，如果代码可能因为这一点造成死循环的，需要提前验证所给两个链表是否有公共节点。方法1：对于每一个list1的节点，遍历list2查找有无相同节点，O(N^2)方法2：用一个set存list2的节点，遍历list1找第一个匹配的，O(N)时间O(N)空间方法3：分别遍历两个链表计算各自长度L1，L2 长度长的链表先走(L1-...
2020-02-09 03:54:48
177
原创 剑指offer 面试题43. 1~n整数中1出现的次数
leetcode上也见过一样的题，当时不会做 看了一下解法是纯数学解法就没看，结果剑指offer上也出现了这道题，那还是认真看下吧对于数字abcde，如果第一位是1，比如12345，即计算f(12345)。那么首位为1对结果的增益一共是10000到12345一共2346个。另外首位为1的数字，后四位还可能有1出现，这部分即0001到2345（对应的数字就是10001到12345），也递归解决...
2020-02-08 17:13:57
441
原创 剑指offer 面试题40. 最小的k个数
O(N)划分法：要求前k小的数，只要执行快排划分，每次划分都会把数据分成大小两拨。直到某一次划分的中心点正好在k处，则左侧0~k-1的数字正好就是所求。class Solution {public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { int n=in...
2020-02-08 14:51:13
214
原创 快速排序的三种划分算法
#include<vector>#include<iostream>#include<time.h>using namespace std;int partition_1(vector<int> &nums,int le,int ri){ //来回填坑法 if(le>=ri){ return le;...
2020-02-08 02:51:23
630
原创 剑指offer 面试题38 字符串的排列
我惯用的dfs模板直接拿来套class Solution {public: vector<string> Permutation(string str) { if(str.empty()){return{};} int n=str.size(); vector<string> res; vector...
2020-02-07 22:49:30
117
原创 剑指offer 面试题36.二叉搜索树与双向链表
中序递归，一个pre节点记录前一个节点/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: TreeNod...
2020-02-07 15:36:11
116
原创 剑指offer 面试题35.复杂链表的复制
时间O(N)，空间O(N)/*struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { }};*/class Solutio...
2020-02-07 01:42:09
117
原创 剑指offer面试题30.包含min函数的栈
一开始写的垃圾代码，push和pop都是O(N)class Solution {public: vector<int> vec; int min_val=INT_MAX,min_cnt=0; void push(int value) { vec.push_back(value); if(min_cnt==0){ ...
2020-02-06 16:31:53
189
原创 C++析构、拷贝、赋值函数的一个知识点
看书看到这，感觉耳目一新，记录一波。众所周知，C++的类如果没有默认构造函数，会自动生成一个。同理，如果没有复制构造函数即A::A(const A&){}这个函数 ，则系统也会自动生成一个，但这个自动生成的复制构造函数不一定满足我们的要求。比如下面的例子：class A{ public: int* a; int b; A()=default; ...
2020-02-03 23:55:40
159
原创 394. 字符串解码
dfs：class Solution {public: string decodeString(string s) { int i=0; return dfs(s,i); } string dfs(string& s,int& i){//计算一对括号内的解码后字符串 string tmp=""; ...
2020-02-02 22:27:50
125
原创 leetcode78.子集➕90.子集2
78子集dfsdfs1:和全排列的区别就是对于当前考察的索引i，全排列如果不取i，之后还要取i，所以需要一个visited数组用来记录。对于子集问题如果不取i，之后也不必再取i。class Solution {public: vector<vector<int>> subsets(vector<int>& nums) { ...
2020-02-02 16:12:30
368
原创 leetcode5. 最长回文子串
Solution1 动态规划方法1：dp[i][j]表示i到j是否是回文class Solution {public: string longestPalindrome(string s) { int n=s.size(); int max_len=1,le=0,ri=0; if(n==0){return "";} ve...
2020-02-02 14:16:48
116
原创 Leetcode找三个数字的和满足xx条件的题目总结15➕16➕259
双指针最基础的题目是一个区间里找两个数字的和等于Target。首先将区间从小到大排序。接下来只要一个le指针，一个ri指针，分别从区间左右边界往中间推进即可。复杂度是排序的nlogn。下面几道题都是一个区间里找三个数字的和满足xx条件的。这个题目的做法就是先固定一个数字，然后在该数字的右侧区间内重新使用之前找两个数字的和的算法。 即i 从0到n-1，j 从i+1开始增加，k 从n-1开始减小直...
2020-01-31 01:43:38
308
原创 牛客腾讯2020校园招聘-后台&综合-第一次笔试
第一题Q:小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？输入描述:输入第一行包含一个字符串s，代表压缩后的字符串。S的长度<=100...
2020-01-28 22:47:25
2610
转载 C++四种初始化方式
1.默认初始化如果定义变量时没有指定初值，则变量被默认初始化，此时变量被赋予了“默认值”。int i;A a;2.直接初始化如果不使用等号，则执行的是直接初始化。int a(0);string str1(“hello”);string str2(10, ‘c’);//这种情况拷贝初始化不能完成A a(pa);3.拷贝初始化如果使用一个等号初始化一个变量，实际上执行的是拷贝初始...
2020-01-27 01:27:03
4153
原创 STL关联容器总结
有序的都不带unordered，即如下：set multiset map multimap其中带multi的表示关键字可以重复无序的带unordered，如下：unordered_mapunordered_setunordered_multimapunordered_multisetmap系有KEY和VALUE,set系只有KEY没有VALUE4个有序容器的KEY必须重载<...
2020-01-26 10:55:39
209
原创 C++泛型算法总结
1accumulate(b,e,T) 累和（基础和为T）注意T的类型必须和序列中元素类型相同，如double序列后面的T就必须是0.0，如果是0就会把序列中的数当成int进行求和2count(b,e,T) 计数，查找[b,e)中T出现的次数3equal(b1,e1,b2) 确定是否相同，[b1,e1)为序列1，b2为序列2开头默认b2序列长度比b1到e1要长4fill(b,e,...
2020-01-20 23:00:21
153
原创 STL顺序容器用法自我总结
顺序容器类型：vector、deque、list、forward_list、string、array。queue（单向队列）底层也是用deque（双端队列）实现的a.swap(b);swap(a,b);可以交换两个容器的数据结构初始化：声明时定义.assign(n,t)，以n个t初始化.assign(b,e)，用迭代器b到e初始化.assign(il)，用il表示的数据初始化添...
2020-01-19 15:45:32
187
原创 定义两个一样的字符串，为什么地址不一样的解释
如图，直接取二者的地址是不一样的。但实际上二者应该是共用常量数据区内的一片地址。但&s1、&s2取的是两个字符串对象的地址，对象的地址是在栈区的，所以肯定不一样。只是实际上整个程序内存中应该只有一个"hello"，这是我的理解，有问题的话麻烦评论指出我的错误，谢谢。...
2019-12-29 20:23:19
1033
原创 Leetocde的两道丑数题目：264. 丑数 II➕313. 超级丑数
Q：A：用变量记录已经✖2、✖3、✖5的元素下标i2、i3、i5。表示截止到i2的元素都已经乘过2（结果添加到序列尾部的意思），i3、i5同理。这样每次可以循环可以O(1)时间找到下一个最小的丑数，时间O(N)，空间O(N)。class Solution {public: int nthUglyNumber(int n) { if(n<=0){ ...
2019-12-19 12:43:59
159
原创 395. 至少有K个重复字符的最长子串
Q:A:分治，对于字符串s的任何一个字符，如果它的频数（在s中出现的次数）小于k，则它一定不会出现在最后的结果里，也就是从它的位置一劈两半，考察左右。对于当前字符串s，我们先建立字典统计其中每种字符出现的次数，对于某字符，假设为x，x在当前字符串中出现的次数小于为kk，kk<k。则所有的字符x可将当前字符串s切片为kk+1个子串，递归对这kk+1个子串进行考察即可。class Sol...
2019-12-15 21:51:23
147
原创 378. 有序矩阵中第K小的元素
//O(NK)class Solution {public: int kthSmallest(vector<vector<int>>& matrix, int k) { int m=matrix.size(); int cnt=0; vector<int> indexes(m,0); int...
2019-12-12 15:40:09
119
原创 指针常量与字符串常量的冲突
看程序员面试笔记看到一段代码，记录一下：int main(){ char* const str="apple"; *str="orange"; cout<<str<<endl; getchar();}这段代码有两个问题：1.str是char类型，要给str赋值要写str=“orange”;2.如果只把str前的号去掉，程序还是不对的。str是常量指针，开...
2019-12-10 20:26:43
188
原创 链表中环的入口节点题目的双指针解法证明
头节点Head，快指针fast，慢指针slow。初始快慢指针都等于Head，slow一次走一格，fast一次走两格。另外我们现在要达成共识，first_meet节点一定在环内部，即相遇的地方一定是在环里面的某处。能理解再往下看。快慢指针第一次相遇时，假设都等于first_meet，即二者在first_meet节点相遇。那么二者第一次相遇一定是因为快指针把慢指针套圈了，即fast比slow多走...
2019-12-07 21:55:44
176
原创 295. 数据流的中位数
Q:A:用两个堆（一大顶堆、一小顶堆模拟中位数），没见过类似的题目记录一下。class MedianFinder {public: priority_queue<int,vector<int>,less<int>> heap1; //大顶堆 priority_queue<int,vector<int>,great...
2019-12-07 00:35:00
119
原创 399. 除法求值
Q:没思路，看别人思路做的，记录一下。把问题转化为图的遍历。DFS：class Solution {public: set<string> points; //点集 map<pair<string,string>,double> edges; //边集 vector<double> res; ...
2019-12-01 20:41:36
176
原创 394. 字符串解码
Q:递归：class Solution {public: string decodeString(string s) { if (s.empty()){ return ""; } string res="",str; int i=0,siz=s.size(); int repea...
2019-11-28 18:09:07
135
原创 621. 任务调度器
Q:class Solution {public: int leastInterval(vector<char>& tasks, int n) { map<char,int>dc; for(char c:tasks){ dc[c]+=1; } vector<i...
2019-11-28 15:35:24
127
原创 剑指Offer：面试题20：表示数值的字符串
记录一下书上的写法。很整洁，每个函数的功能都显而易见。自己开始写的一堆if else语句像是一坨屎。另外注释的地方短路效应也要注意一下。总之这题还挺考察代码素质的（我这种就不存在什么素质。。乱糟糟一团）#include<iostream>using namespace std;bool is_unsignedint(char** str);bool is_int(char** ...
2019-11-26 23:15:16
125
原创 416. 分割等和子集
Q:A:1.DP主要题目中说了不超过100个数字，数字都不超过200。所以可能的和不会超过20000，这个量级对计算机来说不算大，所以考虑用DP考察每个可能的和是否存在。class Solution {public: bool canPartition(vector<int>& nums) { if(nums.empty()){ ...
2019-11-24 21:00:07
131
原创 C++实现索引堆及完整测试代码
首先贴一篇我看的博客，写的很清楚。作者：Emma_U一些解释索引堆首先是堆，但比堆肯定是更有用。用处：1.加速。 索引堆存储的是索引，并不直接存储值。在堆上浮下沉的元素交换的时候，交换索引可比交换值来的快。虽然我代码只实现了int类型的索引堆，但比方说string类型的索引堆，交换两个string，显然没有交换两个int型的索引快。2.方便改动原数组 比如现在有一个vector，然后我们...
2019-11-15 16:07:18
227
原创 面试题17.打印从1到最大的n位数
void print_n_number(int n){ if(n<=0){ cout<<"fuckyou"; return; } string s="1"; while(s.size()<=n){ while(s.back()<='9'){ cout<<s<<endl; s.back()+=1; } in...
2019-11-14 01:11:08
112
原创 leetcode全部滑动窗口题目总结C++写法(完结)
3. 无重复字符的最长子串A：要找最长的无重复子串，所以用一个map保存出现过的字符，并且维持一个窗口，用le和ri指针标识。ri为当前要遍历的字符，如果ri字符在map中出现过，那么将le字符从map移除，le++。如果ri字符没出现过，那ri++，并更新最大无重复子串长度。全程利用map保持无重复的要求，每次循环要么le++，要么ri++。最差情况是n个一样的字符，那么ri++，le++，...
2019-11-13 22:23:45
629
原创 560. 和为K的子数组
Q:A:1.暴力找所有可能的子数组，n^2个子数组，最长长度n，则n ^3。2.n^2解法从1~n-1各起点开始，一直找到结尾，n^2class Solution {public: int subarraySum(vector<int>& nums, int k) { int res=0; for(int i=0;i<...
2019-11-12 14:05:22
150
原创 536. 从字符串生成二叉树
Q:A:1.递归，左右边界做函数参数，太弟弟略过。2.迭代，鼓捣了半天题目给的字符串只看数字顺序的话是前序。那么想一下我们写非递归前序遍历时候，对于一个节点cur，如果不是空直接输出它的值，然后放到栈顶，再令cur=cur的左孩子进行循环。如果cur为空，那么令cur=栈顶的右孩子并pop栈顶并继续。对于给定前序字符串，假如前三个数字是a、b、c，首先应该新建一个值为a的节点A（毕竟我...
2019-11-11 20:05:02
752
原创 501. 二叉搜索树中的众数
Q:A:首先这题可以遍历一遍二叉树，用一个map来存每个数字出现的次数之后取最大的就行，但这样没有利用到二叉搜索树的条件。所以我们利用二叉搜索树中序遍历升序（此题中为非降序）的性质，保存中序前缀节点，若当前节点与前缀节点值相同，计数+1，若不同则重新从0开始计数。因为是非降序，所以一旦遍历到了一个更大的数字，之后的数字都只会相同或更大。额外维持一个全局变量maxsize记录目前为止的出现最多...
2019-11-10 14:47:27
127
原创 297. 二叉树的序列化与反序列化+449. 序列化和反序列化二叉搜索树
297. 二叉树的序列化与反序列化Q:A：没啥说的，层次遍历，空节点存个特殊符号标记一下就好，重建树也是按层次BFS重建树。class Codec {public: // Encodes a tree to a single string. string serialize(TreeNode* root) { string res("");...
2019-11-09 20:17:49
302
C++实现图书管理系统（无GUI，利用控制台交互）.zip
2019-12-27
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人