qq_45223955的博客

原创 topK问题

使用堆排序来求解 数组维持k个数 新来的元素和根进行比较 找k个最大值 建小堆 此时堆顶为最小值 当新来的元素比堆顶元素还要小 直接抛弃就可以了 因为不可能是最大值 否则 堆顶为新来的元素 替换堆顶在进行重新调整 (找最小值同样原理) 调整的时候根据最后一个父节点开始调整 遵循从下到上 从右向左的原理#include<iostream>#include<vector>#include<algorithm>using namespace s...

原创 堆排

#include<iostream>using namespace std;#define Left 2*nRootID+1#define Right 2*nRootID+2void Adjust(int arr[],int nlen,int nRootID) //大根堆{ int max; for(max = Left;max<nlen;max = Left) { //有两个孩子 if(Right<nlen) { if(arr[Right].

原创 快排代码

#include<iostream>#include<vector>using namespace std;//快排思想：找到一标准值 比标准值小的都放在左侧 比标准值大的 都放在右侧int _Find(int arr[],int nlow,int nhigh){ int temp; //保存标准值 temp = arr[nlow]; while(nlow<nhigh) { //从后向前找比标准值小的 if(arr[nhigh]<t.

原创 自己实现atoi

原创 二叉树的非递归中序遍历

原创 二叉树的非递归前序遍历

原创 缺失的第一个正数

题目明确给出了，是缺失的第一个“正数” 可以通过下标位置来进行解题 元素的值符合给定的区间范围 那么对应的下标元素放对应的值 值放好之后 那么我们遍历数组 因为缺失的正数 所以遍历从1开始 因为1是最小的第一个正数 如果这个时候位置与元素值不对应 那么我们找到了缺失的正数 否则再向下走说明1往后的位置都对应 那么我们看nums[0]也就是第一个元素值...

原创 最长公共子序列

一般这种最长的字眼 都是使用dp来求解

原创 最长不含重复字符的最长子串

注意是子串 而不是子序列解题思路：我们可以使用额外的空间 比如申请一个数组 保存我们每一个字符所出现的次数 并且每次都记录最大值 并且定义left让他从0开始 一旦vector当中的记录>1了 那说明出现重复的了 所以从头开始排除 是哪一个字符重复出现了...

原创 最长上升子序列

本题没有说连续 只是说上升的子序列 稍微有一点难度 也是典型的dp问题 我们可以申请dp数组 但是注意到的是 每一个dp里面的元素都要初始化为1 因为默认一个元素也是上升的子序列 并且在最大值比较的时候 也会用到 此题需要两次循环 外层循环i 内层循环j 并且j的下标要小于i的 dp[j]表示位置为j的最长上升子序列 为了可以让nums[i]拼接到nums[j]的后面 需要保证nums[j] <nums[i] 并且j的小标要比i小 相当于dp[j]保存当前的最长子序...

原创 最长连续递增序列

题目中给出 未经排序的数组 求最长的 并且还是连续的递增子序列的长度 “最长”、“连续” 典型的动态规划问题 因为题目中给了连续 所以减轻了题目的难易程度 申请动态数组 dp[i]表示位置i的最长连续递增数组的长度 默认初始化值为1 并且定义最大长度值为1因为连续 所以有了状态转移方程 dp[i] = dp[i-1]+1 nums[i]>nums[i-1] dp[i] = 1 nums[i]<=nums[i-1] 注意是小于等于 比如{2，2...

原创 字符串的最长回文子串

求字符串的最长回文子串 一般求“最长”这种基本都是用动态规划的思想来求解 我们申请二维数组表示dp[i][j]他表示字符串s[i...j]为回文子串 回文串本身的性质 去掉头、尾仍未回文串 所以状态转移方程dp[i][j] = dp[i+1][j-1] 但是还要注意一个问题 比如字符串 cbbd 此时bb是回文子串 但是此时i在b j也在b 没有i+1 j-1 所以我们要判断下标 看二者是否挨着 也就是j-1-(i+1)+1<2 这种情况 其实对于dp的问题 一般都是在填写一个表格...

原创 栈区堆区

浅谈堆区 栈区 字符常量区 全局区 代码区1.栈区：我们可能有时候分不清栈区堆区二者，栈区是由计算机自动分配与释放的，存放函数的参数值，局部变量的值等，内存的分配是连续的，如果说这样让我们很模糊的话，不防把它想成是个数组，对于数组来说，...

原创 Mfc中postMessage与sendMessage

Mfc中SendMessage与PostMessage区别？一直以为它们两个没有太大的本质区别，直到自己写东西遇到问题了才知道，所以记载下来方便以后的复习。对于sendmesaage来举例：如果说用户向窗口发送了内容（一块buffer）那么对于接收方直到接受完这块内容并且进行相应的处理后才会返回，也可以说成sendmessage是阻塞型。对于postmessage来讲：就可能会对内容啊产生覆...