数据结构和算法的课程讲解，目前已告一段落，也算是完成了自己的一个心愿。因为去年听某同学抱怨过，说自己去爱奇艺面试，其他问题都答得不错，面试官问了一个哈夫曼算法的题没答出来，后来面试官很明确的说，我们还是想找一个会些算法基础的。
如果之前有学过数据结构和算法，建议大家不定时的去刷刷算法题，因为从面试的角度来讲，目前 BAT 和 TMD 等一线互联网企业或多或少都会有几个算法题，而对应届毕业生来说算法的要求度则更高。当然大家面试过程中遇到的算法题，90%都来自于各大刷题网站。另一方面从开发的角度来讲，数据结构和算法绝对是一门内功，思维方式和严谨程度上都会有一个跳跃性的提升。就在前几天团队出现了两个疑难杂症，一个是小米手机的 View 数据丢失的 Bug，一个是直播间高斯模糊算法的卡顿。解决问题时若我们能站在底层源码和算法的角度去分析问题，绝对会要轻松许多。
在线编程评测的平台有很多，比较有名的有 Hihocoder，LintCode，LeetCode。我们一般在 LeetCode 上刷题比较多，目前有九百多道题目。不必每道题都刷，但建议至少把前 200 道刷一遍。不要看标签，不要看标签，标签相当于问题的分类，看了标签就会往那个方向去想，不利于自主思考。如果目前正处于面试阶段建议每天刷两三题，如果目前是工作状态可以不定时的刷一刷。LeetCode 的题型都非常简单明了，并不需要复杂的理解，一般都在几十行以内就可以解决了，如果你写了上百行代码，就肯定说明你想太多了或太复杂，虽然都能用很短的代码就能解决，但并不意味着 LeetCode 的题目非常简单，实际上LeetCode 基本上涉及到了所有常规的算法类型。
独立解决一个问题是最好的学习途径。如果你被某一个地方卡住了，不要急着去网上找答案，不管代码写得有多么烂先想办法实现，然后再想想有没有更好的方案，最后再去参考参考他人的实现方式。切记不是为了简单的实现，而是去想有没有更好的解决方案。请看第一题：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
这道题从通过率来看已经比较高了，题目本身也非常简单，用暴力破解即可：
public int[] twoSum(int[] nums, int target) {
for(int i=0;i<nums.length;i++){
for(int j= i + 1;j<nums.length;j++){
if(nums[i]+nums[j] == target){
return new int[]{i,j};
}
}
}
return null;
}
单从结果上来看是通过了，但切记不是为了简单的实现，而是去想有没有更好的解决方案。就好比现在有一个棘手的问题摆在咋们面前，我们的追求只是简单去实现，还是应该想想有没有更好的解决方案呢？再想想：
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> maps = new HashMap<>(nums.length);
for(int i=0;i<nums.length;i++){
int diff = target - nums[i];
if(maps.containsKey(diff)){
return new int[]{maps.get(diff),i};
}
maps.put(nums[i],i);
}
return null;
}
从上面来看，该题算法的复杂度可以优化到 O(n) ，那为何测试结果却显示未达最优？我们之前分析 HashMap 的源码时，可知其查找算法的复杂度，最好的情况是 O(1) 最坏是 O(logN) 。因此我们还可以有更好的解决方案：
public int[] twoSum(int[] nums, int target) {
Integer[] filter = new Integer[4096];
int length = nums.length;
int diff = 0;
for(int i=0;i<length;i++){
diff = target - nums[i];
Integer index = filter[diff&4095];
if(index != null){
return new int[]{index,i};
}
filter[nums[i]&4095] = i;
}
return null;
}
8. String to Integer (atoi)
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
- Only the space character ' ' is considered as whitespace character.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
这题也是鹅厂面试题中的一道高频算法题，题目本身并不难，但从通过率上来看却是一道极低的题目，主要考察的是我们思考问题的时候是否严谨。好比我们在公司完成了一个需求，测试没问题，灰度也没问题，但上线就出现问题了。某部分原因也是我们在做需求的时候很多场景没有考虑到，在公司老大最喜欢说的口头禅之一就是 “你这样写有坑”。
int myAtoi(string str) {
long result = 0;
int len = str.length();
int index = 0;
// 过滤空格
while(index<len && str[index] == ' '){
index++;
}
// 正负符号
int negative = 1;
if(index<len && str[index] == '+'){
index++;
}
else if(index<len && str[index] == '-'){
negative = -1;
index++;
}
if(index == len){
return 0;
}
// 计算结果
while(index<len){
char c = str[index++];
if(c<'0' || c>'9'){
break;
}
result = result*10 + (c-'0');
// 处理越界的情况
if(negative*result > INT_MAX)
return INT_MAX;
else if(negative*result < INT_MIN)
return INT_MIN;
}
return result*negative;
}
视频链接：https://pan.baidu.com/s/1onpWrPBrS3cvnMmc9FzJhQ
视频密码：txq8
