- 博客(177)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 C++动态规划之最长公共子序列与最长公共子串
子序列： 从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列子串： 将一个序列从最前或最后或同时删掉零个或几个字符构成的新系列故子串必是连续的，子序列不一定连续最长公共子序列Leetcode1143. 最长公共子序列使用动态规划，最主要的就是求出其状态转移方程：若：input1 = [“a”, “c”, “b”, “a”, “d”],input2 = [“a”, “b”, “c”, “a”, “d”, “f”]初始条件： 首先设置我们的第一个子序列为空字
2020-09-15 09:49:31
691
原创 C++之快速排序的递归与非递归调用
912. 排序数组给你一个整数数组 nums，请你将该数组升序排列。示例 1：输入：nums = [5,2,3,1]输出：[1,2,3,5]示例 2：输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]递归方法相信递归方法大家闭着眼也能写出来，毕竟这是各大互联网公司面试必手撕的代码#include<iostream>#include<map>#include<string>#include<vector>
2020-09-14 21:57:54
377
原创 C++之链表的三种排序-归并/插入/快速
148. 排序链表在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1:输入: 4->2->1->3输出: 1->2->3->4归并排序之前我们写过一个归并排序：LeetCode之链表排序-归并排序采用分治的思想，先写出两个链表的合并，再进行分。。/** * Definition for singly-linked list. * struct ListNode { * int val; * Lis
2020-09-14 14:55:08
2699
原创 C++之二叉树的非递归遍历-栈迭代
144. 二叉树的前序遍历/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int>
2020-09-14 10:00:21
195
原创 C++之删除链表的重复元素
面试题 02.01. 移除重复节点编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。示例1:输入：[1, 2, 3, 3, 2, 1]输出：[1, 2, 3]示例2:输入：[1, 1, 1, 1, 2]输出：[1, 2]因为会保留一个重复结点，所以在遍历链表的时候，我们就要判断这个节点是不是一个重复结点，这个时候set和unorder_set就比较合适了。/** * Definition for singly-linked list. * struct ListNode
2020-09-10 15:28:58
3156
原创 C++输入不定数量整数，以’#‘结束
9月5号，好未来公司笔试，快速排序的非递归实现，然而居然栽在了输入数据上，尝试了将近一个小时还是失败，在此记录一下：#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;int main(){ int a; vector<int> v; while (cin >> a) { v
2020-09-06 16:18:11
1139
2
原创 最大公约数与最小公倍数
#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;int comdiv(int a, int b){ int r; while (r = a % b) { a = b; b = r; } return b;}int main(){ int N,M; cin >> N &
2020-09-06 16:13:05
121
原创 Linux下的fork()与vfork()函数
一、fork()函数fork函数是在<unistd.h>头文件中被定义，是系统的一个服务，fork函数是在当前进程中创建一个新的进程，这个新的进程叫做子进程(child process)。当前进程称作父进程(parent process)。系统负责创建父进程的副本，包括代码段，数据段，堆和栈的复制。fork函数是“调用一次，返回两次”。1、在父进程中返回生成子进程的ID，（因为父进程拥有不只一个的子进程）2、在子进程中返回一个整数0（因为子进程只有一个父进程，可以通过调用函数getppi
2020-08-19 09:50:44
155
原创 C/C++之代替字符串子串
跟谁学公司二面时，直接上来就出了一道题，就是代替用一个字符串代替一个字符串中的某个子串（存在多个），而且只能用到strlen()、strcpy()、strcmp()函数。当时是蒙圈的，写了半个小时也没写出来。。下面记录一下吧：#include<stdlib.h>#include<iostream>#include<algorithm>int checkStr(char *s1, char *s2) //匹配字符串相不相等 { for (int i = 0;
2020-08-17 22:13:27
744
原创 LeetCode之递归与非递归求二叉树最大最小深度
104. 二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。利用递归我们很容易就可以写出来：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),
2020-08-17 16:35:31
280
原创 LeetCode之链表排序-归并排序
剑指 Offer 25. 合并两个排序的链表输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。输入：1->2->4, 1->3->4输出：1->1->2->3->4->4常规做法是逐个比较即可，引入头结点/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; *
2020-08-17 09:48:34
360
原创 LeetCode之被围困的区域
Leetcode中存在被围困区域，或者相连区域的一类题。今天就总结一下，一种方法解决该问题。这种方法就是使用递归实现。733. 图像渲染有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他
2020-08-16 15:05:15
149
原创 C++之每日知识树-09-从static到extern “C“再到C无法重载原因
之前我们写过C++之每日知识树-08-从static到单例模式再到多线程安全今天我们再写一个由static引出的一个面试点。关于static关键字的五处用处的内存位置、作用域、初始化等，大家可以看上一篇文章，今天就从作用域展开。大家都知道static声明定义的函数或者变量的作用域就是在本文件中，普通全局变量是在整个工程文件中都可以使用，然而由C语言演化而来的C++语言可以使用另外一个C文件吗？？这就是需要用到extern关键字！一、extern “C"extern可以置于变量或者函数前，以标示变量
2020-08-10 11:41:28
206
原创 Leetcode之买卖股票的最佳时机
Leetcode关于股票交易的有7道题，但是在面试过程中基本就会问到四种，另外三种过于复杂没在这里先不列举，等以后慢慢研究。121. 买卖股票的最佳时机给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润
2020-08-07 20:36:02
216
原创 C++之每日知识树-08-从static到单例模式再到多线程安全
一、static关键字在c++中，static关键字主要有五个用处：名称内存中位置作用域初始化全局静态变量静态存储区本文件自动默认初始化为0局部静态变量静态存储区局部作用域（不销毁）第一次静态函数本文文件类的静态成员所有对象共享类的静态函数所有对象共享注意：所谓的编译期间分配静态空间是指静态分配空间（相对于用new动态申请空间），如全局变量或静态变量（包括一些复杂类型的常量），它们所需要的空间大小可以 明确计算出来，并
2020-08-07 15:59:49
672
原创 Leetcode之打家劫舍
Leetcode中打家劫舍总共三道题，包含了动态规划和树的递归问题，十分典型，所以在这里记录一下。198. 打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3
2020-08-06 16:28:11
179
原创 C++之每日知识树-07-数组名
先说一下结论：1、数组名内涵在于其指代实体是一种数据结构–数组2、数组名其可以隐式转换为指向数组实体的指针，而且是一个指针变量3、指向数组的指针则是一种变量类型，意味着数组的存放首地址4、数据名作为函数形参时，其全面沦落为一个普通指针，失去其常量性解释如下：1、数组名内涵在于其指代实体是一种数据结构–数组int intArray[10];cout << sizeof(intArray) ;此时输出为40（整型数组占据的内存空间大小）。在此注意：许多程序员以为sizeo
2020-08-03 10:19:25
265
原创 C++之每日知识树-07-STL容器和适配器底层实现
what：STL有哪些容器？哪些适配器？容器：分为顺序容器：vector、list、deque关联式容器：map、set、multimap、multiset、hash_map、hash_set、hash_multimap、hash_multiset适配器：容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。即容器适配器是对容器的一
2020-07-25 20:42:41
189
原创 C++之每日知识树-06-TCP如何保证可靠传输
what：什么是TCP的可靠传输？作为一个面向连接的传输层协议，TCP的目标是为用户提供可靠的端到端连接，保证信息有序无误的传输。它除了提供基本的数据传输功能外，还为保证可靠性采用了数据编号、校验和计算、数据确认等一系列措施。它对传送的每个数据字节都进行编号，接收方在接收到数据后检查校验和并请求接收方回传确认信息（ACK）。发送方如果在规定的时间内没有收到数据确认，就重传该数据。why：为什么会出现不可靠的现象？（1）保护消息边界，就是指传输协议把数据当作一条独立的消息在网上传输，接收端只能接收独立
2020-07-25 11:21:04
213
原创 C++迭代器失效的情况与解决方法
在STL中，迭代器失效可发生在三种情况下：一、数组型数据结构（vector、deque）对于序列式容器(如vector,deque)，序列式容器就是数组式容器，删除当前的iterator或者插入某个iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存，删除或插入一个元素导致后面所有的元素会向前或向后移动一个位置。所以不能使用erase(iter++)的方式，还好erase，insert方法可以返回下一个有效的iterator。解决方法：（1）通
2020-07-24 20:27:24
3703
原创 大数据求交集和并集处理
结合网上面试的实例，下面分三种情况考虑：参考BitMap 详解、算法系列-大数据面试题-两个大文件中找出共同记录**情况一、**有40亿个无序int类型的整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，你会怎么做？解法一、最常规直观的解法，就是使用一个HashSet，将所有数都add进去，然后对要判断的数，执行一下contains函数判断下就ok了。但是这个HashSet会占用多少内存呢？40亿*4Byte=40亿*4/1024/1024/1024G=14.9G空间这需要一个很
2020-07-24 10:46:35
4074
1
原创 c++之批量修改txt文件中的每一行内容
再将cvc-09和cvc-14红外行人检测数据集用于YOLO网络的训练时，由于图像标注的txt文件格式不同，所以需要我们转化。cvc标注文件格式为：cvc标注文件前五个数字分别表示中心坐标和长宽，即在图片中的真是像素值。yolo网络训练所需要的PASCAL VOC标注文件格式为：PASCAL VOC标注文件中包含（class，x, y, w,h），分别表示类别，中心坐标和长宽（都是相对于图片像素大小）代码如下：#include <iostream>#include <fs
2020-07-20 22:27:36
1869
原创 C++实现 LRU (最近最少使用) 缓存机制
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。为了可以在 O(1) 时间复杂度内完成get()和put()两种操作,我们使用两个STL容器：unordered_map<int,list<pair<int,int>>::iterator> m;无序map，存储已经存在的键值对，保证查找时间复杂度为O(1)，注意第二个元素保存的是list的迭代器list<pair<int,i
2020-07-14 11:38:39
455
原创 C++最简单的内存池实现
what：什么是内存池？百度百科：内存池(Memory Pool)是一种内存分配方式，又被称为固定大小区块规划（fixed-size-blocks allocation）。内存池则是在真正使用内存之前，先在堆区申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。这样做的一个显著优点是，使得内存分配效率得到提升。传统默认内存分配方式–new/delete 和 molloc/free分配过程？系统在接收到分配一定大小
2020-07-14 09:22:46
1666
原创 线程池（C++11）
what：什么是线程池？维基百科解释：线程池（英语：thread pool）：一种线程使用模式。线程过多会带来调度开销，进而影响缓存局部性和整体性能。而线程池维护着多个线程，等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代价。线程池不仅能够保证内核的充分利用，还能防止过分调度。可用线程数量应该取决于可用的并发处理器、处理器内核、内存、网络sockets等的数量。例如，线程数一般取cpu数量+2比较合适，线程数过多会导致额外的线程切换开销。why：为什么使用线程池
2020-07-13 20:36:39
128
原创 C++之基类调用自己的虚函数
每个类中存在虚函数时，当构造一个对象时，系统会为对象分配相应的内存空间。但是虚函数表存放在程序的只读数据段中，在实例化对象时，编译器会自动在对象里安插一个指针vPtr指向虚函数表VTable；下面看一个小例子：#include<iostream>using namespace std;class A {public: void f1() { cout << "f1" << endl; } virtual void f2() { cout <
2020-07-13 10:01:49
2154
原创 C++之每日知识树-05-进程/线程的同步/通信
依旧以铁三角来进行思维的小扩散（what、why、how）。what：什么是同步/通信？首先，同步是一种通信。进程/线程的同步/通信：在并发过程中，进程之间需要相互等待和互通消息，这就是进程/线程的同步/通信。why：为何要进行同步/通信？先说一下进程：进程在整个生命周期中经历了创建-就绪-运行-阻塞-结束的过程，在并发环境下，不同的进程相互独立，要想实现并发，CPU必须很好的协调和调度不同的进程。在并发过程中，进程之间的关系为：1、竞争关系，通过互斥来协调。资源竞争容易出现两个问题：死锁问
2020-07-13 09:24:40
145
原创 C++之二叉树的左右视图
发现这个问题在面试者出现的频率非常高，，刚刚写了一下，发现直接就写了出来，而且左右视图代码差别只是一个数字，感觉很有意思。Leetcode199. 二叉树的右视图给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
2020-07-09 09:28:17
568
原创 C++之回溯算法解决二叉树的路径问题
之前我们写过C++之回溯算法解决子集、全排列和组合问题，二叉树的路径问题，其实也是属于排列组合问题，今天就以Leetcode上的真题来使用回溯算法解决二叉树的路径问题：Leetcode112. 路径总和给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *lef
2020-07-07 17:09:23
398
原创 C++之每日知识树-04-STL六大组件
先贴一下图，一个博主总结的非常全面，以前存的，忘记是哪位博主了！what：1、容器（序列式容器、关联时容器）2、迭代器（输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器）3、算法（质变算法【插入、删除、拷贝、替代】、非质变算法【遍历】）各种常用的算法，如sort，search，copy，erase，max，min等…4、适配器一种用来修饰容器(container)或仿函数(functor)或迭代器(iterator)接口的东西。改变 容器 接口的称为 容器适配器(contai
2020-07-06 20:33:49
161
原创 C++之每日知识树-03-逻辑地址、线性地址、物理地址
打算放弃铁六角而改用铁三角（what、why、how）形式，因为铁六角过于臃肿和牵强，只利用铁三角和三扩展（树根扩展，同枝扩展，枝叶扩展）形式展开。what：数据总线、地址总线、物理地址、线性地址、逻辑地址过程：CPU要利用其段式内存管理单元，先将为个逻辑地址转换成一个线性地址，再利用其页式内存管理单元，转换为最终物理地址。why：为什么CPU需要进行两次地址转换？这样做两次转换，的确是非常麻烦而且没有必要的，因为直接可以把线性地址抽像给进程。之所以这样冗余，Intel完全是为了兼容而已（Intel
2020-07-03 10:23:14
570
原创 C++之每日知识树-02-HTTPS流程，是如何加密的？
计划采用铁六角（6W）的形式来实现知识树，即what、why、how、when、where、who，另外再加想到的扩展（树根扩展，同枝扩展，枝叶扩展）。构造出来的知识树一开始是不完美的，我在以后会不断的修改吗，争取包含更全面，更系统的知识点，但我不会对知识点进行过多的解释。力求心平气和、戒骄戒躁！本文参考深入理解HTTPS工作原理HTTPS流程，是如何加密的？what：什么是http、https？why：https作用？----http缺点（get/post请求方式）。从传输的角度来说，他们
2020-06-30 22:39:08
221
原创 C++之每日知识树-01-析构函数为什么是虚函数？
知识树的构造，目的是在面试时，面试官抛出一个问题，自己简单几句就回答了。这样并不会给面试官好的印象。而多方面去回答这个知识点，可以把面试节奏掌握在自己手中，也会给面试官留下会更深刻的印象。计划采用铁六角（6W）的形式来实现知识树，即what、why、how、when、where、who，另外再加想到的扩展（树根扩展，同枝扩展，枝叶扩展）。构造出来的知识树一开始是不完美的，我在以后会不断的修改吗，争取包含更全面，更系统的知识点，但我不会对知识点进行过多的解释。力求心平气和、戒骄戒躁！析构函数为什么是虚函
2020-06-29 10:29:20
109
原创 C++之TopK求解
TopK问题，就是找到一堆数据中最大/最小、出现频率最高等问题。现在想一下其实解决TopK问题的话，有一下几个想法：1、直接各种排序，前提是内存足够的话，如果数据量极大，那就不太抗得住了。2、最大最小堆。保留K个值，然后其他值与之比较，对最大/最小堆进行增加删除操作。3、分治思想。把所有数据分成无数的k段，然后再合并不同的段称为新的k段，直到最后剩下一个段，即为所求。4、hash法下面就用实例来上手一下：Leetcode347. 前 K 个高频元素给定一个非空的整数数组，返回其中出现频率前 k
2020-06-23 20:27:02
1480
1
原创 C++之二分查找解题套路
对于二分查找的相关Leetcode试题，有两类：找目标点的位置和找目标点的边界。一、找目标点的位置这也是二分查找的基本用法，这个应该是非常简单就可以写出来：int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { int mid = left + (right - left) / 2
2020-06-19 15:42:04
177
原创 C++之回溯算法解决子集、全排列和组合问题
这篇文章回溯算法团灭子集、排列、组合问题写得很好，在此记录一下自己的理解以及使用LeetCode真题来帮助更好地运用。先说一句话：回溯算法就类似于多叉树的遍历问题！！！！作者说回溯算法就是多叉树的遍历问题，我认为其中还有一个区别，那就是遍历问题每个元素只会使用一次，而回溯算法中，每个元素使用多次，这也是为何算法中会有撤销选择这一步了。。上面这句话猛一看很难理解，接下来咱们慢慢揭开它的神秘面纱！！一、从二叉树的遍历开始讲起我之前写过c++之二叉树的递归实现与广义表实现，其中关于二叉树的递归遍历解
2020-06-17 20:27:07
2653
2
原创 C++之移动构造函数与拷贝构造函数关系
在c++右值引用之转移构造函数文章中，我们介绍了移动构造函数三点注意问题1、参数（右值）的符号必须是右值引用符号，即“&&”。2、参数（右值）不可以是常量，因为我们需要修改右值。3、 参数（右值）的资源链接和标记必须修改。否则，右值的析构函数就会释放资源。转移到新对象的资源也就无效了。关于第三点原因：虽然调用移动构造函数或者移动赋值操作符后，已经获得了右值的的内存空间，但是之后右值就被销毁了，那么获得的的那片内存也被释放了，指向的就是一个不合法的内存空间。所以我们就要防止这片空间
2020-06-08 15:36:23
1138
原创 c++之并查集
假如已知有 n 个人和 m 对好友关系 （存于数字 r） 。 如果两个人是直接或间接的好友 （好友的好友的好友…） ， 则认为他们属于同一个朋友圈，请写程序求出这 n 个人里一共有多少个朋友圈，或者判断两个人是否属于同一个朋友圈。 假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有 5 个人，1 和 2 是好友，2 和 3 是好友，4 和 5 是好友，则 1、2、3 属于一个朋友圈，4、5 属于另一个朋友圈，结果为 2 个朋友圈。直接来真题吧
2020-06-08 10:11:13
152
QT5翻金币小游戏（window7）
2019-12-10
c++贪吃蛇实现/图形化编程
2019-10-31
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人