-
单调队列和单调栈
===Index 介绍 单调队列 滑动窗口最大值 满足条件的出发点数量 连续子序列的最大和 和至少为 K 的最短子数组 和大于等于k的最长连续序列 单调栈 每日温度 好子数组的最大分数 左边区间第一个比它小的数 队列中可以看到的人数 使数组按非递减顺序排列 介绍单调栈单调栈是指一个栈内部的元素是具有严格单调性的一种数据结构，分为单调递增栈和单调递减...…
-
动态规划分类选题
===Index 树形DP 没有上司的舞会 选课 树的重心 树的最长路径 树的中心 二叉树染色 监控二叉树 换根dp 最大深度和 树中距离之和 去掉一个端点的最长路径和 树上边权加终点点权最长路径 根节点的潜力值 状态压缩dp 完成所有工作的最短时间 完成任务的最少工作时间段 线段树优...…
-
C/C++知识点
===Index 基础语法 继承/多态 C++11特性 如何定义一个只能在堆上（栈上）生成对象的类 实现单例模式 实现c语言字符串库函数基础语法1. new, delete与malloc, free的区别联系 malloc, free是c语言库函数，new和delete是C++运算符 new与malloc都是堆分配。malloc仅分配一定size的字节，返回值是void*, new和delete会调用构造函数和析构函数，new 返回值是对象类型指针 2. 描述...…
-
海量数据处理
===Index 备忘 如何判断一个数是否在40亿个无重复整数中？ 布隆过滤器 用2g内存找到20亿整数中出现次数最多的数 40亿个非负整数中找到没出现的数 100亿个URL中重复的URL及搜索词汇的topk问题 40亿个非负整数中找出现两次的数或所有数的中位数备忘 1 GB: 十亿个字节（Byte） 1(B) * 10*10^8 / 1024 / 1024 ≈ 953.67(MB) ≈ 1000(MB) ≈ 1(GB) 400 MB: 一亿...…
-
双指针专题
=== 双指针问题无论在笔试还是面试中出现的频率都非常高；是性价比非常高的一类问题。模板小结 首尾双指针 一般用于寻找数组/双向链表中满足条件的两个节点；如果是寻找多个数，则先固定前 n-2 个数； 为了不遗漏所有可能情况，可能要求数组有序； 典型问题：两数之和、三数之和、三角形计数 同向双指针 数组中，一般用于寻找满足某个条件的连续区间； 链表相关问题中经常会使用快慢双指针来寻找某个节点...…
-
数据结构
===Index 用两个栈模拟队列 最小栈 LRU 缓存机制 LFU 缓存 添加与搜索单词 树状数组 简介 一维树状数组 二维树状数组 线段树 ST 表 字典树（Trie）用两个栈模拟队列用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。思路 假设 stack_in 用于处理入栈操作，stack_out用于处理出栈操作 stack_in 按栈的方式正常处理入栈数据； 关键在于出栈操作 ...…
-
二叉树系列
===Index 二叉树遍历 先序遍历 中序遍历 后序遍历 二叉树的层次遍历II 二叉树的锯齿形层次遍历 N叉树的层序遍历 二叉树的垂直遍历 二叉树构造 从前序与中序遍历序列构造二叉树 从中序与后序遍历序列构造二叉树 恢复二叉搜索树 填充每个节点的下一个右侧节点指针 填充每个节点的下一个右侧节点指针II 最大二叉树 最大...…
-
洗牌、采样、随机数
Index 洗牌算法 Knuth-Durstenfeld Shuffle（Fisher–Yates Shuffle 改进版） Inside-Out Shuffle Inside-Out Shuffle 无穷版 采样（等概率） 无放回思路 有放回思路 蓄水池采样 采样（不等概率） 查表法（有放回） 如何采样，使 n-1 被采样 n 次？...…
-
数学/数论算法
===Index 大数取模 快速幂运算 64位数乘法 最大公约数 最小公倍数 试除法判定质数 试除法分解质因数 素数筛法 欧拉函数 扩展欧几里得算法 高斯消元 组合计数 前缀和 约瑟夫环 卡特兰数 施罗德数 NIM游戏大数取模取模运算的性质： 因为 (a%n) - (b%n) 可能小于 n，所以 +n 因为 (a%n)(b%n) 可能溢出，计算前应该强转为 long long a * b % m = (a % m) * (b % m)...…
-
leetcode中的图
===Index 并查集 岛屿数量2 拓扑排序 课程表1 课程表2 火星词典 完成拓扑图的最短时间 克隆图 判断二分图 dijkstra算法 SPFA算法 floyd算法 Prim算法 Kruskal算法 有向图求强联通分量并查集leetcode 684 : 冗余连接 无向图leetcode 685 : 冗余连接II 有向图岛屿数量2大小为 m*n 的二进制网格，0表示水，1表示陆...…
-
位运算
===Index 常用位操作 获取和设置数位 一些有用的位操作 二进制所有是1的位 进制转换 格雷编码 汉明距离 汉明权重 不用额外变量交换整数的值 只用位运算实现整数的加减乘除常用位操作在下面示例中，1s 和 0s 分别表示一串1和一串0x ^ 0s = x x & 0s = 0 x | 0s = xx ^ 1s = ~x x & 1s = x x | 1s = 1sx ^ x = 0 x & ...…
-
日期类问题
计算两个日期之间的天数leetcode 1360请你编写一个程序来计算两个日期之间隔了多少天。日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。 给定的日期是 1971 年到 2100 年之间的有效日期。 例如：输入：date1 = "2019-06-29", date2 = "2019-06-30"输出：1 int toDay(const string& dateStr) { int year, month, day; ...…
-
背包问题
背包问题总结Index 01背包 体积很大时的01背包 完全背包 多重背包 混合背包 二维费用的背包问题 分组背包 有依赖的背包问题01背包题目描述：有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。思路：动态规划，对于每一件物品遍历背包容量，当背包可容纳值大于等于当前物品，与之前已放进去的物品所得价值进行对比，考虑把是否需要置换。状态...…
-
专题-排列组合
Index 排列 下一个排列 上一个排列 STL 提供的实现（下一个排列、上一个排列） 第 k 个排列 第 k 个排列（两个元素） 排列的字典序 排列的字典序(有重复元素) 全排列（无重复） 基于插入的写法 基于交换的写法 全排列（有重复） 基于插入的写法 基于...…
-
剑指offer题解
说明 主要编程语言为 C/C++ 涉及字符串的问题可能会使用 Python 题目编号以原书为准，如“面试题 3：数组中重复的数字” 因为题目不多，所以就不做分类了 所有代码均通过 OJ 测试 在线 OJ 地址：剑指Offer_编程题 - 牛客网 Index 3.1 数组中重复的数字 3.2 不修改数组找出重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到头打印链表 7. 重建二叉树 8. 二叉树的...…
-
排序数组系列
===Index 搜索旋转排序数组 搜索旋转排序数组II（有重复） 寻找旋转排序数组中的最小值 寻找旋转排序数组中的最小值（有重复） 寻找两个正序数组的中位数 两个排序数组第k大数 合并k个有序数组搜索旋转排序数组leetcode 33假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组...…
-
二维数组遍历系列
===Index 螺旋矩阵 螺旋矩阵II 螺旋矩阵III 旋转图像 二维数组右上左下遍历 对角线遍历 神奇的幻方 蛇形填充数组螺旋矩阵leetcode 54给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 vector<int> spiralOrder(vector<vector<int>>& mx) { int m = mx.size(), n = m ...…
-
买卖股票系列
1.买卖股票的最佳时机给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。leetcode 121int maxProfit(vector<int>& prices) { int minprice = INT_MAX, maxprofit = 0; for (int price: prices) { maxprofit = max(ma...…
-
leetcode 打家劫舍系列
1.打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。leetcode 198 int rob(vector<int>& nums) { int n = nums.size(); if (!...…
-
正则表达式匹配
1.正则表达式匹配leetcode 10给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素分析 dp[i][j] 表示s的前i个字符和p前j个字符是否匹配。则if (p[j-1] == s[i-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1];如果 p[j - 1] == '*': 如果 p[j-2] == s[i-...…
