24届要毕业的我，不小心又做了实习笔试。一直以为是算法的笔试，然后搞了个开发的笔试，算了当回忆了，记录一下。有一说一，今天的选择题比前几天算法选择题简单很多，基本能对75%以上吧。第一题题意：对于n个顶点，判断m条边能否构成图切不包含重边自环。做法：临界n-1，n*(n-1)/2第二题题意：给定一个长度为n(做法：看到最小最大放在一起时，一般就是二分答案。区间加单点查询，搞个八百年没写了的线段树从左到右扫一遍。时间复杂度O(nloglog)。第三题题意：给定一个长度为n(做法：和数组本身没多大关系，记num0表示0的个数，num1表示1的个数，num2表示-1的个数。乘积为0的公式为(2^num0 - 1) * (2^(num1+num2))乘积为-1的公式为(\sum_{i为奇数} (C(num2, i)) * (2^(num1))乘积为1的公式为(\sum_{i为偶数} (C(num2, i)) * (2^(num1)) - 1逆元前缀乘积 + 快速幂。时间复杂度O(n)

不小心做了实习笔试，记录一下。选择题一直不太会，略过。第一题题意：数字符串(长度n做法：根据数据范围，直接二进制枚举。时间复杂度O(n&nbsp;*&nbsp;2^n)。第二题题意：。。模拟某个机器学习数据处理。。做法：输入对写c++的不太友好，py3模拟一下。第三题题意：给定一个01字符串（长度n做法：常规动态规划。注意到数据范围n所以对于第一问，记dp[i][j]表示当前位置i，表示能够向前跳2^i的跳到当前位置的最小跳跃次数，转移方式特判一下j为0的时候，dp[i][0]&nbsp;=&nbsp;min{dp[i-(1对于第二问，记dp[i][j]表示当前位置i，表示能够向前跳2^i的最小次数跳到当前位置最小需要填几次0。转移方程对于当前为1或者0分开考虑，也要特判j为0的情况。对于s[i]&nbsp;==&nbsp;1时候，dp[i][0]&nbsp;=&nbsp;min{dp[i-(1<<j)][j]}，j不是0时为dp[i][j]&nbsp;=&nbsp;min{dp[i-(1<<j&nbsp;-&nbsp;1)][j-1]}。对于s[i]&nbsp;==&nbsp;0时候，dp[i][0]&nbsp;=&nbsp;min{dp[i-(1<<j)][j]&nbsp;+&nbsp;1}，j不是0时为dp[i][j]&nbsp;=&nbsp;min{dp[i-(1<<j&nbsp;-&nbsp;1)][j-1]&nbsp;+&nbsp;1}。

#软件开发2024笔面经#&nbsp;记录一下。第一题题意：给定长度为n(做法：记数组和为sum，&nbsp;答案为&nbsp;fac3(sum)&nbsp;-&nbsp;\sum_i&nbsp;(fac3(a_i))，&nbsp;函数fac3(x)&nbsp;=&nbsp;C(x,&nbsp;3)。时间复杂度O(n)第二题题意：数字符子串，包含byte和dance的字串总数。做法：遍历一遍即可，维护一下左端起始点pos，初始值为0，当当前位置i开始能够能构成byte或者dance时，pos更新为i&nbsp;+&nbsp;1。时间复杂度O(n)。第三题题意：给定一个数组，其用n(做法：前缀和。维护一下y_i的前缀和，二分查找，以及所有数的前缀和。时间复杂&nbsp;O(qlogn&nbsp;+&nbsp;n)第四题题意：给定一个n*m&nbsp;(n&nbsp;做法：矩阵竖的看，看数据范围为二进制枚举，+动态规划一下，时间复杂度O(4^n&nbsp;*&nbsp;m&nbsp;*n)，直接循环套循环了，所以写的变成了2^n&nbsp;*&nbsp;2^n，可能时间复杂度可以压到O(2^n&nbsp;*&nbsp;m&nbsp;*n)，可能写递归能压到O(2^n&nbsp;*&nbsp;m)。

记录一下。第三题题目大概意思：给定一个整数数组（长度做法：搞个函数f(k,n-k)表示n个数中奇数为k个的期望调整次数，为方便起见，f(k,n-k)写为f(k)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;期望转移表达式为&nbsp;f(k)&nbsp;=&nbsp;f(k-1)*k/n&nbsp;+&nbsp;f(k+1)*(n-k)/n&nbsp;+&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;记录a_k&nbsp;=&nbsp;f(k)&nbsp;-&nbsp;f(k-1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;上式转化为等比数列，即a_k&nbsp;=&nbsp;(n-k)/k&nbsp;*&nbsp;a_{k+1}&nbsp;+&nbsp;n&nbsp;/&nbsp;k&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;考虑到边界为a_n&nbsp;=&nbsp;f(n)&nbsp;-&nbsp;f(n&nbsp;-&nbsp;1)&nbsp;=&nbsp;1，可以直接循环一遍算出所有a_k值&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;若原数组奇数个数为u，则答案为(\sum_{1}^{u}&nbsp;a_k)&nbsp;+&nbsp;f(0)，&nbsp;而f(0)为0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;乘法逆元的话直接线性筛或者快速幂。&nbsp;时间复杂度O(n)