首页 > 08.30 中国电信 天翼云 算法笔试
头像
loyair
编辑于 2021-08-30 22:00
+ 关注

08.30 中国电信 天翼云 算法笔试

第一题:贪心算法里的重叠问题(原A 50%,修改后下面代码不知道能不能全A)
from typing import List


class Solution:
    def SumLength(self, lines: List[List[int]]) -> int:
        if not lines:
            return 0
        n = len(lines)
        if n == 1:
            return lines[0][1] - lines[0][0]
        lines.sort(key=lambda x: (x[0], x[1]))
        for i in range(1, n):
            if lines[i][0] < lines[i - 1][1]:
                lines[i][0], lines[i - 1][1] = lines[i - 1][1], lines[i][0]
        res = 0
        for i in range(n):
            if lines[i][0] >= lines[i][1]:
                continue
            else:
                res += lines[i][1] - lines[i][0]

        return res


if __name__ == "__main__":
    sl = Solution()
    N = int(input())
    Lines = list()
    for _ in range(N):
        Lines.append(list(map(int, input().split(","))))
    print(sl.SumLength(Lines))
第二题:奇偶数排序(AC)
from typing import List


class Solution:
    def reOrderArray(self, nums: List[int]):
        j_list = []
        o_list = []
        for num in nums:
            if num % 2 == 0:
                o_list.append(num)
            if num % 2 == 1:
                j_list.append(num)

        return o_list + j_list


if __name__ == "__main__":
    sl = Solution()
    N = int(input())
    arr = list(map(int, input().split(",")))
    ans = sl.reOrderArray(arr)
    print(",".join([str(i) for i in ans]))

第三题:01背包问题(AC)
from typing import List


class Solution:
    def MaxSumValue(self, m: int, values: List[int], cost: List[int]):
        n = len(cost)
        dp = [[0] * (m + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = 0
        for j in range(m + 1):
            if j < cost[0]:
                dp[0][j] = 0
            else:
                dp[0][j] = cost[0]
        for i in range(n):
            for j in range(m + 1):
                if j < cost[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + values[i])

        return dp[n - 1][m]


if __name__ == "__main__":
    sl = Solution()
    M = int(input())
    list_1 = list(map(int, input().split()))
    list_2 = list(map(int, input().split()))
    N = list_1[0]
    print(sl.MaxSumValue(M, list_1[1:], list_2[1:]))



全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐