题目：POJ1961. 题目大意：给定一个长度为n的字符串，求出对于每一个前缀满足最大循环次数大于1，该前缀的长度与最大循环次数. 注：一个串的一个i最小的前缀满足重复次与完全相同，那么被称为的最小循环元，k被称为的最大循环次数. 最小循环元问题是KMP的一个很经典的应用，所以先求出原串的next数组. 我们回忆next数组的含义，next数组表示的是最长的一个既是前缀又是后缀的串的长度.那么考虑应用这个数组的一些性质，很容易猜到一...
一.算法题题目Given a string, find the length of the longest substring without repeating characters.ExampleGiven "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of Note that the answer must be a substring, "pwke" is a subsequence and not a substring.二.算法题解读题目大意:给定一个字符...
一.算法题 题目 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.Example输入: (2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 0 -> 8 原因: 342 + 4...
进阶指南中给了一个好玩的方法，对顶栈，与对顶堆有这异曲同工之妙，涉及左侧栈的操作，都需要对保存最大前缀和的数组进行维护 #include<iostream> #include<stack> #include<algorithm> using namespace std; stack<int>a,b; long long sum[1000005];int main(){int n;cin>>n;while(n--){char c;cin>>c;int x;if(c=='I'){cin>>x;a.push(x);sum[a.size()]=sum[a.size()-1]+x;}if(c=='Q'){cin>>x;long long maxans=-0x3f3f3f;for(in...
在算法竞赛进阶指南的第一章中利用堆的特性，我这里直接利用优先队列，不过做起来我做的有点麻烦，重载运算符，最关键的问题是，格式我还调了半天，诶； #include<iostream> #include<queue> using namespace std;struct rec{int num; }; struct rev{int num; };bool operator <(const rec &a, const rec &b){return a.num>b.num; } bool operator <(const rev &a, const rev &b){return a.num<b.num; }priority_queue<rev>mx; pri...
本道题目是利用递归，去把最后等级1的某个位置求出来，然后回溯向上去把上一等级的相应位置求出来，一般是右下角向左上右上左下扩展，根据旋转的规律回溯计算 城市的规划在城市建设中是个大问题。不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：左上顺时针90，右上向上反转，左下是逆时针90 #include<iostrea...
题目是二维前缀和，N^2完成维护 S[i,j]=S[i-1,j]+S[i,j-1]+A[i,j]，简化操作数据直接输入S中 题目中要注意目标的坐标，往往被包含在x+1,y+1之中 #include<cstdio> #include<algorithm> using namespace std; int f[5005][5005];int main(){int n,R;scanf("%d%d",&n,&R);int maxx=R,maxy=R;while(n--){int x,y,v;scanf("%d%d%d",&x,&y,&v);x++;y++;//注意f[x][y]+=v;maxx=max(maxx,x);maxy=max(maxy,y);}for(int i=1;i<=maxx;i++){f...
1、二叉树的特点： (1)、每个节点最多有两个子树(2)、左子树和右子树是有顺序的，次序不能颠倒(3)、即使某节点只有一个子树，也要区分左右子树 2、二叉查找树（Binary Search Tree）:（又：二叉搜索树，二叉排序树） (1)、它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为...
文章目录 前言一、二叉树的存储1、顺序存储2、链表存储：二叉链表 二、二叉树的遍历1.前序遍历2、中序遍历3、后序遍历4、层序遍历5、代码实现： 总结前言 二叉树的进阶内容一、二叉树的存储 1、顺序存储 说白了，就是数组存储。不多说，直接上图： 这个是一颗完全二叉树，可以发现如果按照层序编号，编号即数组下标，就会发现一个规律：左儿子 = 父节点 2；右节点=父节点2 +1 ； 这样的话，就可以利用这一下标变换，表达一个节点的...