LeetCode（Array)1313. Decompress Run-Length Encoded List

谁借莪１个温暖的怀抱￠ 2023-09-23 22:34 5阅读 0赞

# 1. 问题 #

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements \[freq, val\] = \[nums\[2*i\], nums\[2*i+1\]\] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.

Return the decompressed list.

Example 1:

> Input: nums = \[1,2,3,4\]  
> Output: \[2,4,4,4\]  
> Explanation: The first pair \[1,2\] means we have freq = 1 and val = 2 so we generate the array \[2\].  
> The second pair \[3,4\] means we have freq = 3 and val = 4 so we generate \[4,4,4\].  
> At the end the concatenation \[2\] + \[4,4,4\] is \[2,4,4,4\].

Example 2:

> Input: nums = \[1,1,2,3\]  
> Output: \[1,3,3\]

Constraints:

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

# 2. 解题思路 #

## 方法1 ##

> 1.新建list为temp  
> 2.遍历数组，nums\[2 \* i\]是限定前个数，nums\[2 \* i + 1\]是限定数字，比如1个2，3个4，将其添加temp中  
> 3.设定一个临时的数组，长度为temp的长度，比例数组放到result中  
> 4.返回数组

## 方法2 ##

> 1.定义size为0，求size的长度  
> 2.定义result的数组，长度为size  
> 3.定义 startIndex的初始值为0，使用Arrays.fill（）填充result的数据，从 startIndex到startIndex + nums\[i\]，value为nums\[i + 1\]， startIndex += nums\[i\]  
> 4.返回数组

## 方法3 ##

> 方法3和2的思路是基本相同的，不同的是使用Arrays.fill（）填充和两层for循环遍历得到result结果

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int[] decompressRLElist(int[] nums) {
        
            List<Integer> temp = new ArrayList();//1.新建list为temp
            for(int i =0;i<nums.length/2;i++) {
        //2.遍历数组，nums[2 * i]是限定前个数，nums[2 * i + 1]是限定数字，比如1个2，3个4，将其添加temp中
                for (int j = 0; j < nums[2 * i]; j++) {
        
                    temp.add(nums[2 * i + 1]);
                }
            }
    
            int[] result = new int[temp.size()];//3.设定一个临时的数组，长度为temp的长度，比例数组放到result中
            for(int r=0;r<temp.size();r++){
        
                result[r]=temp.get(r);
            }
            return result;//4.返回数组
            
        }
    }

> 以下代码解题思路相同，只不过是int i = 0; i < nums.length; i += 2，换成int i =0;i<nums.length/2;i++

class Solution {
        
        public int[] decompressRLElist(int[] nums) {
        
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i += 2) {
        
                for (int j = 0; j < nums[i]; j++) {
        
                    list.add(nums[i + 1]);
                }
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        }
    }

## 代码2： ##

class Solution {
        
            int size = 0;//1.定义size为0，求size的长度
            for (int i = 0; i < nums.length; i += 2) {
        
                size += nums[i];
            }
    
            int[] result = new int[size];//2.定义result的数组，长度为size
    
            int startIndex= 0;//3.定义 startIndex的初始值为0，使用Arrays.fill（）填充result的数据，从 startIndex到startIndex + nums[i]，value为nums[i + 1]， startIndex += nums[i]
            for (int i = 0; i < nums.length; i += 2) {
        
                Arrays.fill(result, startIndex, startIndex + nums[i], nums[i + 1]);
                startIndex += nums[i];
            } 
            return result;//4.返回数组
        }
    }

## 代码3： ##

class Solution {
        
        public int[] decompressRLElist(int[] nums) {
        
            int size = 0;//1.定义size为0，求size的长度
            for (int i = 0; i < nums.length; i += 2) {
        
                size += nums[i];
            }
            int[] result = new int[size];//2.定义result的数组，长度为size
            int StartIndex = 0;//3.定义 startIndex的初始值为0
            for (int i = 0; i < nums.length; i += 2) {
        //4.遍历数组，StartIndex++,而不是 startIndex += nums[i];是因为在for循环i+=2下，nums[i]代表数组个数， nums[i + 1]代表数组的值
                for (int j = 0; j < nums[i]; j++, StartIndex++) {
        
                    result[StartIndex] = nums[i + 1];
                }
            }
            return result;//4.返回数组
        }
    }