1313. 解壓縮編碼列表(java / c / c++ / python / go / rust)

語言: CN / TW / HK

theme: channing-cyan

這是我參與11月更文挑戰的第11天,活動詳情檢視:2021最後一次更文挑戰

非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】~
放棄不難,但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子:https://le-yi.blog.csdn.net/ 部落格原創~


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

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

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++

cpp 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

```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

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

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/


「其他文章」