X

LEETCODE 1313. Decompress Run-Length Encoded List 解题思路分析

题目大意:

解压缩编码列表

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

考虑每相邻两个元素 [a, b] = [nums[2i], nums[2i+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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1313

解题思路分析:

本题虽然是一道简单题,但是我却花了大量时间去理解题目描述,看了许久才明白题目要我们做什么。这里简单解释一下题目大意,比如例子中给出的数组[1,2,3,4],我们可以将所有数字以相邻的两两一组分割,即1,2和3,4,他们代表了返回结果中要包含1个2和3个4,即:[2,4,4,4]。再举个例子,[2,3,2,5]代表了返回结果包含2个3和2个5。

弄明白题意之后,本题并没有什么难度,直接按照数组的双数位下标是个数,相邻的单数位下标是数值来理解即可。解题时,我们先循环一遍数组的双数位,查看返回结果一共包含多少元素,然后用得到的元素个数新建一个数组作为返回结果,再遍历一遍数组,将对应的数字填入返回结果即可。

实现代码:

public int[] decompressRLElist(int[] nums) {
    int size=0; // 返回结果元素个数
    // 统计返回结果元素个数
    for(int i=0;i<nums.length;i+=2) size+=nums[i];
    // 返回结果
    int[] res = new int[size];
    int index=0;
    // 将元素逐个填入返回结果
    for(int i=0;i<nums.length;i+=2){
        for(int j=1;j<=nums[i];j++){
            res[index++]=nums[i+1];
        }
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.71% of Java online submissions for Decompress Run-Length Encoded List.

Memory Usage: 37.8 MB, less than 100.00% of Java online submissions for Decompress Run-Length Encoded List.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1313-decompress-run-length-encoded-list-解题思路分析/
Categories: leetcode
kwantong: