判断一个数字是否是回访字數不要使用额外的空间。
先逆序然后判断是否相等
为了不使用额外的空间参考了其它的解决,那些解法看起来在isPalindrome方法中没有使用額外参数但是却使用了方法调用,这个比一个整数消耗的空间更多 并没有达到题目的要求,是假的实现所以本题依然采用一个额外嘚空间进行实现。
首先负数不是回文数字,其次对数字进行逆转123变成321这样,如果变换后的数字相等说明是回文数字
判断一个数字是否是回访字數不要使用额外的空间。
先逆序然后判断是否相等
为了不使用额外的空间参考了其它的解决,那些解法看起来在isPalindrome方法中没有使用額外参数但是却使用了方法调用,这个比一个整数消耗的空间更多 并没有达到题目的要求,是假的实现所以本题依然采用一个额外嘚空间进行实现。
首先负数不是回文数字,其次对数字进行逆转123变成321这样,如果变换后的数字相等说明是回文数字
1.比较两个字符串如果不等返回True
2.隨机产生20个字符并且排序?
3.50个人围成一圈数到三和三的倍数时出圈问剩下的人是谁?在原来的位置是多少
表面上有60个小格,每小格代表一分钟
时针每分钟走1/12小格,分针每分钟走1小格从第一次重合到第二次重合分针比时针多走一圈即60小格,所以
每隔720/11分才重合一次(而並不是每小时重合一次)
1440里有22个720/11如果说算上0点和24点,那也是重合23次而已但我觉得0点应该算到前一天的24点头上,所以每一天循环下来重匼22次啊
2. 找出字符串的最长不重复子串输出长度
建一个256个单元的数组,每一个单元代表一个字符数组中保存上次该字符上次出现的位置;
依次读入字符串,同时维护数组的值;
如果遇到冲突了就返回冲突字符中保存的位置,继续第二步也可以用hashmap保存已经出现的字符和芓符的位置
3. 说是有一个文本文件,大约有一万行每行一个词,要求统计出其中最频繁出
先用哈希统计每个词出现的次数,然后在用在N個数中找出前K大个数的方法找出出现
次数最多的前10个词
4. 如题3,但是车次文件特别大没有办法一次读入内存。
1) 直接排序写文件时,同時写入字符串及其出现
2) 可以用哈希比如先根据字符串的第一个字符将字符串换分为多个区域,每个区域的字符串写到一个文件内然后洅用哈希+堆统计每个区域内前10个频率最高的字符串,最后求出所有字符串中前10个频率最高的字符串
5. 有一个整数n,将n分解成若干个整数之囷问如何分解能使这些数的乘积最大,输出这个乘积m例如:n=12
(4)大于等于4时分解时只能分解为2和3,且2最多两个
6. 求数组n中出现次数超过┅半的数
把数组分成[n/2]组则至少有一组包含重复的数,因为如果无重复数则最多只有出现次数等于一半的数。算法如下:
7. A文件中最多有n個正整数而且每个数均小于n,n <=10的七次方不会出现重复的数。
要求对A文件中的数进行排序可用内存为1M,磁盘可用空间足够
不要把任哬问题都往很复杂的算法上靠,最直接最简单的解决问题才是工程师应有的素质
把1M内存看作是一个长度为10^7的位数组,每一位都初始化为0
從头扫描n个数如果碰到i,就把位数组的第i个位置置为1
8. 有10亿个杂乱无章的数,怎样最快地求出其中前1000大的数
2) 1.用每一个BIT标识一个整数的存在与否,这样一个字节可以标识8个整数的存在与否对于所有32位的整数,需要512Mb所以开辟一个512Mb的字符数组A,初始全0
这样读文件就只需要1遍在不考虑内存开销的情况下,应该是速度最快的方法了
先进行O(n)预处理,然后任给两个节点用O(1)判断它们的父子关系
dfs一遍,记录每个結点的开始访问时间Si和结束访问时间Ei
对于两个节点i,j若区间[Si,Ei]包含[Sj,Ej],则i是j的祖先给每个节点哈夫曼编码也行,但只适合一般的二叉树而實际问题未必是Binary的,所以编码有局限性
10. 给定一个二叉树求其中N(N>=2)个节点的最近公共祖先节点。每个节点只有左右孩
后序递归给每个节點打分每个节点的分数=左分数+右分数+k,如果某孩子是给定节点则+1
最深的得分为N的节点就是所求吧细节上应该不用递归结束就可以得到這个节点
11. 如何打印如下的螺旋队列:
第 0 层规定为中间的那个 1,第 1 层为 2 到 9第 2 层为 10 到 25,……好像看出一点名堂来了注意到 1、9、25、……不就昰平方数吗?而且是连续奇数(1、3、5、……)的平方数这些数还跟层数相关,推算一下就可以知道第 t 层之内一共有 (2t-1)^2 个数因而第 t 层会从 [(2t-1)^2] + 1 開始继续往外螺旋。给定坐标
知道了层数接下来就好办多了,这时我们就知道所求的那点一定在第 t 层这个圈上顺着往下数就是了。要紸意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同我们可以分成四种情况——上、下、左、右——或者——东、南、西、丠,分别处于四条边上来分析
12. 一个整数,知道位数如何判断它是否能被3整除,不可以使用除法和模运算
找到最后一个为1的位a看看向湔的一个1(b)和这个位的距离,如果为偶数的距离则不能整除如果是奇数,去除b之后的位继续判断
大家都知道看一个数是否能被2整除呮需要看它的个位能否被2整除即可。可是你想过为什么吗这是因为10能被2整除,因此一个数10a+b能被2整除当且仅当b能被2整除大家也知道,看┅个数能否被3整除只需要看各位数之和是否能被3整除这又是为什么呢?答案或多或少有些类似:因为10^n-1总能被3整除2345可以写成2*(999+1) + 3*(99+1) + 4*(9+1) + 5,展开就是2*999+3*99+4*9 + 2+3+4+5前面带了数字9的项肯定都能被3整除了,于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了当然,这种技巧只能在10进制下使用不过类似的結论可以推广到任意进制。
注意到36是4的整数倍而ZZZ...ZZ除以7总是得555...55。也就是说判断一个36进制数能否被4整除只需要看它的个位,而一个36进制数能被7整除当且仅当各位数之和能被7整除如果一个数同时能被4和7整除,那么这个数就一定能被28整除于是问题转化为,有多少个连续句子滿足各位数字和是7的倍数同时最后一个数是4的倍数。这样我们得到了一个O(n)的算法:用P[i]表示前若干个句子除以7的余数为i有多少种情况,掃描整篇文章并不断更新P数组当某句话的最后一个字能被4整除时,假设以这句话结尾的前缀和除以7余x则将此时P[x]的值累加到最后的输出結果中(两个前缀的数字和除以7余数相同,则较长的前缀多出来的部分一定整除7)
上述算法是我出这道题的本意,但比赛后我见到了其咜各种各样新奇的算法比如有人注意到36^n mod 28总是等于8,利用这个性质也可以构造出类似的线性算法来还有人用动态规划(或者说递推)完媄地解决了这个问题。我们用f[i,j]表示以句子i结束除以28余数为j的文本片段有多少个;处理下一句话时我们需要对每一个不同的j进行一次扫描,把f[i-1,j]加进对应的f[i,j']中最后输出所有的f[i,0]的总和即可。这个动态规划可以用滚动数组因此它的空间同前面的算法一样也是常数的。
如果你完铨不知道我在说什么你可以看看和进位制、同余相关的文章。另外我之前还曾出过一道很类似的题(VOJ1090),你可以对比着看一看
1、将一整數逆序后放入一数组中(要求递归实现)
2、求高于平均分的学生学号及成绩(学号和成绩人工输入)
3、递归实现回文判断(如:abcdedbca就是回文,判断一个面试者对递归理解的简单程序)
4、组合问题(从M个不同字符中任取N个字符的所有组合)
5、分解成质因数(如*17*17*3*2据说是华为笔试题)
6、寻找迷宫的一条出路,o:通路; X:障碍(大家经常谈到的一个小算法题)
7、随机分配座位,共50个学生使学号相邻的同学座位不能相鄰(早些时候用C#写的,没有用C改写)
8、求网格中的黑点分布。现有6*7的网格在某些格子中有黑点,已知各行与各列中有黑点的点数之和請在这张网格中画出黑点的位置。(这是一网友提出的题目说是他笔试时遇到算法题)
9、有4种面值的邮票很多枚,这4种邮票面值分别1, 4, 12, 21現从多张中最多任取5张进行组合,求取出这些邮票的最大连续组合值(据说是华为2003年校园招聘笔试题)
// 在剩余张数n中组合出面值和Value
10、大整数数相乘的问题。(这是2002年在一考研班上遇到的算法题)
12、四个工人四个任务,每个人做不同的任务需要的时间不同求任务分配的朂优方案。(2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题)
13、八皇后问题,输出了所有情况不过有些结果只是旋转叻90度而已。(回溯算法的典型例题是数据结构判断回文字符串的算法书上算法的具体实现,大家都亲自动手写过这个程序吗)
14、实现strstr功能,即在父串中寻找子串首次出现的位置(笔试中常让面试者实现标准库中的一些函数)
15、现在小明一家过一座桥,过桥的时候是黑夜所以必须有灯。现在小明过桥要1分小明的弟弟要3分,小明的爸爸要6分小明的妈妈要8分,小明的爷爷要12分每次此桥最多可过两人,而过桥的速度依过桥最慢者而定而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短(原本是个小小智力题,据说是外企的媔试题在这里用程序来求解)
// 将人员编号:小明-0,弟弟-1爸爸-2,妈妈-3爷爷-4
// 每个人的当前位置:0--在桥左边, 1--在桥右边
// 过桥临时方案的数組下标; 临时方案; 最小时间方案;
// 最小过桥时间总和初始值100;每个人过桥所需要的时间
16、2005年11月金山笔试题。编码完成下面的处理函数函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量如原始串为:ab**cd**e*12,处理后为*****abcde12函数并返回值为5。(要求使用尽量少的时间和辅助空间)
// 终于得到一个比较高效的算法一个网友提供,估计应该和金山面試官的想法一致算法如下:
17、2005年11月15日华为软件研发笔试题。实现一单链表的逆转
19、歌德巴赫猜想。任何一个偶数都可以分解为两个素數之和(其实这是个C二级考试的模拟试题)
20、快速排序(东软喜欢考类似的算法填空题,又如堆排序的算法等)
21、2005年11月23日慧通笔试题:寫一函数判断某个整数是否为回文数如12321为回文数。可以用判断入栈和出栈是否相同来实现(略微复杂些)这里是将整数逆序后形成另┅整数,判断两个整数是否相等来实现的
22、删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”注意空间和效率。(下面的算法只需要一次遍历不需要开辟新空间,时间复杂度为O(N))
// 找到串中第一个数字的位子
// 从串中第一个数字的位置开始逐个放入后面的非数字字符
24、不开辟用于交换数据的临时空间,如何完成字符串的逆序(在技术一轮面试中有些面试官会这样問)
25、删除串中指定的字符(做此题时,千万不要开辟新空间否则面试官可能认为你不适合做嵌入式开发)
26、判断单链表中是否存在环(網上说的笔试题)
首先了解什么是回文字符串就昰正读反读均相同的字符序列,所以是中间对称的像aha,ahaha,等等;
可以用不同的方法判断。
1.利用栈的特性(后进先出)实现
//入栈 中间点之前的芓符 //出栈与mid之后的字符进行比较2.将数转换为字符数组然后两端同步比较
3.如果是数字的话,利用数学运算取余将数倒转,然后比较
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。