Data Structure

发表于 | 更新于: | | 阅读次数:
字数统计: 1,363 | 阅读时长 ≈ 7

先作一个草稿集

排序

详细请看

查找

概述

查找的种类

1. 二分查找
2. hash查找
3. 树查找
4. 图查找

查找涉及的数据结构

树和图

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
int binarySearch(vector<int> nums, int target) {
	int left = 0;
    int right = nums.size() - 1;
    while(left <= right) {
    	int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

查找LeetCode的练习题：

  • 对撞指针
    • No.125 Valid Palindrome
    • No.344 Reverse String
    • No.345 Reverse Vowels of a string
    • No.11 Container with Most water
  • 滑动窗口
    • No.438 Find All Anagrams in a String
    • No.76 Minimum Window Substring

hash查找

set(集合)处理存在的问题
map(字典)处理查找的问题

STL 底层实现 时间复杂度
map, set 平衡二叉树 O(log(n))
unordered_map, unordered_set 哈希表 O(1)

LeetCode练习题：

  • No.242 Valid Anagram
  • No.202 Happy Number
  • No.290 Word Pattern
  • No.205 Isomorphic Strings
  • No.451 Sort Characters By Frequency
  • No.15 3Sum
  • No.18 4Sum
  • No.16 3Sum Closest
  • No.49 Group Anagrams
  • No.447 Number of Boomerangs
  • No.149 Max Points on a Line

树的遍历

深度优先遍历，一般考虑使用递归或者使用栈。

递归版本

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
struct TreeNode{
	int val,
    TreeNode *right,
    TreeNode *left,
    TreeNode(int x) val(x), left(NULL), right(NULL) {}
}
// **先序遍历**
void preOrder(TreeNode *root) {
	if (root) {
    	cout << root -> val << endl;
        preOrder(root -> left) << endl;
        preOrder(root -> right) << endl;
    }
}
// **中序遍历**
void inOrder(TreeNode *root) {
	if (root) {
    	preOrder(root -> left) << endl;
    	cout << root -> val << endl;
        preOrder(root -> right) << endl;
    }
}
// **后序遍历**
void preOrder(TreeNode *root) {
	if (root) {
        preOrder(root -> left) << endl;
        preOrder(root -> right) << endl;
    	cout << root -> val << endl;
    }
}

非递归版本

版本1

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// **先序遍历**
void PreOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != NULL || !s.empty()) {
        if (P != NULL) {
            s.push(p);
            cout << p -> val << endl;
            p = p -> left;
        }
        else {
            p = s.top();
            s.pop();
            p = p -> right;
        }
    }
}
//**中序遍历**
void InOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != NULL || !s.empty()) {
        if (P != NULL) {
            s.push(p);
            p = p -> left;
        }
        else {
            p = s.top();
            s.pop();
            cout << p -> val << endl;
            p = p -> right;
        }
    }    
}
//**后序遍历**
//这个是错的，这种思路下，后序遍历的写法差异很大
void PostOrder(TreeNode* root) {
void InOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != NULL || !s.empty()) {
        if (P != NULL) {
            s.push(p);
            p = p -> left;
        }
        else {
            p = s.top();
            s.pop();
            
            if (! p -> right) {
                cout << p -> val << endl;
            }
            p = p -> right;
        }
    }    
}    
}

版本2

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct TreeNode {
	int val,
    TreeNode *left,
    TreeNode *right,
    TreeNode(int x) val(x), left(NULL), right(NULL) {}
}
struct Command {
	string s, //两个状态go和print，go用于继续往下访问的状态，print用于输出当前节点的状态
    TreeNode* node,
    Command(string s, TreeNode* node) s(s), node(node) {}
}
//先序遍历
void preOrder(TreeNode *root) {
	stack<Command> stk;
    stk.push(Command("go", root));
    while(!stk.empty()) {
    	Command tmp = stk.top();
        stk.pop();
        if (tmp.s == "print") cout << tmp.node -> val << endl;
        else {
        	if (tmp.node -> right) stk.push(Command("go", tmp.node -> right));
            if (tmp.node -> left) stk.push(Command("go", tmp.node -> left));
            stk.push(Command("print", tmp.node));
        }
    }
}
//中序遍历
void inOrder(TreeNode *root) {
	stack<Command> stk;
    stk.push(Command("go", root));
    while(!stk.empty()) {
    	Command tmp = stk.top();
        stk.pop();
        if (tmp.s == "print") cout << tmp.node -> val << endl;
        else {
        	if (tmp.node -> right) stk.push(Command("go", tmp.node -> right));
            stk.push(Command("print", tmp.node));
            if (tmp.node -> left) stk.push(Command("go", tmp.node -> left));
        }
    }
}
//后序遍历
void postOrder(TreeNode *root) {
	stack<Command> stk;
    stk.push(Command("go", root));
    while(!stk.empty()) {
    	Command tmp = stk.top();
        stk.pop();
        if (tmp.s == "print") cout << tmp.node -> val << endl;
        else {
        	stk.push(Command("print", tmp.node));
        	if (tmp.node -> right) stk.push(Command("go", tmp.node -> right));
            if (tmp.node -> left) stk.push(Command("go", tmp.node -> left));
        }
    }
}

栈LeetCode的练习题：

  • No.150 Evaluate Reverse Polish Notation
  • No.11 Simplify Path

图的遍历

广度优先遍历，考虑使用队列

  • 层序遍历
  • 无权图的最短路径

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct TreeNode {
	int val,
    TreeNode *left,
    TreeNode *right,
    TreeNode(int x) val(x), left(NULL), right(NULL) {}
}
vector<vector> levelOrder(TreeNode *root) {
	if (root == NULL) return {};
	vector<vector<int>> res;
    queue<pair<TreeNode*, int>> q;
    q.push(make_pair(root, 0));
    while(!q.empty()) {
    	TreeNode *node = q.front().first;
        int level = q.front().second;
        q.pop();
        if (level == res.size()) {
        	res.push_back(vector<int> ());
        }
        res[level].push_back(node -> val);
        if (node -> left) q.push(make_pair(node -> left, level + 1));
        if (node -> right) q.push(make_pair(node -> right, level + 1));
    }
    return res;
}

层序遍历LeetCode练习题：

  • No.107 Binary Tree Level Order Traversal II
  • No.103 Binary Tree ZigZag Level Order Traversal
  • No.199 Binary Tree Right Side View

无权图最短路径

以LeetCode的279题“Perfect Sqaure”为例，将问题转化为无权图路径问题
tushi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numSquare(int n) {
	queue<pair<int, int>> q;
    q.push(make_pair(n, 0));
    bool visited(n + 1, false);
    while(!q.empty()) {
    	int num = q.front().first();
        int step = q.front().second();
        q.pop();
        int i = 1;
        int a = num - i * i;
        while (a >= 0) {
        	if (a == 0) return step + 1;
            if (!visited[a]) {
            	q.push(make_pair(a, step + 1));
                visited[a] = true;
            }
            i ++;
            a = num - i * i;
        }
    }
}

无权图LeetCode练习：

  • No.127 World Ladder
  • No.126 World Ladder II

优先队列

和普通队列，栈相比

  • 不同：不是从线性结构的头或尾出数据
  • 同：是一种广义的队列，出最大的数或者最小的数
  • 实现方式：堆
  • c++容器: priority_queue

优先队列实验

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
#include <iostream>
#include <queue>
#include <ctime>
using namespace std;
int main() {
	srand(time(NULL));
	priority_queue<int> pq;//默认是最大堆
	//最小堆的声明，在VS2015中greater<int>报错
	//priority_queue<int, vector<int>, greater<int>> pq;
	cout << "insert: " << endl;
	for (int i = 0; i < 10; i++) {
		int num = rand() % 100;
		pq.push(num);
		cout << num << '\t';
	}
	cout << endl;
	cout << "pop: " << endl;
	while (!pq.empty()) {
		cout << pq.top() << '\t';
		pq.pop();
	}
	cout << endl;
	return 0;
}

结果：
image

LeetCode 347. Top K Frequent Elements

给定一个非空数组，返回前k个出现频率最高的元素

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
vector<int> topKFrequent(vector<int>& nums, int k) {
	// table中(number, frequent)
	unordered_map<int, int> table;
    for (int i = 0; i < nums.size(); i ++) {
    	table[nums[i]] ++;
    }
    // pair中(frequent, number),因为需要对frequent进行排序
    priority_queue<pair<int ,int>, vector<pair<int, int>>, greater<pair<int, int>>) pq;
    for (auto iter = table.begin(); iter != table.end(); iter ++) {
    	if (pq.size() == k) {
        	// 频率与频率比较，最小堆的堆顶最小
        	if (iter -> second > pq.top() -> first) {
            	pq.pop();
                pq.push(make_pair(iter -> second, iter -> first));
            }
            continue;
        }
        pq.push(make_pair(iter -> second, iter -> first));
    }
    vector<int> res;
    while(!pq.empty()) {
    	res.push_back(pq.top() -> second());
        pq.pop();
    }
    return res;
}

优先队列练习

  • No. 23. Merge k Sorted Lists