当前位置:   article > 正文

【笔试代码题记录】20190728拼多多_给定两个只包含数字的数组a, b, 调整数组a里面数字的顺序,使得尽可能多的

给定两个只包含数字的数组a, b, 调整数组a里面数字的顺序,使得尽可能多的

【第一题】
给定数组A和B,数组A是几乎严格升序的,几乎的定义是只需改变其中一个数,即可满足完全升序序列。
要求:从A中找到这个数字,并从B中选取一个数字将其替换,使得数组A是严格升序的。(不允许相邻两个为相同的数)。请找出B中满足要求的最大数字,并输出最终有序的数组。如果不存在就输出NO。

我的思路(通过率75%):遍历A数组,找到a[i] >= a[i-1]的位置,然后记录a[i-1]和a[i+1]的值,在数组B中查找是否存在该范围内的值。

看到的一个100%通过率思路:在找到a[i] >= a[i+1]的位置后,先看看能不能换掉i+1位置的数,让数组a有序(因为要找b中最大的数),如果不行,就看能不能换掉i位置的数让数组a有序,如果还是不行就输出NO。

对比区别:比如A数组为[1,20, 5, 40], 当找到5这个数字之后,我的做法是直接把5替换掉,也就是在B中找[21,39]范围内的数,找不到直接返回No了。但是参考的解法里面,先尝试换掉5(因为先换后面的能保证整个数组尽可能的大),也就是说只要B数组中存在[21, 39]的数字,都是可以的;如果换掉5不可行,再尝试换掉20,在B中找[1,4]范围内的数.(思路很巧妙)

def func(nums1, nums2):
    if not nums1 or not nums2:
        print('NO')
    index = 0
    min_value, max_value = float('-inf'), float('inf')
    flag1 = False # 替换掉波谷的那个数(最小的数)
    flag2 = False  # 替换掉波谷前面那个大的数
    for i in range(1, len(nums1)):
        if nums1[i] < nums1[i - 1]:
            min_value = nums1[i - 1]
            if i + 1 < len(nums1):
                max_value = nums1[i + 1]
            index = i

    value1, value2 = float('-inf'), float('-inf')
    for i in range(len(nums2)):
        if nums2[i] > min_value and nums2[i] < max_value:
            value = max(value, nums2[i])
            flag1 = True
        elif index == 1 and nums2[i] < nums1[index]: # 尝试换index前面那个大的数
            value2 = max(value2, nums2[i])
            flag2 = True
        elif index >= 2 and nums2[i] > nums1[index - 2] and nums2[i] < nums1[index]:
            value2 = max(value2, nums2[i])
            flag2 = True
    if flag1 == True:
        res = nums1
        res[index] = value1
        print(" ".join(str(i) for i in res))
    elif flag2 == True:
        res = nums1
        res[index - 1] = value2
        print(" ".join(str(i) for i in res))
    else: # 没找到min_value 和max_value之间的数
        print('NO')

nums1 = list(map(int, input().split()))
nums2 = list(map(int, input().split()))
func(nums1, nums2)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

【第二题】
给定一个字符串数组,所有字符均为大写字母,请问,给定的字符串数组是否能通过更换数组中元素的顺序,从而首尾相连,形成一个环,环上相邻字符串首尾衔接的字符相同。
例如:
输入: CART TIGER RPC 输出:True
输入:CART RPC 输出:False(T和R不相同)

我的解法(90%):使用start和end记录第一个字符串的首尾字符,然后从字符串。

def func(string):
    if not len(string):
        return False
    start = string[0][0]
    end = string[0][-1]
    for i in range(1, len(string)):
        if string[i][0] == end:
            end = string[i][-1]
        else:
            return False
    if string[-1][-1] == start:
        return True
    return False
string = list(map(str,input().split()))
string = ["CAT","TIGER","RPC"]
print(func(string))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

【第三题】执行任务的最短时间
一共N个任务,每个任务需要Pi的时间完成,同时,任务间存在依赖关系(某些任务必须在其他任务完成后才可以才可以进行)。
要求:安排完成任务的顺序,使得平均等待时长最短。

输入描述:
第一行包含两个正整数N,M,分别表示任务数量以及M个任务的依赖关系。
第二行包含N个正整数,第i个数表示完成第i个任务所需时间。
接下来的M行,每行表示一个任务依赖关系,每行包含2个整数Ai和Bi,表示第Bi个任务依赖于第Ai个任务。

输出描述:
输出一行,包含N个整数,两两之间用空格符分隔,代表可行方案的顺序。

牛客上一个大佬AC的思路: 主要思想是可以完成的任务中优先完成时间短的(保证平均等待短),这部分用优先队列就可以(堆)。然后依赖关系用计个数就可以了,新的加到队列中
自己还不会。

【第四题】积木问题
N个积木,每个的长度为Li,重量为Wi,对于每块积木,其上方的积木重量之和必须小于其自重的7倍。问,最高可以搭多高的金字塔?
数据范围: 1 <= N <= 100, 1 <= Li <= 1000, 1 <= Wi <= 1000
输入:
第一行为一个整数N,表示积木数量
第二行包含N个正整数,表示每个积木的长度Li
第三行包含N个正整数,表示每个积木的重量Wi
输出: 积木的最大高度

https://www.nowcoder.com/discuss/212358

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/780551
推荐阅读
相关标签
  

闽ICP备14008679号