阿里7.24笔试

第一题直接记录当前位置的最小值，第二题只拿了30%

第二题20% 真的吐了

第一题关键在于每次有个范围和最小值，初始范围为n，最小值就是min(a[1...n])，然后最小值变为0之后，如果最小值最早的位置是index,那么范围变为index-1,再考虑min(a[1...index-1])，我用的单调栈做

第一题一维dp，状态是第i个盘子最多能吃掉多少，dp[i] = min(dp[i-1], s[i])，输出最后一个就行了。

贴一下第一题吃烧饼后来的想法，时间复杂度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);

第一道单调栈应该可以做出来

死磕了50分钟搞不定。。。

第一题全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))

第一题 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;     } }

纯暴力😂 #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); }

第二题考完之后想到一个思路。本来的想着用异或来找操作的列（比特位），后来想到的方法似乎能通过，大家看看帮忙分析分析。 对于初始矩阵，对每列求和，统计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") 欢迎大家提出意见~~~

第一题思路：（测试全通过）题目条件是每次从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);

第一题思路：对第二行的输入数组，每次找到最少烧饼的盘子，然后对最少烧饼的盘子右边的所有盘子吃最少烧饼数量，再对左边的盘子做同样处理直到第一个盘子。 考完在本地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)

第一个是不是有大数问题啊 ，累加起来会超过long，我的思路是找到最小的值，记录下来他还有他的下标，然后他前面的数都能吃到剩下min,然后剩下的就是min*n

第二题真的太难了吧

https://www.nowcoder.com/discuss/459044?source_id=profile_create&channel=666 第二个我不确定，大伙来看看对不对把

第一题dp，蹲一个第二题

第二道样例给错了吗

第一道20%，第二道0😔

第一道10%，第二道0