Searching - hash table

[ahasusie]

Hash Table is a data structure which organises data using hash functions in order to support quick insertion and search. -hash function design -resolve collision -key choose

python: dict, set, enumerate,

// hash set is able to store only values. for no duplicates values. // hash map is an implementation of map which is able to store (key, value) pairs. and can perform really well in grouping information by key.

1. provide more information, like index
2. aggregate keys: The key to solving this kind of problem is to decide your strategy when you encounter an existing key, Sometimes, we might sum all the values up. And sometimes, we might replace the original value with the newest one.
3. choose a proper key: https://leetcode.com/explore/learn/card/hash-table/185/hash_table_design_the_key/1128/ designing a key is to build a mapping relationship by yourself between the original information and the actual key used by hash map. rules 1). All values belong to the same group will be mapped in the same group. 2). Values which needed to be separated into different groups will not be mapped into the same group.

[ahasusie]

def singleNum(nums):
    d = {}
    for i in nums:        
        try:
            d.pop(i)
        except:
            d[i] = 1
    return d.popitem()[0]

def hasDuplicates(nums):
    hashTable = set()
    for i in nums:
        if i in hashTable:
            return True
        hashTable.add(i)
    return False        

def intersction(nums1, nums2):
    res = []
    nums1Set = set(nums1)
    for i in nums2:
        if i in nums1Set:
            res.append(i)
            nums1Set.remove(i)
    return res

def twoSum(nums, target):
    d = {}
    for i, n in enumerate(nums):
        if target-n in d:
            return d[target-n], i
        d[n] = i

def canChange(s, t):
    d1, d2 = {}, {}
    for i, val in enumerate(s):
        d1[val] = d1.get(val, []) + [i]
    for i, val in enumerate(t):
        d2[val] = d2.get(val, []) + [i]       
    print d1
    print d2
    return sorted(d1.values()) == sorted(d2.values())  

def buildDict(s):
    d = {}
    for k, val in enumerate(s):
        d[val] = d.get(val, []) + [k]
    print d

def firstUniqChar(s):
    d = {}
    for c in s:
        if c in d.keys():
            d[c] += 1
        else:
            d[c] = 1
    for i in range(len(s)):
        c = s[i]
        if d[c] == 1:
            return i    
    return -1

if __name__ == "__main__":
    arr = [1,2,3]
    #print singleNum([1,1,1,2,2,3])
    #print hasDuplicates(arr)
    #print intersction([4,9,5], [9,4,9,8,4])
    #print twoSum(arr, 15)
    #print canChange("paper", "title")
    #buildDict("hayley")
    print firstUniqChar("leetcode")