Press "Enter" to skip to content

Posts tagged as “counter”

花花酱 LeetCode 2206. Divide Array Into Equal Pairs

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

  • Each element belongs to exactly one pair.
  • The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

  • nums.length == 2 * n
  • 1 <= n <= 500
  • 1 <= nums[i] <= 500

Solution: Hashtable

Each number has to appear even numbers in order to be paired. Count the frequency of each number, return true if all of them are even numbers, return false otherwise.

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

C++

花花酱 LeetCode 2150. Find All Lonely Numbers in the Array

You are given an integer array nums. A number x is lonely when it appears only once, and no adjacent numbers (i.e. x + 1 and x - 1) appear in the array.

Return all lonely numbers in nums. You may return the answer in any order.

Example 1:

Input: nums = [10,6,5,8]
Output: [10,8]
Explanation: 
- 10 is a lonely number since it appears exactly once and 9 and 11 does not appear in nums.
- 8 is a lonely number since it appears exactly once and 7 and 9 does not appear in nums.
- 5 is not a lonely number since 6 appears in nums and vice versa.
Hence, the lonely numbers in nums are [10, 8].
Note that [8, 10] may also be returned.

Example 2:

Input: nums = [1,3,5,3]
Output: [1,5]
Explanation: 
- 1 is a lonely number since it appears exactly once and 0 and 2 does not appear in nums.
- 5 is a lonely number since it appears exactly once and 4 and 6 does not appear in nums.
- 3 is not a lonely number since it appears twice.
Hence, the lonely numbers in nums are [1, 5].
Note that [5, 1] may also be returned.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 106

Solution: Counter

Computer the frequency of each number in the array, for a given number x with freq = 1, check freq of (x – 1) and (x + 1), if both of them are zero then x is lonely.

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

C++

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

  • Every letter in a is strictly less than every letter in b in the alphabet.
  • Every letter in b is strictly less than every letter in a in the alphabet.
  • Both a and b consist of only one distinct letter.

Return the minimum number of operations needed to achieve your goal.

Example 1:

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Example 2:

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Constraints:

  • 1 <= a.length, b.length <= 105
  • a and b consist only of lowercase letters.

Solution: Brute Force

Time complexity: O(26*(m+n))
Space complexity: O(1)

C++

花花酱 LeetCode 383. Ransom Note

题目大意:给你一个字符串,问能否用它其中的字符组成另外一个字符串,每个字符只能使用一次。

Problem:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution: HashTable

Time complexity: O(n + m)

Space complexity: O(128)

C++

 

Python3

 

花花酱 LeetCode 771. Jewels and Stones

题目大意:给你宝石的类型,再给你一堆石头,返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

 

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

C++ v2

Java

Python