2018华为线上题 |
您所在的位置：网站首页 › 华为考试123连线题 › 2018华为线上题 |
|
昨天晚上做的。。。不知道怎么那个时候脑子有毒。。。好多东西没想出来。。。 就三道线上题 1 比如字符串 abccba123，它这里面最大的相对称字符串 abccba，长度为6，再举个例子， 12333321，整个字符串都是，长度为8. 你要做的就是求整个字符串里，最长的对称字符串长度。 昨晚脑子有点懵。。大概是和美团的题不一样的风格。。。。第一题那时候只知道暴力法。果断超时。。跑路了才发现新的思路 那就是直接倒着遍历 比如 abcddcba,第一次，max=len（str）， 第一次N=1，直接查询整个字符串是否满足 满足则break，长度肯定是最长 第二次N=2，遍历0-max-1,1到max 以此类推。这样子能够最少时间的遍历字符串，找到最大长度并跳出。 推荐这个大佬的博客 http://blog.163.com/xie_wenbin613/blog/static/175489095201242611557464/ 啊啊啊啊啊。。为什么脑子当时懵逼了。。。。。 第二题是字符串处理。。。不想做就跑路了
第三题是背包算法。。。当时不好意思去网上百度。。于是跑路了，然后今天恶补了一下。 找到了一个python版本，网址忘了 = =，谢谢那位大佬的代码，基本是搞明白了。 def bag(n, c, w, v): res = [[-1 for j in range(c + 1)] for i in range(n + 1)] print(len(res),'\n') for j in range(c + 1): res[0][j] = 0 print(res) ##n是物品书 ##c是重量上线 for i in range(1, n + 1): for j in range(1, c + 1): res[i][j] = res[i - 1][j] ###思想，N个物品，所以会有N轮的选择 ###J是遍历，对当前剩余空间，拿还是不拿，决定于 空间足够且价值大于 ''' i指的是 第I件物品，J指的是当前的背包空间是J 这个时候要判断 { 1 如何W（i）的重量大于J： 没有空间了，那就只能不拿 2 如果空间》= 那就可以拿或者不拿 { 如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。 如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1） 究竟是拿还是不拿，自然是比较这两种情况那种价值最大。 } } ''' ###如果 不拿的价值 小于 丢了上个物品，节约出来的空间的价值+拿了新物品的价值 if j >= w[i - 1] and res[i][j] < res[i - 1][j - w[i - 1]] + v[i - 1]: #如果空间大于，则 上一轮，未放入时候 【i-1】【j-w（i-1）】+ value #且 res[i-1][j]的价值 小于新放进来，即拿掉 i-1件的价值 res[i][j] = res[i - 1][j - w[i - 1]] + v[i - 1] return res def show(n, c, w, res): ### ''' n是数目 c是重量上限 ''' print('最大价值为:', res[n][c]) x = [False for i in range(n)] j = c for i in range(1, n + 1): if res[i][j] > res[i - 1][j]: ###如果下一轮 i 的value 大于 这一轮 i-1 ###说明应该是 这一轮的物品被放入了 x[i - 1] = True j -= w[i - 1] print('选择的物品为:') for i in range(n): if x[i]: print('第', i, '个,', end='') print('') n = 5 #设置物品数目 c = 10 #设置重量上限数 w = [2, 2, 6, 5, 4]#重量 v = [6, 3, 5, 4, 6]#价值 res = bag(n, c, w, v) show(n, c, w, res)
华为公司我还是很喜欢的，可惜这次就凉凉了，希望能找到别的公司实习2333.强网杯最后居然跑到了157名了嚯嚯哈哈，可惜还只是一个比赛参与奖，希望自己能够更加厉害吧
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |