| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 2597 人关注过本帖, 3 人收藏
标题:常见水题,若有可能,会陆续补充
只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:490
帖 子:8758
专家分:52412
注 册:2011-1-18
结帖率:91.67%
收藏(3)
 问题点数:0 回复次数:8 
常见水题,若有可能,会陆续补充
题目1:找出缺少的一个数(极易)
一个长度为 n 的整数数组,其中每个元素都大于等于0且小于等于n,且无重复,请找出“大于等于0且小于等于n”但不在此数组中的那一个数。
例如给出 { 5, 0, 2, 1, 4 },则输出 3
 
题目2:找出缺少的两个数(中等)
一个长度为 n 的整数数组,其中每个元素都大于等于0且小于等于n+1,且无重复,请找出“大于等于0且小于等于n+1”但不在此数组中的那两个数。
例如给出 { 5, 0, 2, 1 },则输出 3, 4
 
题目3:找出重复的一个数(极难)
一个长度为 n 的整数数组,其中每个元素都大于等于0且小于等于n-1,有一个数重复出现了两次或更多次,请找出此数。
例如给出 { 1, 0, 4, 3, 4, 4 },则输出 4
原题:https://
 
题目4:找不重复出现的数(容易)
一个长度为 2*k+1 的整数数组,其中k个整数出现了2次,1个整数出现了1次,找出出现1次的那个整数。
例如给出 { 9, 5, 5, 9, 7, 1, 1 },则输出 7
 
题目5:找重复两次的数(中等)
一个长度为 4*k+2 的整数数组,其中k个整数出现了4次,1个整数出现了2次,找出出现2次的那个整数。
例如给出 { 9, 5, 5, 9, 9, 5, 5, 9, 7, 1, 7, 1, 1, 1 },则输出 7
 
一个阶乘数的末尾有几个0? https://bbs.bccn.net/thread-469357-1-1.html

求出第N个汉明数 https://bbs.bccn.net/thread-469358-1-1.html

----------------------------------------------------------------------------
大家有类似“问题描述起来简单,但需要巧妙算法”的题目,可以发给我,我汇总上来

[此贴子已经被作者于2016-10-8 09:12编辑过]

搜索更多相关主题的帖子: 元素 
2016-09-29 10:40
linlulu001
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:20
帖 子:944
专家分:4047
注 册:2016-4-13
收藏
得分:0 

全部都是用同一种算法来解…………

[此贴子已经被作者于2016-9-29 10:57编辑过]

2016-09-29 10:55
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
我以为水题是指非常容易、放水的居然还有人拿来问的题
2016-09-29 11:02
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:490
帖 子:8758
专家分:52412
注 册:2011-1-18
收藏
得分:0 
以下是引用linlulu001在2016-9-29 10:55:31的发言:

 
全部都是用同一种算法来解…………
肯定得用最牛逼(效率最高、耗费资源最少)的方法呀,否则算法就没存在的必要了
2016-09-29 11:48
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:490
帖 子:8758
专家分:52412
注 册:2011-1-18
收藏
得分:0 
以下是引用xzlxzlxzl在2016-9-29 11:02:51的发言:

 我以为水题是指非常容易、放水的居然还有人拿来问的题
水题就是在竞赛中或面试中,经常会被问到,或在其它算法中间某一步会遇到的算法题。
2016-09-29 11:50
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
1.0到N累加求和 - 遍历数组求和 = 少掉的那个元素
2.1到N求阶乘/数组中非零元素的累积=x*y,1到N累加求和-数组中元素的累加求和=x+y ,解二元一次方程组
------------------------------
3. 遍历数组求和 - 0到N累加求和 = 多出的元素(和1有区别?)--->错误,待修订
去了那个网址看了原题,他们指出限制算法复杂度在O(N^2)以内。如果这样的话可以先用O(NlogN)的复杂度对数组执行非降序排序。然后用O(N)的复杂度遍历找到到那个重复的元素Key(已知所有非Key的元素排序过后所在位置必然等于它本身)
如:{1,0,1,1,4}排序后为{0,1,1,1,4}下标为2,3两处的元素和下标不一致,,所以1是我们要找的Key。  (然而这个方法一点都不巧妙,只能勉强实现而已)

----------------
4.异或  (a^=b^=a 最后结果是b)
5.位运算 把9解析为1001,7解析为0111...以此类堆,把所有数字转化为二进制,每个位对应求和(例本题运算结果为4 6 2 14),然后模4,剩下(0 2 2 2)的再除于二(0 1 1 1),组合起来就是7了  (这个算法不好,一点也不简单因为当数字比较大的时候二进制数会拉很长的。。。而且,我本人并没有写过涉及位运算的程序<< 2  >>2 头晕)  求更优解~~

-------------
刷刷水题,找回自信!(楼主更新,我也更新)




[此贴子已经被作者于2016-10-5 19:23编辑过]


φ(゜▽゜*)♪
2016-09-29 19:59
linlulu001
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:20
帖 子:944
专家分:4047
注 册:2016-4-13
收藏
得分:0 
回复 6楼 书生牛犊
先声明下,当时看到这个问题的时候是没有考虑程序效率的。
第1,2,3题的数组有相同的条件一个长度为 n 的整数数组。用一个长度n+1(这里的题有的不是n+1)的数组并初始化0,对数组里整数出现的次数进行统计。
第4,5题相同的条件是k个整数。用长度k的线性表统计相应的整数以及出现的次数。

个人看来算一种算法。
如果在你看来这算两种算法那就算两种,哪怕是五种也行。
2016-09-29 21:12
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
回复 7楼 linlulu001
谢谢明白了

φ(゜▽゜*)♪
2016-09-29 21:25
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:490
帖 子:8758
专家分:52412
注 册:2011-1-18
收藏
得分:0 
以下是引用书生牛犊在2016-9-29 19:59:16的发言:
3. 遍历数组求和 - 0到N累加求和 = 多出的元素(和1有区别?)

题1中缺少一个数,题3中少一个并且重复了一个。
你算出来的是 重复元素减去缺少元素的值
{ 3, 1, 2, 1 } 你算出来的是 1-0
{ 3, 0, 2, 2 } 你算出来的是 2-1

不过这一道题目确实出错了,我改一下


[此贴子已经被作者于2016-9-30 08:14编辑过]

2016-09-29 23:49
快速回复:常见水题,若有可能,会陆续补充
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030450 second(s), 9 queries.
Copyright©2004-2023, BCCN.NET, All Rights Reserved