阿里 2020/7/22笔试题(三面炸，被boss怼懵了

从头到尾扫一遍，计算以i结尾的满足条件的区间数cnt[i]。 根据题意有一个结论：对于以i结尾的区间，若pt使得a[pt...i]满足条件，则对pt'<pt都满足条件。所以只要找到满足条件最大的pt，cnt[i]就等于pt+1了（不是pt）。 所以就是循环维护pt值，方法是：对每个值，记录下的出现位置list。扫描到a[i]时，查看到目前为止倒数第m-1次出现（如果存在）的位置pt_pre_m，且pt_pre_m大于pt，则更新pt为pt_pre_m。 O(N)复杂度

public static int calculate(int[] nums , int k){     Map<Integer,Integer> map = new HashMap<>();     int[] dp = new int[nums.length+1];     int left=0 , right=0; //    map.put(nums[left],1); //    int result=0;     while(left<=right && left<nums.length && right<nums.length){         for( right=left ; right<nums.length ; right++ ){             if(map.containsKey(nums[right])){                 map.put(nums[right],map.get(nums[right])+1);                 if(map.get(nums[right]) >= k )                     break;             }             else{                 map.put(nums[right],1);             }         }         for(int i=right+1 ; i<=nums.length ; i++ ){             if(i==right+1)                 dp[i]++;             else{                 dp[i]=dp[i-1]+1;                       }             }         left++;         map.clear();              }          return dp[nums.length]; }

第一个题复杂度直接暴力dfs的复杂度是O(n!)，n=10的时候一般就很慢了，剪枝一下可能能过。我感觉正解应该是用状压dp，dp[i][j]表示在状态i下最后一个数是j的数据总数，这样复杂度就能降到O(n*2^n)，就能解决部分评论说的回溯超时的问题了。 第二个题可以用一个双指针+map的做法复杂度O(nlogn)，枚举子数组左区间，显然可行的右区间是一段后缀，而且当左区间越枚举时可行右区间的后缀越来越小。就可以用双指针来枚举，用map记录可行性，然后记一下每一次后缀长度累加一下即可。 楼上的第二题O(n)做法看不懂，我太菜了。

动态规划。先统计一共有多少种数字。表示为k。 dp[i][k][m]表示前i个组成的数组中的k元素的出现个数>=m的子数组个数。 dp[i][k][m]=dp[i-1][k][m]+dp[i-1][k][m-1] (  if nums[i]=k) 最后统计dp[i][0~k][m]的和

第二题动态规划或者双指针。

第一题我这dfs超时了😑，10的时候过不了

a最多40w，没跑出来😓

就没人说一下第一题的那个相邻的绝对值咋处理吗😂，还是我太菜了

看看这份代码：思路是双指针的同时维护一个unordered_map，当遇到map[a[j]] == m 的时候就说明后面的都是可行解，同时移动前方的指针使得a[i] == a[j]，并且更新map的数据，去掉前方的部分数据也是可行解，因此 ret += ( i - before + 1 )*( a.size() - j ) int calulate2(vector<int>& a, int m) { int ret = 0; unordered_map<int, int> map; int before = 0; for (int j = 0; j < a.size(); ++j) { int& num = ++map[a[j]]; if (num < m) continue; else { int i = before; while (a[i] != a[j]) { map[a[i]] --; i++; } num--; ret += ( i - before + 1 )*( a.size() - j ); before = i + 1; } } return ret; }

弱弱的问一句，可以笔试用matlab吗

请问相邻的两个数字的绝对值不能等于1是什么意思呢

求第二题代码

第二题我思路是取i=区间左起点，然后j从i开始向后滑，直到出现m个相同的数字，此时从j往后的都算是符合要求，然后加起来。。但是答案不对，0%。是啥问题啊。我思路哪里错了吗

第一题递归+回溯跑到90就不行了，想了半天没没想出来咋剪枝 第二题可以直接暴力的（虽然不一定能A），我自以为是的想了个好办法，结果给自己整懵逼了

第二题输入一直不对，能编译，但是一直是0

我怎么就没想到回溯！！被剃光头