算法笔记_面试题_21.数据结构相关_模板及示例十几道

目录

1. 栈相关（stack）

例1. 最小栈

例2. 用栈实现队列

2. 单调栈

例3. 直方图最大矩形面积 （单调递增栈）

例4. 最大树 (MaxTree)（单调递减栈）

例5. 接雨水 （单调递减栈）

3. 哈希表(or 散列表) （hash table）

例6. 实现一个字符串转数字的常用hash函数 （magic number 33）

例7. 重哈希（Rehashing）

例8. LRU Cache (Least Recently Used 最近最少使用缓冲器）

例9. 乱序字符串分组（anagrams）

例10. 无序整数数组中 最长连续子序列

4. 堆 （heap）

例11. 寻找数据流的中位数

例12. 堆化操作 siftdown

例13. 找从小到大的第n个丑数

描述：实现一个栈, 支持以下操作:push(val) 将 val 压入栈;pop() 将栈顶元素弹出, 并返回这个弹出的元素;min() 返回栈中元素的最小值;要求 O(1) 开销;保证栈中没有数字时不会调用 min(). （来源 ：lintcode 12 · 带最小值操作的栈 = leetcode 剑指 Offer 30. 包含min函数的栈 = leetcode 155. 最小栈）样例 输入：push(1)  min()  push(2)  min()  push(3)  min() 输出：                  1                     1                      1

代码1_常规方法

因为每层都有返回当前情况下的最小值，所以每次存储一个值，就需要更新（或者确认）当前最小栈的最小值。所以考虑使用两个普通栈（std::stack）来实现。一个stack mData 存储数据，一个stack mMin 存储当前状态下的最小值。在push入栈时，比较当前值和当前最小值那个更小，若当前值更小，则将当前值加入mMin 栈，否则，将当前最小值再次加入 mMin 栈 （可改进点）。以便在pop时，mData每弹出一个元素, mMin就弹出一个元素。代码实现如下。

class MinStack {
public:
    stack mData;
    stack mMin; 
    
    MinStack(){ }

    void push(int number) {
        mData.push(number);
        if (mMin.empty()) {
            mMin.push(number);
        } else {
            mMin.push(std::min(number, mMin.top()));
        }
    }

    int pop() {
        if (!mData.empty()) {
            int res = mData.top();
            mData.pop();
            mMin.pop();
            return res;
        } else {
            return INT_MIN;
        }
    }

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

代码1_空间优化（重点记忆）

可以看到上述 mMin栈 中 有很多重复的元素，若第一个值是1，后面全是比1大的n个数，则mMin中岂不是要存n个1，存一个1，省点空间不可以吗？答案是可以的。此时的方法变成了，在push时，只有在当前值 val) { //若当前值比 栈顶元素大，则栈顶元素为当前节点的左子节点(因为根据最大树的要求，在每一个子数组中，最大值左侧的数在左子树) curNode->left = stk[stk.size()-1]; // 谁大谁是“爸爸” stk.pop_back(); } if (!stk.empty()) { //上面的处理完后，当遇到当前值小于此时的栈顶元素，则 当前值对应的节点，为栈顶元素节点的右子节点。 stk[stk.size()-1]->right = curNode; // 谁大谁是“爸爸” } stk.push_back(curNode); } return stk[0]; //注意：返回的是栈低节点(最大树，所以栈顶节点一定是最大的) //不是栈顶哦！！ } }; 例5. 接雨水 （单调递减栈）

描述：给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。（来源：lintcode 363 · 接雨水 中等 = leetcode 42. 接雨水 困难)42. 接雨水

样例1： 输入: [0,1,0]  输出: 0样例2： 输入: [0,1,0,2,1,0,1,3,2,1,2,1]  输出: 6 挑战： O(n) 时间, O(1) 空间； O(n) 时间, O(n) 空间也可以接受

代码

该题后多种解法，这里以单调栈为例进行分析。考虑到计算当前位置上能接多少雨水，取决于左右两侧的最大值。所以选择使用单调递减栈 （因为可以方便找到比当前值大的元素，栈中元素从栈底到栈顶依次递减）。为了方便计算两个柱子之间的间距，同例4一样，我们在栈中保存高度数组对应的索引；同时，采用横向分层计算的方式比较方便。

我们依次将元素入栈，当遇到当前元素 i （记作 cur  = heights[i] ）比 栈顶元素对应的值 大时，就开始计算。 这里有三个关注的元素： 待判定是否插入栈的当前元素 cur （对应的索引设为 i）；栈顶元素 （对应的高度记为 bottom，此时必定是最低的一个）；栈顶元素的前一个元素（ 在进行一次 stk.pop()之后，索引成了 stk.top()）则 计算积水面积的 高度 h = min(heights[stk.top()], heights[i]) - bottom; （即当前计算对象，左右两侧的最小高度 减去 当前高度）。 宽度 w = i - stk.top() - 1; (即当前元素 对应的索引 i 减去 当前栈中（未弹出时）的倒数第二个索引 再减去 1)

注意：pop() 完后，要 判断栈是否为空 if (!stk.empty())  

class Solution {
public:
    int trapRainWater(vector &heights) {
        // write your code here
        int n = heights.size();
        if (n = heights[stk.top()]) {
                int bottom = heights[stk.top()]; //以当前栈顶元素作为计算对象,当前栈顶元素必定为此时的最低点
                stk.pop();                       // 在弹出后，若有计算记得判断栈是否为空！
                if (!stk.empty()) {
                    int h = min(heights[stk.top()], cur) - bottom;   //横向分层计算
                    int w = i - stk.top() - 1;
                    sum += h * w;
                }
            } 
            stk.push(i);
        }

        return sum;
    }
};

关于hash常问的问题有：（参考 C++_Hash容器总结）

• hash这种数据结构，你了解多少？内部怎么实现的？时间复杂度是什么样的？hash为什么是O(1) 插入删除查找的？什么情况下不能当成是O(1)的？
  • 我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
• 你能不能自己实现一个hash map？hash function 怎么写的？
• hash常遇到的问题是什么？怎么解决 hash collision（哈希冲突）的？

​描述：在数据结构中，哈希函数是用来将一个字符串（或任何其他类型）转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数算法是使用数值 33，假设任何字符串都是基于 33 的一个大整数，比如：

 其中HASH_SIZE表示哈希表的大小(可以假设一个哈希表就是一个索引 00 ~ HASH_SIZE - 1的数组)。给出一个字符串作为 key 和一个哈希表的大小，返回这个字符串的哈希值。

对于这个问题你不需要自己设计hash算法，你只需要实现上述描述的hash算法即可。对于这个问题，您没有必要设计自己的哈希算法或考虑任何冲突问题，您只需要按照描述实现算法.（来源： lintcode 128 · 哈希函数 简单）

样例 输入:  key = "abcd", size = 1000   输出: 978     样例解释：(97 * 33^3 + 98*33^2 + 99*33 + 100*1)%1000 = 978

代码

利用性质 ： 对一个数多次取余等于一次取余。 a%b%b = a%b。 注意：这里 33乘在sum上，然后下一次循环再乘在sum上，避免多次求33的n次方。

class Solution {
public:
    int hashCode(string &key, int HASH_SIZE) {
        int sum = 0;

        for (int i = 0; i < key.size(); i++) {
            sum = sum * 33 + (int)key[i];   // 注意：这里对 sum 乘以 33，避免了重复计算33的倍数
            sum %= HASH_SIZE;               // 利用性质 a%b%b = a%b
        }

        return sum;
    }
};

class Solution {
public:
    vector rehashing(vector hashTable) {
        int n = hashTable.size();
        if (n == 0) {
            return hashTable;
        }
        
        int N = 2 * n;
        vector result(N, nullptr); //注意：直接初始化为 nullptr!(后面用来判断该位置是否有元素)
        for (int i = 0; i < n; i++) {      // 进入到处理原始hash中单个节点的逻辑
            ListNode * head = hashTable[i];  // 原始hash中的节点的头
            while (head != nullptr) {
                ListNode * nextNode = head->next;   //将 head 作为当前处理对象，先把下一个节点拿到手
                head->next = nullptr;
                
                int index = (head->val % N + N) % N;    //计算在新的hash中的位置
                if (result[index] == nullptr) {     // 特别注意：插入新的hash前，新的位置无元素直接插入
                    result[index] = head;
                } else {                            // 特别注意：新的位置有元素，插入到对应位置的"链表结尾"！
                    ListNode * cur = result[index];
                    while (cur->next != nullptr) { // 找到最后一个节点，然后挂上去
                        cur = cur->next;
                    }
                    cur->next = head;
                }
                
                head = nextNode;            //指向原始hash中该位置对应链表的下一个元素
            }
        }

        return result;
    }
};

代码

本文采用双向链表（list）和 hash表（unordered_map）来实现。

根据题目要求，当容量到达最大时，长时间不用的就要删除，而且最近访问的要优先保留，所以考虑使用双向链表来管理各个key值，即 list mKeys;（通过将新元素插入到链表结尾，将最新访问的移动到链表的结尾，这样就可以在超过容量时，删除链表头，即删除长时间不用的元素）。对于重复插入相同的key，自然是先移动到链表尾部，再更新其值即可。这时，我们还需要一个容量来保存value值。考虑到要在该容器中以O(1)时间复杂度找到重复的key值，所以考虑使用 hash表，在C++中对应的数据结构是unordered_map，为了方便查找到hash中key在list中对应的位置，我们在 该哈希表中存入三个元素：key， value，以及key在list中对应的位置即list::iterator，所以 定义 unordered_mapsecond.second); // 根据迭代器，更新list中的key的位置 mKeys.push_back(key); // 放到list尾部 《====== mData[key].second = --mKeys.end(); //更新hash中对应的list中的位置 //或 it->second.second = --mKeys.end(); return mData[key].first; } } void put(int key, int value) { if (get(key) != -1) { //若存在，则移动到list结尾，并更新它的值 《====== mData[key].first = value; } else { //若不存在，则插入新的值 insert(key, value); if (mKeys.size() > mCapacity) { //若元素数量超过了容量，则删除最老的(队列头)key int oldKey = mKeys.front(); //注意：是 front() ！ mKeys.pop_front(); mData.erase(oldKey); } } } }; /** * 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); */

描述：给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。所有的字符串都只包含小写字母。（来源：lintcode 171 · 乱序字符串 ≈ leetcode 49. 字母异位词分组 = leetcode 面试题 10.02. 变位词组）

样例1: 输入:["lint", "intl", "inlt", "code"]   输出:["lint", "inlt", "intl"]样例 2: 输入:["ab", "ba", "cd", "dc", "e"]   输出: ["ab", "ba", "cd", "dc"]

代码

从题中可以看出：目的是找到含有相同字母的字符串，若含有相同字母的字符串个数大于1，就输出。看到“相同”两个字，首先就应该想到使用hash表（因为hash表在查找一个元素的时间复杂度最低位O(1)），又因为是anagram（变位词、相同字母异序词），所以要先将字符串中的字母进行排序，然后就可以比较是否相等，进而知道是否是同一个anagram。

注意string的排序，可以使用数组索引的方式（参考  string getSortedString(string &str) 采用一个 array[26] 数组的形式进行统计计数 array[char - 'a']++ ），也可以直接使用 std::sort(str.begin(), str.end()) 直接对字符串中的字母进行排序。

采用hash表时，以排好序的字符串作为key，以排序前的字符串组成的vector作为value,这样就可以很方便的找到anagrams, 然后，当 某个key对应的anagrams的个数大于1，就输出即可。

class Solution {
public:
    vector anagrams(vector &strs) {

        unordered_map hash; //注意: 这里的定义很巧妙
        for(auto& str : strs){
            string key = str;
            sort(key.begin(), key.end());        //注意：对字符串中的字母进行排序
            hash[key].push_back(str);
        }

        vector results;
        for(auto& result : hash){     // result 是 std::pair
            if (result.second.size()  0) {
            mMax.pop();
        }
        while(mMin.size() > 0) {
            mMin.pop();
        }
    }
    
    void addNum(int num) {
        int n = mMax.size() + mMin.size();
        if ( n % 2 == 0) { //原来总共偶数个元素，插入mMin堆
            if ( mMax.size() > 0 && num < mMax.top()) {//若当前元素比小顶堆的最小元素还小，
                mMax.push(num);     // 就应该插入到大顶堆，
                num = mMax.top();   // 并且把大顶堆的最大元素（mMax.top()）拿出来作为补偿给小顶堆。
                mMax.pop();
            }
            mMin.push(num);
        } else {            //原来总共奇数个元素，插入mMax堆
            if (mMin.size() > 0 && num > mMin.top()) {
                mMin.push(num);
                num = mMin.top();
                mMin.pop();
            }
            mMax.push(num);
        }
    }
    
    double findMedian() {
        int n = mMax.size() + mMin.size();
        if (n % 2 == 1) {
            return mMin.top();
        } else {
            return (mMax.top() + mMin.top()) / 2.0; // 有的地方中值定义成索引为(n-1)/2的元素，则return mMax.top();
        }
    }
};

相关题目：未排序数组中的中位数 ，两个排序数组的中位数

描述：给出一个整数数组，把它变成一个最小堆数组（小顶堆），这称为堆化操作。对于堆数组A，A[0]是堆的根，并对于每个A[i]，A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。

什么是堆？ 什么是堆化？ 如果有很多种堆化的结果？ 堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到 A[i * 2 + 1] >= A[i] 和 A[i * 2 + 2] >= A[i] 返回其中任何一个。

样例：输入 : [3,2,1,4,5]   输出 : [1,2,3,4,5]    解释 : 返回任何一个合法的堆数组 挑战 ：O(n)的时间复杂度完成堆化

代码

该题考察的是模拟  std::make_heap() 操作。本文使用 siftdown  的方法：从索引为 N/2 的元素 向 索引为 0 的元素 依次遍历； 在一个while循环中（相当于树结构上从叶节点到根节点向上递归），对于每个元素（索引为i ）找它的 左子节点（2i +1） 和 右子节点 （2i + 2），在这三者中找到最小的（索引为 smallest ），然后交换当前元素 i 和 smallest 对应的元素， 然后把当前元素（在新的位置 i = smallest） 作为新的根节点，执行上述同样的操作，直到没有叶节点。特别注意，代码中找根/左子节点/右子节点时，比较的对象是 A[smallest]。

class Solution {
public:
    void heapify(vector &A) { //一句话的话就是：std::make_heap(A.begin(), A.end(), greater());
        int n = A.size();
        if (n = 0; i--) { //从最低层最右侧的根节点开始向上遍历 siftdown 操作
            siftdown(A, i);
        }
    }

    void siftdown(vector &A, int i) {
        while (i < A.size()) {
            int smallest = i;       //特别注意：下面比较的是 A[smallest] 而不是 A[i], 因为一次if后， smallest 可能发生变化
            if (2 * i + 1 < A.size() && A[2 * i + 1] < A[smallest]) { //若当前节点的左子节点存在且更小，就将该索引当成最小
                smallest = 2 * i + 1;
            }
            if (2 * i + 2 < A.size() && A[2 * i + 2] < A[smallest]) { //若当前节点的右子节点存在且更小，就将该索引当成最小
                smallest = 2 * i + 2;
            }
            if (smallest == i) { //比较后，发现当前节点作为根节点仍是最小，就不必操作，直接返回
                break;
            }

            std::swap(A[i], A[smallest]);
            
            i = smallest;   //精华代码：将最小的位置现在的值（还是交换前的A[i]）当做根，循环的看左右子节点是否有更小需要交换。
        }
    }
};

描述：给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。（来源：leetcode 264. 丑数 II = leetcode 剑指 Offer 49. 丑数）示例 1： 输入：n = 10  输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2： 输入：n = 1  输出：1 解释：1 通常被视为丑数。

代码

本题有多种方法（比如动态规划），本文采用小顶堆的方式。初始时堆为空。首先将最小的丑数 1加入堆。每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆。上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数。

利用的性质：优先队列（此处用 最小堆）的排序性质（每次弹出的都是最小的值），循环pop n次即得到第n个丑数； hash的无重复性质  和  find一个元素O(1)时间复杂度的性质。

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n