一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3242|回复: 29
收起左侧

刚做完狗家OA,发现题目有变

[复制链接] |试试Instant~ |关注本帖
111180611 发表于 2016-9-24 03:20:56 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Google - Other - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一题,给一个数字,把两个相邻数换成这两个数的平均数(round up),返回替换后的最大值
比如612215应该返回62215. 1point 3acres 璁哄潧
一开始以为找升序就好了,结果最后检查发现bug 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
比如62215按照升序替换应该返回6223但是突然发现62215替换21返回6225 > 6223当时就懵了
然后看了一会没想出来, 就用了最笨的方法做了
现在想想应该是按照平均数升序或平找
看看大家什么想法 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感觉OA要跪了
翱翔天空的蜗牛 发表于 2016-10-7 04:27:50 | 显示全部楼层
我没读懂楼主的题目意思。。。麻烦大家说下题目是啥意思吗?
回复 支持 2 反对 0

使用道具 举报

XavierWangXY 发表于 2016-9-24 13:55:22 | 显示全部楼层
应该是从前往后扫第一次遇到两个数字的平均数的round up比这两个数的前一个大或者平  注意算平均数的时候round up     ((x+y)-1)/2 + 1   

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 111180611 发表于 2016-9-24 03:24:02 | 显示全部楼层
平均数升序也不对
回复 支持 反对

使用道具 举报

UpDownDOTA 发表于 2016-9-24 04:00:48 | 显示全部楼层
反正暴力枚举也是O(n)。。所以没关系的吧
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-9-24 04:28:36 | 显示全部楼层
UpDownDOTA 发表于 2016-9-24 04:00
反正暴力枚举也是O(n)。。所以没关系的吧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
一个题上耽误了好久
回复 支持 反对

使用道具 举报

Sai_L 发表于 2016-9-24 04:56:55 | 显示全部楼层
楼主攒rp~ 下面是一点想法
升序应该是第一个升序,bug是特殊情况,要考虑升序前是不是降序且比谷底大一,然后round up取前边
回复 支持 反对

使用道具 举报

pigeyes 发表于 2016-9-24 07:29:19 | 显示全部楼层
111180611 发表于 2016-9-24 03:24
平均数升序也不对

樓主有反例嗎?
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-9-24 08:05:12 | 显示全部楼层
pigeyes 发表于 2016-9-24 07:29. from: 1point3acres.com/bbs
樓主有反例嗎?

62215 and 22222228
回复 支持 反对

使用道具 举报

xzhuge 发表于 2016-9-24 22:25:18 | 显示全部楼层
XavierWangXY 发表于 2016-9-24 13:55
应该是从前往后扫第一次遇到两个数字的平均数的round up比这两个数的前一个大或者平  注意算平均数的时候ro ...

651812 这种情况呢? 61812 < 63812 < 65512
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-25 00:55:30 | 显示全部楼层
楼主你看这个行不:第一次遇到"少多"的情况下,比如325就分别求32 和 25得出的结果并且返回,如果25以前没有数字就直接求25平均值,如果走到最后一直都是递减就求最后两个数字的平均值
回复 支持 反对

使用道具 举报

chenqidi 发表于 2016-9-25 01:30:05 | 显示全部楼层
XavierWangXY 发表于 2016-9-24 13:55
应该是从前往后扫第一次遇到两个数字的平均数的round up比这两个数的前一个大或者平  注意算平均数的时候ro ...
. from: 1point3acres.com/bbs
赞同。。。。
回复 支持 反对

使用道具 举报

chenqidi 发表于 2016-9-25 02:16:23 | 显示全部楼层
不过这题需要debug几次才能做出来。这个帖子里的test case我的算法都通过了。
回复 支持 反对

使用道具 举报

chenqidi 发表于 2016-9-25 02:17:40 | 显示全部楼层
还有其他test cases吗? 如果都过了 我就把算法贴出来
回复 支持 反对

使用道具 举报

regist1234 发表于 2016-9-26 01:29:40 | 显示全部楼层
62215替换平均后最小的不应该是4215吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-9-26 01:31):
哦是找最大啊!我看错题了。
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-9-26 13:01:49 | 显示全部楼层
chenqidi 发表于 2016-9-25 02:16
不过这题需要debug几次才能做出来。这个帖子里的test case我的算法都通过了。

你怎么想的?
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-27 09:38:50 | 显示全部楼层
从左往右走,当遇到a[i] < a[i + 1]时(升序),看pre = a[i - 1] 和a[i] 的平均值是否等于a[i - 1] ,即,a[i] == a[i - 1] || a[i] == a[i - 1] - 1,的时候,我们直接删a[i], 否则取a[i] 和 a[i + 1] 的平均值。
1. a[i] >= a[i + 1] 不做事
2. a[i] < a[i + 1] 分2个case:
       1. a[i] == a[i - 1] || a[i] + 1 = a[i - 1] : .......
      2. else :  ......... more info on 1point3acres.com
应该是对的,目前testcase都过了
回复 支持 反对

使用道具 举报

星辰亿万 发表于 2016-9-27 10:12:04 | 显示全部楼层
lzlmike 发表于 2016-9-27 09:38
从左往右走,当遇到a < a时(升序),看pre = a 和a 的平均值是否等于a ,即,a == a || a == a - 1,的时候 ...
. 1point3acres.com/bbs
如果全部都是降序的你怎么处理?
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-9-27 10:46:12 | 显示全部楼层
我去。。只能希望OA别卡人了。。。。我是直接按照升序做的。。LZ的test case真是严谨
回复 支持 反对

使用道具 举报

lzlmike 发表于 2016-9-27 10:54:32 | 显示全部楼层
星辰亿万 发表于 2016-9-27 10:12
如果全部都是降序的你怎么处理?

最后没找到,就把最后2位处理就好了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表