-
POJ 1961 HDU 1358 KMP的性质
2012-03-22 21:41:17题目大意:求给出串的每个前缀串的重复次数。 例如aabaabaabaab; 1.aa中前缀a出现2次。...大概就是这么个意思。 这里利用了kmp中的next标记的性质。 看看这个字符串 下标:1 2 3 4 5 6 7 8 9 10题目大意:求给出串的每个前缀串的重复次数。
例如aabaabaabaab;
1.aa中前缀a出现2次。
2.aabaab中前缀aab出现2次
3.aabaabaab中前缀aab出现3次
4.aabaabaabaab中前缀aab出现4次.
大概就是这么个意思。
这里利用了kmp中的next标记的性质。
看看这个字符串下标:1 2 3 4 5 6 7 8 9 10 11 12
原串:a a b a a b a a b a a b
next: 0 1 2 1 2 3 4 5 6 7 8 9
用下标i减去next[i]即为(i-next)匹配的前缀的长度.
若这个数能被整除,整除的个数即为使用该前缀的个数。
so就是这样.....#include<iostream> using namespace std; char t[1111111]; int len,next[1111111]; int ri[1111111],rl[1111111]; void setNext() { int j=0,k=-1; next[0]=-1; while( j<len ) { if( k==-1|| t[j]==t[k] ) next[++j]=++k; else k=next[k]; } } int main() { int Ncase=0; while( scanf("%d",&len)!=EOF&&len!=0 ) { scanf( "%s",&t ); setNext(); printf( "Test case #%d\n",++Ncase ); for( int i=2;i<=len;i++ ) if( i%(i-next[i])==0&&i/(i-next[i])>1 ) printf( "%d %d\n",i,i/(i-next[i]) ); printf( "\n" ); } return 0; }
-
剑指Offer-二叉搜索树的后序遍历序列
2017-06-19 14:51:35题目解析刚开始看这道题目的时候,比较蒙,大概是因为我一开始就直接看代码,没看到什么细节性质的提示。再读了下题目,基本明白了他的意思,主要意思就是说给你一个序列,你确认下这个序列到底是不是一个二叉搜索树...题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
题目解析
刚开始看这道题目的时候,比较蒙,大概是因为我一开始就直接看代码,没看到什么细节性质的提示。再读了下题目,基本明白了他的意思,主要意思就是说给你一个序列,你确认下这个序列到底是不是一个二叉搜索树的后序遍历结果。这里稍微讲下,二叉搜索树的概念:根节点为参考,比根节点大的数据在右侧,比根节点小的数据在左侧,叶子节点左子节点比父节点小,右子节点比父节点要大。
解题思路
这个题目属于二叉搜索树的一个性质的考察,懂得什么是二叉搜索树的话才可以顺利进行,否则,概念都不懂根本搞不清楚哪里作为判断的标准。我觉得这个题目而言,找到判定标准很重要的,这应该说是一个决定本题能不能真正求出的关键,那么,我给出的建议是读者在自己思考时辅助举例子的方式进行,自己测试下,根据自己定义的一个二叉搜索树得到他的后续遍历序列,然后逆向推他到底是不是一个二叉搜索树的后续遍历的结果串。
这里以4,8,6,12,16,14,10为例子,首先,根节点10,这是可以直接得到的,那么根据其性质,根节点左侧的小于10,根节点右侧的大于10,那么可以将本题中的序列,切分为两个子集,切分为子集,一般的方式可以采用递归了,因为子集和其本身都是一个集合的抽象,将子集和全集视为一个类型的对象就可以了。注意这里当切分完成后需要进行一个检查,这个检查就是:第一个大于10的后面的这些序列中必须全部大于10,否则直接返回false。再看看左侧子集,左侧子集的话主要是4,8,6这个三个,然后将其视为新的全集进行上述操作,那么将6作为新的根节点,那么6而言,将4,8切分为两个子集,然后子集内进行上面的操作。
代码实现
这个题还有优化的可能,比如上面的检查可以和查找比他大的数的index同时来进行,但是时间上并不会得到客观的提升,都是O(n),无非是代码减少了,下面是按照几个特例划分了左侧递归,右侧子集的递归,左侧和右侧都进行递归。public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence == null || sequence.length == 0) { return false; } if(sequence.length == 1) return true; int endNum = sequence[sequence.length - 1]; int i = 0; for(; i < sequence.length - 1; i ++) { if(sequence[i] > endNum) { break; } } int index = i; for(; index < sequence.length - 1; index++) { if(sequence[index] < endNum) { return false; } } int[] smaller = null; int[] bigger = null; smaller = new int[i]; bigger = new int[sequence.length- i - 1]; int in = 0; for(int j = 0; j < sequence.length - 1; j ++) { if(j < i) { smaller[j] = sequence[j]; } else { bigger[in ++] = sequence[j]; } } if(i == 0) { return VerifySquenceOfBST(bigger); } else if(i == sequence.length - 1) { return VerifySquenceOfBST(smaller); } else { return VerifySquenceOfBST(bigger) && VerifySquenceOfBST(smaller); } } }
需要注意为空的情况,这是一个特例。其实我感觉这个特例不需要设计的,要么就在题目中说明。不过真正的项目中这个确实是要你自己去考虑到的。 -
最下的串(贪心)
2018-02-04 17:52:00题的大概意思是: 输入一个字符串的长度大小,然后输入字符串,首先分别选取字符串的首尾两个字符,进行字典序比较,将较小的放到新创建的字符串的后面,直到原本的字符串长度为0。这种思想适合贪心算法,每选...题的大概意思是:
输入一个字符串的长度大小,然后输入字符串,首先分别选取字符串的首尾两个字符,进行字典序比较,将较小的放到新创建的字符串的后面,直到原本的字符串长度为0。这种思想适合贪心算法,每选一步就选最值,所以理解了题意应该很简单。只需要做一些简单的处理还有题目要求的处理数据
* *这题主要是用贪心,目标主要是从已知的字符串构造出字典序尽可能小的字符串 *从字典序性质来看,无论字符串末尾有多大,只要保证前面部分较小就可以咯! *假设原来字符串为S,目标字符串为T,那么,不断取出S的开头和末尾较小的一个 *字符放到T的末尾。上面的没有针对开头与结尾相同,如果,遇到这样动情况,应 *该比较下一个字符的大小。如果,下一个字符也相同,那么可以得到下面的算法: *按照字典序比较S和将S反转后的字符串S’ *如果,S较小,那么取出S开头字符,追加到T的末尾 *如果,S'较小,那么取出S结尾字符,追加到T的末尾 *如果,相同则取出那一个都可以。 * * */ #include <iostream> #include <string> using namespace std; int n; char s[2010]; void solve() { int start = 0, end = n - 1,count = 0; while(start <= end) // 将从左起和从右起的字符串比较 { bool flag = false; for(int i = 0; i <= end - start; i++) // 字符串的开头与结尾相同,则继续比较下一个 { if(s[start+i] < s[end-i]) { flag = true; count++; break; } else if(s[start+i] > s[end-i]) { flag = false; count++; break; } } if(flag) cout<<s[start++]; else cout<<s[end--]; if(count % 80 == 0) cout<<endl; } cout<<endl; } int main(void) { cin>>n; for(int i = 0; i < n; i++) cin>>s[i]; solve(); return 0; }
-
P1028 数的计算
2017-05-12 09:21:49基础递归题目。题目:我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n),然后对此自然数按照如下...大概意思是说一个 小于输入的数一半的数可以计入总数。 可以一直加到这个数字的一半为0 把基础递归题目。
题目:
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.加上数后,继续按此规则进行处理,直到不能再加自然数为止.
理解:
- 题目不太好理解
- 大概意思是说一个 小于输入的数一半的数可以计入总数。
- 可以一直加到这个数字的一半为0
- 把每次除以二的过程理解为一层,用递归来做
- 多层递归, 时间复杂度大概爆炸了。。
代码:
#include<iostream> #include<string> using namespace std; int sum=1,i=0; //包括这个数字本身,所以sum初始化为1 int fun(int i); int main() { cin>>i; i=i/2; //第一层 sum +=i; fun(i); //开始递归 cout<<sum<<endl; } int fun(int i) { for(int j=1;j<=i;j++) //遍历该层所有的数 { if(j/2 != 0) { //判断下一层是否存在 sum+=j/2; fun (j/2); } } }
- 题目不太好理解
-
俩个相同大小升序序列合并在一起的中位数解法
2019-08-28 21:27:19大概意思就是一个如果一个序列S1(11,13,15,17,19)则中位数是15, S2=(2,4,6,8,20) ,如果把S1和S2按照升序合在一起则11是中位数。 让你写算法: 当然最常见的无非就是把他俩放在一个数组里然后直接就找到中间... -
使用ffmpeg转码时遇到aac报错
2019-10-07 10:49:59今天尝试用ffmpeg转一个视频的格式,结果报出这个错误: The encoder 'aac' is experimental but experimental...这句话的大概意思似乎是指aac是个实验性质的编码解码器,但是你的命令行里,并没有允许使用试验性质的编... -
架构之美阅读笔记03
2017-01-30 22:06:00随着读的深入,感觉这本书有点意思了,大概是书的作者为了提升趣味性才把案例弄的都那么有意思吧。第三章就讲到了游戏。本章根本是要把Web那套搬游戏里去,不过毕竟还是试验阶段的玩意,我也没能力评价,最后结果会... -
【专题属性】图论
2012-07-31 16:19:34这一题的大概意思就是一种叫做Dagy的有向图,满足以下性质,删去其中的一条边后是有向无环图,且这个图存在一个环,这个环能够包含图上的所有节点。问输入的图是否满足性质。 题解: 1.如果存在入 -
股票: 换手率
2019-03-10 07:01:32什么是换手率? 换手率”也称“周转率”,指在一定时间内市场中股票转手买卖的频率,是反映股票流通性强弱的指标之一...其实从字面理解就知道换手率的大概意思。但是我们股票必须要了解的并不是单单的概念,我们要知... -
算法日记-贪心算法1
2020-06-29 22:46:00算法日记-贪心算法1贪心算法自顶向下和自底向上贪心算法性质例题解题贪心算法验证 贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在...自顶向下大概意思是从抽象到具体 贪心算法性质 理解每种算法的 -
疯狂的程序员
2012-07-18 18:05:32比如卖车的找个好的造车的不容易,炒蛋炒饭的找只好母鸡不容易,拉广告的要找个好的做广告的更不容易。大的广告公司,别人瞧不起你;小的广告公司,绝影瞧不起别人。 一直过了半个月,这事情才总算落实,还像模像样... -
DSU on tree CodeForces - 741D
2019-08-02 14:20:54主要还是去学了一下这个东西,大概就是利用的轻重链的性质,把暴力的复杂度优化到了(nlogn)。非常神奇的算法。 题目还是略板的。 题目意思就是问每棵子树上有多少权值异或和为0或者二进制最多1个1的链。 #... -
OC学习之多态初解
2013-07-28 22:11:16对多态的含义还不是很理解,大概的意思应该是这样 多态是基于继承, 不同的对象使用同一个方法或者说名字相同的方法 能实现不同的功能 比如 两个人在吃饭, 吃饭就是方法 两个人就是对象 ,两个人在吃饭就是多态 ... -
8/14训练日记
2019-08-15 00:28:29今天终于没再下雨了! 但是还是要继续看同余,同余什么的最讨厌了!...矩阵的乘法,就是线代里面矩阵的乘法,a行乘b列呗,但是啊,这个书上写出来的算式就很没意思,让人看不懂,所以这大概就是老师的... -
HDU 1695 BZOJ 2301 莫比乌斯反演
2016-09-23 15:19:00看了两个多小时,大概意思我觉得莫比乌斯是一个利用一个数的能被整除的一些数,通过容斥来计算出这个数的一些信息,很高级。这个题就当做是模板吧。然后把两种形式贴出来: 第一种: 第二种: 然后是容斥的... -
【CF1053E】Euler tour
2019-07-10 10:27:00大概意思是你有一棵树,然而你并不知道这棵树是啥。给你一个确定了一些位置的欧拉序(就是\(ST\)表求\(LCA\)的那个序列),问你是否存在一个合法的序列,如果可以构造出一个。 题解 首先我们一定能够确定的是以下... -
新年计划!
2011-01-18 20:44:00新年了,一直想自己新的一年目标应该怎么定。这几天下来,终于,初步定了下来,我要翻译一些技术手册...另外一方面,网上的中文技术文章,大概意思都是对的,但重复率大不说,也总是出现这样那样的错误。 ... -
PC/UVa 题号:110401/10041 Vito's Family
2012-02-24 11:27:12大概意思可以描述为 求道到一条直线上n个点的距离和的最短距离。本题的重点在排序。这道题初中证明过利用绝对值的性质,当一个点在线段两端点之间时,这个点到两端点的距离之和最短,当线段上游n个点,如果为奇数个... -
uva540
2012-07-14 12:06:00题目的意思大概就是现在让你做一个数据结构,具体的应该是一个队列,有一堆元素,这堆元素拥有两个特性,一是它的值,二是它所在的team值。这个队列满足以下的一些性质(操作)。 ENQUEUE(k) : 将元素k插入队列,... -
冲刺阶段:霍夫曼树查找
2018-06-28 14:47:28这个题目是看到别人说的,也没有oj判断,题目大概是这个意思:比如2 :1111 :03: 110构造哈夫曼树,给你一串编码 比如 1111100 让你找出编码所代表的原文,然后再输出哈夫曼树中每一个结点被访问的次数。... -
卷积神经网络
2021-01-07 16:11:50提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。 提示:以下是本篇文章正文内容,下面... -
了解php面向对象
2014-06-09 23:54:00php 三大特性:封装、继承、多态,一直以来只知道其字,却不大了解其意思和具体使用,只是对继承有大概的了解,优点是代码的重用性,oop概念,记得有一次我去面试,人家问我什么是oop,然后我答了很多什么继承、封装... -
【SHOI2017】【线段树】【均摊分析】【广义欧拉定理】相逢是问候
2019-09-22 21:45:22这个需要维护的东西十分鬼畜,大概是这个意思: cccccc...cai c^{c^{c^{c^{c^{c^{...^{c^{a_{i}}}}}}}}} cccccc...cai 考虑区间修改。我们发现,这个玩意儿并没有办法打lazy标记,所以线段树区间修改就凉凉了。... -
大概的意思有两点: a. ThreadLocal提供了一种访问某个变量的特殊方式:访问到的变量属于当前线程,即保证每个线程的变量不一样,而同一个线程在任何地方拿到的变量都是一致的,这就是所谓的线程隔离。 b. 如果要...
-
windows实用dos命令大全
2010-12-10 21:27:354.使用说明:该命令可以一步就将目录及其下的所有文件、子目录、更下层的子目录一并删除,而且不管文件的属性为隐藏、系统或只读,只要该文件位于删除的目录之下,DELTREE都一视同仁,照删不误。使用时务必小心!!... -
mouseenter与mouseover为何这般纠缠不清?
2020-12-08 23:50:18可见mouseover事件因其具有冒泡的性质,在子元素内移动的时候,频繁被触发,如果我们不希望如此,可以使用mouseenter事件代替之,但是早期只有ie浏览器支持该事件,虽然现在... -
[老饭骨] 茯苓糕 - https://youtu.be/oIMCCi78aa4
2020-12-09 10:04:26翻译主要意思即可,不要超过 100 个字符) 【国宴大师•茯苓糕】软糯香甜满口桂花香!传承百年的传统糕点茯苓糕,好吃又养颜!大爷二伯大问答|老饭骨 简介 小友们好,今天老饭...
-
自动化测试Python3+Selenium3+Unittest
-
linux基础入门和项目实战部署系列课程
-
用Go语言来写区块链(一)
-
Galera 高可用 MySQL 集群(PXC v5.7+Hapro)
-
积分排行榜代码.zip
-
libFuzzer视频教程
-
snake_stm32.zip
-
vc截获并过滤某个程序中的某个消息的程序源代码。比如通过过滤WM_TIMER消息来消除某些未注册程序的运行时间限制.zip
-
【ssm项目源码】在线答题系统.zip
-
企业自建应用使用钉钉账号密码登录(钉钉第三方登录)
-
SDL2+Opengles2.0使用,SDL_GL_SwapWindow()立即刷新问题
-
vc替换开始菜单的程序源代码.visual c++
-
vue小例子-购物车页面
-
1.8jdk的百度云
-
Windows系统管理
-
【C】【插入排序】使用插入排序对少量数进行简单排序
-
14-Spring事务原理
-
element upload上传组件 如何去掉删除按钮
-
龙芯生态应用开发基础:C语言精要
-
项目管理工具与方法