简答算法
2021-04-09 13:26
标签：算法 而不是 for 正确答案 怎样 get int 最小值 部分 在leetcode上遇到的题： 给定一个整数数组 A ，考虑 A 的所有非空子序列。对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。返回 A 的所有子序列的宽度之和。 例子： 输入：[2,1,3] 输出：6 解释： 子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。 相应的宽度是 0，0，0，1，1，2，2 。 这些宽度之和是 6 。 思考：怎样用程序将此题解决？ 首先分析： 方法一：例举法（笨方法） 从其中取出2个数，用大数减去小数求和 从其中取出3个数，比较大小用最大数减去最小数求和 。。。。。。。。。 n个数的最大数减去最小数求和。 在这样的思考下，这样的方法使得程序复杂且难以动态的实现，而且若是数据量比较大，这样的方法很难去实现。所以在这样的情况下想到更好的方法。 首先，将给出的数组里面的数据由小到大进行排列 我为什么要这样做呢？通过题所给出的规律可以得出，我们只需要取得一个最大值，一个最小值，然后将这两最值中间得数按排列组合进行取值，能排多少个就可以用这个个数乘上这两最值得差值（大数减小数）。然后再求和就可以得出答案。 以为这样就完了吗？ 还没结束呢。题中给出的是数组而不是集合。所以数组中是可以出现重复的值的。如果一个数组中没有重复的数，那么上述的方法就不能够得出正确的答案。 所以我引入了Map 首先将数组进行由小到大排序。（这样方便进行Map的操作） 采用遍历的方式进行，key表示数组中数字的大小，value表示数组中key出现的次数。 map.put(A[0],1); for(int i=1;i if(A[i-1]==A[i]){ map.put(A[i-1],map.get(A[i-1])+1) }else{ map.put(A[i],map.1) } } 这样得到每个数出现的次数，现在通过例举法取出任意两个数（不允许重复），两个数中间有t个数。 sum=sum+(max-min)*(2^t-map.get(A[j])*(2^map.get(A[j])-map.get(A[j]));(min
按照排列组合就可以得出正确答案。 本人是2020届大学毕业生，本科的 专业是数学与应用数学，对算法很感兴趣。有空也会在leetcode上刷刷算法题，会及时与大家分享。后续的代码实现，我会尽快的上传，可能会再做优化。 哎，不是计算机专业面试计算机的工作确实有些难度。不过我不会灰心，在这次面试中也发现了自己在java方面的不足之处。现在来填补这些空缺，未来的事谁也说不准，只有使得自己变得更好才能在这亚历山大的世界中拔得头筹。给自己加加油。 加油加油。come on !!! 简答算法 标签：算法 而不是 for 正确答案 怎样 get int 最小值 部分 原文地址：https://www.cnblogs.com/zhou2420032204/p/13375268.html
