字节跳动2024.3.24算法笔试

#软件开发2024笔面经# 记录一下。
第一题题意：给定长度为n(<2e5)的数组，数组每个位置有$a_i$个数，从所有数中选三个，且不落在同一个位置的总数。
做法：记数组和为sum， 答案为 fac3(sum) - \sum_i (fac3(a_i))， 函数fac3(x) = C(x, 3)。时间复杂度O(n)

第二题题意：数字符子串，包含byte和dance的字串总数。
做法：遍历一遍即可，维护一下左端起始点pos，初始值为0，当当前位置i开始能够能构成byte或者dance时，pos更新为i + 1。时间复杂度O(n)。

第三题题意：给定一个数组，其用n(<1e5)段(x_i, y_i）表示连续出现y_i个值为x_i的数，比如((6, 2), (1,3))表示 数组[6，6，1，1，1]。给定q个区间(p, q)求区间和。
做法：前缀和。维护一下y_i的前缀和，二分查找，以及所有数的前缀和。时间复杂 O(qlogn + n)

第四题题意：给定一个n*m (n < 6, m<1000)矩阵，其中值为0，1，或者?，?表示0或者1，总共有多少矩阵数量满足没有相邻的两个数为1。
做法：矩阵竖的看，看数据范围为二进制枚举，+动态规划一下，时间复杂度O(4^n * m *n)，直接循环套循环了，所以写的变成了2^n * 2^n，可能时间复杂度可以压到O(2^n * m *n)，可能写递归能压到O(2^n * m)。