LeetCode Day 06 Hash map (1/2)

Day 5 is rest day, so Day 6 continued from Day4. And today is first day of hash map practice (1/2).

Summary of hash tables in a nutshell:

Hash tables are used to quickly determine whether an element is present in a set, but sacrifice space for time.

Question 1

242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

First thought is still Brute Force, with two For loops, with no doubt O(n^2) complexity, not much sense.

This question needs to find out if there are the same letters in two strings, but can be in different positions (anagrams). Applying the idea of hash table, we first find an array of 26 bits long (to correspond to the 26 letters), then count the frequency of each letter, +1 if the string s occurs, then compare it with the string t, -1 if it occurs, if the last one is 0, it means the two strings are anagrams.

A Python function: ord() is needed.

ord().

Takes a string (Unicode character) as an argument and returns the corresponding ASCII value, or Unicode value. For example, ord(‘a’) returns the integer 97, and ord(‘€’) (the Euro symbol) returns 8364.

ord() is the opposite of chr():

chr().

Returns a string representing the character with Unicode bit integer i. For example, chr(97) returns the string “A”, while chr(8364) returns the string “€”. For example, chr(97) returns the string “A”, while chr(8364) returns the string “€” (euro). The valid range of parameters is from 0 to 1114111 (based on the 16-bit 0x10FFFF). If this range is exceeded, a value error is raised.

The solution is easy if we know these kndwledges

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        for i in range(26):
            if record[i] != 0:
                return False
        return True

Besides the hash table method, there is an easy way to record the number of occurrences with a dictionary, and then just compare the contents of the two dictionaries

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import defaultdict
        
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)
        for x in s:
            s_dict[x] += 1
        
        for x in t:
            t_dict[x] += 1
        return s_dict == t_dict

Question 2

349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Save it in a dictionary, then traverse the second array, and compare it to the dictionary

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        from collections import defaultdict
        Dict_1 = defaultdict(int)
        for i in nums1:
            Dict_1[i] += 1
        
        res = []
        for i in set(nums2):
            if i in Dict_1:
                res.append(i)
        return res

Question 3

202. Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

The point of this question is to determine whether sum will recur or not, and how to take each bit of the numbers

class Solution:
    def isHappy(self, n: int) -> bool:        
        record = set()
 
        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
            if n in record:
                return False
            else:
                record.add(n)
 
    def get_sum(self,n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

Question 4

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

The first question of leetcode, but it’s not as easy as one might think.

I’ve done this before with the double pointer method, but it was too much work. Now try the set method.

Use a dict for the letter and the corresponding index, then traverse the array to find out if target-i is in the previous dict, if it is, return the two indices, and if it’s not found, save it to the dict for the rest of the elements in the nums to find!

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = {}
 
        for index ,i in enumerate(nums):
            if (target - i) in record:
                return [index,record[target-i]]
            else:
                record[i] = index
        return []