面试之哈希表leetcode

1 案例1 leetcode-----242

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

示例 1:

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

python版本

方法1:直接排序

方法二:API map计数

方法三:数组模拟hash

 '''

 方法1 按照字母序排序 如果一样则是 时间复杂度是nlogN 快排

 方法2 数字符串每个字符串字符的个数，也就是使用map来计算{letter:count}

 a---->

 n---->

 r---->

 时间复杂度O(N) * 为O(N)

 '''

 class Solution(object):

     def isAnagram(self, s, t):

         """

         :type s: str

         :type t: str

         :rtype: bool

         """

         #方法一

         #return sorted(s)==sorted(t)

         #方法二

         '''

         dic1,dic2={},{}

         for item in s:

             dic1[item]=dic1.get(item,)+

         for item in t:

             dic2[item]=dic2.get(item,)+

         return dic1==dic2

         '''

         #方法三

         dic1,dic2=[]*,[]*

         for item in s:

             dic1[ord(item)-ord('a')]+=

         for item in t:

             dic2[ord(item)-ord('a')]+=

         return dic1==dic2

2 案例2 leetcode------1

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

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

示例:

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

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

 class Solution(object):

     def twoSum(self, nums, target):

         """

         :type nums: List[int]

         :type target: int

         :rtype: List[int]

         dict1={}

         for i in range(,len(nums)):

             num=target-nums[i]

             if num not in dict1:

                 dict1[nums[i]]=i

             else:

                 return [dict1[num],i]

         """

         hash_map=dict()

         for i,x in enumerate(nums):

             if target-x in hash_map:

                 return [i,hash_map[target-x]];

             hash_map[x]=i

3 案例3 leetcode---15

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

方法1：暴力求解三层循环时间复杂度n*n*n

方法2：c= -(a+b)枚举ab两层循环，然后在set中查询-(a+b) 时间复杂度n*n 多了空间复杂度n

方法3:sort find: 整个数组排序o(n*logn),首先先第一层循环取出第一个元素a,然后后面使用二分查找bc两个值，如果存在b+c=a则找到，时间复杂度O(N*N)

python版本:

 class Solution(object):

     def threeSum(self, nums):

         nums.sort()#先排序

         n = len(nums)

         res = []

         #print(nums)

         for i in range(n):

             if i >  and nums[i] == nums[i-]:

                 continue

             #左右边界

             left = i +

             right = n -

             while left < right:

                 cur_sum = nums[i] + nums[left] + nums[right]

                 if cur_sum == :

                     tmp = [nums[i],nums[left],nums[right]]

                     res.append(tmp)

                     #去掉重复的解

                     while left < right and nums[left] == nums[left+]:

                         left +=

                     while left < right and nums[right] == nums[right-]:

                         right -=

                     left +=

                     right -=

                 elif cur_sum > :

                     right -=

                 else:

                     left +=

         return res

c++版本

 class Solution {

 public:

     vector<vector<int>> threeSum(vector<int>& nums) {

          int target;

         vector<vector<int>> ans;

         sort(nums.begin(), nums.end());

         for (int i = ; i < nums.size(); i++) {

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

             if ((target = nums[i]) > ) break;

             int l = i + , r = nums.size() - ;

             while (l < r) {

                 if (nums[l] + nums[r] + target < ) ++l;

                 else if (nums[l] + nums[r] + target > ) --r;

                 else {

                     ans.push_back({target, nums[l], nums[r]});

                     ++l, --r;

                     while (l < r && nums[l] == nums[l - ]) ++l;

                     while (l < r && nums[r] == nums[r + ]) --r;

                 }

             }

         }

         return ans;

     }

 };

巴特西

面试之哈希表leetcode

最新文章

热门文章