剑指offer题解c++版(二)

3，栈队列堆

9-用两个栈实现队列

剑指 offer 面试题9

用两个栈实现队列, 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

解题思路：

• in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。
• 当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。

C++代码：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        int res;
        if(stack2.empty()){
            while(!stack1.empty()){
                int temp = stack1.top();
                stack1.pop();
                stack2.push(temp);
            }
        }
        res = stack2.top();
        stack2.pop();
        return res;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

30-包含 min 函数的栈

30-包含 min 函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路：

• 数据栈 A ： 栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
• 辅助栈 B ： 栈 B 中存储栈 A 中所有 非严格降序 的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。

C++代码：

class MinStack {  // 利用辅助栈
private:
    stack<int> stack1;
    stack<int> stack2;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    void push(int x) {
        stack1.push(x);
        if (stack2.empty()) {
            stack2.push(x);
        }
        else {
            if (x < stack2.top()) {
                stack2.push(x);
            }
            else {
                stack2.push(stack2.top());
            }
        }
    }
    void pop() {
        stack1.pop();
        stack2.pop();
    }

    int top() {
        return stack1.top();
    }

    int min() {
        return stack2.top();
    }
};

31-栈的压入、弹出序列

31-栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

解题思路：

C++代码实现：

// 剑指offer31: 栈的压入、弹出序列
class Solution { // 辅助栈解法，时间超过 77.62%，空间超过 74.84%
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int k = 0;
        stack<int> st;
        for(int i=0; i<pushed.size();i++){
            st.push(pushed[i]);
            for(int j=k;j<=i;j++){
                int temp = popped[j];
                if(temp == st.top()){
                    k++;
                    st.pop();
                }
                else{
                    break;
                }
            }
        }
        if(k==popped.size()) return true;
        else return false;
    }
};

40-最小的 K 个数

40-最小的 K 个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解题方法：

1. 数组原地排序法：对原数组从小到大排序后取出前 k 个数即可。时间复杂度：O(nlog n)，空间复杂度：O(log n)。
2. 使用最大堆结构：优先队列(最大堆，优先输出最大数)。时间复杂度：O(nlongk), 插入容量为k的大根堆时间复杂度为O(longk), 一共遍历n个元素；空间复杂度：O(k)。
3. 快速排序算法：TODO.

C++代码：

// priority_queue<Type, Container, Functional>  // 默认定义最大堆
// priority_queue<int, vector<int>, greater<int> >p;  // 定义最小堆

class Solution {
public:
    // // stl 自带的 sort() 排序算法
    vector<int> getLeastNumbers1(vector<int>& arr, int k) {
        vector<int> ret(k, 0);
        sort(arr.begin(), arr.end());
        for(int i=0;i<k;++i){
            ret[i] = arr[i];
        }
        return ret;
    }
    // 大顶堆维护小顶堆的方法
    vector<int> getLeastNumbers2(vector<int>& arr, int k) {
        vector<int> vec(k,0);
        if(k==0)
            return vec;
        priority_queue<int> heap;  // 大顶堆，堆顶为最大值
        for(int i=0;i<(int)arr.size();i++){
            if(i<k){
                heap.push(arr[i]);
            }
            else{
                if(heap.top() > arr[i]){  // 使用大顶堆来维护最小堆
                    heap.pop();
                    heap.push(arr[i]);
                }
            }
        }
        for(int i=0;i<k;i++){
            vec[i] = heap.top();
            heap.pop();
        }
        return vec;
    }
    // 直接使用小顶堆
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k,0);
        if(k==0)
            return vec;
        priority_queue<int, vector<int>, greater<int> > heap; // 小顶堆，堆顶为最小值
        priority_queue<int> heap2; // 大顶堆，堆顶为最大值
        for(int i=0;i<(int)arr.size();i++){
            heap.push(arr[i]);
        }
        for(int i=0;i<k;i++){
            vec[i] = heap.top();
            heap.pop();
        }
        return vec;
    }
};

41.1-数据流中的中位数

41.1-数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。例如，[2,3,4] 的中位数是 3；[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

解题方法：

数据流左半边的数用大顶堆，右半边的数用小顶堆，中位数由两个堆的堆顶元素求得。

C++代码：

class MedianFinder {  // 大根堆+小根堆 解法，时间超过 99..38%，空间超过 18.07%
private:
    // 从左到右，数据依次从大到小
    priority_queue<int> right; // 大顶堆，堆顶为最大值
    priority_queue<int, vector<int>, greater<int> > left; // 小顶堆，堆顶为最小值

public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    void addNum(int num) {
        // 插入数据要始终保持两个堆处于平衡状态，即较大数在左边，较小数在右边
        // 两个堆元素个数不超过 1
        if(left.size() == right.size()){
            right.push(num);
            left.push(right.top());  // 保证左边堆插入的元素始终是右边堆的最大值
            right.pop();  // 删除堆顶元素
        }
        else{
            left.push(num);
            right.push(left.top());
            left.pop();
        }
    }
    double findMedian() {
        if(left.size() == right.size()) return (left.top() + right.top())*0.5;
        else return left.top()*1.0;
    }
};

41.2-字符流中第一个不重复的字符

41.2-字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数

string caseout = “”;
1.读入测试用例字符串 casein
2.如果对应语言有 Init()函数的话，执行 Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
4. 输出 caseout，进行比较

返回值描述：

如果当前字符流没有存在出现一次的字符，返回 # 字符。

解题思路（参考牛客网题解）：

1. 对于“重复问题”，惯性思维应该想到哈希或者set。对于“字符串问题”，大多会用到哈希。因此一结合，应该可以想到，判断一个字符是否重复，可以选择用哈希，在 c++ 中，可以选择用 unordered_map<char, int>。
2. 对于字符流，源源不断的往池子中添加字符，然后还要返回第一个满足什么条件的字符，显然设计到了“顺序”，也就是先来的先服务，这种先进先出的数据结构不就是队列嘛。因此，这里可以用队列 queue。

算法过程如下：

1. 初始化一个哈希表 unordered_map<char, int> mp 和队列 queue<char> q。
2. 对于 void Insert(char ch) 字符插入函数的实现，当且仅当 ch 是第一次出现，则将 ch 添加到队列中；同时，不管 ch 是不是第一次出现，都需要在 mp 中更新一下字符的出现次数，方便后续判断字符是否是第一次出现。
3. 对于 char FirstAppearingOnce() 函数，通过哈希表 mp 判断队列 q 的头部元素的出现次数，如果是 1 则返回对应字符 ch；如果不是 1，则队列 pop() 弹出头部元素继续判断下一个字符。

class Solution
{
public:
  //Insert one char from stringstream
    queue<char> q;
    unordered_map<char, int> mp;
    void Insert(char ch)
    {
         // 如果是第一次出现，则添加到队列中
         if (mp.find(ch) == mp.end()) {
             q.push(ch);
         }
         // 不管是不是第一次出现，都进行计数
         ++mp[ch];
    }
    // return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while (!q.empty()) {
            char ch = q.front();
            // 拿出头部，如果是第一次出现，则返回
            if (mp[ch] == 1) {
                return ch;
            }
            // 不是第一次出现，则弹出，然后继续判断下一个头部
            else {
                q.pop();
            }
        }
        return '#';
    }
};

59-滑动窗口的最大值

剑指offer 59-滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

解题方法：

1. 对于每个滑动窗口，可以使用 O(k) 的时间遍历其中的每一个元素，找出其中的最大值。对于长度为 n 的数组 nums 而言，窗口的数量为 n-k+1，算法的时间复杂度为 $O((n-k+1)\ast k)=O(n\ast k)$。
2. 维护单调递减的双端队列！如果发现队尾元素小于要加入的元素，则将队尾元素出队，直到队尾元素大于新元素时，再让新元素入队，从而维护一个单调递减的队列。

C++代码：

class Solution {
public:
    // 简单方法：遍历滑动窗口找最大值，合理选择区间,时间超出限制
    vector<int> maxSlidingWindow2(vector<int>& nums, int k) {
        vector<int> ret;
        if (nums.size() == 0 && k == 0) return ret;
        for (int i = 0; i <= nums.size() - k; i++) {
            int maxNum = nums[i];
            for (int j = i; j < (i + k); j++) {
                if (nums[j] > maxNum)
                    maxNum = nums[j];
            }
            ret.push_back(maxNum);
        }
        return ret;
    }
    // 维护一个单调队列，队头是最大值
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        deque<int> window;  // 创建双端队列,单调递减的队列
        // 先将第一个窗口的值按照规则入队
        for (int i = 0; i < k; i++) {
            while (!window.empty() && window.back() < nums[i]) {
                window.pop_back();
            }
            window.push_back(nums[i]);
        }
        ret.push_back(window.front());
        // 模拟滑动窗口的移动
        for (int j = k; j < nums.size(); j++) {
            if (nums[j - k] == window.front()) window.pop_front();  // 移动后窗口的前一个元素等于队头元素
            while (!window.empty() && window.back() < nums[j]) {
                window.pop_back();
            }
            window.push_back(nums[j]);
            ret.push_back(window.front());
        }
        return ret;
    }
};

59.2-队列的最大值

剑指offer 59.2-队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数 max_value、push_back 和 pop_front 的均摊时间复杂度都是 $O(1)$。

若队列为空，pop_front 和 max_value 需要返回 -1。

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

解题思路：

定义一个单调递减的辅助队列（双端队列）

C++代码实现：

class MaxQueue {
private:
    queue<int> que1;
    deque<int> que2;  // 辅助队列，头部位置存放最大值值
public:
    MaxQueue() {

    }
    int max_value() {
        if(que1.empty())
            return -1;
        return que2.front();
    }
    void push_back(int value) {
        // 维护单调递减队列
        while(!que2.empty() && que2.back() < value){
            que2.pop_back();  // 移除队尾元素直到队尾元素大于新添加元素
        }
        
        que2.push_back(value);
        que1.push(value);
    }
    int pop_front() {
        if(que1.empty()) return -1;
        else{
            int ans = que1.front();
            if( ans == que2.front()) que2.pop_front();
            que1.pop();
            return ans;
        }
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

leetcode 768-最多能完成排序的块 II

leetcode 768-最多能完成排序的块 II

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为 2000，其中的元素最大为 10**8。

arr 是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

示例 1:

输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

解题思路：

1，辅助栈法：栈中存放每个块内元素的最大值，栈的 size() 即为最多分块数。

题中隐含结论：

• 下一个分块中的所有数字都会大于等于上一个分块中的所有数字，即后面块中的最小值也大于前面块中最大值。
• 只有分的块内部可以排序，块与块之间的相对位置是不能变的。
• 直观上就是找到从左到右开始不减少（增加或者不变）的地方并分块。
• 要后面有较小值，那么前面大于它的都应该在一个块里面。

复杂度分析：

• 时间复杂度: O(n)
• 空间复杂度: O(1)

C++代码：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> ret; // 创建单调栈
        // 单调栈中只保留每个分块的最大值
        for (int i = 0; i < arr.size(); i++) {
            // 遇到一个比栈顶小的元素，而前面的块不应该有比 arr[i] 小的
            // 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 arr[i] 小的值都需要 pop 出来
            if (!ret.empty() && arr[i] < ret.top()) {
                int temp = ret.top();
                // 维持栈的单调递增
                while (!ret.empty() && arr[i] < ret.top()) {
                    ret.pop();
                }
                ret.push(temp);
            }
            else {
                ret.push(arr[i]);
            }
        }
        int m = ret.size();
        return m;
    }
};

leetcode 215. 数组中的第K个最大元素

leetcode 215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路：小顶堆维护大顶堆的方法

维护一个有 k 个元素的最小堆：

• 如果当前堆不满，直接添加；
• 堆满的时候，如果新读到的数大于堆顶元素，则将堆顶元素弹出，同时将新读到的数放入最小堆中（堆会自己调整内部结构）。

复杂度分析：

• 时间复杂度： $O(nlogk)$
• 空间复杂度： $O(k)$

class Solution {
public:
    // 小顶堆维护大顶堆的方法，时间复杂度 O(n logk)
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> vec(k,0);
        // priority_queue<int> heap;  // 大顶堆，堆顶为最大值
        priority_queue<int, vector<int>, greater<int> > heap; // 小顶堆，堆顶为最小值

        for(int i=0; i < nums.size();i++){
            if(i < k){  // 创建一个大小为 k 的最小堆
                heap.push(nums[i]);
            }
            else{
                if(heap.top() < nums[i]){  
                    heap.pop();
                    heap.push(nums[i]);
                }
            }
        }
        int ret = heap.top();
        return ret;
    }
};

4，字符串

leetcode 58-最后一个单词的长度

leetcode 58-最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词：是指仅由字母组成、不包含任何空格字符的最大子字符串。

C++代码：

class Solution {
public:
    int lengthOfLastWord(string s) {
        s +=  ' ';
        vector<string> res; // 存放字符串的数组
        string temp; // 临时字符串
        for(char ch:s){
            if(ch == ' '){
                if(!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else{
                temp += ch;
            }
        }
        string last_word = res.back();  // 数组最后一个元素
        return last_word.size();
    }
};

leetcode 557-反转字符串中的单词 III

leetcode 557. 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

提示：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

C++代码：

class Solution {
public:
    string reverseWords(string s) {
        s +=  ' ';
        vector<string> res; // 存放字符串的数组
        string temp; // 临时字符串
        for(char ch:s){
            if(ch == ' '){
                if(!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else{
                temp += ch;
            }
        }
        s.clear();
        for(string &str: res){
            reverse(str.begin(), str.end());
            s += str + ' ';
        }
        s.pop_back();
        return s;
    }
};

leetcode 1805-字符串中不同整数的数目

leetcode 1805-字符串中不同整数的数目

给你一个字符串 word ，该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如，“a123bc34d8ef34” 将会变成 " 123  34 8  34" 。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）：“123”、“34”、“8” 和 “34” 。

返回对 word 完成替换后形成的 不同 整数的数目。只有当两个整数的 不含前导零 的十进制表示不同， 才认为这两个整数也不同。

示例 1：

输入：word = "a123bc34d8ef34"
输出：3
解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。

C++代码：

class Solution {
public:
    int numDifferentIntegers(string word) {
        set<string> s;
        word += 'a';
        string temp; // 临时字符串
        for(char ch:word){
            // 如果遇到字母且临时字符串非空，就把它加入集合并重置临时字符串
            if(isalpha(ch)){   
                if(!temp.empty()){
                    s.insert(temp);
                    temp.clear();
                }
            }
            else{
                if(temp == "0") temp.clear();  // "001" 和 "1" 是等值的
                temp += ch;
            }
        }
        return s.size();
    }
};

leetcode 1816-截断句子

leetcode 1816-截断句子

句子 是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。每个单词仅由大小写英文字母组成（不含标点符号）。

例如，“Hello World”、“HELLO” 和 “hello world hello world” 都是句子。给你一个句子 s​​​​​​ 和一个整数 k​​​​​​ ，请你将 s​​ 截断 ​，​​​使截断后的句子仅含 前 k​​​​​​ 个单词。返回 截断 s​​​​​​ 后得到的句子。

示例 1：

输入：s = "Hello how are you Contestant", k = 4
输出："Hello how are you"
解释：
s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
前 4 个单词为 ["Hello", "how", "are", "you"]
因此，应当返回 "Hello how are you"

C++代码：

class Solution {
public:
    string truncateSentence(string s, int k) {
        s +=  ' ';
        vector<string> res; // 存放字符串的数组
        string temp; // 临时字符串
        for(char ch:s){
            if(ch == ' '){
                res.push_back(temp);
                temp.clear();
            }
            else{
                temp += ch;
            }
        }
        s.clear();
        for(int i=0; i< k;i++){
            s += res[i] + ' ';
        }
        s.pop_back();
        return s;
    }
};

leetcode 394-字符串解码

leetcode 394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

解题思路：

本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

复杂度分析：

• 时间复杂度 O(N)： s；
• 空间复杂度 O(N)：辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。

C++代码：

class Solution {
public:
    string decodeString(string s) {
        stack<pair<string, int>> s1;
        string res = "";
        int num = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num *= 10;
                num += (s[i] - '0');
            }
            else if (s[i] == '[') {
                s1.push(make_pair(res, num));
                num = 0;
                res = "";
            }
            else if (s[i] == ']') {
                auto cur_num = s1.top().second;
                auto latest_res = s1.top().first;
                s1.pop();
                for (int j = 0; j < cur_num; j++) latest_res = latest_res + res; // res 加 n 次
                res = latest_res;
            }
            else {
                res += s[i];
            }
        }
        return res;
    }
};

leetcode 821-字符的最短距离

leetcode 821-字符的最短距离

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 

解题方法：

1，两次遍历

• 从左向右遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 i - prev。
• 从右想做遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 prev - i。

2，哈希表法

• 获取 s 中所有目标字符 c 的位置，并提前存储在数组 c_indexs 中。
• 遍历字符串 s 中的每个字符，如果和 c 不相等，就到 c_indexs 中找距离当前位置最近的下标。

复杂度分析：

• 时间复杂度: O(n)
• 空间复杂度: O(1)

C++代码：

class Solution {
public: // 1，两次遍历法
    vector<int> shortestToChar(string s, char c) {
        vector <int> ret;
        int prev = -10000;
        int distance = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == c) prev = i;
            distance = i - prev;
            ret.push_back(distance);
        }
        prev = 10000;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == c) prev = i;
            distance = prev - i;
            ret[i] = min(ret[i], distance);
        }
        return ret;
    }
    // 解法2：空间换时间，时间复杂度 O(n*k)
    vector<int> shortestToChar2(string s, char c) {
        int n = s.size();
        vector<int> c_indexs;
        // Initialize a vector of size n with default value 0.
        vector<int> ret(n, 0);

        for (int i = 0; i < n; i++) {
            if (s[i] == c) c_indexs.push_back(i);
        }

        for (int i = 0; i < n; i++) {
            int distance = 10000;
            if (s[i] == c) ret[i] = 0;
            else {
                for (int j = 0; j < c_indexs.size(); j++) {
                    int temp = abs(c_indexs[j] - i);
                    if (temp < distance) distance = temp;
                }
                ret[i] = distance;
            }
            
        }
        return ret;
    }
};

5，哈希表

50-第一个只出现一次的字符位置

剑指offer 题50. 第一个只出现一次的字符位置

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

限制：0 <= s 的长度 <= 50000

解题方法：

哈希表法。map：基于红黑树，元素有序存储; unordered_map：基于散列表，元素无序存储

C++代码：

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, bool> dic;
        for(char c:s){
            dic[c] = dic.find(c) == dic.end();
        }
        for(char c:s){
            if(dic[c] == true)
                return c;
        }
        return ' ';
    }
    
    char FirstNotRepeatingChar(string s) {
        unordered_map<char, bool> dic;
        for(char c:s){
            dic[c] = dic.find(c) == dic.end();
        }
        for(int i=0; i<s.size();i++){
            if(dic[s[i]] == true)
                return i;
        }
        return -1;
    }
};

leetcode 146-LRU 缓存机制

leetcode 146-LRU 缓存机制

解题方法：

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置（双向链表的节点地址）。

C++代码：

//定义双链表
struct Node{
    int key, val;
    Node* left ,*right;
    Node(int _key, int _value): key(_key),val(_value),left(NULL),right(NULL){}
}*head,*tail; // 双链表的最左和最右节点，不存贮值。

class LRUCache {
private:
    unordered_map<int, Node*> cache;
    int n;
public:
    LRUCache(int capacity) {
        n = capacity;
        // head、tail 双链表的头尾节点
        head = new Node(-1, -1), tail = new Node(-1, -1);
        head -> right = tail;
        tail -> left = head;
    }
    
    int get(int key) {
        if(!cache.count(key)) return -1;
        Node* p = cache[key]; // 通过哈希表定位 key 对应的键值 p
        removeNode(p);
        addToHead(p);
        return p->val;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            Node* p = cache[key];
            p -> val = value; // 定位双向链表的节点 p，并更新 val
            removeNode(p);
            addToHead(p);
        }
        else{
            if(cache.size() == n){
                auto p = tail->left;
                removeNode(p);
                cache.erase(p->key);  // 更新哈希表
                delete p;
            }
            auto p = new Node(key, value);
            addToHead(p);
            cache[key] = p;
        }
    }
    void removeNode(Node* p){  // 移除指定节点 p
        p->left->right = p->right;
        p->right->left = p->left;
    }

    void addToHead(Node* p){ // 插入到头节点 L 之后
        p->right = head->right;
        p->left = head;
        head->right->left = p;
        head->right = p;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

leetcode 30-串联所有单词的子串

leetcode 30. 串联所有单词的子串

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

解题思路：滑动窗口 + 哈希表。滑动窗口的大小为 $k*len$。

1. 从 words 出发，考虑 words 所有单词排列生成的字符串 X，通过字符串匹配查看 X 在 s 中的出现位置，但是 X 的可能情况有 $k!$ 种， $k$ 为 words 中单词的个数，明显超时！
2. 从 s 串出发，遍历 s 串中所有长度为 (words[0].length * words.length) 的子串 Y，并判断 Y 是否可以由 words 数组构造生成。

代码步骤：首先构建 words 单词出现次数的哈表表，然后滑动窗口移动的时候，每次获取 len 长度的子串，并判断这个子串是否在 words 中，并构建子串出现次数的哈希表，同时要求子串出现的次数不能大于原来 words 中单词出现的次数。

时间复杂度： $O((n-k* len)* k)$，n 是字符串 s 的长度，k 是 words 中单词的个数，len是每个单词的长度。

这道 hard 题目居然被我做出来了！代码第二次修改参考了西法的剪枝代码，之前自己用嵌套 if 判断实在太傻了。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> freq;
        // 计算字符串数组中每个单词出现的频率
        for(auto s1: words){
            freq[s1]++;
        }

        vector<int> ret;
        int len = words[0].size();

        for(int i=0; i< s.size()-len*words.size()+1; i++){
            int pos = i;
            int num = 1;
            unordered_map<string, int> freq2;
            while(num <= words.size()){
                auto target = s.substr(pos, len);
                
                if(freq.count(target) == 0) break;  // 剪枝
                freq2[target]++;  // 滑动窗口中子串出现次数+1
                if(freq2[target] > freq[target]) break;  // 剪枝
 
                pos += len;
                num++;
            }
            if(num-1 == words.size()) ret.push_back(i);
        }
        return ret;
    }
};

leetcode

解题方法：

根据同余定理，只要求前缀和 p[i] 和 p[j] 模数 k 同余出现的次数。

1. 前缀和：使用公式 $pre[i]=pre[i−1]+nums[i]$ 得到每一位前缀和的值，从而通过前缀和进行相应的计算和解题。
2. 同余定理：给定一个正整数m，如果两个整数 a 和 b 满足 a-b 能够被 m 整除，即 $(a-b)/m$ 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a≡b(mod m)。对模 m 同余是整数的一个等价关系。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        // 哈希表初始化，record[0] = 1
        unordered_map<int, int> record = {{0, 1}};
        int sum = 0, ans = 0;
        for (int elem: nums) {
            sum += elem;
            // 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % k + k) % k;
            // 边遍历边计算答案
            if (record.count(modulus)) {
                ans += record[modulus];
            }
            ++record[modulus];
        }
        return ans;
    }
};

6，二叉树

07-重建二叉树

剑指 Offer 07-重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例1：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

解题方法：

1，递归法

• 中序遍历的结果可以获取左右子树的元素个数；
• 前序遍历结果可以获取树的根节点 node 的值。

C++代码：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 哈希表 dic 存储中序遍历的值与索引的映射
        for(int i=0; i<inorder.size(); ++i){
            index[inorder[i]] = i;
        }
        auto root = recur(preorder, 0, 0, inorder.size());
        return root;
    }

private:
    unordered_map<int,int> index;
    TreeNode* recur(vector<int>& preorder, int root, int left, int right){
        if (left > right) return nullptr;
        int i = index[preorder[left]]; // 获取中序遍历中根节点值的索引
        TreeNode* node = new TreeNode(preorder[left]);
        node->left = recur(preorder, root+1, left, i-1);
        node->right = recur(preorder, root+i-left+1, i+1, right);

        return node;

    }
};

leetcode 104-二叉树的最大深度

104-二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

55.2-平衡二叉树

55.2-平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

leetcode 109-有序链表转换二叉搜索树

leetcode109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解题方法：

1，将单调递增链表转化为数组，然后分治递归。
2，快慢指针找链表的中间节点，然后递归。

复杂度分析：

• 时间复杂度: O(n)
• 空间复杂度: O(n)

C++代码：

class Solution {
public:
    // 分治递归
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> vec;
        for(auto it = head; it!=nullptr ; it=it->next ){
            vec.push_back( it->val );
        }
        return recur(vec, 0, vec.size()-1);
    }

    TreeNode* recur(vector<int> &arr, int left, int right){
        if(left > right) return nullptr;
        int mid = right + (left-right)/2;  // 数组中间位置的索引
        TreeNode* node = new TreeNode(arr[mid]);
        node -> left = recur(arr, left, mid - 1);
        node -> right = recur(arr, mid + 1, right);

        return node;
    }
};

7，图