Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 1313. Decompress Run-Length Encoded List

By zxi on January 11, 2020

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

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0).  For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example 1:

Input: nums = [1,2,3,4]
Output: [2,4,4,4]

Constraints:

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

Solution: Simulation

Time complexity: O(sum(n_i))
Space complexity: O(sum(n_i)) or O(1)

C++

花花酱 LeetCode 1304. Find N Unique Integers Sum up to Zero

By zxi on December 29, 2019

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

Constraints:

  • 1 <= n <= 1000

Solution: Generation

Use numbers from {-n/2, … n/2} + {0 if n is odd}

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1299. Replace Elements with Greatest Element on Right Side

By zxi on December 28, 2019

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5

Solution: Scan from right to left

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

By zxi on December 26, 2019

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^5

Solution: Math

Time complexity: O(n * log(max(num)))
Space complexity: O(1)

C++

Python3

花花酱 LeetCode 1287. Element Appearing More Than 25% In Sorted Array

By zxi on December 14, 2019

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Constraints:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5

Solution 1: Linear Scan

if arr[i] == arr[i + len/4] => arr[i] is the special integer.

Time complexity: O(n)
Space complexity: O(1)

C++

Solution 2: Binary Search

The answer must be one of (s[0], s[l/4], s[l/2], s[l*3/4])
Using binary search to find the range of each number, the one has more than 1/4 of total elements is the answer.

Time complexity: O(logn)
Space complexity: O(1)

C++