【筆試代碼題記錄】20190728拼多多

【第一題】

給定數組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)
           

【第二題】

給定一個字元串數組，所有字元均為大寫字母，請問，給定的字元串數組是否能通過更換數組中元素的順序，進而首尾相連，形成一個環，環上相鄰字元串首尾銜接的字元相同。

例如：

輸入： 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))
           

【第三題】執行任務的最短時間

一共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