alex1997222-CSDN博客

原创 (模板)树状数组模板

#include <iostream>using namespace std;const int MAX_N= 10010;int C[MAX_N];int n;int lowbit(int x){ return x & (-x);}int getsum(int x){ int res = 0; for(;x; x-=lowbit(x...

2019-04-21 20:56:03 141

原创 (模板)线段树(单点更新,区间更新)模板

单点更新#include <iostream>using namespace std;const int MAX_N = 10010;int s[4*MAX_N];void up(int p){ s[p] = s[p*2] + s[p*2+1];}void modify(int p,int l,int r,int x,int v){ //x为要修改...

2019-04-21 18:57:51 190

原创 Six Degrees of Cowvin Bacon POJ - 2139 (Floyd-warshall算法模板)

The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon".The game works like this: each cow is considered to be zero degrees of se...

2019-04-08 20:59:51 184

原创 Agri-Net POJ - 1258 (最小生成树模板题prim)

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.Farmer John ordered a high spee...

2019-04-07 15:47:25 160

原创 The Triangle POJ - 1163 (动态规划经典入门题)

73 88 1 02 7 4 44 5 2 6 5(Figure 1)Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top an...

2019-03-30 20:52:22 448

转载挑战程序设计竞赛（第二版）题集

第一章：蓄势待发热身：POJ 1852第二章：初出茅庐 2.1：（穷竭搜索）POJ 2386 习题：深度优先搜索：POJ 1979Aizu 0118Aizu 0033POJ 3009 广度优先搜索：Aizu 0558POJ 3669Aizu 0121 穷竭搜索：POJ 2718POJ 3187POJ 3050Aizu 0525 2.2：（贪心）POJ 3617POJ...

2019-02-14 16:47:56 1024

原创 (模板重要)Tarjan算法解决LCA问题(PAT 1151 LCA in a Binary Tree)

关于最近的公共祖先,如上图所示４和５的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。LCA问题一个好的解决思路是Tarjan算法,关于算法的思想见:https://www.cnblogs.com/JVxie/p/4854719.html,这篇博客的讲解比较通俗易懂,我根据博主给出的算法思路用代码进行了实现。int tAncestor = -1;void ta...

2019-01-28 14:44:17 262

原创 (重要)1133 Splitting A Linked List (怎样把一条链表拆成若干条新链表然后相连)

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those grea...

2019-01-25 15:46:35 207

原创 (模板)已知二叉树先序(后序)中序,求这棵二叉树

这种题型为考研常考题型。看这张图就比较好理解了,先序的第一个元素或后序的最后一个元素为当前子树的根确认先序/后序的根后,我们遍历中序序列寻找根在中序序列中的位置,上图中为ink,那么ink左边的序列位于二叉树的左子树部分,ink右边的序列位于二叉树的右子树部分我们确认左子树部分k个元素,就可以确定子树区间了先序左子树区间 [POSTL+1,POSTL+k]先序右子树区间 [...

2019-01-22 19:39:21 273

原创 (模板)深度优先遍历与背包问题

深度优先算法除了可以解决图遍历问题,还可以解决背包问题,主要思想是遇到岔路:选还是不选比如背包问题:对于每件物品都有选或者不选两种情况,好比迷宫中的岔路,这时候我们可以利用深度优先算法思想遍历出所有的情况,然后选择不超过V的同时物品价值最大的情况void DFS(int index, int sumW, int sumC) { //递归到界限的话,退出循环 if (index...

2019-01-21 17:41:16 755

原创 (模板)堆的快速搭建

堆排序是指使用堆结构对一个序列进行排序的过程,此处讨论递增排序的情况考虑对一个堆来说,堆顶元素是最大的,因此在建堆完毕后,思路就是取出堆顶元素,然后将堆的最后一个元素替换至堆顶,再进行一次针对堆顶元素的向下调整--如此重复,直到堆中剩下最后一个元素为止如此重复,直到堆中只剩下最后一个元素为止我们可以直接用一个数组来表示堆,const int maxn = 1001;int ...

2018-11-08 21:41:32 399

原创 (模板)AVL树的实现

#include <iostream>#include <algorithm>using namespace std;class ANode {public: int v, height; //v表示权值,height表示树的高度 ANode *lchild, *rchild; //左右孩子的结点信息};//建立一个新的结点ANode* c...

2018-11-05 09:19:55 324 2

原创 (方法)给定一个有序数列,通过中序遍历利用数组建立起二叉查找树(PAT1064)

建树的时候,有时候没有必要大费周章地去通过结点构造一棵二叉树,我们利用各结点之间的数学关系,通过数组就可以实现一棵二叉树,假设结点序列为a,那么其左子就是a*2,右子就是a*2+1由于二叉树中序遍历的结果是一串有序序列,那么我们可以通过中序来得到一棵二叉树void leveltra(int root) { //从根节点开始遍历 if (root > n) { return...

2018-11-01 18:33:41 1320

原创 (方法)利用层序遍历返回二叉树上的节点

我们在查找二叉树上的节点时,会通过递归去进行遍历,如果我们要把这个节点作为函数返回值进行返回的话,递归遍历法就无法满足我们可以通过层序遍历去查找结点然后进行返回,只需一个辅助队列就行中序遍历的思想很简单(1)先将父亲结点入队(2)如果父亲结点的左子不为空,左子入队(3)如果父亲结点的右子不为空,右子入队(4)父亲结点出队(5)重复上述操作直到队列为空我们通过层序遍历...

2018-10-05 16:18:47 750

原创 (方法)二叉树的广义表形式,建树和输出

二叉树的广义表示形式:a:表示根节点为a,左右节点均为空a(b):表示根节点为a,左节点为b,右节点为空a(,c):表示根节点为a,左节点为空,右节点为ca(b,c)表示父节点为a,左子节点与右子节点分别为b和c同样的表示方法还有a(b(d),c) 存储广义表二叉树的方法:将广义表创建成二叉树,可以借助栈来实现。利用栈先进先出的特点,如果左孩子节点不为空,则将其...

2018-10-05 16:08:34 15411 2

原创多态

C++中所谓的多态是指由继承产生相关的不同的类,其对象会对同一消息做出不同的反应比如使用绘图软件时选择不同的图形,执行同一个托动作就可以绘制不同的图形多态是面向对象的一个重要特征,能增加程序的灵活性,可以减轻系统的维护工作量多态的基本要求:赋值兼容赋值兼容规则是指,在需要基类的任何地方,都可以使用公有派生类来进行替代。只有在公有派生类中才有赋值兼容,赋值兼容是一种默认行为,不需...

2018-08-28 22:29:40 195

原创指向类成员/函数的指针

C++扩展了指针在类中的使用,使其可以指向类成员,这种行为是类层面的,而不是对象层面的。指向类成员/函数的指针的本质并不是取地址.而是利用了对象地址的偏移量我们创建了一个类,假设我们要使用指针指向类中的成员class Student {public: Student(string n,int nu):name{n},num{nu}{} void dis(int idx) {...

2018-08-23 16:36:04 5882

原创类成员指针及成员函数指针

如果我们要指定一个指向类内部元素的指针,那我们该怎么操作呢假设我们定义了一个类:里面有两个变量和两个函数struct Vector{public: int x; int y;public: Vector(int tX, int tY) :x{ tX }, y{ tY } {} int getX() const { return x; } int getY() ...

2018-08-04 21:03:34 1132

原创菱形继承

两个子类继承同一个父类，而又有子类又分别继承这两个子类,就称作菱形继承多重继承产生的二义性假设有一个基类,他派生了两个子类分别继承于它,比如说下面这个例子:class A {public: A(int d) { cout << "A()" << endl; _data = d; }protected: int _data;};cla...

2018-08-02 18:00:05 172

原创面向对象常用STL函数与算法(常用模板算法笔记)

STL里面的所有容器都有迭代器的概念,迭代器分为好几类,有只读的,有随机的有顺序的,等等。C++当初在设计迭代器的时候,是想把它设计成指针那么用,类似一个数组指针,我们可以对其进行++和—操作,可以*它,也可以->它。这些指针具有的操作,迭代器基本都有之所以要一对迭代器而不是一个迭代器,是因为迭代器本身就是一个范围,这个范围是左开右闭的,如[a,b),用if判断的方法就是 a<...

2018-07-31 20:58:39 262

原创浅拷贝与深拷贝(防止指针传递而出错)

C++中,一个对象的实例可以像int一样,可以被复制构造和传递,而且不用担心new和delete的问题（1）要保证这个类型的构造函数和析构函数,如果没有的话就意味着自动生成那些,应该是对使用者可见的 (2) 复制语义要准确,一个值类型可以使用operator=运算符重载和复制构造函数来实现复制比如要做一个字符串类型,里面肯定带一个char*成员,如果我们什么...

2018-07-26 15:11:38 864

原创 HTML5介绍以及常用标签

标题:h1,h2,h3,h4,h5段落:p换行:br容器:div,span表格:table,tr,td列表:ul,ol,li链接:a图片:img表单:input

2018-01-02 15:54:17 296

转载算法导论阅读顺序

对于学计算机的，特别是搞开发的人来说，算法是一个很重要的内功，其重要性不言而喻。同时也是较难的一个点。当你被人安利了无数次《算法导论》，拿起书却发现根本读不下去。本场 Chat 我将告诉你对于一个入门的新手来说应该如何以正确的姿势在 10 天内读完这本书的基础部分的，我会一步一步告诉大家每一章应该怎么读，具体到读书的顺序。亲测有效！算法基础部分包括：算法在计算中的应用算法基础函数增

2017-12-08 19:18:46 1210

原创 C++ 重载实例:复数的运算操作

因为涉及到输入流和输出流的重载,这里先介绍一下输入流和输出流的重载方法:struct Vector{ int x; int y;};我们要在输出流中直接输出类,比如(1,2),(3,4),那么我们该怎么做呢这个时候我们要重载输出流:ostream& operator<<(ostream& o, Vector v){ return o &...

2017-11-18 22:19:48 2633

原创计算右侧小于当前元素的个数(归并排序)

###解题思路归并排序###代码class Solution {public: vector<int> res; vector<pair<int,int>> temp; vector<pair<int,int>> pairIdx; void mergeSort (vector<pair<int,int>>& nums,int l,int r){ if..

2021-02-25 19:55:59 307

原创 (模板)旋转数组模板

class Solution {public: int minArray(vector<int>& numbers) { if(numbers.size() == 1) return numbers[0]; //直接返回结果 int offset = numbers.size()-1; while(offset && numbers[0] == numbers[offset]) offset--; .

2021-02-24 15:40:04 227

原创剑指 Offer 51. 数组中的逆序对

###解题思路利用归并排序算法:由于用于归并的两个序列是已序的,所以在进行两辆比对时,序列A中的一个数大于序列B中的一个数,那么序列A中这个数的后面所有数都大于这个数###代码class Solution {public: int res = 0; vector<int> temp; int mergeSort(vector<int>& nums,int l,int r){ if(l >= r) retur..

2021-02-24 14:21:56 259

原创深度优先搜索去重(47. 全排列 II)

比如需要全排列的数组中存在重复元素,首先我们将数组排序将重复的元素放在一起,然后在递归的时候判断当前元素是否和其前一个元素值相等,如果相等,则判断前一个元素是否已经在dfs序列中(被使用过),如果前一个元素还没被使用过,则当前元素也无法被使用。因此这里的逻辑为:(nums[i-1]==nums[i] && !hm[i-1])class Solution {public: vector<bool> st; //这个数是否被用过 vector<in

2021-02-23 19:50:24 222

原创 *435. 无重叠区间(贪心)

###解题思路贪心策略:按照右端点从小到大排序,然后拼接区间###代码class Solution {public: static bool cmp(vector<int>& a,vector<int>& b){ return a[1] < b[1]; } int eraseOverlapIntervals(vector<vector<int>>& intervals)..

2021-02-17 12:20:59 102

原创 43. 字符串相乘(大数相乘模拟)

就是模拟乘法的一个过程,这里我们不按正常的乘法做法来做:我们在每一位相乘后不进行进位,而是保留相乘得到的结果,到最后相加的时候再去进行进位。如下图所示:代码如下所示:class Solution {public: string multiply(string num1, string num2) { vector<int> A,B; int n = num1.size(),m = num2.size(); for(int

2021-02-17 09:27:06 138

原创原地哈希法(41,442,448)

某些类型的题目希望我们在解题时找到重复出现或是缺失的那个数却不让我们使用额外空间,这意味着我们无法使用额外的哈希表来统计数字出现的次数比如下面这道题目:442给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？示例：输入:[4,3,2,7,8,2,3,1]输出:[2,3]我们在遍历这个数组的过程中,首先把每个数字其真正对应位置

2021-02-15 20:37:36 352

原创 (背下来)169. 多数元素(BM投票法)

###解题思路BM算法如果当前字符和前一个字符一样:计数++如果当前字符和前一个字符不一样:1.如果c>0,则c--2.如果c==0,则把r替换为当前字符,c=1###代码class Solution {public: int majorityElement(vector<int>& nums) { int r ,c = 0; for(auto x : nums){ if(!c) r..

2021-02-15 19:14:12 126

原创 (背下来)59. 螺旋矩阵 II

###解题思路经典模拟题,首先定义row=0,col=-1然后用试探法判断下一步有没有越界以及可不可以摆放相应的元素###代码class Solution {public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n,vector<int>(n,0)); int row = 0,co...

2021-02-15 02:38:40 110

原创 (考前看)57. 插入区间(二分+区间合并)

###解题思路利用二分法找到合适的位置插入区间1.枚举特殊情况:插入最左端和插入最右端2.找到第一个区间,使得区间的右端点大于目标区间的左端点3.找到第二个区间,使得区间的右端点大于目标区间的右端点4.处理一种特殊情况,就是这个区间单独成为区间段,不与其他区间合并###代码class Solution {public: int binsearch(int l,int r,int tar,vector<vector<int>>& in..

2021-02-13 00:31:26 113

原创 (背下来)简化路径(栈模拟)

###解题思路利用string来模拟栈的思维###代码class Solution {public: string simplifyPath(string path) { if(path.back() != '/') path += '/'; string res,name; for(auto c : path){ if(c != '/') name+=c; else{ ..

2021-02-12 21:10:29 81

原创找到字符串中所有字母异位词(异位词统计)

###解题思路首先利用哈希表保存s1中字符出现的次数利用双指针在s2中维护一段长度为s1的滑动窗口,然后统计这段窗口中的字符出现次数是否与s1一致把符合条件的字符串首字母加入哈希表###代码class Solution {public: unordered_map<char,int> hm1,hm2; vector<int> findAnagrams(string s, string p) { vector<int&g..

2021-02-11 23:29:53 241

原创 63. 不同路径 II

###解题思路在62题的基础上加上了判断每一个格子能不能走还是62题的做法,把不能走的格子置为0即可###代码class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(),n = obstacleGrid[0].size(); if(m ==..

2021-02-10 02:21:47 146

原创 *662. 二叉树最大宽度(层序遍历+保留每一层的位置)

解题思路用pos2与pos2+1来保存节点的位置,在层序遍历中,每一层第一个遍历到的节点就是该层的左边界然后通过res = max(res,pos-l+1)来求最长宽度(不用去寻找右边界)利用unsigned long long来保存每个节点的位置防止越界代码class Solution {public: queue<pair<unsigned long long,TreeNode*>> q; int widthOfBinaryTree(TreeNo

2021-02-10 01:24:29 189

原创 (背思路)316. 去除重复字母(贪心)

###解题思路贪心思路:遍历字符串,尝试将每个字母入栈,如果栈顶字母值大于当前要入栈的字母的值,则将栈顶的那个字母出栈同时要保证每个元素的个数不为0开两张哈希表用来保存每个字母出现的次数以及是否已经存在于栈中然后遍历字符串即可###代码class Solution {public: vector<int> st; unordered_map<int,bool> vis; unordered_map<int,int> ..

2021-02-10 00:21:46 134

原创 138. 复制带随机指针的链表

###解题思路和克隆图133是一个思路,利用哈希表保存每个节点克隆出来的节点,边遍历边克隆###代码class Solution {public: unordered_map<Node*,Node*> hm; Node* copyRandomList(Node* head) { if(head == NULL) return head; Node* p = head; Node* root = new Node(..

2021-02-09 02:11:48 111

空空如也

python 安装autopy3失败