Skip to content

Commit 8ee1866

Browse files
krahetskrahets
committed
1. Add C++ codes.
2. Update readme. 3. Add docstring in Python, Java, C++ libs.
1 parent 2656687 commit 8ee1866

File tree

118 files changed

+4349
-25
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

118 files changed

+4349
-25
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
[![stars](https://img.shields.io/github/stars/krahets/LeetCode-Book?style=social)](https://github.com/krahets/LeetCode-Book) [![forks](https://img.shields.io/github/forks/krahets/LeetCode-Book?style=social)](https://github.com/krahets/LeetCode-Book) [![followers](https://img.shields.io/github/followers/krahets?style=social)](https://github.com/krahets)
44

5-
![leetcode-tests](https://img.shields.io/badge/LeetCode%20tests-75%20passed%2C%200%20failed-brightgreen) [![Python](https://img.shields.io/badge/Language-Python3-teal)](https://github.com/krahets/LeetCode-Book/tree/main/python) [![Java](https://img.shields.io/badge/Language-Java-orange)](https://github.com/krahets/LeetCode-Book/tree/main/java) [![C++](https://img.shields.io/badge/Language-C++-blue)](https://github.com/krahets/LeetCode-Book/tree/main/cpp)
5+
![leetcode-tests](https://img.shields.io/badge/LeetCode%20tests-75%20accepted%2C%200%20failed-brightgreen) [![Python](https://img.shields.io/badge/Language-Python3-teal)](https://github.com/krahets/LeetCode-Book/tree/main/python) [![Java](https://img.shields.io/badge/Language-Java-orange)](https://github.com/krahets/LeetCode-Book/tree/main/java) [![C++](https://img.shields.io/badge/Language-C++-blue)](https://github.com/krahets/LeetCode-Book/tree/main/cpp)
66

77
本 Repo 为 LeetBook《图解算法数据结构》的配套代码仓，全部代码已在本地与 LeetCode 测试通过。
88

‎cpp/include/ListNode.hpp

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/*
2+
* File: PrintUtil.hpp
3+
* Created Time: 2021-12-19
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#pragma once
8+
9+
#include <iostream>
10+
using namespace std;
11+
12+
/**
13+
* @brief Definition for a singly-linked list node
14+
*
15+
*/
16+
struct ListNode {
17+
int val;
18+
ListNode *next;
19+
ListNode(int x) : val(x), next(nullptr) {}
20+
};
21+
22+
/**
23+
* @brief Generate a linked list with a vector
24+
*
25+
* @param list
26+
* @return ListNode*
27+
*/
28+
ListNode* vectorToLinkedList(vector<int> list) {
29+
ListNode *dum = new ListNode(0);
30+
ListNode *head = dum;
31+
for (int val : list) {
32+
head->next = new ListNode(val);
33+
head = head->next;
34+
}
35+
return dum->next;
36+
}
37+
38+
/**
39+
* @brief Get a list node with specific value from a linked list
40+
*
41+
* @param head
42+
* @param val
43+
* @return ListNode*
44+
*/
45+
ListNode* getListNode(ListNode *head, int val) {
46+
while (head != nullptr && head->val != val) {
47+
head = head->next;
48+
}
49+
return head;
50+
}

‎cpp/include/PrintUtil.hpp

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
/*
2+
* File: PrintUtil.hpp
3+
* Created Time: 2021-12-19
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#pragma once
8+
9+
#include <iostream>
10+
#include <string>
11+
#include <sstream>
12+
#include "ListNode.hpp"
13+
#include "TreeNode.hpp"
14+
15+
/**
16+
* @brief Find an element in a vector
17+
*
18+
* @tparam T
19+
* @param vec
20+
* @param ele
21+
* @return int
22+
*/
23+
template <typename T>
24+
int vecFind(const vector<T>& vec, T ele) {
25+
int j = INT_MAX;
26+
for (int i = 0; i < vec.size(); i++) {
27+
if (vec[i] == ele) {
28+
j = i;
29+
}
30+
}
31+
return j;
32+
}
33+
34+
/**
35+
* @brief Concatenate a vector with a delim
36+
*
37+
* @tparam T
38+
* @param delim
39+
* @param vec
40+
* @return string
41+
*/
42+
template <typename T>
43+
string join(const string& delim, const T& vec) {
44+
ostringstream s;
45+
for (const auto& i : vec) {
46+
if (&i != &vec[0]) {
47+
s << delim;
48+
}
49+
s << i;
50+
}
51+
return s.str();
52+
}
53+
54+
/**
55+
* @brief Repeat a string for n times
56+
*
57+
* @param str
58+
* @param n
59+
* @return string
60+
*/
61+
string repeat(string str, int n) {
62+
ostringstream os;
63+
for(int i = 0; i < n; i++)
64+
os << str;
65+
return os.str();
66+
}
67+
68+
/**
69+
* @brief Get the Vector String object
70+
*
71+
* @tparam T
72+
* @param list
73+
* @return string
74+
*/
75+
template <typename T>
76+
string getVectorString(vector<T> &list) {
77+
return "[" + join(", ", list) + "]";
78+
}
79+
80+
/**
81+
* @brief Print a vector
82+
*
83+
* @tparam T
84+
* @param list
85+
*/
86+
template <typename T>
87+
void printVector(vector<T> &list) {
88+
cout << getVectorString(list) << '\n';
89+
}
90+
91+
/**
92+
* @brief Print a vector matrix
93+
*
94+
* @tparam T
95+
* @param matrix
96+
*/
97+
template <typename T>
98+
void printVectorMatrix(vector<vector<T>> &matrix) {
99+
cout << "[" << '\n';
100+
for (vector<T> &list : matrix)
101+
cout << " " + getVectorString(list) + "," << '\n';
102+
cout << "]" << '\n';
103+
}
104+
105+
/**
106+
* @brief Print a linked list
107+
*
108+
* @param head
109+
*/
110+
void printLinkedList(ListNode *head) {
111+
vector<int> list;
112+
while (head != nullptr) {
113+
list.push_back(head->val);
114+
head = head->next;
115+
}
116+
117+
cout << join(" -> ", list) << '\n';
118+
}
119+
120+
/**
121+
* @brief Print helper for binary tree
122+
*
123+
* @param root
124+
* @param level
125+
*/
126+
void printTreeHelper(TreeNode *root, int level) {
127+
if (root == nullptr)
128+
return;
129+
printTreeHelper(root->right, level + 1);
130+
cout << repeat(" ", 4 * level) + "->" << root->val << '\n';
131+
printTreeHelper(root->left, level + 1);
132+
}
133+
134+
/**
135+
* @brief Print a binary tree (90º counter-clockwise rotated)
136+
*
137+
* @param root
138+
*/
139+
void printTree(TreeNode *root) {
140+
printTreeHelper(root, 0);
141+
}

‎cpp/include/TreeNode.hpp

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/*
2+
* File: PrintUtil.hpp
3+
* Created Time: 2021-12-19
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#pragma once
8+
9+
/**
10+
* @brief Definition for a binary tree node
11+
*
12+
*/
13+
struct TreeNode {
14+
int val;
15+
TreeNode *left;
16+
TreeNode *right;
17+
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
18+
};
19+
20+
/**
21+
* @brief Generate a binary tree with a vector
22+
*
23+
* @param list
24+
* @return TreeNode*
25+
*/
26+
TreeNode* vectorToTree(vector<int> list) {
27+
TreeNode *root = new TreeNode(list[0]);
28+
queue<TreeNode*> que;
29+
que.emplace(root);
30+
int i = 1;
31+
while(!que.empty()) {
32+
TreeNode *node = que.front();
33+
que.pop();
34+
if(list[i] != INT_MAX) {
35+
node->left = new TreeNode(list[i]);
36+
que.emplace(node->left);
37+
}
38+
i++;
39+
if(list[i] != INT_MAX) {
40+
node->right = new TreeNode(list[i]);
41+
que.emplace(node->right);
42+
}
43+
i++;
44+
}
45+
return root;
46+
}
47+
48+
/**
49+
* @brief Get a tree node with specific value in a binary tree
50+
*
51+
* @param root
52+
* @param val
53+
* @return TreeNode*
54+
*/
55+
TreeNode* getTreeNode(TreeNode *root, int val) {
56+
if (root == nullptr)
57+
return nullptr;
58+
if (root->val == val)
59+
return root;
60+
TreeNode *left = getTreeNode(root->left, val);
61+
TreeNode *right = getTreeNode(root->right, val);
62+
return left != nullptr ? left : right;
63+
}

‎cpp/include/include.hpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/*
2+
* File: PrintUtil.hpp
3+
* Created Time: 2021-12-19
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#pragma once
8+
9+
#include <iostream>
10+
#include <string>
11+
#include <vector>
12+
#include <stack>
13+
#include <queue>
14+
#include <deque>
15+
#include <unordered_map>
16+
#include <unordered_set>
17+
#include <set>
18+
19+
#include "ListNode.hpp"
20+
#include "TreeNode.hpp"
21+
#include "PrintUtil.hpp"
22+
23+
using namespace std;

‎cpp/sfo_03_find_duplicate_numbers_in_an_array_s1/sfo_03_find_duplicate_numbers_in_an_array_s1.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/*
2+
* File: sfo_03_find_duplicate_numbers_in_an_array_s1.cpp
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#include "../include/include.hpp"
8+
9+
// ===== Solution Code =====
10+
class Solution {
11+
public:
12+
int findRepeatNumber(vector<int>& nums) {
13+
unordered_map<int, bool> map;
14+
for(int num : nums) {
15+
if(map[num]) return num;
16+
map[num] = true;
17+
}
18+
return -1;
19+
}
20+
};
21+
22+
int main() {
23+
// ======= Test Case =======
24+
vector<int> nums = { 2, 3, 1, 0, 2, 5, 3 };
25+
// ====== Driver Code ======
26+
Solution* slt = new Solution();
27+
int res = slt->findRepeatNumber(nums);
28+
cout << res << endl;
29+
30+
return 0;
31+
}

‎cpp/sfo_03_find_duplicate_numbers_in_an_array_s2/sfo_03_find_duplicate_numbers_in_an_array_s2.cpp

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
* File: sfo_03_find_duplicate_numbers_in_an_array_s2.cpp
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#include "../include/include.hpp"
8+
9+
// ===== Solution Code =====
10+
class Solution {
11+
public:
12+
int findRepeatNumber(vector<int>& nums) {
13+
int i = 0;
14+
while(i < nums.size()) {
15+
if(nums[i] == i) {
16+
i++;
17+
continue;
18+
}
19+
if(nums[nums[i]] == nums[i])
20+
return nums[i];
21+
swap(nums[i],nums[nums[i]]);
22+
}
23+
return -1;
24+
}
25+
};
26+
27+
int main() {
28+
// ======= Test Case =======
29+
vector<int> nums = { 2, 3, 1, 0, 2, 5, 3 };
30+
// ====== Driver Code ======
31+
Solution* slt = new Solution();
32+
int res = slt->findRepeatNumber(nums);
33+
cout << res << endl;
34+
35+
return 0;
36+
}

‎cpp/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.cpp

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
* File: sfo_04_find_a_number_in_2d_matrix_s1.cpp
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
#include "../include/include.hpp"
8+
9+
// ===== Solution Code =====
10+
class Solution {
11+
public:
12+
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
13+
int i = matrix.size() - 1, j = 0;
14+
while(i >= 0 && j < matrix[0].size())
15+
{
16+
if(matrix[i][j] > target) i--;
17+
else if(matrix[i][j] < target) j++;
18+
else return true;
19+
}
20+
return false;
21+
}
22+
};
23+
24+
int main() {
25+
// ======= Test Case =======
26+
vector<vector<int>> matrix = {
27+
{ 1, 4, 7, 11, 15 },
28+
{ 2, 5, 8, 12, 19 },
29+
{ 3, 6, 9, 16, 22 },
30+
{ 10, 13, 14, 17, 24 },
31+
{ 18, 21, 23, 26, 30 }
32+
};
33+
int target = 5;
34+
// ====== Driver Code ======
35+
Solution* slt = new Solution();
36+
bool res = slt->findNumberIn2DArray(matrix, target);
37+
cout << boolalpha << res << endl;
38+
39+
return 0;
40+
}

0 commit comments

Comments
 (0)