2019-09-06 22:17 已编辑华中科技大学算法工程师

关注

依图笔试, 求大佬指点

第一题, 交换数组递增 10%

'''
@Author: rayenwang
@LastEditTime: 2019-09-06 20:40:27
@Description: 
'''
N = int(input())
nums = [int(n) for n in input().split()]

# N = 5
# nums = [1, 5, 2, 4, 3]
result = 0
for i in range(N):
    if nums[i] == i + 1:
        continue
    index = nums[i] - 1
    nums[i], nums[index] = nums[index], nums[i]
    result += 1
print(result)

第二题, 粉碎我自己 AC

'''
@Author: rayenwang
@LastEditTime: 2019-09-06 20:01:39
@Description: 
'''


def fill(height, space, index, N):
    pre_sum = 0
    for i in range(index, N):
        if pre_sum + height[i] <= space:
            pre_sum += height[i]
        else:
            return False, i, space - pre_sum
    return True, i, space - pre_sum


import math
N, H, K = [int(n) for n in input().split()]
height = []
for _ in range(N):
    height.append(int(input()))
# N, H, K = [5, 5, 3]
# height = [5, 4, 3, 2, 1]

time = 0
finish, index, space = fill(height, H, 0, N)
if finish:
    print(math.ceil((H - space) / K))
else:
    while index < N:
        wait = math.ceil((height[index] - space) / K)
        time += wait
        space = min(H, space + wait * K)
        finish, index, space = fill(height, space, index, N)
        if finish:
            break
    print(time + math.ceil((H - space) / K))

第三题, 最大的K个节点之和 0%

'''
@Author: rayenwang
@LastEditTime: 2019-09-06 20:33:16
@Description: 
'''

N, K, S = [int(n) for n in input().split()]
path = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = [int(n) for n in input().split()]
    path[x].append(y)
value = [0]
for _ in range(N):
    value.append(int(input()))
result = [0 for _ in range(N + 1)]


def recur(root):
    if not root:
        return []
    temp = [root]
    for child in path[root]:
        temp = sorted(temp + recur(child), reverse=True)[:K]
    result[root] = sum(temp)
    return temp


recur(S)
for i in range(1, N + 1):
    print(result[i])

#笔试题目##依图科技#

全部评论

推荐最新楼层

华为招聘专员007

西安电子科技大学算法工程师

这是第三套卷子，楼主第一题题目应该没说数组是连续的吧，直接index = num[i]-1是不对吧

点赞回复分享

发布于 2019-09-06 21:33

维德北海

门头沟学院算法工程师

第一题这个思路对吗？AC了？

点赞回复分享

发布于 2019-09-07 14:38

wings and wind

清华大学 C++

# coding=utf-8 import sys if __name__ == "__main__": nhk = sys.stdin.readline().strip().split() n = int(nhk[0]) h = int(nhk[1]) # kerongna k = int(nhk[2]) # meimiao a = [] for _ in range(n): a.append(int(sys.stdin.readline().strip())) temp = 0 i = 0 res = 0 while i < n or temp > 0: if i < n and temp + a[i] <= h: temp += a[i] i += 1 temp = max(temp-k, 0) res += 1 print(res) 求问第二题，哪里没考虑全😭，按照粉碎的过程

点赞回复分享

发布于 2019-09-07 00:42

wings and wind

清华大学 C++

第一题没有说是1～N吧，数组是随意给的

点赞回复分享

发布于 2019-09-07 00:34

无艺青年

华中科技大学算法工程师

"""依图笔试第三套第一题，数组交换""" import sys n = int(input()) nums = list(map(int,input().split())) dicts = {} sort_nums = sorted(nums) for i in range(len(sort_nums)): dicts[sort_nums[i]] = i cnt = 0 flag = [False]*len(nums) for i in range(len(nums)): if not flag[i]: j = i while not flag[j]: flag[j] = True j = dicts[nums[j]] cnt += 1 print(len(nums) - cnt)

点赞回复分享

发布于 2019-09-06 23:21

找offer呀啊啊

上海科技大学算法工程师

交换数组 #!/usr/bin/env python # encoding: utf-8 import sys n = int(sys.stdin.readline().strip()) nums = map(int, sys.stdin.readline().strip().split(' ')) nums = [0] + nums Flag = True count = 0 while Flag: Flag = False for i in range(1, n+1): if nums[i] != i: # print nums[i] tmp = nums[nums[i]] nums[nums[i]] = nums[i] nums[i] = tmp count += 1 Flag = True print count

点赞回复分享

发布于 2019-09-06 21:54

莉柚

门头沟学院

第一道ac 第二道80% 后面两道怎么搞都是0 很绝望

点赞回复分享

发布于 2019-09-06 21:53

找offer呀啊啊

上海科技大学算法工程师

第二题粉碎50% 超时。。。。感觉复杂度不高啊 #!/usr/bin/env python # encoding: utf-8 import sys import math n, h, k = map(int, sys.stdin.readline().strip().split(' ')) a = [] for i in range(n): tmp = int(sys.stdin.readline().strip()) a.append(tmp) total_time = 0 tmp = a.pop(0) rem = h - tmp is_empty = False Flag = True while a: Flag = False # print a tmp = a.pop(0) while rem >= tmp: rem = rem - tmp if a: tmp = a.pop(0) else: is_empty = True break if is_empty: total_time += int(math.ceil((h-rem)*1./k)) else: tmp_time = int(math.ceil((tmp - rem)*1. / k)) # print rem, tmp # print tmp_time # break rem = min(tmp_time * k + rem, h) total_time += tmp_time a = [tmp] + a if Flag: total_time = int(math.ceil(tmp*1./k)) print total_time

点赞回复分享

发布于 2019-09-06 21:52

找offer呀啊啊

上海科技大学算法工程师

#!/usr/bin/env python # encoding: utf-8 import sys def sub_k(s): max_k = 0 for i in range(10, -1, -1): Flag = True for j in range(2**i-1, -1, -1): tmp = bin(j)[2:] for k in range(i-len(tmp)): tmp = '0'+tmp if tmp not in s: Flag = False break if Flag: max_k = i break return max_k n, m = map(int, sys.stdin.readline().strip().split(' ')) string = ['-1'] for i in range(n): tmp_str = sys.stdin.readline().strip() string.append(tmp_str) op = [[i] for i in range(n+1)] for i in range(m): left, right = map(int, sys.stdin.readline().strip().split(' ')) op.append(op[left]+op[right]) concat = [] for l in op[n+1:]: # tmp_str = string[left] + string[right] tmp_str = ''.join([string[i] for i in l]) string.append(tmp_str) # print tmp_str print sub_k(tmp_str) 第四题 80%

点赞回复分享

发布于 2019-09-06 21:50

炼金术士jm

北京航空航天大学算法工程师

第四题呢。。

点赞回复分享

发布于 2019-09-06 21:45

nnplus

复旦大学算法工程师

第三题并不是前面的就是父节点你需要自己判断；第一题：借鉴LeetCode的41题的思想https://leetcode.com/problems/first-missing-positive/ def change(arr): res=0 for i in range(len(arr)): while (arr[i]!=arr[arr[i]]): res+=1 arr[arr[i]],arr[i]=arr[i],arr[arr[i]] return res def p1(): n=int(input()) arr=[int(i) for i in input().split()] ind=sorted(range(n),key=lambda x:arr[x]) # 返回index print(change(ind))

点赞回复分享

发布于 2019-09-06 21:32

随缘笔试

杭州电子科技大学 C++

这是哪套题？

点赞回复分享

发布于 2019-09-06 21:25

ぴé菍伱~↘

西安电子科技大学 C++

第二题需要考虑什么边界么，只做了80%

点赞回复分享

发布于 2019-09-06 21:18