iOS面试算法数据结构和算法分析

2019 算法面试相关(leetcode)--哈希表

2019-01-10  本文已影响0人  Theendisthebegi

哈希表相关的原理可以参考下:
浅谈哈希表(HashTable)
深入理解哈希表
哈希表的理解
理解HashSet及使用

哈希表最突出的优点就是查找时间复杂度是o(1),所以其应用场景多数为查找
哈希表和集合另一个特性是无重复,可以用来计数


1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]


这道题目也是leetcode第一题,我们可以利用哈希表,在哈希表中查找是否有target-nums[i],存在则返回,否则将nums[i]存入哈希表中

var twoSum = function(nums, target) {
    
    let dict = {}
    
    for (let i = 0; i < nums.length; i++) {

        if ((target - nums[i]) in dict) return [dict[target-nums[i]], i]

        dict[nums[i]] = i
    }
};
2. 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?


题目意思很简单,判断两个字符串是否有同样的字符,字符以及字符的数量都要相同。
我们同样可以用哈希表来解决,现将第一个字符串的字符及数量保存到哈希表中,然后去和第二个字符串对比,完全一致则返回true否则返回false。

var isAnagram = function(s, t) {

    let dic = {}

    for (const c of s) {

       dic[c] = (dic[c] || 0) + 1
    }

    for (const c of t) {
        
        if(c in dic) dic[c]--

        else return false
    }

    for (const key in dic) {
        
        if(dic[key] != 0) return false
    }

    return true
};

还有一种比较简单的写法,就是分别对两个字符串分别排序然后判断是否相同,不过只是写起来简单,实际时间复杂度是o(logn),比上边的方法效率要差一些,不建议这样写哈。

var isAnagram = function(s, t) {

    return s.split('').sort().join('') == t.split('').sort().join('')
};
3. 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]


var threeSum = function(nums) {
    
    nums.sort((a,b) => a - b)

    let result = []

    let resSet = new Set()

    for (let i = 0; i < nums.length - 2; i++) {
        
        let set = new Set()

        for(let j = i + 1; j < nums.length; j++){
            
            let target = 0-(nums[i] + nums[j])

            if(set.has(target)){

                let arr = [nums[i],nums[j],target]

                let tmp = arr
        
                tmp = tmp.sort().join(',')

                if(!resSet.has(tmp)){

                    result.push(arr)

                    resSet.add(tmp)
                }
                
            }else set.add(nums[j])
        }
    }

    return result
};

这种方法的时间复杂度是o(n^2),效率还是挺低。

var threeSum = function(nums) {

    nums.sort((a,b)=>a-b)
    
    let result = []

    for (let i = 0; i < nums.length; i++) {
        
        let target = -nums[i];

        if(target < 0) break;

        if(i>0 && nums[i]==nums[i-1]) continue;

        let j = i + 1,k = nums.length - 1

        while(j < k){

            
            if(nums[j] + nums[k] == target){
                
                while(j<k && nums[j] === nums[j+1])
                   ++j;
               
               while(j<k && nums[k] === nums[k-1])
                   --k;

                let pushArr = [nums[i], nums[j++],nums[k--]]

                result.push(pushArr)

            }else if (nums[j] + nums[k] < target) {
                
                j++;

            }else {
                
                k--;
            }
        }
    }

    return result
};

这种方法的时间复杂度同样是o(n^2),但不再需要用到set去保存,空间复杂度有优化。另外先排序的情况下会规避掉很多不必要的操作,也不需要再用set去去重,在测试用例不是特别大的情况下,实际运行起来要比上边的快不少

上一篇 下一篇

猜你喜欢

热点阅读