共 8 篇文章
传送门 树状数组板子题。借这道题整理一下树状数组的模板 class NumArray { private: vector<int> tree; vector<int> arr; int n; int lowbit(int x) { return x & -x; } // 求前缀和 // [0, x) int query(int x) { int res = 0; for (int i = x; i > 0; i -= lowbit(i)) { res …
最近几天LeetCode高强度推送单调栈的题目，以往对这个数据结构的认识都只是停留在肤浅的表层上，看了这些题目后发现这个看似简单的栈结构其实用法很多，也很灵活，于是单独开一篇文章记录学习。 单调栈介绍 顾名思义，单调栈是满足一定单调性的栈结构。现在我们通过模拟实现一个单调递减栈来了解它具体的结构。 有一组数[10,3,7,4,12]。从左到右依次入栈。当且仅当栈为空或入栈元素值小于栈顶元素值时入栈；否则将所有比入栈元素小的元素全部出栈，再进行入栈操作，以确保栈的单调性不被破坏。 10入栈时，栈为空，直接入栈，栈内元素为10。3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。 单调递增的栈反之即可。了解了单调栈的概念，接下来就该撸题了。 单调栈例题 LeetCode-402：移掉K位数字 传送门 思路 题目要计算一个整数去掉k个数位后的最小新整数。最直接的思路就是枚举每一种取法然后维护最小值，但这么做的复杂度显然是指数级，不能这么莽。 考虑O(n)的方法：从左到右遍历num，对每一位数字决定它是否保留，这个操作执行k次即可。那么以什么依据来判断当前数字是该留还是该舍呢？ 假设有两个数字，123a456与123b456，怎么去判断它们谁大谁小呢？显然，a>b时前者大于后者，反之亦然。即，判断两个数大小关系的依据是两者第一个不同的数位大小关系。 根据上面的思路，我们只需要在枚举到每一位的时候去维护一个局部单调递增栈作为答案就好了。为什么是“局部”递增栈呢？因为题目要求我们要去掉k位数位，单调栈在不满足入栈条件的情况下会一直弹出栈内元素直到满足入栈条件，我们显然不能让它把答案全弹出去，所以当不能再弹的时候(即(n-k)-ans.size()>=n-i时)就继续去枚举下一位数位。 代码 ```cpp class Solution { public: string removeKdigits(string num, int k) { int n = num.size(); string ans = ""; if(n == k) return "0"; if(k == 0) return num; for(int …
LeetBook传送门 LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。 集合set的使用 t1两个数组的交集 求两个集合的交集，重复元素计算一次。 思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。 ```cpp class Solution { public: vector intersection(vector& nums1, vector& nums2) { setset1; setset2; vector ans; for(int i = 0; i < nums1.size(); i++) set1.insert(nums1[i]); for(int i = 0; i < nums2.size(); i++) set2.insert(nums2[i]); set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans)); return …
二叉堆简介 二叉堆是一种特殊的数据结构，它是一颗具有独特优势的二叉树。 简单地说，二叉堆即是一颗父节点与左右子节点间具有严格大小关系的二叉树。其中父节点大于左右子节点的堆被称为最大堆，反之为最小堆。 二叉堆的操作 插入 二叉堆中新元素的插入位置总是最后一个叶子节点所在位置。通过将新节点上浮至合法位置来维持二叉堆的特性。 删除 与插入相对应，二叉堆总是删除当前的根节点，也就是它的堆顶。删掉当前堆顶后，将最后一个叶子节点放在堆顶并下沉至合法位置，以此来维护二叉堆的特性。 构建 二叉堆的构建是从最后一个叶子节点开始，依次通过执行上浮与下沉操作将每一个节点都归位到合法位置的过程。 二叉堆的存储 不同于传统二叉树，二叉堆的存储采用顺序存储，即数组。在不存在左右儿子指针的情况下，假设父节点为parent，那么它的左右儿子分别为2*parent+1与2*parent+2。 ```cpp #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; const int INF = 0X7F7F7F7F; //上浮叶节点 …
[图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/06/图-xmind-589x1024.png 图 逻辑结构 遍历 dfs 栈/递归 ①从图中某个顶点V0出发②找出刚访问的顶点的第一个邻接点，访问它并将他置位当前节点③重复步骤2直至当前节点不再有邻接点④返回上一个仍有邻接点并未被访问过的节点，重复步骤 bfs 队列 依次访问当前节点的每一个邻接点 存储结构 邻接矩阵 定义 设矩阵A，对于任意的Vi与Vj，若∈VR，则Aij＝1，反之为0 实现 有权图的邻接矩阵初值赋为∞，无权图初值为0. 再通过循环存入每一条弧。 复杂度 时间复杂度 存弧的时间复杂度为O(e)，赋初值的时间复杂度为O(n²) 空间复杂度 空间复杂度为O(n²) 特性 便于运算 因为使用矩阵存储，所以可以便捷地访问每一条弧。显然，判断弧存在、求顶点的度都可以在短时间内较优地完成 …
传送门→ 就是实现一个能在常数时间内返回最小值的栈。根据常规思维，减少时间开销的代价一般都是增大空间开销，所以往这个方向去思考。因为栈可能随时都在弹出元素，所以单纯的用一个变量去维护最小值是不够的，这里可以用另一个栈来辅助。 单独设置一个栈mini用以保存当前栈顶元素进栈时的最小值，即每一个新元素进站时从此元素与当前mini栈顶元素中得到较小值，在x进栈的同时将这个最小值压入mini栈。这样mini栈顶就一定是当前栈内的最小值。 ```cpp class MinStack { protected: vector data; vector mini; public: /** initialize your data structure here. */ MinStack() { mini.push_back(INT_MAX); } void push(int x) { int tmp = min(mini.back(), x); data.push_back(x); mini.push_back(tmp); } void pop() { if(data.empty()) return; data.pop_back(); mini.pop_back(); } int …
```cpp // // linklist.cpp // 链表 // // Created by edisoncgh on 2020/4/4. // Copyright © 2020 edisoncgh. All rights reserved. // #include #include #include using namespace std; //构建节点类 class Node { public: int data;//数据域 Node* next;//指针域 }; class List//构建链表类 { public: List();//构建函数 ~List();//析构函数 void createList(int n);//创建一个n结点的链表 …
在pta上完成数据结构的课程作业时发现一道很有意思的题，记录一下。传送门 题面 本题要求编写程序，计算N个有理数的平均值。 输入 输入第一行给出正整数N(≤100)；第二行中按a1/b1,a2/b2...的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。 输出 在一行中按a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。 样例 样例输入1 4 1/2 1/6 3/6 -5/10 样例输出1 1/6 样例输入2 2 4/3 2/3 样例输出2 1 这题成功的让我拓宽了关于c语法的知识面，所以我在此记录下来，虽然它不算经典意义上的难题与要题。 首先，因为题目中指明是有理数，所以可以求最小公约数来约分计算，难度降低了不少。使用C++的pair类来存储分子与分母，然后分别读入它们再累加求平均数即可。 #include <cmath> #include <cstdio> #include <utility> …