leetcode列表
| 序号 | 题目 | 代码 | 解答 |
|---|---|---|---|
| 1 | 二叉搜索树的第k大节点 | 😊 | 😊 |
| 2 | 实现LRU内存模型 | 😊 | 😊 |
| 3 | 并查集实现最小生成树 | 😊 | 😊 |
| 4 | 最短路径算法 | 🙂 | 🙂 |
| 5 | 重载赋值运算符 | 😀 | 😀 |
| 6 | 调整数组使奇数位于偶数前面 | 😀 | 😀 |
| 7 | 第一个只出现一次的字符 | 😂 | 😂 |
| 8 | 奇偶升降序数组重组 |
解答：
二叉搜索树的第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
using namespace std;
int midTravelKthest(TreeNode* root, int k){
TreeNode* p = root;
stack<TreeNode*> s;
int count = 0;
while(p || !s.empty()){
if(p){
s.push(p);
p = p->left;
}else{
p = s.top();
s.pop();
count++;
if (count == k) {
cout << p->val << endl;
return;
}
p = p->right;
}
}
}
实现LRU内存模型
解答：
- get操作，先检查pos 优先级set里面是否有该元素，如果有则重新put该k-value。
- put操作，先检查其中pos是否有该key，如果有，则erase该元素 通过iterator，如果没有，则检查元素的个数是否达到了capacity，如果到了就要将list队尾元素erase掉；最后统一的在队列最前面插入元素，并在pos中记录其位置
代码：
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
30class LRU {
public:
LRU : capacity(int ca){}
int Get(int key){
if(pos.find(key) != pos.end()){
Put(key, recent[pos[key].second]);
return recent[pos[key]].second;
}
return -1;
}
int Put(int key, int val){
if(pos.find(key) != pos.end()){
recent.erase(pos[key]);
}else if (pos.size() >= capacity){
pos.erase(recent.back().first);
recent.pop_back();
}
recent.push_front({key, val});
pos[key] = recent.begin();
}
private:
int capacity;
list<pair<int, int>> recent;
unordered_map<int, list< pair<int, int> >::iterator> pos;
};
并查集生成找到最小生成树
标签：并查集
解答：最小生成树，是将一个图形成一个连接分量，而这个连接分量的边的权值之和最小。采用贪心法，首先将边按权值大小进行排序。边按大小顺序进行连通，连通前检查该连通的头是否相同，即是否形成环，若形成环则取消该边的加入，若不形成环则将该边加入到连通分量，当连通了所有的点之后，则形成了左右的最小的生成树
代码：
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
59
60
61
62
63
using namespace std;
//第一部分完成并查集类的设计
class UnionFindSet {
public:
UnionFindSet(int s){
size = s;
parents = vector<int>(-1, s);
}
int Find(int x){
if(parents[x] < 0) return x;
return parents[x] = Find(parents[x]);
}
void Union(int root1, int root2){
if(root1 == root2) return;
if(parents[root1] < parents[root2]){
parents[root2] = root1;
parents[root1] -= 1;
}else {
parents[root1] = root2;
parents[root2] -= 1;
}
return;
}
private:
vector<int> parents;
int size;
}
struct Edge {
int begin;
int end;
int val;
}
vector<Edge> krus(vector<Edge> edges, int n){
vector<Edge> res;
UnionFindSet ufs = new UnionFindSet(n+1);
for(auto edge : edges){
q.push(edge);
}
int i= 0;
while(i < n){
Edge temp = q.top();
q.pop();
if(ufs.Find(temp.begin) == ufs.Find(temp.end)){
continue;
}else{
ufs.Union(ufs.Find(temp.begin), ufs.Find(temp.end));
res.push_back(temp);
i++;
}
}
return res;
}
最短路径算法-dijskra算法
标签：priority_queue
解答：算法有几个辅助的存储，
- dis保存每个点到起点的距离的数组
- vis记录是否拜访过
- pre记录通过该点的上一个拜访点
- priority_queue记录了可访问点的集合，保存的是pair<dis, node_id> 该点到起点的最小距离，通过优先级对列每次都将最小距离的点先拜访，这样就形成了最短路径，到该点的距离最短
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18int Dijkstra(int x){
while(!q.empty()){
pair<int, int> temp;
temp = q.top();
q.pop();
if( vis[temp->second] != 0) continue;
vis[temp->second]++;
for(int i = 1; i <= M; i++){
if(graph[temp->second][i] < INT_MAX && vis[i] != 0 && dis[i] > dis[temp->second] + graph[temp->second][i]){
dis[i] = dis[temp->second] + graph[temp->second][i];
pre[i] = temp->second;
q.push_back(make_pair(dis[i], i));
}
}
}
}
错题集
| 序号 | 题目 | 代码 | 解答 |
|---|---|---|---|
| 1 | 清除注释代码 | 😊 | 😊 |
| 2 | 空缺的第一个正整数 | 😢 | 😢 |
| 3 | 数组组成最小的整数 | 😭 | 😭 |
| 4 | Knight走棋的最小步骤 | 🙂 | 🙂 |
remove comments from a given c/c++ program
- 标签：c++, string
- 解答：指定单行注释标示和多行注释标示，当处理流程为判断当前的是否处在注释期间，处理流程为：
- 如果在单行注释区间，是否当了行尾
- 如果在多行注释区间，是否在多行注释结尾
- 如果在注释区间，当前字符丢弃
- 如果不在注释区间，而找到了单行注释的开头，改变单行注释的标示
- 不在注释区间，找到了多行注释的开头，改变多行注释的标示
- 如果不在注释区间，也没找到标示，则留下当前字符
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
59
60
using namespace std;
string removeComments(string prgm)
{
int n = prgm.length();
string res;
// Flags to indicate that single line and multpile line comments
// have started or not.
bool s_cmt = false;
bool m_cmt = false;
// Traverse the given program
for (int i=0; i<n; i++)
{
// If single line comment flag is on, then check for end of it
if (s_cmt == true && prgm[i] == '\n')
s_cmt = false;
// If multiple line comment is on, then check for end of it
else if (m_cmt == true && prgm[i] == '*' && prgm[i+1] == '/')
m_cmt = false, i++;
// If this character is in a comment, ignore it
else if (s_cmt || m_cmt)
continue;
// Check for beginning of comments and set the approproate flags
else if (prgm[i] == '/' && prgm[i+1] == '/')
s_cmt = true, i++;
else if (prgm[i] == '/' && prgm[i+1] == '*')
m_cmt = true, i++;
// If current character is a non-comment character, append it to res
else res += prgm[i];
}
return res;
}
// Driver program to test above functions
int main()
{
string prgm = " /* Test program */ \n"
" int main() \n"
" { \n"
" // variable declaration \n"
" int a, b, c; \n"
" /* This is a test \n"
" multiline \n"
" comment for \n"
" testing */ \n"
" a = b + c; \n"
" } \n";
cout << "Given Program \n";
cout << prgm << endl;
cout << " Modified Program ";
cout << removeComments(prgm);
return 0;
}空缺的第一个正整数
标签：array
解答：
- 位图法：将每个正整数进行按顺序进行标记
- 转换位置法：将数据按其大小放到该放的位置上，速度上较快，缺点：当不是从0开始计数时，则需要先找到最大的数据
- 去重后的最小堆：将数据一个个放出，是否满足规则，但是比较慢
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20int firstMissingPositive(vector<int> &nums){
int n = nums.size();
for(int i = 0; i < n; i++){
while(nums[i] != i + 1){
int v = nums[i];
// 针对从0开始的第一个缺失的数，大于0的数据即可丢失
if(v > n || v <= 0) break;
else{
if(nums[v-1] == v) break;
swap(nums[v - 1], nums[i]);
}
}
}
for(int i=0; i < n; i++){
if(nums[i] != i + 1) return i +1;
}
return n + 1;
}
数组组成最小的整数
标签: string
解法：理解比较算法，通过字符串大小的比较得到字符串相对的位置，最后将字符串的位置串起来就可以得到最后组成的最小的字符串，由于算法题需要证明字符串比较的各种延展和传递性，这里不展开比较。
代码：
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//
// Created by zhanGGe on 2018/10/23.
//
using namespace std;
int main(){
int N;
cin >> N;
vector<string> data_s(N, "");
for(int i = 0; i < N; i++){
cin >> data_s[i];
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N - i - 1; j++){
if(data_s[i] > data_s[i+1]){
string temp = data_s[i];
data_s[i] = data_s[i + 1];
data_s[i + 1] = temp;
}
}
}
string res = "";
for(int i = 0 ; i < N; i++){
res += data_s[i];
}
cout << res << endl;
return 0;
}反思：对string还是不是很熟悉，默认的库里已经对string的各种操作符进行了重载完全可以重新使用包括“+”， “>”等等。对于剑指offer的题目的理解和练习漏洞太多了。
knight的最小步数
关键词： bfs
解析：当处理图中最小步数问题的时候，直接想到最短路劲问题，最短路径的实现实际上就是利用的bfs，分层去探索不同的路，当找到重点时反馈行走的步数，若队列都pop完了还是没找到，则不可能到达改点返回-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//
// Created by zhanGGe on 2018/10/23.
//
using namespace std;
int moves[][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
struct pos{
int x;
int y;
pos(int m, int n){
x = m;
y = n;
}
};
int main(){
queue<pos> q;
pos start(2, 2);
q.push(start);
int D_x = 0;
int D_y = 1;
int M = 5;
int N = 5;
int count = 0;
if(start.x == D_x && start.y == D_y) {
cout << 0;
return 0;
}
while(!q.empty()){
count++;
pos temp = q.front();
q.pop();
for(auto move : moves){
int x = temp.x + move[0];
int y = temp.y + move[1];
if(x== D_x && y == D_y){
cout << count << endl;
return 0;
}
if(x >=0 && x < M && y >= 0 && y < M){
q.push(pos(x, y));
}
}
}
cout << -1 << endl;
return 0;
}反思：
- 对queue的几个操作还不熟悉
- front() 返回 队列的头
- back() 返回队列的尾
- push() 插入元素在尾部
- pop() 在头部删除元素
- 对于图或者树的BFS的理解不够
- BFS肯定类似于层次遍历，肯定不能采用递归的方法，需要使用非递归加queue的方法去使用
- 对queue的几个操作还不熟悉
重载赋值运算符
解答：这里考虑的主要问题是带类成员变量的类的赋值运算函数的重载要考虑深复制，这里先
复习一下：
赋值运算函数和复制构造函数的区别和运用的场景的不同。
复制构造函数： 用于将一个对象复制到新创建的对象中。用于初始化过程中
何时调用：新建一个对象并将其初始化为同类的现有对象时
1
2string metoo = motto; // 调用复制构造函数
string also = String(motto); // 先复制构造函数每当程序生成一个对象的复本，编译器都会先调用的复制构造函数，具体说就是按值传递或函数返回对象的时候，就是说产生临时复本的时候都会调用复制构造函数，所以用值传递减少复制构造函数的调用
有何功能：
- 默认的复制构造函数会逐个复制非静态的成员函数，复制的是成员的值，所以默认的复制构造函数只是浅复制
- 一般要定制显示构造函数进行深度复制
赋值运算符的重构
- 定义：类对象赋值。通过类重载赋值运算符实现。
- 何时使用：将已有的一个对象赋值给另外一个对象的时候，将使用重载的运算符
- 有何功能：
- 复制数据前会将以前的分配的空间进行释放
- 函数应该避免将值赋给自身，因为赋值前会将自己空间进行释放
- 函数指向一个指向调用对象的引用，因为需要进行连续的赋值
引出关于运算符的话题
重载的运算符是选择成为成员函数还是非成员函数
成员函数通过成员进行调动
非成员对象不需要成员调动，左边的操作数对应于运算符函数的第一个参数，右边的操作符对应于第二个参数，问题是非成员函数不能访问类的私有数据
Friend Time operator*(double m, const Time &t);
双向操作符和单向操作符在重载的时候有区别吗？
解法：按上述的三个要点
代码：
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
38class string {
public:
string(const char* s);
string();
~string();
private:
char* str;
int len;
}
// 1. 返回string &， 这样才可以连续赋值
// 2. 输入的参数为常量引用，引用可以减少复制构造函数调用，由于函数内不会变更实例的状态，需要将输入参数的定义为常量
// 3. 需要将原先对象占据的空间清除
// 4. 赋值操作需要避免赋值给自己，需要检查是否赋值给自己
string & string::operator=(const string & st){
if(this == &st) return *this; //避免自己赋值给自己
delete[] str;
len = st.len;
str = new char[len + 1];
std::strcpy(str, st.str);
return *this;
}
// 升级的代码考虑了异常安全性的原则， 赋值函数内部抛出异常的时候，str由于delete了，会指向不定的地址，导致异常安全性问题，完美的方案是不让空指针产生，让临时的string变量承接输入变量，置换内部的指针和变量，临时变量调用正常调用析构函数释放空间
string& string::operator=(const string & st){
if(this != &st){
string temp(st);
char* pTemp = temp.str;
temp.str = str;
str = pTemp;
int lenTemp = temp.len;
temp.len = len;
len = lenTemp;
}
return *this;
}
奇偶升降序数组重组
题目：一个数组奇数位是降序，偶数位是升序，重组数组，将数组从小到大排列，算法复杂度要求是O(n)。
解法：可以将奇数位数组想成一个带顺序的数组，偶数位数组也是一个带顺序的数组，题目就是一个合并两个排序数组的题目。
代码:
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//
// Created by 张哲 on 2018/11/8.
//
using namespace std;
vector<int> MySort(vector<int> data){
int len = data.size();
int i = 0;
int j = (len % 2 == 0) ? len -1 : len - 2;
cout << "i: " << i << endl;
cout << "j: " << j << endl;
vector<int> res;
while( i <= (len - 1) && (j >= 0)){
if(data[i] < data[j]){
res.push_back(data[i]);
i = i + 2;
}else{
res.push_back(data[j]);
j = j - 2;
}
}
while(i <= len - 1){
res.push_back(data[i]);
i = i+ 2;
}
while(j >= 0){
res.push_back(data[j]);
j= j - 2;
}
return res;
}
int main(){
vector<int> data = {0, 10, 1, 9, 2, 5, 4, 4, 5, 3, 10, 2, 20, -1};
for(auto v : MySort(data)){
cout << v << " " ;
}
cout << endl;
return 1;
}
动态规划专题
最长有效括号对
Unique Path II 有障碍物情况下，一点到另外一点的走法
| 序号 | 题目 | 解答 | 代码 |
|---|---|---|---|
| 1 | 将数据尽量平均的分到两个数组 | 🤣 | 🤣 |
将数据尽量平均的分到两个数组
关键词： 动态规划
解答： 将数组尽量平均的分配到两个数组，可以转化为将数据放到zongzhizongzhi
海量数据处理
TopN的问题
- 海量数据中找到重复次数最多的一个
内存可以放下的TopN问题
- 快排降低排序数量
- 堆排序，保留topN
位图法
- 在2.5亿数字中找出不重复的数字
- 使用2-bit位图法，00表示不存在，01表示出现一次， 10表示出现多次，11表示无意义。这样需要1G内存
- 或者hash划分小文件，小文件使用hash_set检查各个元素，得到不重复的整数
如何在40亿数字中判断是否有某个数
- 位图法标记某个数是否存在，check标记数组
设计题： 设计长链接转短链接
- 基于范围的查找的数据结构： B+树 和跳表
- 散列表扩容的方案
- static 其他文件调用的方法
哈夫曼树
是什么？
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。
怎么用？
怎么构建哈夫曼树？
演算过程[编辑]
进行霍夫曼编码前，我们先创建一个霍夫曼树。
⒈将每个英文字母依照出现频率由小排到大，最小在左，如Fig.1。
⒉每个字母都代表一个终端节点（叶节点），比较F.O.R.G.E.T六个字母中每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点。如Fig.2所示，发现F与O的频率最小，故相加2+3=5。
⒊比较5.R.G.E.T，发现R与G的频率最小，故相加4+4=8。
⒋比较5.8.E.T，发现5与E的频率最小，故相加5+5=10。
⒌比较8.10.T，发现8与T的频率最小，故相加8+7=15。
⒍最后剩10.15，没有可以比较的对象，相加10+15=25。
进行编码1.给霍夫曼树的所有左链接’0’与右链接’1’。
2.从树根至树叶依序记录所有字母的编码，如Fig.3。