浅谈剑指Offer

相遇

如今的程序猿相关产业链已越发成熟。一个行业的成熟必然催生培训机构新专业的形成。培训机构成功扮演了工厂的角色。尽管培训机构能短时间制造出程序猿的外衣，但也由于是短时间制成，外衣的质量也必然有些许不尽人意。如何提升外衣的质量，从而提升获得Offer的机率呢。这就需要提前看看一些譬如《剑指Offer》攻略了。说到这，不得不感叹如今的线上学习环境真是好，只要想提升自己，总是能快速在线上找到适合自己的方式。从多个维度对自己进行不断打磨。LeetCode 上提供了剑指Offer的题库，初遇《剑指Offer》便是在LeetCode上。花了几天的时间将其题库刷完，后又花了几天时间翻了翻《剑指Offer》书。颇获得一些感悟，如今总结总结，供新人提供一点微不足道的信息。

相识

根据题型可将其分为这样几种类型：

1. 结构概念类（数组，链表，栈，堆，队列，树）
2. 搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）
3. 双指针定位类（快慢指针，指针碰撞，滑动窗口）
4. 排序类（快速排序，归并排序）
5. 数学推理类（动态规划，数学）

相知

结构概念类

结构概念类型的题，主要针对的是基础数据结构，只要能熟知基本的数据结构特点，并将其特点带入便可解。由下表统计的题型可以看出，考察数组主要在于简易版的MAP，进行对数据的简单统计。对于链表和树结构的考察主要在于遍历，遍历链表的方法主要是双指针，双指针分为快慢指针，碰撞指针。遍历树结构的方法主要是深度优先遍历和广度优先遍历。对于堆和队列结构的考察主要在于搜索，能快速搜索出目标值。

搜索遍历类

搜索遍历类属于基础算法，主要配合基本数据结构使用。深度优先遍历侧重的是破解迷宫的思想，从起点开始，沿着一条路径走，直到死胡同或者到达终点。广度优先遍历侧重的是画同心圆的思想，以同个圆心不同半径画圆。二分遍历侧重的是一半一半的思想，将有一定规律的数据根据不同的特征进行一半一半的排除。

深度优先遍历

深度优先遍历代码多采用递归的思想实现，递归采用的系统栈，系统栈有个特点便是将当前环境和系统变量保存到寄存器中，然后走下一步，如果下一步走到了死胡同那还可以恢复环境，从而可以尝试另一条路径。

void dfs(int 下一步){if(走到死胡同||走到终点)return;//回头dfs(下一步+1);
}
int main(){dfs(第一步);
}

广度优先遍历

广度优先遍历代码多采用队列的思想实现，队列的特点是先入先出，而广度优先遍历就如一笔画游戏一般，不会重复访问某个节点。

void bfs(int s){queue<int> q;q.push(s);while(!q.empty()){取出队首节点top;访问队首节点top;将队首元素出队;将top的下一层节点中未曾入队的节点全部入队，并设置为已入队;}
}

二分遍历

二分遍历使用的场景多为 已排序好 数据的数组，二分遍历代码多采用三指针，指向数据的头部、尾部、中部，通过中部数据和尾部数据或头部数据的比对确定下一半遍历的位置。

void binarySearch(vector<int> nums){int low = 0;int high = nums.size() - 1;int mid;while (low < high) {mid = low + (high - low) / 2;if (nums[mid] < nums[high]){high = mid;}else if (nums[mid] > nums[high]){low = mid + 1;}else {break;}}
}

双指针定位类

双指针定位类的题，主要针对的链表的遍历，或是动态查找一定范围内的最大、最小值。下面介绍3种双指针类型。

快慢指针

快慢指针指的是两个指针以 同起点不同步长 进行运动，或是以 不同起点相同步长 进行运动。同起点不同步长一般用于判断链表是否是环形链表，不同起点相同步长可用于获得相隔距离的数据。

1. 不同起点相同步长（22-链表中倒数第k个节点）

ListNode* getKthFromEnd(ListNode* head, int k) {ListNode* low = head;ListNode* fast = head;int cnt = 0;while (fast!=NULL){if (cnt > k-1){low = low->next;}fast = fast->next;cnt++;}return low;
}

2. 相同起点不同步长

bool hasCircle(Node *head)
{if(head == NULL)return false;Node *slow = head, *fast = head;while(fast != NULL && fast->next!=NULL){slow = slow->next; fast = fast->next->next;if(slow == fast)return true;}return false;
}

指针碰撞

指针碰撞指的是两个指针分别处于数组或链表的一头一尾，相向而行，直到碰撞。（57-和为s的两个数字）

vector<int> twoSum(vector<int>& nums, int target) {vector<int> ans;int left = 0, right = nums.size() - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {ans.push_back(nums[left]);ans.push_back(nums[right]);break;} else if (sum < target) {left++;} else {right--;}}return result;
}

滑动窗口

滑动窗口法，可以用来解决在连续区间上查找符合某个条件数据的问题，当区间发生变化时，可以通过旧的计算结果对其搜索空间进行剪枝，降低了时间复杂度。现提供两种滑动窗口的应用场景。

1. 纯双指针（48-最长不含重复字符的子字符串）

int lengthOfLongestSubstring(string s) {map<char, int> mp;int ans = 0, left = 0, right = 0;while (right < s.size()) {if (mp.find(s[right]) != mp.end()) {left = max(left, m[s[right]] + 1);}mp[s[right++]] = right;ans = max(right - left, ans);}return ans;}

这道题采用了双指针的方式，通过制造一个窗口，窗口的右端不断的向右滑动，根据窗口右端的数据判断是否扩大或者缩小窗口，缩小窗口也只能通过左端右移，扩大窗口只能通过右端右移。这也凸显了滑动窗口的特点：右端扩大，左端缩小

2. 滑动窗口+单调队列（59-I-滑动窗口的最大值）

vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;deque<int> tem;for(int i=0; i<nums.size(); ++i){while(!tem.empty() && nums[i]>nums[tem.back()]){   tem.pop_back();}if(!tem.empty() && tem.front()<i-k+1){tem.pop_front();}tem.push_back(i);if(i>=k-1){res.push_back(nums[tem.front()]);}}return res;
}

这道题采用滑动窗口的方式遍历数组，通过单调队列的结构记录未来可能的最大值。因为本题中连续区间的长度是固定的，而每次窗口向右移动的步长都为1，因此用i表示即可。

排序类

排序类的思想很关键，快速排序关键在于 分离，先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。也是 一分为二 的思想。归并排序关键在于 合并，先使每个子序列有序，再使子序列段间有序，最后将其合并。也是 合二为一 的思想。

快速排序

快速排序的一分为二的分离思想可以用在 39-数组中出现次数超过一半的数字 场景中。随机选择一个数字，然后使得此数字左边的数字都小于此数字，右边都大于此数字，若选中的数字最后存在的下标为n/2，则为中位数，若下标小于n/2，中位数则位于其左边，若下标大于n/2，中位数则位于其右边。

快速排序模板

int Partition(int data[], int length, int start, int end){if(data==NULL||length<=0||start<0||end>=length){throw new std::exception("Invalid Parameters");}int index = RandomInRange(start, end);Swap(&data[index], &data[end]);int small=start-1;for(index=start;index<end;++index){if(data[index]<data[end]){++small;if(small!=index)Swap(&data[index],&data[small]);}}++small;Swap(&data[small],&data[end]);return small;
}
void QuickSort(int data[], int length, int start, int end){if(start==end){return;}int index=Partition(data,length,start,end);if(index>start){QuickSort(data,length,start,index-1);}if(index<end){QuickSort(data,length,index+1,end);}
}
int main(){int data[n];QuickSort(data,n,0,n-1);
}

合并排序

合并排序的合二为一的合并思想可以用在 51-数组中的逆序对 场景中。先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目，在统计逆序对的过程中，还需要对数组进行排序。

合并排序模板

const int maxN = 100010;
int arr[maxN];
void merge(int L1, int R1, int L2, int R2){int i = L1;int j = L2;int idx = 0;int tmp[maxN];while(i<=R1 && j<=R2){if(arr[i]<arr[j]){tmp[idx++] = arr[i]; }else{tmp[idx++] = arr[j];}}while(i<=R1){tmp[idx++] = arr[i];}while(j<=R2){tmp[idx++] = arr[j];}for(int k=0; k<idx; k++){arr[L1+k] = tmp[k];}
}
void mergeSort(){for(int step=2; step/2<maxN; step*=2){for(int i=0; i<N; i+=step){int mid = i+step/2-1;if(mid+1<N){merge(i, mid, mid+1, min(i+step-1, maxN-1));}}}
}

相离

《剑指Offer》是个不错的面试指南，从如何理解面试题到如何将抽象问题具体化，从如何基本解决问题到如何深度优化问题都介绍的十分详细。但要形成这样的思维方式还是得多看题多做题多总结题型才能达到。一起加油吧！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！