drawbridge画桥oa 60min最新版跪经

replyreload += ‘’,’’ + 4369567;刚刚收到画桥发的oa 马上就做了 看了很多地里的本来以为题目没多大变化 可是一做发现是新题
60min 两题版

第一题
给一串string 问每个string最少改动几次才能使得没有相邻的两个字母一样
比如 abb —> aba 只用把b改成a就行 算1次
或者 abbb 只用改中间的b就行 变成abxb 也算一次
不用return怎么改 只用记录次数

第二题 global maximum

大坑啊
是在一个不重复的integer list中找到所有size为m的组合 然后每个组合中挑出所有pair 比较绝对值
然后在每个组合的绝对值中 找最小差值
然后放在所有组合中 比较一个最大值 return这个最大值. 1point3acres
比如 {1,2,3,5,7} m = 4
==> {1,2,3,7} {1,2,3,5} {1,2,5,7} {1,3,5,7} {2,3,5,7}
在每一对中找出 最小的diff
分别是 1 1 1 2 1 所以最后return 2

lz本来用dfs找combination做看起来很轻松 但是最后几个test一直time limit 真的很绝望

估计是挂了 发出来攒攒人品希望能有offer

听说回复看第二题。?

第一题不问具体操作只问次数显然dp。
f = Math.min(1 + f[i - 1], 1 + f[i - 2]) // 改当前字母, 或改前一个字母

补充内容 (2018-8-16 12:32):
当然, 字母不一样f = f[i - 1];

第二题不用dfs求出所有组合吧应该?个人思路目前是list排个序,然后比如m为4,就比较第一和倒数第三个,然后第二个和倒数第二个,第三个和倒数第一个,这几个数中最大的就是了

兄弟在哪申请的new grad职位啊

第一题要啥DP??? O(1)空间就够了吧

请问global maximum具体是什么样子的呀