This is the 11th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021
It is not difficult to give up, but it must be very cool to insist. I hope we can make progress a little bit every day
1313. List of decompressed codes:
Give you a list of compressed integers encoded in stroke length, NUMs.
Consider each pair of adjacent elements [freq, val] = [nums[2* I], nums[2* I +1]] (where I >= 0). Each pair represents a freq element of val in the unzipped sublist. You need to join all the sublists left to right to generate the unzipped list.
Return to the unzipped list.
Sample 1:
Input: nums = [1,2,3,4] Output: [2,4,4] Explanation: The first pair [1,2] represents the occurrence frequency of 2 is 1, so generate array [2]. The second pair [3,4] represents the occurrence frequency of 4 is 3, so the array [4,4,4] is generated. Finally, string them together [2] + [4,4,4] = [2,4,4,4].Copy the code
Example 2:
Input: nums = [1,1,2,3]Copy the code
Tip:
- 2 <= nums.length <= 100
- nums.length % 2 == 0
- 1 <= nums[i] <= 100
Analysis of the
-
This algorithm topic feeling does not have what special skill really, just can imitate according to the meaning of the topic.
-
Dynamic data structures are supported for most languages, but one caveat to dynamic data structures is that when elements are added dynamically, dynamic expansion occurs, which can lead to content copying.
-
Some of the problems are traversed first to calculate the total length, which can offset the cost of using dynamic data structures for dynamic expansion.
Answer key
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]; }}returnans; }}Copy the code
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;
}
Copy the code
c++
class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> ans;
for (int i = 0, l = nums.size(a); i < l; i +=2) {
ans.insert(ans.end(), nums[i], nums[i + 1]);
}
returnans; }};Copy the code
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])]
Copy the code
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
}
Copy the code
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()
}
}
Copy the code