未来做啥网站致富,服装企业 北京 网站建设,前端注册wordpress,网站开发不满意-----------------第二天------------------------
面试官 : 好的#xff0c; 我们再来做个算法题吧。平时工作中会尝试用算法吗#xff0c; 用到了什么数据结构#xff1f; 3妹 : 有用到#xff0c; 用到了 bla bla… 面试官 : 好的#xff0c; 题目是这样的#xff1…
-----------------第二天------------------------
面试官 : 好的 我们再来做个算法题吧。平时工作中会尝试用算法吗 用到了什么数据结构 3妹 : 有用到 用到了 bla bla… 面试官 : 好的 题目是这样的
题目
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下
令 nums[i…j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组满足 0 i j nums.length 那么我们称子数组 nums[i…j] 中不同值的数目为 nums[i…j] 的不同计数。 请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大请你将它对 109 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1
输入nums [1,2,1] 输出15 解释六个子数组分别为 [1]: 1 个互不相同的元素。 [2]: 1 个互不相同的元素。 [1]: 1 个互不相同的元素。 [1,2]: 2 个互不相同的元素。 [2,1]: 2 个互不相同的元素。 [1,2,1]: 2 个互不相同的元素。 所有不同计数的平方和为 12 12 12 22 22 22 15 。 示例 2
输入nums [2,2] 输出3 解释三个子数组分别为 [2]: 1 个互不相同的元素。 [2]: 1 个互不相同的元素。 [2,2]: 1 个互不相同的元素。 所有不同计数的平方和为 12 12 12 3 。
提示
1 nums.length 100 1 nums[i] 100
思路 1、使用哈希表统计各数字出现次数。 2、枚举每个元素分别作为子数组的起始元素每次步长递增1使用列表记录步长的统计结果。 3、引用的方式错位继承步长1的结果。以{1,2,3}为例起始元素为2且步长为1的结果等于上一个起始元素1且步长为3的结果并去掉元素1。
java代码 class Solution {public int sumCounts(ListInteger nums) {int sum 0;int key (int) (Math.pow(10, 9) 7);int len nums.size();// 按步长统计ListHashMapInteger, Integer stepList new ArrayList(len);// 枚举各个元素分别作为子数组的起始元素for (int i 0; i len; i) {// 步长递增for (int j 0; i j len; j) {int num nums.get(i j);HashMapInteger, Integer numCntMap new HashMap();if (i 0) {if (j 0) {numCntMap.put(num, 1);} else {// 继承上一次步长-1的结果numCntMap.putAll(stepList.get(j - 1));if (numCntMap.containsKey(num)) {// 和上个元素重复numCntMap.put(num, numCntMap.get(num) 1);} else {// 不重复numCntMap.put(num, 1);}}} else {if (j 0) {sum (sum 1) % key;continue;} else {// 错位继承步长1的结果并移除上一个元素// numCntMap.putAll(stepList.get(j 1));// 优化将putAll每次都要复制遍历全部改为直接引用numCntMap stepList.get(j 1);int preNum nums.get(i - 1);int preNumCnt numCntMap.get(preNum);if (preNumCnt 1) {numCntMap.remove(preNum);} else {numCntMap.put(preNum, preNumCnt - 1);}}}if (i 0) {stepList.add(numCntMap);} else {// 更新stepList.set(j, numCntMap);}// 累加平方和sum (sum (int) (Math.pow(numCntMap.keySet().size(), 2))) % key;}}return sum;}
}
