Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 2194. Cells in a Range on an Excel Sheet

By zxi on March 8, 2022

A cell (r, c) of an excel sheet is represented as a string "<col><row>" where:

  • <col> denotes the column number c of the cell. It is represented by alphabetical letters.
    • For example, the 1st column is denoted by 'A', the 2nd by 'B', the 3rd by 'C', and so on.
  • <row> is the row number r of the cell. The rth row is represented by the integer r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, <col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.

Return the list of cells (x, y) such that r1 <= x <= r2 and c1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.

Example 1:

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Example 2:

Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

Constraints:

  • s.length == 5
  • 'A' <= s[0] <= s[3] <= 'Z'
  • '1' <= s[1] <= s[4] <= '9'
  • s consists of uppercase English letters, digits and ':'.

Solution: Brute Force

Time complexity: O((row2 – row1 + 1) * (col2 – col1 + 1))
Space complexity: O(1)

C++

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

花花酱 LeetCode 2180. Count Integers With Even Digit Sum

By zxi on February 28, 2022

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

The digit sum of a positive integer is the sum of all its digits.

Example 1:

Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.

Example 2:

Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.

Constraints:

  • 1 <= num <= 1000

Solution: Brute Force

Use std::to_string to convert an integer to string.

Time complexity: O(nlgn)
Space complexity: O(lgn)

C++

花花酱 LeetCode 2185. Counting Words With a Given Prefix

By zxi on February 26, 2022

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] and pref consist of lowercase English letters.

Solution: Straight forward

We can use std::count_if and std::string::find.

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

C++

花花酱 LeetCode 2169. Count Operations to Obtain Zero

By zxi on February 13, 2022

You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

  • For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

  • 0 <= num1, num2 <= 105

Solution 1: Simulation

Time complexity: O(max(n,m) / min(n, m))
Space complexity: O(1)

No code

Solution 2: Simualtion + Math

For the case of 100, 3
100 – 3 = 97
97 – 3 = 94
…
4 – 3 = 1
Swap
3 – 1 = 2
2 – 1 = 1
1 – 1 = 0
It takes 36 steps.

We can do 100 / 3 to skip 33 steps
100 %= 3 = 1
3 / 1 = 3 to skip 3 steps
3 %= 1 = 0
total is 33 + 3 = 36.

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

C++