1313. 解压缩编码列表：
给你一个以行程长度编码压缩的整数列表 nums 。
考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。
请你返回解压后的列表。
样例 1：
输入：
nums = [1,2,3,4]
输出：
[2,4,4,4]
解释：
第一对 [1,2] 代表着 2 的出现频次为 1，所以生成数组 [2]。
第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。
最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
样例 2：
输入：
nums = [1,1,2,3]
输出：
[1,3,3]
提示：
- 2 <= nums.length <= 100
- nums.length % 2 == 0
- 1 <= nums[i] <= 100
分析
- 这道算法题目感觉真的没有什么特别技巧，就是按照题意模拟即可。
- 对于大部分语言都有动态数据结构支持，但是动态数据结构有一个点需要注意，就是在动态添加元素的时候，会发生动态扩展，也就可能发生内容拷贝。
- 二当家的其中一些题解先遍历一次，计算出总的长度，这样的开销可以抵消使用动态数据结构发生动态扩展的开销。
题解
java
class Solution {
public int[] decompressRLElist(int[] nums) {
int len = 0;
for (int i = 0; i < nums.length; i += 2) {
len += nums[i];
}
int[] ans = new int[len];
for (int i = 0, j = 0; i < nums.length; i += 2) {
for (int k = 0; k < nums[i]; ++k) {
ans[j++] = nums[i + 1];
}
}
return ans;
}
}c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decompressRLElist(int* nums, int numsSize, int* returnSize){
*returnSize = 0;
for (int i = 0; i < numsSize; i += 2) {
*returnSize += nums[i];
}
int *ans = malloc(*returnSize * sizeof(int));
for (int i = 0, *p = ans; i < numsSize; i += 2) {
while (nums[i]--) {
(*p++) = nums[i + 1];
}
}
return ans;
}c++
class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> ans;
for (int i = 0, l = nums.size(); i < l; i += 2) {
ans.insert(ans.end(), nums[i], nums[i + 1]);
}
return ans;
}
};python
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
return [nums[i + 1] for i in range(0, len(nums), 2) for _ in range(nums[i])]
go
func decompressRLElist(nums []int) []int {
l := 0
for i := 0; i < len(nums); i += 2 {
l += nums[i]
}
ans := make([]int, l)
for i, j := 0, 0; i < len(nums); i += 2 {
for k := 0; k < nums[i]; k, j = k+1, j+1 {
ans[j] = nums[i+1]
}
}
return ans
}rust
impl Solution {
pub fn decompress_rl_elist(nums: Vec<i32>) -> Vec<i32> {
(0..nums.len()).step_by(2).flat_map(|i|{
[nums[i + 1]].repeat(nums[i] as usize).into_iter()
}).collect()
}
}原题传送门：https://leetcode-cn.com/problems/decompress-run-length-encoded-list/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
