1. 数据结构与算法
- 面试中对数据结构和算法的考察就是手写代码解决具体题目
- 这种解题的能力或者编程的能力是可以通过有意识的训练来提高的，即使你是一个菜到不行的菜鸟
- 科学训练包括了有目的的重复性训练、周期性总结
- 下面章节中的示例代码只是为了说明解题思路，更容易理解，所以他们不一定是最优的
1.1 第一阶段-重温基本数据结构
Tip: 我们大部分练习题目来自leetcode，请小伙伴们先行注册一下。
Tip: leetcode虽然现在已经上线了中文网站，但还是建议大家使用原版，顺便练习下英文理解能力
Note: 第一阶段计划我们通过尝试解决一些简单题目，帮大家熟悉常见的数据结构及其表达方式
- 我们会使用固定的流程（理解题目-画图-核心代码-完善边界条件-优化）去解决这些问题，目的是想帮助小伙伴们一开始就建立一个比较良好的思维习惯，解决一道题目的重点在于理清解题思路，对应的代码实现是一个熟能生巧的过程。有些小伙伴一见到题目，就急急忙忙去直接思考代码怎么实现。在初级阶段，我们不建议这么做。
Note: 小伙伴们的主要任务是把下面题目代码敲一遍提交到leetcode
Note: 这一阶段你可以过的比较放松，琢磨明白下面题目的示意图和代码的对应关系就可以了。
1.1.1 数组
217. Contains Duplicate
判断一个整数数组是否包含重复元素，包含返回true，否则返回false
1.举例子-画图-解题思路
总体思路是：将集合中元素两两比较
- 从第一个元素（5）开始依次与后面元素进行比较，5-6、5-7、5-6，没有重复元素
- 从第二个元素（6）开始依次与后面元素进行比较，6-7、6-6，发现相等元素（6），返回true
2. 写核心逻辑代码
通常涉及无序数组nums的两两元素比较，可以直接应用下面的双重循环框架：
for (int i = 0; i < nums.size(); ++i)
{
for (int j = i+1; j < nums.size(); ++j)
{
//判断逻辑
}
}
利用上个模板我们直接写出本题核心代码
for (int i = 0; i < nums.size(); ++i)
{
for (int j = i+1; j < nums.size(); ++j)
{
// 遇到相等的元素直接返回true
if (nums[j] == nums[i]) return true;
}
}
3. 完善边界条件并提交代码
除了核心逻辑外，边界条件的考虑是必不可少的一个环节，例如nums没有元素或者只有一个元素时候我们的代码应该返回什么结果。加上边界条件后的代码如下：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int n = nums.size();
if(n <= 1) return false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] == nums[i]) return true;
}
}
return false;
}
};
上述代码按Submit Solution按钮后，会提示： Submission Result: [Time Limit Exceeded]，意思是在验证一些特殊case时候算法超时了，需要我们优化算法
4. 更优方案
Tip: 上面的情况有些类似我们面试时候的套路：
面试套路.png
所以我们会想：如果在一个有序数组中查找重复数字是否能提高效率？
217-op.png
可以看到，不同于上面的双重循环，排序后只需要一次遍历中比较相邻元素是否相等就可以了。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
//边界条件
if(nums.size() <= 1)
return false;
//先对无序数组排序
sort(nums.begin(),nums.end());
//一次遍历，每个元素都与它前面的元素进行对比
for(int i = 1; i < nums.size(); ++i)
{
if(nums[i] == nums[i -1])
return true;
}
return false;
}
};
提交上面的代码，可以得到 Submission Result: [Accepted]的提示，意味着你已经在leetcode上提交了第一段验证通过的代码，恭喜下自己吧
剧透: 后面我们还会看到使用hash table来解决上面这个问题
5. 总节
- 我们知道了数组这一数据结构的表达方式（vector）
- 我们学到了第一个常用技巧：先排序再处理
- 我们使用了一个最简单的算法：双重循环
怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）
