第三题 啥完美分割吧? 回溯a96%
点赞 评论

相关推荐

09-11 22:16
已编辑
重庆大学 Java
更新:9月11日。挂时间:8.25岗位是后端开发,一共就 4 道算法题,无选择题,120 分钟1. 题目没读懂。。2. 给 n 个数,对数进行操作:1. 值减半;2. 将两个值用他们的和替换。问最少多少次操作才能使数组全部元素变为奇数。解题思路:奇 + 偶 = 奇,利用这个性质,只要有一个奇数,我们就可以利用操作 2 在 n 次操作将 n 个偶数变为奇数,答案就是偶数的个数。而果没有奇数,可以通过操作 1 将一个偶数变为奇数,答案为通过操作 1 获得一个奇数所需要的最少步骤 + 偶数个数 - 1。3. 给定一个数组,和一个数 k。可以将 k 与数组中任意一个小于 k 的元素进行交换。问至少交换多少次,才能够使得数组单调不减。解题思路:根据题目要求,只有当前持有的 k 大于数组元素时,可以进行交换,也就是说,数组的每个元素之能增加或不变,不可能减少,并且每次交换之后,所持有的 k 的值一定会减小。那么什么时候不可能得到单调不减的数组呢?对于下标 i 位置处的元素和目前所持有的 k,都小于下标 i 之前最大的那个数,说明不管交换与否,下标 i 之前那个最大的数永远比下标 i 处的元素大,也就不可能得到单调不减数组。因此,我们可以倒序遍历数组,对于每个下标 i 的元素 ai 去看是否需要交换。第一种情况是 max(ai, k)  < i 之前最大数,单调递减数组不可能得到,输出 -1。第二种情况是 ai < i 之前最大的数 < k,那么必须进行交换才有可能得到单调递减数组;第三种情况是 i 之前最大的数 < ai < k。那么对于这种情况换不换都可以,如果不换的话,这就意味着 k 不能再与 i 之前的数进行交换,否则就会出现 k > ai,而 k 在 ai 前面,也就无法构成单调不减的数组,也就是说,只有前面的数已经满足题意了,才可以不换,否则就必须交换,只有交换了,才能够在接下来的遍历中拥有交换的权利,使得依然有可能构成单调不减的数组。为了优化复杂度,可以预处理两个数组,order[i] 和 mx[i]。order[i] 表示下标 i 之前的数组是否单调不减;mx[i] 表示下标 i 之前的最大的数。4. 给定一个 01 字符串,每次操作可以将字符串分成前后两个部分,然后将前后两个部分翻转再拼接,问最长能够得到的 01 交替字符串长度。解题思路:观察这样的变化:++--|--++  ->  --++|++--。所谓的切分翻转拼接其实就是将前缀和后缀拼接,答案要么为原始字符串中最长交替字符串长度,要么最左边和最右边翻转过来的拼接得到的 01,条件是首尾字符不同。翻转一次就够了,题目说任意次操作有点误导人。第一次分享思路,没表达清楚意思的话还请原谅。代码我发在评论区。
查看6道真题和解析 投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务