字符频率排序

1. 根据字符出现频率排序

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入: s = "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

提示:

1 <= s.length <= 5 * 105
s 由大小写英文字母和数字组成

答：

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const map = new Map();
    for (let i = 0, len = s.length; i < len; i++) {
        const val = map.get(s[i]);
        map.set(s[i], val ? val + s[i] : s[i]);
    }
    return Array.from(map.values()).sort((a,b) => b.length - a.length).join('');
};

2. 最小操作次数使数组元素相等

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1：

输入：nums = [1,2,3]
输出：3
解释：
    只需要3次操作（注意每次操作会增加两个元素的值）：
    [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

示例 2：

输入：nums = [1,1,1]
输出：0

提示：

n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
答案保证符合 32-bit 整数

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
     let res = 0;
    let min = Math.min.apply(null, nums);
    for (const num of nums) {
        res += num - min;
    }
    return res;
}

3. 所有奇数长度子数组的和

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：

输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例 3：

输入：arr = [10,11,12]
输出：66

提示：

1 <= arr.length <= 100
1 <= arr[i] <= 1000

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function(arr) {
    const len = arr.length;
    // 原地修改，计算前缀和
    for (let i = 1; i < len; i++) {
        arr[i] += arr[i - 1];
    }
    // 定义返回值，初始为0
    let res = 0;
    // 定义左边界
    for (let i = 0; i < len; i++) {
        // 定义右边界，因为长度奇数，j每次+2
        for (let j = i; j < len; j += 2) {
            // 此时arr已经是前缀和
            // i!==0, [i,j]区间内的长度和 = arr[j] - arr[i - 1]
            // i===0, [i,j]区间内的长度和 = arr[j]
            res += arr[j] - (arr[i - 1] || 0);
        }
    }
    return res;
};