阿里7.24笔试

a0道……大佬有说说怎么做的嘛,第二道矩阵求等价着实实现不了

#阿里巴巴#
全部评论
第一题直接记录当前位置的最小值,第二题只拿了30%
1 回复 分享
发布于 2020-07-24 23:13
第二题20% 真的吐了
1 回复 分享
发布于 2020-07-24 22:29
第一题关键在于每次有个范围和最小值,初始范围为n,最小值就是min(a[1...n]),然后最小值变为0之后,如果最小值最早的位置是index,那么范围变为index-1,再考虑min(a[1...index-1]),我用的单调栈做
1 回复 分享
发布于 2020-07-24 20:16
第一题一维dp,状态是第i个盘子最多能吃掉多少,dp[i] = min(dp[i-1], s[i]),输出最后一个就行了。
1 回复 分享
发布于 2020-07-24 20:14
贴一下第一题吃烧饼后来的想法,时间复杂度O(n)......(目前测试用例是对的)         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int[] nums = new int[n];         for (int i=0;i<n;i++){             nums[i] = in.nextInt();         }         int count = 0;         int min = nums[0];         for (int i=0;i<nums.length;i++){             if (nums[i]<min) {                 min = nums[i];             }             count += min;         }         System.out.println(count);
点赞 回复 分享
发布于 2020-07-24 23:58
第一道单调栈应该可以做出来
点赞 回复 分享
发布于 2020-07-24 23:01
死磕了50分钟搞不定。。。
点赞 回复 分享
发布于 2020-07-24 22:29
第一题全AC Python代码 n = int(input()) s = list(map(int, input().split(' &(5528)#39;))) def sol(n, s):     if n == 1:         return s[0]     ret = 0     t = float('inf&(835)#39;)     min_index = None     for i, v in enumerate(s):         if v < t:             t = v             min_index = i     if min_index == 0:         return s[0] * n     ret = t * (n - min_index)     return ret + sol(min_index, s[:min_index]) print(sol(n, s))
点赞 回复 分享
发布于 2020-07-24 22:29
第一题 20% 不知道哪里出错了,显示了死循环😥 import java.util.Scanner; public class t1 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         if(!sc.hasNextInt()) System.out.println(0);         int n = sc.nextInt();         int[] array = new int[n];         for (int i = 0; i < n; i++) {             array[i] = sc.nextInt();         }         int res = eat(array, n);         System.out.println(res);     }     static int eat(int[] array, int n) {         int counter = 0;         while (array[0] > 0) {             for (int i = 0; i < n; i++) {                 if (array[i] == 0) {                     break;                 } else {                     array[i] = array[i] - 1;                     counter = counter + 1;                 }             }         }         return counter;     } }
点赞 回复 分享
发布于 2020-07-24 21:41
纯暴力😂 #include<iostream> #include<vector> using namespace std; class Solution { public:     long long EatCake(int n, vector<int>& nums) {         long long count = 0;         while (nums[0] > 0) {             for (auto& c : nums) {                 c--;                  if (c >= 0) {                      count++;                  }                  else                      break;             }         }         return count;     } }; int main() {        vector<int> a{1,4,5,3,2,6};     Solution c;     c.EatCake(5, a); }
点赞 回复 分享
发布于 2020-07-24 21:29
第二题考完之后想到一个思路。本来的想着用异或来找操作的列(比特位),后来想到的方法似乎能通过,大家看看帮忙分析分析。 对于初始矩阵,对每列求和,统计1的个数,然后跟目标矩阵每列求和的结果对比(因为列的不会调换的,所以可以直接比较),如果相等,可以该列不用操作;否则,再判断两者相加是否等于N(N为行数,代表拨动该列的开关后,1的数量就相同)。 上面的条件并不完整,但是能排除错误的用例。在上面条件通过的基础上,再对两个矩阵每行进行求和,即求1的个数,然后排序(这一步可以抵消随意换行的操作)。排序后的序列相同,则两者可以相互转化;否则,输出 Impossible。 因为这里有很多列求和,行求和,所以用 Python 表示会更直白。这里写个伪码: 给定: mat1, mat2, N, L 过程: colSum1 = sum(mat1, axis=0) colSum2 = sum(mat2, axis=0) rowSum1 = sum(mat1, axis=1) rowSum2 = sum(mat2, axis=1) cnt = 0 for i in range(L):     if colSum1[i] == comSum2[i]:         continue     else if colSum1[i] + comSum2[i] == N:         cnt += 1     else:         print("Impossible")         return if sort(rowSum1) == sort(rowSum2):     print(cnt) else:     print("Impossible") 欢迎大家提出意见~~~
点赞 回复 分享
发布于 2020-07-24 21:26
第一题思路:(测试全通过)题目条件是每次从1到x每个盘子吃去1个烧饼,假设在s[0]到s[x-1]当中,s[x-1]最小,那么这个范围能吃s[x-1]遍,直至把它吃完,再从左边选一个新的x。也就是说,靠右侧的较小值限定了在其左侧盘子中同时能吃到烧饼的数量。所以我们可以从0开始遍历,每次更新访问过的最小值,用作限定在这个盘子最终能吃到的最大值。讲的可能不太清楚,这里给个伪码吧。 long cnt = s[0]; long tmpMin = s[0]; for (long i = 1; i < N; ++i) {     tmpMin = Math.min(tmpMin, s[i]);     cnt += tmpMin; } System.out.println(cnt);
点赞 回复 分享
发布于 2020-07-24 21:08
第一题思路:对第二行的输入数组,每次找到最少烧饼的盘子,然后对最少烧饼的盘子右边的所有盘子吃最少烧饼数量,再对左边的盘子做同样处理直到第一个盘子。 考完在本地IDE上调试出来,自己测试没啥问题,发出来请大家找找问题。。。一起学习 def funa(s,sum):     s1 =sorted(s)     for i, item in enumerate(s):         if item == s1[0]:             s1.pop(0)             sum += item*(len(s)-i)             if i == 0:                 return sum             else:                 return(funa(s[:i], sum)) ans = funa(s,0) print(ans)
点赞 回复 分享
发布于 2020-07-24 20:47
第一个是不是有大数问题啊 ,累加起来会超过long,我的思路是找到最小的值,记录下来他还有他的下标,然后他前面的数都能吃到剩下min,然后剩下的就是min*n
点赞 回复 分享
发布于 2020-07-24 20:27
第二题真的太难了吧
点赞 回复 分享
发布于 2020-07-24 20:24
https://www.nowcoder.com/discuss/459044?source_id=profile_create&channel=666 第二个我不确定,大伙来看看对不对把
点赞 回复 分享
发布于 2020-07-24 20:17
第一题dp,蹲一个第二题
点赞 回复 分享
发布于 2020-07-24 20:17
第二道样例给错了吗
点赞 回复 分享
发布于 2020-07-24 20:14
第一道20%,第二道0😔
点赞 回复 分享
发布于 2020-07-24 20:14
第一道10%,第二道0
点赞 回复 分享
发布于 2020-07-24 20:13

相关推荐

VirtualBool:都去逗他了?
点赞 评论 收藏
分享
点赞 评论 收藏
分享
昨天 15:52
东南大学 C++
点赞 评论 收藏
分享
评论
1
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务