Skip to content

Commit 649c652

Browse files
krahetskrahets
committed
[Update]
1. Update topic names of Pyhon file. 2. Replace the binary tree printer with a more clear one. 3. Update README.
1 parent 61d63ee commit 649c652

File tree

90 files changed

+310
-176
lines changed

Some content is hidden

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

90 files changed

+310
-176
lines changed

‎.gitignore

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
__pycache__
2+
.vscode
3+
.DS_Store

‎README.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ LeetBook《图解算法数据结构》面向算法初学者、互联网求职者
1010

1111
### :green_book: 剑指 Offer 图文题解
1212

13-
- 图文详解 75 道题目，覆盖主要算法知识点，非常适合作为算法学习的**第一份题库**。
13+
- 图文详解 75 道题目，覆盖主要算法知识点，非常适合作为算法学习的 **第一份题库** 。
1414
- 题库活跃于各大互联网公司招聘中，可使笔面试准备事半功倍。
1515
- 致力于行文深入浅出、图文搭配，提供简洁的 **Python3, Java, C++** 解题代码。
1616
- 笔者整理了 **30 天刷题计划**、**题目分类**，让刷题有迹可循。
@@ -35,8 +35,8 @@ LeetBook《图解算法数据结构》面向算法初学者、互联网求职者
3535

3636
> 建议对数据结构不熟悉的同学，先看这篇熟悉用法。
3737
38-
- 常用数据结构的**分类**和**基本特点**；
39-
- 在算法解题中，数据结构的**常用操作**；
38+
- 常用数据结构的**分类**和**基本特点**。
39+
- 在算法解题中，数据结构的**常用操作**。
4040
- 在 Python3 , Java , C++ 语言中，各数据结构的**初始化与构建方法**。
4141

4242
### 「[算法复杂度](https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/r84gmi/)」

‎cpp/include/PrintUtil.hpp

Lines changed: 173 additions & 117 deletions
Original file line numberDiff line numberDiff line change
@@ -12,130 +12,186 @@
1212
#include "ListNode.hpp"
1313
#include "TreeNode.hpp"
1414

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;
15+
class PrintUtil {
16+
public:
17+
/**
18+
* @brief Find an element in a vector
19+
*
20+
* @tparam T
21+
* @param vec
22+
* @param ele
23+
* @return int
24+
*/
25+
template <typename T>
26+
static int vecFind(const vector<T>& vec, T ele) {
27+
int j = INT_MAX;
28+
for (int i = 0; i < vec.size(); i++) {
29+
if (vec[i] == ele) {
30+
j = i;
31+
}
32+
}
33+
return j;
2934
}
30-
}
31-
return j;
32-
}
3335

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;
36+
/**
37+
* @brief Concatenate a vector with a delim
38+
*
39+
* @tparam T
40+
* @param delim
41+
* @param vec
42+
* @return string
43+
*/
44+
template <typename T>
45+
static string strJoin(const string& delim, const T& vec) {
46+
ostringstream s;
47+
for (const auto& i : vec) {
48+
if (&i != &vec[0]) {
49+
s << delim;
50+
}
51+
s << i;
52+
}
53+
return s.str();
4854
}
49-
s << i;
50-
}
51-
return s.str();
52-
}
5355

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-
}
56+
/**
57+
* @brief Repeat a string for n times
58+
*
59+
* @param str
60+
* @param n
61+
* @return string
62+
*/
63+
static string strRepeat(string str, int n) {
64+
ostringstream os;
65+
for(int i = 0; i < n; i++)
66+
os << str;
67+
return os.str();
68+
}
6769

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-
}
70+
/**
71+
* @brief Get the Vector String object
72+
*
73+
* @tparam T
74+
* @param list
75+
* @return string
76+
*/
77+
template <typename T>
78+
static string getVectorString(vector<T> &list) {
79+
return "[" + strJoin(", ", list) + "]";
80+
}
7981

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-
}
82+
/**
83+
* @brief Print a vector
84+
*
85+
* @tparam T
86+
* @param list
87+
*/
88+
template <typename T>
89+
static void printVector(vector<T> &list) {
90+
cout << getVectorString(list) << '\n';
91+
}
9092

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-
}
93+
/**
94+
* @brief Print a vector matrix
95+
*
96+
* @tparam T
97+
* @param matrix
98+
*/
99+
template <typename T>
100+
static void printVectorMatrix(vector<vector<T>> &matrix) {
101+
cout << "[" << '\n';
102+
for (vector<T> &list : matrix)
103+
cout << " " + getVectorString(list) + "," << '\n';
104+
cout << "]" << '\n';
105+
}
104106

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-
}
107+
/**
108+
* @brief Print a linked list
109+
*
110+
* @param head
111+
*/
112+
static void printLinkedList(ListNode *head) {
113+
vector<int> list;
114+
while (head != nullptr) {
115+
list.push_back(head->val);
116+
head = head->next;
117+
}
118+
119+
cout << strJoin(" -> ", list) << '\n';
120+
}
119121

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-
}
122+
/**
123+
* @brief This tree printer is borrowed from TECHIE DELIGHT
124+
* https://www.techiedelight.com/c-program-print-binary-tree/
125+
*/
126+
struct Trunk {
127+
Trunk *prev;
128+
string str;
129+
Trunk(Trunk *prev, string str) {
130+
this->prev = prev;
131+
this->str = str;
132+
}
133+
};
134+
135+
/**
136+
* @brief Helper function to print branches of the binary tree
137+
*
138+
* @param p
139+
*/
140+
static void showTrunks(Trunk *p) {
141+
if (p == nullptr) {
142+
return;
143+
}
144+
145+
showTrunks(p->prev);
146+
cout << p->str;
147+
}
133148

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-
}
149+
/**
150+
* @brief The interface of the tree printer
151+
*
152+
* @param root
153+
*/
154+
static void printTree(TreeNode *root) {
155+
printTree(root, nullptr, false);
156+
}
157+
158+
/**
159+
* @brief Print a binary tree
160+
*
161+
* @param root
162+
* @param prev
163+
* @param isLeft
164+
*/
165+
static void printTree(TreeNode *root, Trunk *prev, bool isLeft) {
166+
if (root == nullptr) {
167+
return;
168+
}
169+
170+
string prev_str = " ";
171+
Trunk *trunk = new Trunk(prev, prev_str);
172+
173+
printTree(root->right, trunk, true);
174+
175+
if (!prev) {
176+
trunk->str = "———";
177+
}
178+
else if (isLeft) {
179+
trunk->str = "/———";
180+
prev_str = " |";
181+
}
182+
else {
183+
trunk->str = "\\———";
184+
prev->str = prev_str;
185+
}
186+
187+
showTrunks(trunk);
188+
cout << " " << root->val << endl;
189+
190+
if (prev) {
191+
prev->str = prev_str;
192+
}
193+
trunk->str = " |";
194+
195+
printTree(root->left, trunk, false);
196+
}
197+
};

‎cpp/sfo_06_print_a_linked_list_in_reverse_order_s1/sfo_06_print_a_linked_list_in_reverse_order_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ int main() {
2828
// ====== Driver Code ======
2929
Solution* slt = new Solution();
3030
vector<int> res = slt->reversePrint(head);
31-
printVector(res);
31+
PrintUtil::printVector(res);
3232

3333
return 0;
3434
}

‎cpp/sfo_06_print_a_linked_list_in_reverse_order_s2/sfo_06_print_a_linked_list_in_reverse_order_s2.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ int main() {
3030
// ====== Driver Code ======
3131
Solution* slt = new Solution();
3232
vector<int> res = slt->reversePrint(head);
33-
printVector(res);
33+
PrintUtil::printVector(res);
3434

3535
return 0;
3636
}

‎cpp/sfo_07_reconstruct_binary_tree_s1/sfo_07_reconstruct_binary_tree_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ int main() {
3535
// ====== Driver Code ======
3636
Solution* slt = new Solution();
3737
TreeNode* res = slt->buildTree(preorder, inorder);
38-
printTree(res);
38+
PrintUtil::printTree(res);
3939

4040
return 0;
4141
}

‎cpp/sfo_09_implement_a_queue_using_two_stacks_s1/sfo_09_implement_a_queue_using_two_stacks_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ int main() {
4141
cQueue->appendTail(2);
4242
res.push_back(cQueue->deleteHead());
4343
res.push_back(cQueue->deleteHead());
44-
printVector(res);
44+
PrintUtil::printVector(res);
4545

4646
return 0;
4747
}

‎cpp/sfo_18_delete_a_node_from_a_linked_list_s1/sfo_18_delete_a_node_from_a_linked_list_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ int main() {
2828
// ====== Driver Code ======
2929
Solution* slt = new Solution();
3030
ListNode* res = slt->deleteNode(head, val);
31-
printLinkedList(res);
31+
PrintUtil::printLinkedList(res);
3232

3333
return 0;
3434
}

‎cpp/sfo_21_adjust_the_order_of_numbers_in_an_array_s1/sfo_21_adjust_the_order_of_numbers_in_an_array_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ int main() {
2727
// ====== Driver Code ======
2828
Solution* slt = new Solution();
2929
vector<int> res = slt->exchange(nums);
30-
printVector(res);
30+
PrintUtil::printVector(res);
3131

3232
return 0;
3333
}

‎cpp/sfo_22_the_kth_node_from_the_end_of_a_linked_list_s1/sfo_22_the_kth_node_from_the_end_of_a_linked_list_s1.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ int main() {
2828
// ====== Driver Code ======
2929
Solution* slt = new Solution();
3030
ListNode* res = slt->getKthFromEnd(head, k);
31-
printLinkedList(res);
31+
PrintUtil::printLinkedList(res);
3232

3333
return 0;
3434
}

0 commit comments

Comments
 (0)