【春招笔试】2024-04-18-腾讯音乐-三语言题解

🍭 大家好这里是 清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新腾讯音乐近期的春秋招笔试题汇总～

👏 感谢大家的订阅➕ 和 喜欢💗

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

💽 01.卢小姐的链表织零术

问题描述

卢小姐在学习编程时遇到了一个有趣的链表操作问题。她需要在一个单向链表的每两个相邻节点之间插入一个值为 0 的新节点。她想要一个程序，能够对任意给定的链表执行这一操作，并输出修改后的链表。

输入格式

第一行包含一个正整数 ，表示链表的长度。

第二行共 个空格分隔的正整数 ，表示链表中各个节点的值。

输出格式

输出共 个空格分隔的正整数，表示插入 0 后的链表中各个节点的值。

样例输入

{1,2,3,1}

样例输出

{1,0,2,0,3,0,1}

数据范围

题解

要解决这个问题，我们需要遍历给定的链表，并在每两个相邻节点之间插入一个值为 0 的新节点。这个过程需要细心处理链表节点的指针，以确保新插入的节点正确地连接到链表中。在链表的末尾，我们不需要添加新的节点。

参考代码

• Python

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

def insert0(head):
    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
    return dummy.next

• Java

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

public class Solution {
    public ListNode insert0(ListNode head) {
        ListNode dummy = new ListNode(-1), p = dummy;
        while (head != null) {
            p.next = new ListNode(head.val);
            p = p.next;
            if (head.next != null) {
                p.next = new ListNode(0);
                p = p.next;
            }
            head = head.next;
        }
        return dummy.next;
    }
}

• Cpp

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* insert0(ListNode* head) {
        ListNode dummy(-1), *p = &dummy;
        while (head) {
            p->next = new ListNode(head->val);
            p = p->next;
            if (head->next) {
                p->next = new ListNode(0);
                p = p->next;
            }
            head = head->next;
        }
        return dummy.next;
    }
};

💾 02.卢小姐的平衡二叉树挑战

问题描述

卢小姐在数据结构课程中学到了二叉树的概念，她现在想要构造一个特殊的满二叉树。这棵二叉树需要满足一个条件：每一层的节点权值和都相等。卢小姐希望你能帮助她构造这样一棵树，树的层数为 ，并且每个节点的权值都是不超过 10000 的正整数。如果有多种构造方法，返回任意一种即可。

输入格式

输入只有一行，包含一个正整数 ，表示二叉树的层数。

输出格式

输出一行，表示二叉树的层序遍历结果。每个节点的值之间用空格分隔。

样例输入

3

样例输出

4 2 2 1 1 1 1

数据范围

题解

为了构造满足条件的二叉树，我们可以采用层序遍历的方式构建树。从根节点开始，每向下一层，节点的值都是上一层节点值的一半。这样可以保证每一层的节点权值和相等。具体实现时，我们可以使用队列来辅助节点的插入和遍历。

参考代码

• Python

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

def create_balanced_tree(n):
    if n == 0:
        return None
    root = TreeNode(1 << (n - 1))
    queue = [root]
    for level in range(n - 1, 0, -1):
        next_queue = []
        for node in queue:
            node.left = TreeNode(1 << (level - 1))
            node.right = TreeNode(1 << (level - 1))
            next_queue.extend([node.left, node.right])
        queue = next_queue
    return root

• Java

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

public class Solution {
    public TreeNode createBalancedTree(int n) {
        if (n == 0) return null;
        TreeNode root = new TreeNode(1 << (n - 1));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        for (int level = n - 1; level > 0; level--) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                node.left = new TreeNode(1 << (level - 1));
                node.right = new TreeNode(1 << (level - 1));
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return root;
    }
}

• Cpp

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* createBalancedTree(int n) {
        if (n == 0) return nullptr;
        TreeNode* root = new TreeNode(1 << (n - 1));
        queue<TreeNode*> queue;
        queue.push(root);
        for (int level = n - 1; level > 0; level--) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = queue.front(); queue.pop();
                node->left = new TreeNode(1 << (level - 1));
                node->right = new TreeNode(1 << (level - 1));
                queue.push(node->left);
                queue.push(node->right);
            }
        }
        return root;
    }
};

💿 03.卢小姐的红色记忆

问题描述

卢小姐在整理她的珍贵收藏时，发现了一串珍珠链，每颗珍珠都有一个特定的价值。部分珍珠已被染成红色，而其他珍珠则保持原色。卢小姐希望通过染色使得所有红色珍珠的价值总和为偶数。她可以选择染色任意未染色的珍珠，你能帮助她计算出有多少种染色方案吗？

输入格式

第一行包含一个整数数组，表示珍珠链上每颗珍珠的价值。
第二行是一个字符串，表示每颗珍珠的颜色状态，'R' 表示已经被染成红色，'W' 表示未被染色。

输出格式

输出一个整数，表示使得所有红色珍珠的价值总和为偶数的染色方案数，结果对 取模。

样例输入

[1, 2, 3]
"RWW"

样例输出

2

数据范围

• 链表长度不超过 。
• 珍珠的价值为正整数。

题解

在这个问题中，我们需要关注两类珍珠：已经染成红色的和未染色的。首先，我们计算所有已染红珍珠的价值总和。接下来，我们需要考虑如何通过选择染色未染色的珍珠来调整总和的奇偶性。

我们将未染色的珍珠根据其价值的奇偶性分类，统计奇数价值珍珠和偶数价值珍珠的数量。基于当前红色珍珠价值总和的奇偶性，我们可以确定需要从未染色的奇数珍珠中选择某些珍珠进行染色以达到目标。

具体的计算方法是使用组合数学中的组合公式来计算选择某些珍珠染色的方案数。最后，将所有可能的选择方案累加起来即可得到最终的答案。

参考代码

• Python

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

def getMethod(head: ListNode, colors: str) -> int:
    mod = 10 ** 9 + 7
    values = []
    while head:
        values.append(head.val)
        head = head.next
    odd_count = even_count = 0
    current_sum = 0
    for value, color in zip(values, colors):
        if color == 'R':
            current_sum += value
        else:
            if value % 2 == 1:
                odd_count += 1
            else:
                even_count += 1
    n = odd_count
    fac = [1] * (n + 10)
    ifac = [1] * (n + 10)
    for i in range(1, n + 6):
        fac[i] = fac[i - 1] * i % mod
    ifac[n + 5] = pow(fac[n + 5], mod - 2, mod)
    for i in range(n + 5, 0, -1):
        ifac[i - 1] = ifac[i] * i % mod

    def combine(n, m):
        if n < m or m < 0:
            return 0
        return fac[n]