数据结构班-第2课-必知必会的数据结构-课堂笔记


第2课 必知必会的数据结构

作业:394. Decode String
class Solution {
private:
    stack<int> counts; // 存储倍数。
    stack<int> digits; // 存储字符,后面累计转换成倍数。
    stack<int> left_index; // 存储 [ 的索引值。
public:
    string sub_string(string sub_str, int times) {
        string res;
        for (int i = 0; i < times; ++i) {
            res += sub_str;
        }
        return res;
    }

    string decodeString(string s) {
        string res;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] <= '9' && s[i] >= '0') {
                digits.push(int(s[i] - '0'));
                s.erase(i, 1);
                i--;
            } else if ('[' == s[i]) {
                left_index.push(i);
                int times = digits.top();
                digits.pop();
                int k = 10;
                while (!digits.empty()) {
                    times = times + digits.top() * k;
                    k *= 10;
                    digits.pop();
                }
                counts.push(times);
            } else if (']' == s[i]) {
                int times = counts.top();
                counts.pop();
                int start = left_index.top();
                left_index.pop();
                int end = i;
                string tmp;
                for (int j = start + 1; j < end; ++j) {
                    tmp += s[j];
                }
                s = s.substr(0, start) + this->sub_string(tmp, times) + s.substr(end + 1);
                i = i - 2; // 去除 [、]。
            }
        }
        return s;
    }
};


并查集

路径压缩:在查找的过程中,将该查找路径上所遇到的所有节点,全部直接连接在父节点上;而不是选择在合并两个集合的时候执行路径压缩,因为可能不是所有的点都会被查找,这样,经常被查找的元素,再查找时,所花费的时间为 \(O(1)\),均摊的时间复杂度为 \(O(1)\)。

155. Min Stack
class MinStack {
private:
    vector<int> *a;
public:
    MinStack() {
        a = new vector<int>();
    }

    void push(int x) {
        a->push_back(x);
    }

    void pop() {
        a->pop_back();
    }

    int top() {
        return (*a)[a->size() - 1];
    }

    int getMin() {
        int n = int(a->size());
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            if ((*a)[i] < res) {
                res = (*a)[i];
            }
        }
        return res;
    }
};


哈希表

时间与空间之间的权衡。

存放数据的集合
  • 操作:根据(Key, Value)进行


插入,查找,删除(可以没有)
  • 空间复杂度:\(O(m)\)
  • 单次操作时间复杂度: \(O(1)\)
  • 本质:Key的索引。


开散列

哈希值相同的元素方一个链表中。

闭散列:

如果冲突,则放在下一个位置。

处理冲突(Key, Value)

  • 开放地址法(数组)
  • 拉链法 (数组+链表)
  • 负载率 = 已有元素大小 / 存储散列大小 • 最坏情况?
  • 哈希函数设计


哈希表的思考

若 n << m,计数排序的大量空间被浪费。
  • 只需判断是否出现过,优化?
  • 将Key区间[0, m) 映射到 [0, p)
  • H(key) = key mod p,p 尽量使用质数。
  • 若m > p, 多对一的映射方式


128. Longest Consecutive Sequence
class Solution {
public:
    /**
     * 用hash表来解决这个问题,先初始化一个hash表,
     * 存储所有数组元素,然后遍历这个数组,
     * 对找到的数组元素,去搜索其相连的上下两个元素是否在hash表中,
     * 如果在, 删除相应元素并增加此次查找的数据长度,如果不在,从下一个元素出发查找。
     * @param nums 数组。
     * @return 最长连续子串长度。
     */
    int longestConsecutive(vector<int> &nums) {
        int n = nums.size();
        if (0 == n) {
            return 0;
        }
        unordered_set<int> my_set(nums.begin(), nums.end());
        int res = 1;
        for (int n : nums) {
            if (my_set.find(n) == my_set.end()) {
                continue;
            }
            my_set.erase(n);
            int prev = n - 1;
            int next = n + 1;
            while (my_set.find(prev) != my_set.end()) {
                my_set.erase(prev--);
            }

            while (my_set.find(next) != my_set.end()) {
                my_set.erase(next++);
            }

            res = max(res, next - prev - 1);
        }
        return res;
    }
};
已邀请:

LostOsiris

赞同来自:


6666666666

要回复问题请先登录注册

返回顶部