笔试时间：2023年3月23日 腾讯音乐 春招实习

第一题

题目：二叉树赋值

小红拿到了一个二叉树，二叉树共有n个节点。小红希望你将所有节点赋值为1到n的正整数，且没有两个节点的值相等。需要满足:奇数层的权值和与偶数层的权值和之差的绝对值不超过1。如果有多种赋值方案，请返回任意—种方案。如果无解，请返回空树。数据范围: 1<n ≤105。给定的二叉树节点初始权值默认为-1。

示例输入一

{-1,-1,-1}

示例输出一

{3,1,2}

示例输入二

{-1,-1,#,-1,-1}

示例输出二

{}

示例输入三

{-1,-1,-1,#,-1,-1}

示例输出三

{1,3,4,#,2,5}

参考题解

贪心。如果奇数层的节点数和偶数层的节点数大于等于2，必然无解。

分配策略为:较少数量的层[n,n-3....；较多数量的层[n-1,n-2....

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

#include <iostream>
#include <vector>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

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

class Solution {
public:
    TreeNode* fun(TreeNode* root) {
        vector<TreeNode*> odd, even;
        cnts(root, 1, odd, even);

        int n = odd.size() + even.size();
        if (abs(odd.size() - even.size()) >= 2) return nullptr;

        if (odd.size() < even.size()) swap(odd, even);
        int i = n - 3, j = n - 2;
        int sum1 = n, sum2 = n - 1;

        even[0]->val = n;
        odd[0]->val = n - 1;

        int index1 = 1, index2 = 1;
        for (int _ = 0; _ < n - 2; ++_) {
            if (sum1 <= sum2) {
                if (index1 >= even.size()) break;
                even[index1]->val = j;
                index1++;
                sum1 += j;
            } else {
                if (index2 >= odd.size()) break;
                sum2 += j;
                odd[index2]->val = j;
                index2++;
            }
            j--;
        }
        while (index1 < even.size()) {
            even[index1]->val = j;
            j--;
            index1++;
        }
        while (index2 < odd.size()) {
            odd[index2]->val = j;
            j--;
            index2++;
        }
        return root;
    }

    void cnts(TreeNode* node, int i, vector<TreeNode*>& odd, vector<TreeNode*>& even) {
        if (!node) return;
        if (i % 2 == 0) even.push_back(node);
        else odd.push_back(node);
        cnts(node->left, i + 1, odd, even);
        cnts(node->right, i + 1, odd, even);
    }
};

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

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Solution {
    public TreeNode fun(TreeNode root) {
        List<TreeNode> odd = new ArrayList<>();
        List<TreeNode> even = new ArrayList<>();
        cnts(root, 1, odd, even);

        int n = odd.size() + even.size();
        if (Math.abs(odd.size() - even.size()) >= 2) return null;

        if (odd.size() < even.size()) {
            List<TreeNode> temp = odd;
            odd = even;
            even = temp;
        }
        int i = n - 3, j = n - 2;
        int sum1 = n, sum2 = n - 1;

        even.get(0).val = n;
        odd.get(0).val = n - 1;

        int index1 = 1, index2 = 1;
        for (int _ = 0; _ < n - 2; ++_) {
            if (sum1 <= sum2) {
                if (index1 >= even.size()) break;
                even.get(index1).val = j;
                index1++;
                sum1 += j;
            } else {
                if (index2 >= odd.size()) break;
                sum2 += j;
                odd.get(index2).val = j;
                index2++;
            }
            j--;
        }
        while (index1 < even.size()) {
            even.get(index1).val = j;
            j--;
            index1++;
        }
        while (index2 < odd.size()) {
            odd.get(index2).val = j;
            j--;
            index2++;
        }
        return root;
    }

    private void cnts(TreeNode node, int i, List<TreeNode> odd, List<TreeNode> even) {
        if (node == null) return;
        if (i % 2 == 0) even.add(node);
        else odd.add(node);
        cnts(node.left, i + 1, odd, even);
        cnts(node.right, i + 1, odd, even);
    }
}

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

class Solution:
    def fun(self , root: TreeNode) -> TreeNode:
        
        # write code here
        odd, even = [], []
        def cnts(node, i):
            if not node: return
            if i%2==0: even.append(node)
            else: odd.append(node)
            cnts(node.left, i+1)
            cnts(node.right,i+1)
        '''1 2 3 4 5 6 7'''
        cnts(root, 1)
        n = len(odd) + len(even)
        if abs(len(odd) - len(even)) >= 2: return None
        
        if len(odd) < len(even): odd, even = even, odd
        i,j = n-3, n-2
        sum1, sum2 = n, n-1
        even[0].val = n
        odd[0].val = n-1
        index1,index2 = 1, 1

        for _ in range(n - 2):
            if sum1 <= sum2:
                if index1 >= len(even): break
                even[index1].val = j
                index1 += 1
                sum1 += j
            else:
                if index2 >= len(odd): break
                sum2 += j
                odd[index2].val = j
                index2 += 1
            j -= 1
        while index1 < len(even):
            even[index1].val = j
            j-=1
            index1 += 1
        while index2 < len(odd):
            odd[index2].val = j
            j-=1
            index2 += 1
        return root

第二题

题目：小红的字符串切分

小红定义一个字符串的权值为:字符串长度乘以字符串的字母种类数量。例如,"abacb"的价值为5*3=15。小红拿到了一个字符串，她准备将该字符串切分成k个子串(将这k个子串按顺序拼在一起即可得到原串）。小红希望切分后这k个子串的最大权值尽可能小。你能帮帮小红吗?你不需要给出一个方案，只需要返回最终这k个子串的最大权值即可。字符串仅包含小写字母，且长度不超过500000。k为不超过字符串长度的正整数。

示例输入

"ababbbb",2

示例输出

6

参考题解

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

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int getMaxValue(string str, int k) {
        int l = 0, r = 26 * 500000;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(str, mid, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    bool check(string str, int x, int k) {
        int cnt = 1;
        int st = 0, ed = 0;
        unordered_set<char> occ;
        while (ed < str.length()) {
            if (occ.find(str[ed]) != occ.end()) {
                if (occ.size() * (ed - st + 1) <= x) {
                    occ.insert(str[ed]);
                    ed++;
                } else {
                    st = ed;
                    occ.clear();
                    cnt++;
                }
            } else {
                if ((occ.size() + 1) * (ed - st + 1) <= x) {
                    occ.insert(str[ed]);
                    ed++;
                } else {
                    st = ed;
                    occ.clear();
                    cnt++;
                }
            }
        }
        return cnt <= k;
    }
};

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

import java.util.HashSet;

class Solution {
    public int getMaxValue(String str, int k) {
        int l = 0, r = 26 * 500000;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(str, mid, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    private boolean check(String str, int x, int k) {
        int cnt = 1;
        int st = 0, ed = 0;
        HashSet<Character> occ = new HashSet<>();
        while (ed < str.length()) {
            if (occ.contains(str.charAt(ed))) {
                if (occ.size() * (ed - st + 1) <= x) {
                    occ.add(str.charAt(ed));
                    ed++;
                } else {
                    st = ed;
                    occ.clear();
                    cnt++;
                }
            } else {
                if ((occ.size() + 1) * (ed - st + 1) <= x) {
                    occ.add(str.charAt(ed));
                    ed++;
                } else {
                    st = ed;
                    occ.clear();
                    cnt++;
                }
            }
        }
        return cnt <= k;
    }
}

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

class Solution:
    def getMaxValue(self , str: str, k: int) -> int:
        # write code here
        
        def check(x):
            cnt = 1
            st, ed = 0, 0
            occ = set()
            while ed < len(str):
                if str[ed] in occ: 
                    if len(occ) * (ed - st + 1) <= x:
                        occ.add(str[ed])
                        ed+= 1
                    else:
                        st = ed
                        occ.clear()
                        cnt += 1
                else:
                    if (len(occ) + 1) * (ed - st + 1) <= x:
                        occ.add(str[ed])
                        ed += 1
                    else:
                        st = ed
                        occ.clear()
                        cnt += 1
            return cnt <= k
                
        
        l, r = 0, 26 * 500000
        while l < r:
            mid = (l + r) // 2
            if check(mid): r = mid
            else: l = mid + 1
        return r

第三题

题目：小红的字符串

小红拿到了一个仅由大写字母和小写字母组成的字符串。她想知道，在不考虑大小写的情况下，有多少对相邻的字母相等?

字符串长度不超过2×105。

示例输入

"aABbbC"

示例输出

3

参考题解

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int getCnt(string str) {
        // write code here
        int cnt = 0;
        for (int i = 0 ; i < str.length() -1; i++) {
            if (str[i] == str[i+1] || (str[i]-'a' == str[i+1] - 'A') || (str[i]-'A' == str[i+1]- 'a')) cnt++;
        }
        return cnt;
    }
};