今天带来的题目是这两天的每日一题和两道字符串的题目

232. 用栈实现队列 ， 225. 用队列实现栈 ， 3. 无重复字符的最长子串 ， 4. 寻找两个正序数组的中位数

232.用栈实现队列 题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空，返回 true ；否则，返回 false

作为栈和队列的基础题目，基本是每个人都必须要掌握的，在之前的代码随想录训练营里也做过这题，整体的思路还是比较简单的，主要熟悉栈和队列的结构以及具体的用法，这题就不难直接写出来。

但要想代码更加简洁高效，还是需要想一想的，这里面还是有点绕圈的。

用栈实现队列主要的方法就是使用两个栈，当一串数据放入栈后，从栈顶到栈底是这段数据的倒序，将栈顶的数据放入另一个栈中直至第一个栈空，这样第二个栈的出栈顺序就是这段数据的原本的顺序了，也和队列先进先出的顺序符合。

push函数只是单纯的存入数据，并不用其他操作。pop函数就需要使用到双栈的操作来模拟实现队列的移除操作了。按照题目描述，pop函数需要将函数的开头函数移除，即第一个放入队列的数。而在栈中第一个放入的数还在栈底待着不能直接移除，将栈中的数全部移至第二个栈中，第一个放入的数就跑到第二个栈的栈顶了，可以直接移除然后return这个数的值了。到了peek函数需要返回队列开头的元素，return的数其实和pop函数一样，只是少了一个移除元素的操作。

但如果执行pop函数之后，剩余的数还残留在第二个栈中，再有新的数加入到第一个栈中，这时候再执行pop函数，将第一个栈中元素放到第二个栈栈顶的话，栈顶元素其实就不是队列首个元素了，队列首个元素应该是栈顶元素的下一个。要解决这种问题，比较容易想到的就是，pop函数和peek函数执行完之后再将第二个栈中的元素全部返回第一个栈中。

int pop() {
        while (!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int value = st2.top();
        st2.pop();
        while (!st2.empty()){
            st1.push(st2.top());
            st2.pop();
        }
        return value;
    }

peek函数的实现和pop函数几乎一样只是没有了st2.pop()的操作。但是这样的代码未免也太过冗余，我们可以减少一些重复的操作将其优化。例如pop函数的操作内容完全是包含peek函数的操作的，我们可以在pop函数中引用peek函数。而在判断队列首元素的时候我们也可以发现，其实如果第二个栈中如果有元素的话，那么其栈顶元素一定就是队列的首元素，所以并不需要再将第二个栈中的元素返回到第一个栈中。

int peek() {
        if (!st2.empty()) return st2.top();
        if (st1.empty()) return -1;
        while (!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int value = st2.top();
        return value;
    }

需要注意的是最开始是两个if而不是if和else if，先判断栈二是否为空，如果为空，会再判断栈一是否为空。

int pop() {
        int value = this -> peek();
        st2.pop();
        return value;
    }

如需要引用同一类里的函数，需要加this ->。

最后的empty函数注意要同时判断栈一和栈二的empty()

bool empty() {
        return st1.empty() && st2.empty();
    }

225.用队列实现栈 题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 Falsey

用队列来实现栈相对来说就简单很多了，同样的也是push函数不用什么其他的操作，主要的操作还是在pop函数中，将数放入队列中，代表栈顶元素的应该是队尾的元素，要将其移除就需要将其移植队首，可以将与队首元素相等的值加入队列中，再将队首元素移除，循环size – 1次就可将原来的队尾元素移至队首。

int pop(){
        int size = que.size();
        size--;
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int value = que.front();
        que.pop();
        return value;
    }
至于剩下的top函数和empty函数就都很简单了，top函数需要求的值其实就是最后一个放入队列中的元素，直接返回队尾元素即可。
int top() {
        return que.back();
    }
   
    bool empty() {
        return que.empty();
    }

3.无重复字符的最长子串 题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例：
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

本题这里主要解析一下滑动窗口的做法，我们可以使用哈希表来存储遍历过的字符，因为哈希表的查找时间比较短，效率较高。

每遍历字符串里的一个字符，就要将其与哈希表中前面遍历过的值比较来判断是否出现过，如果出现过的话，不仅这一个前面出现过的字符需要移除，到这个字符之前的字符也要在哈希表中移除。比如第二个示例中，当遍历到pw时，这两个字符都会加入到哈希表中，到遍历下一个字符w时，我们会发现这个字符在前面出现过，那么我们需要将直到这个相同的字符之前的字符串都移除掉，这样才能保证遍历后面的字符串时能使最长的无重复子串。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        unordered_set<char> slip;
        int left = 0, maxStr = 0;
        for (int i = 0; i < s.size(); i++){
            while (slip.find(s[i]) != slip.end()){
                slip.erase(s[left]);
                left++;
            }
            maxStr = max(maxStr, i - left + 1);
            slip.insert(s[i]);
        }
        return maxStr;
    }
};

代码中left表示的就是滑动窗口的左边界，而不断向右遍历的整形i就是滑动窗口的右边界，当我们发现滑动窗口中出现了前面已经出现过的字符时，滑动窗口就会不断将元素自滑动窗口左端逐个移除，直到滑动窗口中没有与当前遍历的字符重复的元素。并在每次遍历时记录下滑动窗口的最大尺寸。

4.寻找两个正序数组的中位数 题目描述：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

本题算是字符串中很难的题了，看题解也费了不少的时间理解，有很多绕来绕去的地方，需要多代入数据算算才比较容易绕过来。

首先我们需要先明确中位数的定义，这里需要引入一个概念割（cut），割就是一个界限可以从中间将一个有序数组从中间分开，如果数组的大小是奇数的话，我们就可以从正中间那个元素割开，如数组[2,3,4],割就是3，会将数组分为两部分，左部分和右部分，可以得到一个左最大数和一个右最小数，顾名思义，他们分别是左部分的最大数和右部分的最小数，在这个数组中我们可以将左最大数和右最小数都定义成3。如果数组的大小是偶数的话，如[3,4,6,7],割就会产生在元素4和元素6之间，而左最大数就是4，右最小数就是6。

如果只有一个数组的话，我们可以直接的到左最大值Lmax和右最小值Rmin，可以用来确定中位数。

但如果是两个数组的话，也就是这道题的情景，我们会得到L1max, L2max, R1min, R2min四个值，这些值以及数组一中位数c1，和数组二中位数c2就是我们破解两个数组合并后的中位数的关键。如果我们分别找对了两个数组的割，我们就可以将两个数组的左部分和右部分分别融合在一起（不需要真的有融合的操作），取出左部分的最大值和右部分的最小值就可以求出中位数，但两个数组原本的割不能拿来确定融合后的数组的割。

按照正常的一个数组的情况下，我们需要做到的条件其实可以拆分成两个：

一是保证左部分和右部分的元素个数相同；

二是保证右部分的所有元素的值都要大于左部分。

要达到这两个条件的关键就在L1max, L2max, R1min, R2min这四个值上，保证右部分所有元素都大于左部分，就需要L1max < R2min并且L2max < R1min（L1max < R1min以及L2max < R2min原本就成立）

如果L2max > R1min，如下

[2 3 5] [1 4 / 7 9]

此时L1max = 3， R1min = 3, L2max = 4, R2min = 7，这时数组二的左最大值大于数组一的右最小值，不符合上述的条件二， 我们需要将数组二的割向左调整一个单位，但这样的话整体的左部分就减少了一个，我们为了满足上述的条件二，应该将数组的割也往右移一位。

[2 3 /5] [1 / 4 7 9]

但即使是这样我们也能够发现左部分和右部分的元素个数还是不相等，因为有些数组的大小是偶数，有些是奇数，为了统一奇偶，我们需要通过加虚拟‘#’来填充数组中每个元素之间的空位，使得原本大小为n的数组变成2n + 1，另一个数组的大小从m变为2m + 1，这样合并后的数组大小就为2n + 2m + 2，肯定是一个偶数。

[# 2 # 3 # 5 #] [# 1 # 4 # 7 # 9 #]

通过虚拟填充后，我们可以通过/2的方式来的到原本元素在原本数组中的下标。因为这个虚拟填充不会真的在数组中填入‘#’字符，只是放大下标后，通过下标/2的方式避免奇偶产生的变差。

比如元素2本来在位置0， 现在是位置1, 1/2后还是0.

比如元素3本来在位置1， 现在是位置3, 3/2后还是1.

比如元素5本来在位置2， 现在是位置5, 5/2后还是2.

对于割，如果割在‘#’上的话，就相当于在两个元素之间分割，割在一个元素上的话，想到于将这个元素分割到两个部分中。以下总是成立：

LMaxi 为 (Ci-1)/2 位置上的元素
RMini 为 Ci/2 位置上的元素

如割正好在元素3上，元素3现在的位置是3，L1max = nums[(3 – 1) / 2], R1min = nums[3 / 2]正好就是nums[1]，元素3原本的位置。

如果割在4和7之间，L2max = nums[(4 – 1) / 2] = nums[1], R2min = nums[4 / 2] = nums[2]正好分别就是元素4和元素7原本的位置。

剩下我们需要做的就比较简单了，把两个数组合并成一个新数组vec，再找到左最大值和右最大值，就能求出中位数了

vec[n + m + 1] = max(L1max, L2max)

vec[n + m + 2] = min(R1min, R2min)

n + m + 1即是合成后的新数组的左最大值的下标，n + m + 2即是合成后的新数组的右最小值的下标。

mid = (vec[n + m + 1] + vec[n + m + 2]) / 2 = (max(L1max, L2max) + min(R1min, R2min)) / 2

最后的最后的问题，就是我们应该如何去找到这个割呢，其实就是在找数组的中间位置，主要用二分法实现即可，为了减少计算的次数，我们应该使用较小的数组来进行计算。根据我们之前说的条件二保证右部分的所有元素的值都要大于左部分，只要确定了第一个数组的割c1，就能确定第二个数组的割c2。

如果L1max > R2min我们就需要使c1向左移，c2向右移 -> c1向左划分

如果L2max > R2min我们就需要使c1向右移，c2向左移 -> c2向右划分

如果说c1或者c2遍历到头了也没有找到符合条件的左最大值和右最大值怎么办？

假定n < m，可能出现以下四种情况：

1、c1 = 0——数组一整体都在右部分，所以所有值都比要求的中位数大，中位数在数组二中。也就是数组一割的左边为空，左最大值始终比数组二的右最小值大，这样的左最大值是不能参与中位数的计算的，所以可以将其假定为INT_MIN使数组二的左最大值能够参与中位数的计算。而R1min一定会比R2min大，一定不会妨碍到中位数的计算。

2、c1 = 2n——数组一整体都在右部分，所以所有值都比要求的中位数小，中位数在数组二中。也就是数组一割的右边为空，右最小值始终比数组二的右最小值小，这样的右最大值是不能参与中位数的计算的，所以可以将其假定为INT_MAX使数组二的右最小值能够参与中位数的计算。而L1min一定会比L2min大，一定不会妨碍到中位数的计算。

3、c2 = 0——数组2整体在右边了，所以都比中值大，中值在数组1中 ，简单的说就是数组2割后的左边是空了，所以我们可以假定LMax2 = INT_MIN

4、c2 = 2m—— 数组2整体在左边了，所以都比中值小，中值在数组1中, 简单的说就是数组2割后的右边是空了，为了让LMax1 < RMin2 恒成立，我们可以假定RMin2 = INT_MAX

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        if (n > m){
            return findMedianSortedArrays(nums2, nums1);
        }
        int Lmax1, Rmin1, Lmax2, Rmin2, c1, c2, lo = 0, hi = 2 * n;
        while (lo <= hi){
            c1 = (lo + hi) / 2;
            c2 = m + n - c1;

            Lmax1 = c1 == 0 ? INT_MIN : nums1[(c1 - 1) / 2];
            Rmin1 = c1 == 2 * n ? INT_MAX : nums1[c1 / 2];
            Lmax2 = c2 == 0 ? INT_MIN : nums2[(c2 - 1) / 2];
            Rmin2 = c2 == 2 * m ? INT_MAX : nums2[c2 / 2];

            if (Lmax1 > Rmin2){
                hi = c1 - 1;
            }
            else if (Lmax2 > Rmin1){
                lo = c1 + 1;
            }
            else break;
        }
        return (max(Lmax1, Lmax2) + min(Rmin1, Rmin2)) / 2.0;
    }
};

今天写的解析比较多，本来以为不用写很久的，但最后一题真的很复杂，要解释的东西太多了，一写就写了两三个小时了，花了这么多时间，至少自己的理解应该更到位了吧，主要是写到一半就停下会让我感到很不爽，就好像考试考到一半出去打游戏，中断的感觉很强烈，再回来写的话感觉会没什么心思。但今后还是要调整一下学习的比例，算法要减少一点，要多多学学stm32。

今日推荐歌曲：プラトー——sakanaction（点击左下角，倒数第五首歌即可收听）