02 解压编码列表

题目

给你一个以行程长度编码压缩的整数列表 nums 。

考虑每相邻两个元素 [a, b] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后有 a 个值为 b 的元素。

请你返回解压后的列表。

示例：

输入：nums = [1,2,3,4] 输出：[2,4,4,4]

提示：

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

来源：力扣（LeetCode）

分析

刚开始没看懂题目，看了评论区解释

把两个数看成一对，[1,2,3,4]=[1,2]+[3,4] 则表示1个2,3个4 所以最终答案是[2,4,4,4]

我还以为是每个位按公式 [a, b] = [nums[2*i], nums[2*i+1]] 计算 [1,2] = [2*0,2*1+1]=[0,3]

这个公式的意思是：a表示奇数位，b表示偶数位置 这个公式其实不应该给出来，给出来就相当于给出了题解。 显然，我们需要将所有下标为a的数据拿出来，生成对应a个下标为b的数即可。

提示解析

1. 2 <= nums.length <= 100 考虑下标的使用，循环从0~98
2. nums.length % 2 == 0，因此不必考虑奇数个数据使循环越界的情况（比如[1,2,3]，则3个x不存在）
3. 1 <= nums[i] <= 100 考虑最大的100，则可能出现100个100，因此目标数组最大容量为(100/2)*100 (当nums.length=100 && nums[任意 i ]=100 时)
4. 目标target数组的实际长度为Σ nums[b]

算法描述

有时候写算法的时候，考虑“人是如何处理的” 人的解题思路：

• 将nums数组两两凑对 [1,2,3,4]=[1,2]+[3,4]
• 将1个2,3个4放入新数组

翻译成代码

• 遍历nums数组，拿到nums[a]和nums[b]
• 将nums[a]个nums[b]放入新数组

注意： 实际分组时不能直接遍历整个数组然后拿到奇偶位 比如： [1,2,3,4] 可能解析为1个2,2个3,3个4 进行了交叉分组 因此遍历办法：nums.length，步长为2

答案

class Solution {
    public int[] decompressRLElist(int[] nums) {
        int size=0;
        for(int i=0;i<nums.length;i+=2)
            size+=nums[i];
        int[] target = new int[size];
        int index=0;
        for(int i=0;i<nums.length;i+=2){
            int a=nums[i];
            int b=nums[i+1];
            for(int j=0;j<a;j++)
                target[index++]=b;
        }
        return target;
    }
}

在这里插入图片描述

补充学习

class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer>list=new ArrayList<>();
        for(int i=0;i<nums.length;i+=2){
            int j=nums[i];
            while(j>0){
                list.add(nums[i+1]);
                j--;            
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

这个实现避免了求target的长度，但是这种方法其实慢很多。不过，我们可以学习其中使用的List转Array的方法

List To Array

list.stream() 获取list的流 .toArray(String[]::new) 将流中的数据进行new String[]进行装填

上述题解代码

list.stream().mapToInt(Integer::valueOf).toArray()

其他类似

在这里插入图片描述