笔试算法题

算法两个题，给出最长公共子序列的长度的函数，要求空间都复杂度为O(min(m,n)) ,时间复杂度为O(mn) function lcs(str1,str2){ let dp=new Array(str2.length+1).fill(0) for(let i=1;i<=str1.length;i++){ let pre=0 for(let j=1;j<=str2.length;j++){ let temp=dp[j] dp[j]=str1[i-1]==str2[j-1]?pre+1:Math.max(dp[j-1],dp[j]) pre=temp } } return dp[st...

1. 不用库函数求sqrt(xxxx). 要求c / c++   二分       2. 大意：给你n个点以及颜色，只有两种颜色红和蓝，给你n个边（无向图）， 节点的权重为该节点到根节点的红蓝两种颜色数量差，问这个树的权重和为多少？    dfs 超时    bfs 超时    层次遍历超时。   据说用并查集  但是还没想明白。       3. 大意： 给你n个人，每个人会关注mi个股票。 设计一个推荐系统，推荐规则为：如果i人和j人都关注了股票m， 那么j的关注名单就可以推荐给i， 给你一堆查询的人，问每一个人可以推荐多少支股票？      感觉是set的优化，超时。     最开始： ...

麻了，以前都是这么难得题吗，这尼玛。。。就只能得个十几分一共，有没有大佬能帮忙写个题解呢？选择题也是不当人。      1. 猜排列游戏   有一个1到n整数组成的排列，现在来猜这个排列是什么，每次可以猜某一位置的数字，得到的反馈是“大了”，“小了”或者“正确”。求最坏的情况下需要猜测几次，才能在所有位置得到“正确”？      输入一个整数n   输出最坏情况下的猜测次数      例：   输入：   5   输出：   11      2. 圣诞树   圣诞树由n个节点组成，每个节点上为一个整数（可为负数），节点从1到n编号。每次操作需选择一个包含1号节点的子图，并将子图中所有节点的值+...

选择题考到了Huffman树、C++代码阅读、VGG、AE啥的，好多没接触过的知识点，随机选择了可以说。   三道编程题：   第一道是什么闯关拿奖品，其实是LC原题最长公共子序列，笔试的时候没写出来转移方程，就过了10%。   第二道找有多少种安排展览的方式，不知道LC有没有原题，我用的简单的递归也全部通过了。   第一道k-means没接触过直接放弃。   要学的东西好多啊😫

有选择题   三道编程题   第一题：   输入   2   1 3   2 5   第一行是有n个信封，后面的每一行是n个信封的长和宽，只有小信封的长款大小比大信封小才能套进去，问最多能套多少个信封？   import sys if __name__ == "__main__":     # 读取第一行的n     n = int(sys.stdin.readline().strip())     ans = []     for i in range(n):         # 读取每一行         line = sys.stdin.readline().stri...

m个员工，分n个月饼，m<n,每人最少一个，最多max个，第一多的比第二多的多出的个数少于等于3，第n多的比第n-1多的个数少于等于3，求有多少分法

排序子序列 排序子序列   import java.util.Scanner; public class Main{ public static int subArray(int[] array){ i...

好像是25道单选题+3道编程题   原题没有复制下来，俺只记得大致意思，大家将就着看吧   第一题：   1、有俩哥们小A和小B玩游戏，每个游戏会有奖品（用数字和字母表示），相同的奖品（拿的顺序也必须相同）才能带回家，最多能带回多少件奖品   输入   3478297   3djakl7   输出   4   第二题：   信封嵌套问题，有n个信封，每个信封有长和宽，只有长宽比另一个信封的小，才能放进去，问最多能嵌套多少个信封   输入   4   1 2   4 5   2 2   3 4   输出   3   第三题：   有一些居民的坐标（x，y）,用聚类思想设置k(给出)个送菜的中心点...

给定字符串长度，且只包含'c'、'm'字符，不能连续出现2个及以上的字符'c'，求能构成多少种字符串？