亚麻 SDE2 90min OA

昨天刚做的OA

1.

2.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求加米！！

exyman3fendi 发表于 2022-7-31 13:23
楼主链接都失效了， 能不能更新一下 描述内容？

第一题应该是给一个只有0和1的数组nums，每次操作可以交换任意的i和j位置的值。问最少交换几次可以让数组成为回文数组？若无法成为回文则返回-1.

第二题我给忘了不好意思。

mingleetcode 发表于 2022-7-13 19:59
第二题如果从后往前遍历的话那么时间就是O(N*N） 对于数据规模是 0

对，所以需要剪枝。例如子数组789，7和8实际上是不需要进行查询的，因为它俩必然被包含在了以9为结尾的子数组中，且以9为结尾的子串得到的答案必然比以7和8结尾的子串的大。

HammerSICP 发表于 2022-7-11 14:26
请问这是oa part 1 吗

不知道啊 ，就发过来这一个链接。

请问这是oa part 1 吗

第二题如果从后往前遍历的话那么时间就是O(N*N） 对于数据规模是 0 <N<5000, 感觉会有TLE可能

很神奇第二题只要做简单的剪枝就能过全部test cases （如果products[i] - 1 <= 0就停）

是alexa的吗？

要注意update一下cur的值即可

1. public int maxProduct(int[] A) {
   
2.         if (A == null || A.length == 0) {
   
3.             return 0;
   
4.         }
   
5.         int n = A.length;
   
6.         if (n == 1) {
   
7.             return A[0];
   
8.         }
   
9.         int max = 0;
   
10.         for (int i = n - 1; i >= 0; i--) {
    
11.             if (i != n - 1 && A[i] < A[i + 1]) {
    
12.                 continue;
    
13.             }
    
14.             int localMax = A[i];
    
15.             int cur = A[i];
    
16.             for (int j = i - 1; j >= 0 && cur > 0; j--) {
    
17.                 cur = Math.min(--cur, A[j]);
    
18.                 localMax += cur;
    
19.             }
    
20.             max = Math.max(max, localMax);
    
21.         }
    
22.         return max;
    
23.     }

复制代码

楼主链接都失效了， 能不能更新一下 描述内容？