04-07 23:20 已编辑 武汉大学 Java 发布于湖北
关注
淘天 Java研发 笔试4.2
单选：大小根堆转化、快排、线程池、http、状态模式、sql查询。
不定项：索引、tcp、时间复杂度、二分查找、线程同步。
算法
1.求一个数组中全是质数的闭区间的个数。
双指针找被合数分割的区间。
2.a 个 1*1 和 b 个 2*2 正方形，能否刚好拼成大正方形。
a <= b 必定不行，遍历查找 i^2 = a+4*b 。但只过了 34.75% 。
3.给一个字符串，将各个前缀按照字母顺序内部排列之后，再将前缀数组按字典序排列，求第 k 小的元素。
思路是重载 sort 。喜提 0 ，寄。
#淘天##笔试#
不定项：索引、tcp、时间复杂度、二分查找、线程同步。
算法
1.求一个数组中全是质数的闭区间的个数。
双指针找被合数分割的区间。
2.a 个 1*1 和 b 个 2*2 正方形，能否刚好拼成大正方形。
a <= b 必定不行，遍历查找 i^2 = a+4*b 。但只过了 34.75% 。
3.给一个字符串，将各个前缀按照字母顺序内部排列之后，再将前缀数组按字典序排列，求第 k 小的元素。
思路是重载 sort 。喜提 0 ，寄。
#淘天##笔试#
全部评论
牛客163450938号
天津工业大学 Java
这是哪个岗的
牛客108275237号
西安交通大学 Java
第二题可以先判断是不是平方数，再把形成的大正方形的边长求出来，边长整除2的平方就是能容纳最多的2*2正方形，在比较一下大小就行了
相关推荐
淘天集团一面215人在聊 
blueswiller：给出一个做法，刚刚才想到，应该没问题，时间复杂度为 O(max(30n, nlogn)): 1. 根据 0 切分数组。2. 现在问题转化为>=1 的情况，我们首先维护每一个数前一个 > 1 的数的位置，同时维护一个长度的差分数组，初始值全为 0。3. 我们从每一个数 i 开始向前跳，至多跳 30 次，维护这个过程中的乘积，于是得到 30 个区间加和。举例：假设从 j1 跳到 j2 ，相当于对查询长度 (i- j1 + 1) 至 (i - j2) 贡献 a_i * ... * a_j1。4. 对于所有区间加和，我们采用差分数组结合树状数组对其进行维护，由于长度至多为 n ，树状数组构建的复杂度为 O(nlogn)，于是，构建阶段的复杂度为 O(max(30n, nlogn))。在线单次查询的复杂度为树状数组查询的复杂度 O(logn)。
投递淘天集团等公司10个岗位 > 笔试 点赞 评论 收藏
分享
查看30道真题和解析 点赞 评论 收藏
分享
