基本数据结构

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

1. Two Sum

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(target - nums[i])) 
                return {i, hash[target - nums[i]]};
            hash[nums[i]] = i;     //哈希表存的是 数的索引
        }
        return {};
    }
};

#187. Repeated DNA Sequences

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_map<string, int> hash;
        vector<string> ans;
        for (int i = 0; i + 9 < s.size(); i++) {
            string temp =s.substr(i, 10);
            hash[temp]++;
            if (hash[temp] == 2) ans.push_back(temp);   //这里写 == 2 , 是因为第三次，第四次遇到这个值的时候就不会插入了。
        }
        return ans;
    }
};

706. Design HashMap

1
//设计一个哈希表

652. Find Duplicate Subtrees

1
2


如果想用一个遍历序列表示一棵二叉树，那么一定要加上空节点

VLR + LVR 或 LVR + LRV 可以重建一颗二叉树， 如果只给一个序列重建二叉树， 那么这个序列中要包含空节点

例如， 图中二叉树可以表示为

1, 2, 4, #, #, 3, 2, 4, #, #, 4, #, #
这样题目就转化成了类似187题…

哈希的目的是把一个大的空间 映射成一个小的空间

560. Subarray Sum Equals K

前缀和

1
2


[692. Top K Frequent Words] (https://leetcode.com/problems/top-k-frequent-words/)

此题和下面那道题是考察的堆

自己手写的话，可以实现 （任意位置的）
1.查找最大值 o(1)
2.插入一个数 o(logn)
3.删除一个数 o(logn)
4.修改一个数 o(logn)

但是 C++ 的 priority_queue 只能操作堆顶元素

目标 找出出现次数最多的k个单词
用小根堆来维护出现次数最多的k个单词（保证堆中的元素都是最大的）， 反之找最少的维护大根堆。

这里用取相反数的方式来形成一个小根堆，而不用priority_queue<PIS, vector, greater> heap; 是因为pair是按照双关键字排序，而这里我们需要数越大，字典序越小越靠前，二者并不一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<string> topKFrequent(vector<string>& words, int k) {
   unordered_map<string, int> hash;
   typedef PIS pair<int, string> PIS ;
   priority_queue<PIS> heap;

   for (auto word : words) hash[word]++;

   for (auto item : hash) {
       PIS t(-item.second, item.first);   //int元素 前 加负号， 这样后面每次弹出的元素就是当前堆里的最小元素（绝对值）
       heap.push(t);
       if (heap.size() > k) heap.pop();
   }

   vector<string> ans(k);

   for (int i = k -1; i >= 0; i--) {    //这里注意 i 是用作 ans 的索引， 所以从 k - 1 到 0
       ans[i] = heap.top().second;
       heap.pop();
   }
}

295. Find Median from Data Stream

小根堆 n/2

大根堆 n/2

维护一个大根堆， 一个小根堆， 各有 n / 2 个元素； 大根堆中是前一半元素， 小根堆中是后一半元素， （当n为奇数时）我们让上面的元素个数比下面的多一个即可， 这样小根堆的堆顶元素就是中位数。

插入一个元素 x， 当x 大于等于 大根堆的堆顶元素时， 插入到小根堆， 反之插入到小根堆中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MedianFinder {
public:
  
    priority_queue<int, vector<int>, greater<int>> up; //一个小根堆
    priority_queue<int> down; //一个大根堆
    
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if (down.empty() || num >= down.top() ) {
            up.push(num);
        } else {
            down.push(num);
            up.push(down.top());
            down.pop();
        }
        if (up.size() > down.size() + 1) {
            down.push(up.top());
            up.pop();
        }
    }
    
    double findMedian() {
        if (down.size() + up.size() & 1) return up.top();    //注意这里判断奇数的方式
        else return (down.top() + up.top()) / 2.0;
    }
};

判断奇数的方式。 num & 1

352. 352. Data Stream as Disjoint Intervals

用平衡树来维护所有区间 (map的遍历是 o(n) 的)
map<int, int> L, R; L把所有左端点 映射成 右端点

[1, 2], [4, 7], [9, 9]

L[1] = 2， L[4] = 7, L[9] = 9;
R[2] = 1, R[7] = 4, R[9] = 9;

—————————— x ——————————
x-1 x+1

  • 判断x是否已经存在了
  • 左右都存在 x 可以 与两边合并
  • 左边存在，右边不存在 x 与左边合并
  • 左边不存在， 右边存在 x 与右边合并
  • 左右都不存在 [x, x] x单独成为一个区间 
1
2


547. Friend Circles

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    
    vector<int> p;
    
    int find (int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    
    
    
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        for (int i = 0; i < n; i++) p.push_back(i);
        
        int res = n; // 表示最开始n个同学是互相独立的， 有n个集合
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++) {
                if (M[i][j] == 0) continue;
                if (find(i) != find(j)) {
                    p[find(i)] = find(j);  //合并两个集合
                    res--;   //集合总数减一
                }
            }
        
        
       return res;
    }
};
0%