2020年真是不平凡的一年，对于我这种考研复试党更是如此。不知道今年复试是否会改为线上，但随着疫情的好转，我觉得线下的可能性还是大一些，为了准备线下的机试，每天都写几道LeetCode。我之前准备的主要是CCF认证（可以抵机试分数），结果今年这个情况我不敢肯定CCF在复试前还有没有，所以现在还是回归LeetCode了。本文挑选了最近做的几道比较有代表性的（各道题都是一种思路的代表题型或者难题）。
二分思想
这道题我感觉算比较难的了，因为题目限制了时间复杂度为 O(log(m + n)) ，必须要用二分法做，但具体怎么二分操作，我想了好久都没想出来，在一个b站up主的视频（https://www.bilibili.com/video/av93694189 ）里才找到思路
题目如下
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
给定两个大小为 m 和 n 的有序数组nums1和nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设nums1和nums2不会同时为空。
示例 1:
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
题目要求时间复杂度为O(log(m + n))。基本可以确定本题应该用二分查找，对于数组arr的中位数，如果数组长
度为len，len为奇数，则中位数为第（len+1）/2 位，如果len为偶数，我们需要知道第 len/2和 len/2+1 个数。
我们需要找出两个排序数组的第k个数的问题。比较两个数组的第k/2位，然后将第k/2位较小的数组中的前k/2位删除。
然后继续此过程
** 举个例子**
A={1,3,4,9} lenA=4 B={1,2,3,4,5,6,7,8,9} lenB=9 lenA+lenB=13 ，因此找第7个数
7/2 = 3 A的第3个数为4，B的第3个数为3， 因此接下来A={1,3,4,9} B={4,5,6,7,8,9} 找第7-3=4个数，
4/2=2 A的第2个数为3，B的第3个数为6， 因此接下来A={4,9} B={4,5,6,7,8,9} 找第4-2=2个数，
2/2=1 A的第1个数为4，B的第1个数为4， 因此接下来A={4} B={5,6,7,8,9} 找第2-1=1个数，
现在找第1个数，比较A[0]和B[0]谁更小即可，因此最后结果为4
代码如下（C++）（这个代码在我原来的代码上进行了修改，我当时删除元素用的是vector的erase，这样会超时，这个代码学习了别人的写法，他用了i,j标记了vector的起点，避免了删除操作）
//找到两个数组中第k小的元素，i和j分别表示两个数组的起点，这样可以避免对数组元素进行删除操作
int findK(vector nums1, int i, vector nums2, int j, int k) {
if (i >= nums1.size())
return nums2[j + k - 1];
if (j >= nums2.size())
return nums1[i + k - 1];
if (k == 1)
return nums1[i] < nums2[j] ? nums1[i] : nums2[j];
//计算每次比较的两个数的值，来决定删除哪边的元素
int mid1 = (i + k / 2 - 1) < nums1.size() ? nums1[i + k / 2 - 1] : INT32_MAX;
int mid2 = (j + k / 2 - 1) < nums2.size() ? nums2[j + k / 2 - 1] : INT32_MAX;
//通过递归删除前k/2个元素
if (mid1 < mid2)
return findK(nums1, i + k / 2, nums2, j, k - k / 2); //nums1被删除部分
return findK(nums1, i, nums2, j + k / 2, k - k / 2);
}
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int lenA = nums1.size();
int lenB = nums2.size();
int len = lenA + lenB;
int left = (len + 1) / 2;
int right = (len + 2) / 2; //len为奇数时left和right为同一个数
return (findK(nums1, 0, nums2, 0, left) + findK(nums1, 0, nums2, 0, right)) / 2;
}
滑动窗口
滑动窗口本来是计算机网络里的一种流量控制技术。但是这道题用滑动窗口可以减少时间复杂度，算是一种学科互通吧。
题目
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
这里要说明一下，我的代码看起来不是很简洁，但是我的思路和LeetCode官方题解里的滑动窗口思想是比较接近的，只不过我用了一个字符串把滑动窗口存储起来了，而且我的map在运行的过程中需要维护，运行不会超时，我的代码（C++）如下
int lengthOfLongestSubstring(string s) {
int len = s.length();
string temp;
unordered_map<char, int> dict;
int maxLen = 0;
for (int i = 0; i < len; i++) {
char c = s[i];
auto iter = dict.find(c);
if (iter == dict.end()) {
dict.insert({ c,temp.length() });
temp += c;
}
else if (iter->second >= temp.length() || temp[iter->second] != iter->first) {
iter->second = temp.length();
temp += c;
}
else {
int cut = iter->second + 1;
temp = temp.substr(cut, temp.length() - cut);
for (auto& idx : dict) {
idx.second -= cut;
}
iter->second = temp.length();
temp += c;
}
maxLen = temp.length() > maxLen ? temp.length() : maxLen;
}
return maxLen;
}官方的Java滑动窗口代码
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
//如果滑动窗口中不包含s[j]
set.add(s.charAt(j++));
//那么滑动窗口长度就+1
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
//否则就不j++而是i++以缩减滑动窗口，直至
//前面的重复元素被移除出窗口
}
}
return ans;
}双端BFS
这个题的思路是真的新颖，双端的意思是为了降低时间复杂度，从起点BFS或者从终点反向BFS，取决于哪边元素更少，直到二者有共同的元素为止，这个题我自己的超时了，大佬的思路是真的6。下面是题目和大佬的代码
题目
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2:
输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
两端搜索。本题是需要从beginWord转换为endWord。上一份笔记严格按照这个要求，进行转换，结果为88ms。
本条笔记采用两端搜索对上一份笔记进行了优化。两端搜索也就是说：“一头从beginWord转换为endWord，另外一头从endWord转换为beginWord。”为什么要这么做呢？有什么意义呢？
举个例子：
假设从beginWord转换为endWord，存在于字典中的，（第一个）中间结果有30个。
而，从endWord转换为beginWord，存在于字典中的，（第一个）中间结果只有2个。
那么，很显然。从endWord开始会更快。所以，每次都从个数少的那块开始替换一位。
因此，我们每次都从中间结果少的那一端出发，这样就能剪枝掉很多不必要的搜索过程。
以下优化结果16ms。
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordDict(wordList.begin(), wordList.end());
if (wordDict.find(endWord) == wordDict.end()){
return 0;//Not FOUND 404
}
unordered_set<string> beginSet{beginWord};
unordered_set<string> endSet{endWord};
int step = 1;
for (; !beginSet.empty();){
unordered_set<string> tempSet;
++step;
for (auto s : beginSet) {
wordDict.erase(s);
}
for (auto s : beginSet) {
for (int i = 0; i < s.size(); ++i){
string str = s;
for (char c = 'a'; c <= 'z'; ++c){ //每次只改一个字母
str[i] = c;
if (wordDict.find(str) == wordDict.end()){
continue;
//和map一样 如果find没找到 返回的就是end()
}
if (endSet.find(str) != endSet.end()){
return step;
//在endSet中找到，说明两端相碰，路径已通
}
tempSet.insert(str);
}
}
}
if (tempSet.size() < endSet.size()){
beginSet = tempSet;
} else {
beginSet = endSet;
endSet = tempSet;
}
}
return 0;
}