神刀安全网

怎样应对IT面试与笔试-(六)

1.2 第二阶段-常用算法技巧

第一阶段主要是帮小伙伴们熟悉了基本的数据结构,第二阶段我们的关注点在于怎么利用这些数据结构去解决面试题目。这个过程中小伙伴们会看到一些常用的解题“套路”,学会这些“套路”会一定程度上提升你的解题效率。

  • Note 第二阶段我们先出给代码,再用实例去解释,小伙伴们可以尝试先自己阅读分析下代码,希望通过这阶段学习,能提升小伙伴们读懂代码的能力。

暴力搜索,先排序(sort )和 哈希表Hash table(unordered_set)

217. Contains Duplicate

判断一个整数数组是否包含重复元素,包含返回true,否则返回false

重新回忆下217的解题思路:
(1)题目要求寻找数组中的循环元素,按照一般思路,我们自然会想到从数组第一个元素开始循环比较,穷举情况来看是否有符合题目要求的组合。循环遍历穷举可能性这就是一种暴力搜索的算法思想。
(2)在优化部分,分析发现数组本身的无序导致了要用双重循环O(N^2)才能完成穷举。如果数组是有序状态,那么穷举可以在一遍循环O(N)就完成,这样就大大节省了搜索时间。所以在一些情况下,处理前先排序也是一种算法技巧,能提高暴力搜索的效率。
(3)现在我们介绍第三种做法,利用基于哈希表实现的unorderd_set容器来处理

  • C++ 11中对unordered_set描述大体如下:无序集合容器(unordered_set)是一个存储唯一(unique,即无重复)的关联容器(Associative container),容器中的元素无特别的秩序关系,该容器允许基于值的快速元素检索,同时也支持正向迭代。
  • 在一个unordered_set内部,元素不会按任何顺序排序,而是通过元素值的hash值将元素分组放置到各个槽(Bucker,也可以译为“桶”),这样就能通过元素值快速访问各个对应的元素(均摊耗时为O(1))。
class Solution { public:     bool containsDuplicate(vector<int>& nums) {         if(nums.size() <= 1)             return false;         unordered_set<int> temp;         for(int i = 0; i < nums.size(); ++i)         {             //利用unordered_set的count方法可以判断当前元素是否已经在容器中             if(temp.count(nums[i]) != 0)                 return true;             else              //将元素放到容器中                 temp.insert(nums[i]);         }                  return false;     } }; 

以5,6,7,6为例
(1)i=0时,temp中找不到5(nums[0),将5放到temp中
(2)i=1时,temp中找不到6,temp中包含5,6
(3)i=2时,temp中找不到7,temp中包含5,6,7
(4)i=3时,temp中找到了6,直接返回true

哈希表Hash table(unordered_map)

除了unordered_set,还有一种更为常用的基于哈希表的数据结构unordered_map

  • 无序映射表(Unordered Map)容器是一个存储以键值对组合而成的元素的关联容器(Associative container),容器中的元素无特别的次序关系。该容器允许基于主键地快速检索各个元素。

1. Two Sum

给一个数组和一个目标值target,要求在数组中找到两个元素相加等于target,返回这两个元素的下标。我们可以假设每个数组只有一个解。
例如:
nums = [2, 7, 11, 15], target = 9,
nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

能直接想到的解题思路类似做过的217题目,可以用暴力搜索来解决:

class Solution { public:     vector<int> twoSum(vector<int>& nums, int target) {         vector<int> result;         if(nums.size() < 2)             return nums;         for(int i=0; i < nums.size();++i)         {             for(int j=i+1; j < nums.size(); ++j)             {                 if(nums[i] + nums[j] == target)                 {                     result.push_back(j);                     result.push_back(i);                     return result;                 }             }         }     } }; 

来一起看下unordered_map解题思路。仍旧以2, 7, 11, 15(下标依次为0,1,2,3)为例:

class Solution { public:     vector<int> twoSum(vector<int> &numbers, int target) {     unordered_map<int, int> hash;     vector<int> result;     for (int i = 0; i < numbers.size(); i++) {         int numberToFind = target - numbers[i];         if (hash.count(numberToFind) != 0) {             result.push_back(hash[numberToFind]);             result.push_back(i);                         return result;         }         hash[numbers[i]] = i;     }     return result; } }; 

(1)ordered_map中的key是数组中的元素,value是元素对应的下标,例如2是key,0是value
(2)i = 0时候,numberToFind =9-2 = 7,hash里没有key为7的元素,所以把键值对(2—0)放入hash
(3)i = 1时候,numberToFind = 9-7 = 2,hash里通过count方法查到有key为2的元素,并且知道2对应的索引为0,至此把找到的索引放入vector中

Tow Pointers(辅助指针)

167. Two Sum II – Input array is sorted(类似题目还有141)

上面那道1.Tow Sum题目的衍生题目,数组变为升序排列,找出两个元素和等于target,并返回元素的下标(从1开始,而不是从0开始),题中限定只有一个解。
例子:
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

class Solution { public:     vector<int> twoSum(vector<int>& numbers, int target) {         int l = 0, r = numbers.size() - 1;         while (l < r) {             int sum = numbers[l] + numbers[r];             if (sum == target) return {l + 1, r + 1};             else if (sum < target) ++l;             else --r;         }         return {};     } }; 

以2,7,11,15为例
(1)l=0,r=3,sum=2+15=17,17>9,r=2
(2)l=0,r=2,sum=2+11=13,13>9,r=1
(3)l=0,r=1,sum=2+7=9,9==9,return 0+1,1+1

怎样应对IT面试与笔试-(六)

怎样应对IT面试与笔试-(一)
怎样应对IT面试与笔试-(二)
怎样应对IT面试与笔试-(三)
怎样应对IT面试与笔试-(四)
怎样应对IT面试与笔试-(五)
怎样应对IT面试与笔试-(五-1)
怎样应对IT面试与笔试-(六)
怎样应对IT面试与笔试-(七)
怎样应对IT面试与笔试-(八)
怎样应对IT面试与笔试-(九)
怎样应对IT面试与笔试-(十)
怎样应对IT面试与笔试-(十一)
怎样应对IT面试与笔试-(十二)
怎样应对IT面试与笔试-(十三)
怎样应对IT面试与笔试-(十四)
怎样应对IT面试与笔试-(十五)
怎样应对IT面试与笔试-(十六)

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 怎样应对IT面试与笔试-(六)

分享到:更多 ()