242. Effective letter anagrams
Given two strings s and t, write a function that determines whether t is a letter anagram of s.
Note: If each character in s and t occurs the same number of times, s and t are said to be alphabetic anagrams of each other.
Example 1.
Input: s = "anagram", t = "nagaram"
Output: true
Example 2.
Input: s = "rat", t = "car"
Output: false
Tip.
1 <= , <= 5 * 104
s and t contain lowercase letters only
Advanced: What if the input string contains unicode characters? Can you adapt your solution to cope with this situation?
Positive solutions (hash tables)
An array is really just a simple hash table
Assume that s is of length n and t is of length m;
It may only be a valid alphabetic anagram if n=m;
Since there are only 26 lowercase letters, we can use their order in the alphabet as the key of the hash table, and the number of occurrences as the value.
Upcode (●'◡'●)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < (); i++) {
auto iter = (target - nums[i]);
if(iter != ()) {
return {iter->second, i};
}
(pair<int, int>(nums[i], i));
}
return {};
}
};
349. Intersection of two arrays
Given two arrays, nums1 and nums2, return the intersection of the two arrays.
Each element of the output must be unique. We can disregard the order of the output.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also passable
Tip:
1 <= , <= 1000
0 <= nums1[i], nums2[i] <= 1000
It actually lets us return the common element of the two arrays
Positive solution (unordered_set)
Set is used here because the result needs to be de-duplicated;
Since sorting is not required use unordered_set (hereafter referred to as uset) which is a bit more efficient than set;
First use a uset a to store nums1, then traverse nums2, if there is a difference then put it into another uset;
Finally return the uset of the storage node; the
Upper code (●'◡'●)
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set((), ());
for (int num : nums2) {
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
202. Happy Count
Write an algorithm to determine if a number n is a happy number.
"Happy Number" is defined as:
For a positive integer, replace the number each time with the sum of the squares of the numbers in each of its positions.
Then the process repeats until the number reaches 1, or it may loop indefinitely without ever reaching 1.
If the process results in 1, then the number is a happy number.
Returns true if n is a happy number; false if it is not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Tip:
1 <= n <= 231 - 1
Positive solution (simulation + hash table)
Just simulate this question directly, but determine if it's an infinite loop;
This is where uset is used to find out if a value is repeated, which means an infinite loop and exit;
Upper code (●'◡'●)
class Solution {
public.
// Get the sum of the digits of the value in each place.
int getSum(int n) {
int sum = 0; while (n) {
while (n) {
sum += (n % 10) * (n % 10); n /= 10; // get the sum of the digits in each place.
n /= 10; }
n /= 10; n /= 10; }
n /= 10; }
}
bool isHappy(int n) {
unordered_set<int> set.
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true; }
}
// If this sum ever occurs, we're in an infinite loop, so we return false immediately
if ((sum) ! = ()) {
return false; } else {
} else {
(sum); } else {
}
n = sum; }
}
}
}; }
time complexity\(O(n)\)It was pretty quick;
This problem can actually be done with a double pointer, with the same time complexity, which is a lot of work to think about, but seems to be simpler to write;
Just think of it as a chained list and just determine if there are any rings;
1. The sum of two numbers
Given an array of integers nums and an integer target, find the two integers in the array whose sum is the target and return their array subscripts.
You can assume that each input will only correspond to one answer. However, the same element in the array cannot be repeated in the answer.
You can return the answers in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0, 1].
Explanation: Since nums[0] + nums[1] == 9, return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Tip:
2 <= <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
There will only be one valid answer
Advanced: can you come up with an algorithm with time complexity less than O(n2)?
aaaaa~
Where dreams begin.
Though but, we're going for a more elegant approach this time (●ˇ∀ˇ●)
Positive solution (unorded_map).
For this question, we need to Given an element, determine if the element has ever appeared, and if so, return the subscript of the element.
Then determine whether the element appears, this element should be used as the key, so the elements in the array as the key, there is a key corresponding to the value, the value is used to store the subscript.
So the storage structure in map is {key: data element, value: subscript corresponding to array element}.
When traversing the array, you only need to go to the map to query whether there is a match with the currently traversed element, if so, the matching pair found, if not, the currently traversed element into the map, because the map stores the elements we have accessed.
Upper code (●'◡'●)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < (); i++) {
auto iter = (target - nums[i]);
if(iter != ()) {
return {iter->second, i};
}
(pair<int, int>(nums[i], i));
}
return {};
}
};
time complexity\(O(n)\);
The time complexity of violence is\(O(n^2)\);
It's still a lot faster in comparison;
It's not easy to write a blog, so please give me some support 8~!