腾讯笔试-2023年9月10日
5道编程。然后辣鸡牛客系统直接炸了，remake，excuse me?
- 有一颗二叉树，节点的权值为0或1，给定这颗二叉树，计算从根节点到叶子节点的所有路径中，节点权值为1的节点比节点权值为0的节点个数多1的路径个数。直接dfs。
- 给一个数组，再给一个这个数组下标作为元素的数组，逐个删除元素，计算中位数。想了有点久O(nlog)：反序为逐步添加。然后mutiset背后红黑树数据结构，利用其插入自动排序的特性，插入复杂度是logn。然后维护一个middle的iter。
- 勇敢牛牛不怕困难题目就贪心法。排序后，一直选最大、最小依次即可。
- 校验和和子串。在长度为n的二进制01串中，定义其校验和为对于所有长度为k的连续子串，将其全部进行异或，结果为该串的校验和。问：在长度为n，校验和长度为k的所有二进制01串中，校验和相同的串的个数。
- 数学问题+背包？
- 首先稍微推导一下校验和就可以发现：比如对于n=6，k=2，校验和第一位是前五位的异或，第二位是后五位的异或。总结以下规律：
- 对于二进制串S，其k位的校验和中每一位的值计算方法为：
- 对于第一位，取决于[1, n-k+1]中1的个数的奇偶性，如果为偶数，则为0，否则为1。
- 对于第二位，取决于[2, n-k+2]中1的个数的奇偶性，如果为偶数，则为0，否则为1。
- 依次类推，最后一位取决于[n-k+1, n]中1的个数的奇偶性。
- 因此，计算校验和相同的串的个数，即按照k对串进行滑动，保证每个滑动窗口内1的个数的奇偶性相同，即可。计算这个个数。
- 设定S为全0的串，其任意滑动窗口内1的个数均为偶数。寻找和这个串校验和相同的串，即查找所有滑动区间内1的个数为偶数的串，计算满足这个条件的串的个数。
- 把问题转化为滑动窗口，使得每个窗口1的个数都是偶数（且大于0）.这个问题应该是背包问题？背包问题有点不会做了。
- 没空看。
