腾讯音乐笔试腾讯音乐笔试题 0418

笔试时间：2024年04月18日

历史笔试传送门：2023秋招笔试合集

第一题

题目：小红的链表扩展

小红拿到了一个链表,请你将每两个相邻元素之间添加一个值为0的节点。链表长度不超过10^5。

样例输入

{1，2，3，1}

样例输出

{1，0，2，0，3，0，1}

参考题解

题目比较简单，每次访问一个节点，就插入一个0值节点；注意最后一个节点之后，不需要再插入。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insert0(ListNode* head) {
        ListNode dummy(-1), *p = &dummy;
        while (head) {
            p->next = new ListNode(head->val);
            head = head->next;
            p = p->next;
            if (head) {
                p->next = new ListNode(0);
                p = p->next;
            }
        }
        p->next = nullptr;
        return dummy.next;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode insert0(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (head != null) {
            p.next = new ListNode(head.val);
            head = head.next;
            p = p.next;
            if (head != null) {
                p.next = new ListNode(0);
                p = p.next;
            }
        }
        p.next = null;
        return dummy.next;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def insert0(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1)
        p = dummy
        while head:
            p.next = ListNode(head.val)
            head = head.next
            p = p.next
            if head:
                p.next = ListNode(0)
                p = p.next
        p.next = None
        return dummy.next

第二题

题目：小红的二叉树构造

小红希望你构造一个n层满二叉树,满足每一层的节点权值和都相等,你能帮帮她吗? 你需要保证每个节点权值都是不超过10^9的正整数。有多解时返回任意合法二叉树即可。 1≤n≤14。

样例输入

3

样例输出

{5，2，3，1，2，1，1}

参考题解

bfs或者dfs都可。

计算每个根节点的子树所有严重问题数和一般问题数，然后判断即可。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return TreeNode类
     */
    TreeNode* create(int n) {
        TreeNode* root = new TreeNode(1 << (n - 1));
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            n--;
            if (n == 0) break;
            while (sz--) {
                TreeNode* r = q.front(); q.pop();
                r->left = new TreeNode(1 << (n - 1));
                r->right = new TreeNode(1 << (n - 1));
                q.push(r->left); q.push(r->right);
            }
        } 
        return root;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return TreeNode类
     */
    public TreeNode create(int n) {
        TreeNode root = new TreeNode(1 << (n - 1));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            n--;
            if (n == 0) break;
            for (int i = 0; i < sz; i++) {
                TreeNode r = q.poll();
                r.left = new TreeNode(1 << (n - 1));
                r.right = new TreeNode(1 << (n - 1));
                q.add(r.left);
                q.add(r.right);
            }
        }
        return root;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def create(self, n: int) -> TreeNode:
        root = TreeNode(1 << (n - 1))
        q = deque([root])
        while q:
            sz = len(q)
            n -= 1
            if n == 0:
                break
            for _ in range(sz):
                r = q.popleft()
                r.left = TreeNode(1 << (n - 1))
                r.right = TreeNode(1 << (n - 1))
                q.append(r.left)
                q.append(r.right)
        return root