发表于 | 分类于

Longest Substring Without Repeating Characters

题目描述：

给定一个字符串，找到字符串中最长的子串的长度，其子串中的所有字母不重复。见LeetCode3

例子：

‘abcabcbb’其中最长的不重复子串的长度是3；’abba’其中最长的不重复的子串的长度是2。

解题思路：

我们在遍历字符串的过程中，每遍历一个新的位置需要知道当前位置的字母是否曾经在前面中出现，因此我们需要一个哈希表来记录我们先前遍历字母和字母所在的位置；其次在遇到与先前的字母重复时，我们需要找到最靠右侧的那个位置；所以我们需要在哈希表中保存着这个字母在字符串中最右侧的位置。综上整体的思路是，我们定义start和end来代表当前子串的头和尾；用哈希表来保存先前遍历过程中所遇到的字母和字母所在的最右的位置；遍历过程中，如果是不重复的字母，则需要end++并更新当前的最长子串长度；如果是重复的，需要判断该字母出现的位置在start的左侧还是右侧，如果是左侧则不影响当前子串；如果是右侧需要更新start到该位置的下一个地方；然后更新子串的长度。

代码如下：

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0)
            return 0;// 字符串为空的情况
            
        int length = 1;
        int start = 0;
        int end = 0;
        map<char, int> hash; //定义所需要的变量
        while(start < s.size() && end < s.size()){
            if (hash.find(s[end]) == hash.end()){
                hash.insert({s[end], end});
                // 如果不存在，更新哈希表
                length = max(end - start + 1, length);
                //更新长度
                end++;
                //遍历下一个字母
            }else{
                if (start < hash[s[end]] + 1)
                    start = hash[s[end]] + 1;
                 // 判断该位置在start的左侧或者右侧决定是否更新
                hash[s[end]] = end;
                // 更新该字母到最右侧的位置
                length = max(end - start + 1, length);
                end++;
                // 更新长度和继续遍历下一个位置
            }
        }
        return length;
        
    }
};

发表于 | 分类于

Combination Sum

题目描述：

给定一个目标值，以及表示累加和数字的个数k。要求得到找到1-9中k个数为目标值的所有可能，要求结果中不存在重复值，且各个数字只能用一次。

例子：

给定k=3,target=7，则结果为[[1,2,4]];给定k=3,target=9,则结果为[[1,2,6],[1,3,5],[2,3,4]],见LeetCode216

解题思路：

首先已知我们只能用1-9的数，所以用过的数不能再次使用。这样相当于构建一棵树，新的节点的可能只能在上一个节点较大值中取。例如我们当前取值了5，则下一个节点的可能值只有6，7，8，9。基于以上事实，我们使用回溯的算法，在不断寻找的过程中，如果条件不满足则返回，如果满足题意则加入到结果中。

代码如下：

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
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res; // 保存返回结果
        vector<int> record;   // 保存当前遍历结果
        dfs(res, k, n, record); //其中用k保存已经使用几个数
        								// n表示我们还需要多少满足目标值
        return res;
        
    }
    void dfs(vector<vector<int>>& res, int k, int n, vector<int>& record){
        if (k == 0 && n == 0){
            res.push_back(record);
            return; // 如果满足条件，则加入结果并返回
        }
        if (n <= 0 || k == 0)
            return;    // 不满足的情况下，我们直接返回
        int start = record.size() == 0 ? 1 : record.back() + 1;
        // 如果当前的遍历结果是空则从0开始
        // 否则从当前遍历结果中最后一个数的下一个数开始寻找
        for (int i = start; i <= 9; i++){
            record.push_back(i); // 将当前遍历值加入遍历结果
            dfs(res, k - 1, n - i, record); // 递归寻找
            record.pop_back();   // 回溯一步不然record里面会不断添加所有遍历过的数
        }
    }
};

发表于 | 分类于

Construct Tree From Array

题目描述1：

给定树的不同的遍历方式来重建树。第一种是根据先序遍历和中序遍历的结果来重建树。

例子：

这道题是leetcode上的题目,具体描述可以看这个。

解题思路：

根据先序遍历的结果我们可以知道树的根节点，根据中序遍历中该根节点的位置，我们可以知道左右子树的节点。假设先序遍历的结果是[1,2,4,5,3,6,7],中序遍历的结果是[4,2,5,1,6,3,7]。我们根据先序遍历的第一个节点是1，所以知道左子树的节点集合是[4,2,5],右子树的节点集合是[6,3,7];然后根据左子树的长度是3知道[2,4,5]是对应左子树的先序遍历的结果;而[3,6,7]则是右子树的先序遍历的结果。如此不断递归构建即可得到树的结果。

代码如下：

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        return generate(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* generate(vector<int>& preorder, vector<int>& inorder, int p_left, int p_right, int i_left, int i_right){
    //构建树的函数里面有6个参数，主要是先序遍历结果，中序遍历结果以及当前构建树对应节点在遍历结果的开始位置和结束位置
    //p_left表示先序遍历的起始，p_right表示先序遍历的结束
    //i_left表示中序遍历的起始，i_right表示中序遍历的结束
        if (p_left == p_right){
            return new TreeNode(preorder[p_left]);
        }
        //如果起始和结束位置相同，表示只有一个节点，直接新建节点返回
        if (p_left > p_right) return NULL;
        //如果起始超过结束，表示无节点，即为空节点
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == preorder[p_left]) {
                next = i;
                break;
            }
        }
        //找到先序遍历起始节点在中序遍历中的位置，用next保存
        
        int left_length = next - i_left;
        //计算左子树的长度
        TreeNode* root = new TreeNode(inorder[next]);
        //新建根节点用起始节点的数值
        root->left = generate(preorder, inorder, p_left + 1, p_left + left_length, i_left, next - 1);
        //递归调用函数来构建树，主要需要注意关于树的起始位置和结束位置的变化
        root->right = generate(preorder, inorder, p_left + left_length + 1, p_right, next + 1, i_right);
        return root;        
    }
};

题目描述2：

当然，也可以根据中序遍历和后序遍历来重建树。解题的思路和上一题类似，我们主要需要注意的是，在递归函数中，起始位置和终止位置的变化如何计算的问题。

例子：

这题也是leetcode上的题目.

代码实现:

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return NULL;
        return generate(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
        
    }
    TreeNode* generate(vector<int>& inorder, vector<int>& postorder, int i_left, int i_right, int p_left, int p_right){
        if (i_left == i_right){
            return new TreeNode(inorder[i_left]);
        }
        if(i_left > i_right){
            return NULL;
        }
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == postorder[p_right]){
                next = i;
                break;
            }
        }
        int length = i_right - next;
        TreeNode* root = new TreeNode(inorder[next]);
        root->left = generate(inorder, postorder, i_left, next - 1, p_left, p_right - length - 1);
        root->right = generate(inorder, postorder, next + 1, i_right, p_right - length, p_right - 1);
        return root;
    }
};

题目描述3：

给定一个数字n，要求得到根据这个数字所得到的数组[1,2,3…..n]，从这个数组中构建搜索二叉树的个数。

例子：

给定数字假设为3，通过计算分别以1，2，3为头结点的有效的搜索二叉树的个数可以知道，其结果为5。

解题思路：

通过从1开始计算其可能的二叉树个数，可以发现规律：当n=1，二叉树的个数为1；当n=2的时候，二叉树的个数为2；当n=3的时候，二叉树的个数为5。分析n=3的情况：以1为头结点，用于构建左子树的数字为空，用于构建右子树的数字为[2,3]，所以总的个数为h(0) h(2) = 2；同理在以2为头结点的情况下，个数为h(1) h(1) = 1；以3为头结点情况，h(2) h(0) = 1;所以一共有5种。通过推广到n；我们用h(i)表示用i个数构建二叉树的个数，h(0)=1,h(1)=1,h(2)=2…则h(n) = h(n-1) h(0) + h(n-2) * h(1)…这样所得到的序列称为卡特兰数序列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numTrees(int n) {
        vector<int>vec;
        vec.push_back(1);
        vec.push_back(1);
        vec.push_back(2);//定义初始的数
        for(int i = 3; i <= n; i++){
            int res = 0;
            for (int j = 1; j <= i; j++){
                res = res + vec[j - 1] * vec[i - j];
            }
            vec.push_back(res);//计算第i个位置的卡特兰数
        }
        return vec[n];
    }
};

题目描述4：

根据上一题的描述，我们要求返回所有有效的二叉树的头结点的集合。解题的思路，主要是利用递归构建树的想法，直接上代码。

代码如下：

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
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res;
        if (n == 0) return res;
        return helper(1, n);
    }
    vector<TreeNode*>helper(int start, int end){
        vector<TreeNode*>res;
        //用来保存当前递归层的可能二叉树的头节点
        if (start > end) res.push_back(NULL);
        //此时直接构建空树
        if (start == end) res.push_back(new TreeNode(start));
        // 此时返回以当前数的节点
        if (start < end){
            for (int i = start; i <= end; i++){
            //遍历以当前范围中各个数为头结点的可能
                vector<TreeNode*>lefts = helper(start, i - 1);
                vector<TreeNode*>rights = helper(i + 1, end);
                //找到该情况下左右子树的头结点的集合
                for (int j = 0; j < (int)lefts.size(); j++){
                    for(int k = 0; k < (int)rights.size(); k++){
                        TreeNode* root = new TreeNode(i);
                        root->left = lefts[j];
                        root->right = rights[k];
                        //指向左右子树
                        res.push_back(root);
                        //保存结果
                    }
                }
            }
        }
        return res;
    }
};

题目描述5:

给定一个已经排序的数组，要求根据数组构建一棵平衡二叉搜索树.
具体的题目描述可以看LeetCode108。

解题思路：

因为要构建平衡二叉搜索树，所以我们可以从数组的中间取出作为根节点，然后递归的建立左右子树即可。

代码如下:

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
//构建平衡二叉搜索树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return NULL;
        return constructTree(0, nums.size() - 1, nums);
        
    }
    TreeNode* constructTree(int low, int high, vector<int>& nums){
        if (low == high){
            TreeNode* p = new TreeNode(nums[low]);
            return p;
            //当left==right代表只剩下一个数用于构建树，所以直接构建新节点然后返回
        }
        if (low > high){
            return NULL;
        }
        //这种情况，说明已经没有节点用于构建树
        int mid = low + (high - low) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        //找到中间节点构建根节点
        root->left = constructTree(low, mid - 1, nums);
        root->right = constructTree(mid + 1, high, nums);
        //递归构建左右子树
        return root;
    }
};

发表于 | 分类于

Find The Duplicate Number(找到数组中的重复数字)

题目描述：

给定一个数组，其长度为n + 1，数组中的数的范围为1到n。其中有且只有一个数重复了，但是可能重复了很多次。要求在O(1)的空间，小于O(n^2)的复杂度，不改变数组的前提下找到该数。具体描述见LeetCode289

解题思路：

要求的空间过小，所以哈希表方法排除；要求复杂度小，所以暴力解法排除；不改变数组，所以交换数组的数排除；所以本题使用的是二分查找法。原理是我们假设有6个抽屉，如果一共有7个苹果，则在其中的一个抽屉中肯定有2个或者2个以上的苹果。同理，我们假设low = 1, high = n(因为数组的范围是这样)。计算得到mid = (low + high) / 2；然后遍历数组中小于或者等于mid的数。如果该数大于mid，则说明在[low, mid]中一定存在重复的数，此时将high = mid；反之，如果该数小于mid,说明在[low, mid]中肯定不存在重复的数；将low = mid + 1(注意不是low = mid,因为这种情况下，我们已经排除了这个数是mid的可能)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1;
        int high = nums.size() - 1;
        int mid = 0;
        int count = 0;
        while(low < high){
            mid = low + (high - low) / 2; // mid作为标杆
            count = 0;
            for (int i = 0; i < nums.size(); i++){
                if (nums[i] <= mid) count++; 
                // 计算数组中小于等于mid的数
            }
            if (count > mid) high = mid;
            if (count <= mid) low = mid + 1;
            // 不同情况下改变low和high
        }
        return low;
    }
};

发表于 | 分类于

Balance Binary Search Tree(构建平衡二叉搜索树)

题目描述：

例子：

解题思路：

代码如下：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
//
// Created by mfzhu on 2017/4/10.
//
#include <iostream>
#include <memory>
using namespace std;
template <typename T>
class TreeNode{
public:
    T value;
    int height;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode(T key): value(key),height(0),left(NULL),right(NULL){};
    TreeNode(T key, int h):value(key), height(h), left(NULL), right(NULL){};
};
template <typename T>
class AVLTree{
public:
    AVLTree():root(NULL){};
    ~AVLTree(){};
    int height();
    T maximum();
    T minimum();
    void inOrder();
    void preOrder();
    void insert(T value);
    TreeNode<T>* remove(TreeNode<T>* key);
    TreeNode<T>* search(T value);
private:
    TreeNode<T>* root;
    int height(TreeNode<T>* node);
    TreeNode<T>* maximum(TreeNode<T>* node);
    TreeNode<T>* minimum(TreeNode<T>* node);
    void inOrder(TreeNode<T>* node);
    void preOrder(TreeNode<T>* node);
    TreeNode<T>* insert(TreeNode<T>* &node, T value);
    TreeNode<T>* remove(TreeNode<T>* &node, TreeNode<T>* key);
    TreeNode<T>* search(TreeNode<T>* node, T val);
    TreeNode<T>* leftLeftRotation(TreeNode<T>* &node);
    TreeNode<T>* leftRightRotation(TreeNode<T>* &node);
    TreeNode<T>* rightLeftRotation(TreeNode<T>* &node);
    TreeNode<T>* rightRightRotation(TreeNode<T>* &node);
};
template <typename T>
int AVLTree<T>::height(TreeNode<T>* node){
    if (node) return node->height;
    return 0;
}
template <typename T>
int AVLTree<T>::height() {
    return height(root);
}
template <typename T>
TreeNode<T>* AVLTree<T>::maximum(TreeNode<T> *node) {
    if (!node)
        return NULL;
    while(node->right){
        node = node->right;
    }
    return node;
}
template <typename T>
T AVLTree<T>::maximum() {
    TreeNode<T>* p = maximum(root);
    if (p) return p->value;
    return T(NULL);
}
template<typename T>
TreeNode<T>* AVLTree<T>::minimum(TreeNode<T> *node) {
    if (!node)
        return NULL;
    while(node->left){
        node = node->left;
    }
    return node;
}
template <typename T>
T AVLTree<T>::minimum(){
    TreeNode<T>* p = minimum(root);
    if (p) return p->value;
    return T(NULL);
}
template <typename T>
void AVLTree<T>::inOrder(TreeNode<T> *node) {
    if (node){
        inOrder(node->left);
        cout << node->value << " ";
        inOrder(node->right);
    }
}
template <typename T>
void AVLTree<T>::inOrder() {
    inOrder(root);
}
template <typename T>
void AVLTree<T>::preOrder(TreeNode<T>* node) {
    if (node){
        cout << node->value << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}
template <typename T>
void AVLTree<T>::preOrder() {
    preOrder(root);
}
template <typename T>
TreeNode<T>* AVLTree<T>::insert(TreeNode<T>* &node, T value) {
    if (node == NULL){
        node = new TreeNode<T>(value);
    }
    else if (value < node->value){
        node->left = insert(node->left, value);
        if (height(node->left) - height(node->right) == 2){
            if (value < node->left->value){
                node = leftLeftRotation(node);
            }else{
                node = leftRightRotation(node);
            }
        }
    }
    else if (value > node->value){
        node->right = insert(node->right, value);
        if (height(node->right) - height(node->left) == 2){
            if (value > node->right->value){
                node = rightRightRotation(node);
            }else{
                node = rightLeftRotation(node);
            }
        }
    }
    else{
        cout << "can not insert existed value" << endl;
    }
    node->height = max(height(node->left), height(node->right)) + 1;
    return node;
}
template <typename T>
void AVLTree<T>::insert(T value) {
    insert(root, value);
}
template <typename T>
TreeNode<T>* AVLTree<T>::remove(TreeNode<T> *&node, TreeNode<T>* key) {
    if (node == NULL || key == NULL)
        return NULL;
    if (key->value < node->value){
        node->left = remove(node->left, key);
        if (height(node->right) - height(node->left) == 2){
            TreeNode<T>* l = node->right;
            if (height(l->right) > height(l->left)){
                node = rightRightRotation(node);
            }else{
                node = rightLeftRotation(node);
            }
        }
    }
    else if (key->value > node->value){
        node->right = remove(node->right, key);
        if (height(node->left) - height(node->right) == 2){
            TreeNode<T>* l = node->left;
            if (height(l->left) > height(l->right)){
                node = leftLeftRotation(node);
            }else{
                node = leftRightRotation(node);
            }
        }
    }
    else{
        if (node->left && node->right){
            if (height(node->left) > height(node->right)){
                TreeNode<T>* max = maximum(node->left);
                node->value = max->value;
                node->left = remove(node->left, max);
            }else{
                TreeNode<T>* min = minimum(node->right);
                node->value = min->value;
                node->right = remove(node->right, min);
            }
        }
        else{
            TreeNode<T>* tmp = node;
            node = node->left ? node->right : node->left;
            delete(tmp);
        }
    }
    return node;
}
template <typename T>
TreeNode<T>* AVLTree<T>::remove(TreeNode<T>* key) {
    return remove(root, key);
}
template <typename T>
TreeNode<T>* AVLTree<T>::search(TreeNode<T> *node, T val) {
    if (!node){
        cout << "the value is not in the tree" << endl;
        return NULL;
    }
    if (node->value == val) {
        cout << "the value is in the tree" <<endl;
        return node;
    }
    if (val < node->value){
        return search(node->left, val);
    }
    else{
        return search(node->right, val);
    }
}
template <typename T>
TreeNode<T>* AVLTree<T>::search(T value) {
    return search(root, value);
}
template <typename T>
TreeNode<T>* AVLTree<T>::leftLeftRotation(TreeNode<T>* &node) {
    TreeNode<T>* leftNode = node->left;
    node->left = leftNode->right;
    leftNode->right = node;
    node->height = max(height(node->left), height(node->right)) + 1;
    leftNode->height = max(height(leftNode->left), node->height) + 1;
    return leftNode;
}
template <typename T>
TreeNode<T>* AVLTree<T>::rightRightRotation(TreeNode<T>* &node) {
    TreeNode<T>* rightNode = node->right;
    node->right = rightNode->left;
    rightNode->left = node;
    node->height = max(height(node->left), height(node->right)) + 1;
    rightNode->height = max(node->height, height(rightNode->right)) + 1;
    return rightNode;
}
template <typename T>
TreeNode<T>* AVLTree<T>::leftRightRotation(TreeNode<T>* &node) {
    node->left = rightRightRotation(node->left);
    return leftLeftRotation(node);
}
template <typename T>
TreeNode<T>* AVLTree<T>::rightLeftRotation(TreeNode<T>* &node) {
    node->right = leftLeftRotation(node->right);
    return rightRightRotation(node);
}

发表于 | 分类于

全排列专题

题目描述：

全排列是面试中经常出现的题目，所以这边有需要做一下关于这一类的专题。首先我们从最简单的题目开始。给定一个数组，根据全排列的规律，找到当前排列的下一个全排列。

我们已知对于1，2，3排列而言，它的全排列依次如下：
1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1

例子：

以数组[1,3,8,7,6,5,4,2]为例子，我们首先找到第一次出现降序的位置3；再找到第一次比3大的位置4；交换二者的数据得到[1,4,8,7,6,5,3,2]；再将4后面的数组逆序即可得到[1,4,2,3,5,6,7,8]

解题思路：

初看例子我们还无法看出前后排列之间的关系。通过网上资料查询我们可以知道，从当前排列得到下一个排列的算法：

  • 首先我们从数组的末端开始遍历数组，直到第一次遇到num[i] < num[i + 1]的地方
  • 然后我们从数组末尾开始找到第一次出现比num[i]大的数的位置num[j]
  • 交换num[i]和num[j]
  • 将i后面的数组逆序后即可以得到当前排列的下一个排列

代码如下：

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = -1;
        for (int i = nums.size() - 2; i >= 0; i--){
            if (nums[i] < nums[i + 1]){
                k = i;
                break;
            }
        }
        //先找到第一次降序的位置k，如果k是-1说明整个数组降序即为最后一个全排列，直接逆序全数组得到第一个全排列
        if (k == - 1){
            reverse(nums.begin(), nums.end());
            return;
        }
        int l = -1;
        for (int i = nums.size() - 1; i >= 0; i--){
            if (nums[i] > nums[k]){
                l = i;
                break;
            }
        }
        //从数组末尾开始找到第一次大于待交换数字的位置
        swap(nums[l], nums[k]);
        //交换二者的数据
        reverse(nums.begin() + k + 1, nums.end());
        //逆序从降序位置后开始到数组末尾的数字
        
        
    }
};

题目描述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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());//先进行排序
        vector<vector<int>> res;//用于保存结果
        res.push_back(nums);//先将当前结果保存
        
        while(1){
            int k = -1;
            for (int i = nums.size() - 2; i >= 0; i--){
                if (nums[i] < nums[i + 1]){
                    k = i;
                    break;
                }
            }//找到降序
            if (k == -1)break;
            int l = -1;
            for (int j = nums.size() - 1; j > k; j--){
                if (nums[j] > nums[k]){
                    l = j;
                    break;
                }
            }//找到小于待交换的位置
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
            res.push_back(nums);
        }
        return res;
    }
};

题目描述3：

在以上的解题过程中用的都是非递归的方法实现，现在要求使用递归的方式实现找到某个数组的全排列。主要的思路是用begin来标记当前要确定的排列位置，然后在从begin到数组末尾的各个数和begin进行交换得到不同的可能排列，而后进行下一个位置的寻找。遍历的停止条件是当前遍历位置大于数组长度的时候。需要注意的是，我们在遍历后需要进行一步回溯。比如在找到[1,3,2]后我们需要交换3和2变回[1,2,3]，便于下一步进行得到[2,1,3]结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permutation(nums, 0, ans);
        return ans;
    }
    void permutation(vector<int>&nums, int begin, vector<vector<int>>& ans){
        if (begin >= nums.size()){
            ans.push_back(nums);
            return;
        }
        //如果当前遍历的位置到达数组的末尾，将数组保存即可
        for (int i = begin; i < nums.size(); i++){
            swap(nums[i], nums[begin]);
            //与当前遍历位置的各个数进行交换，然后进入下一层递归
            permutation(nums, begin+1, ans);
            swap(nums[i], nums[begin]);
            //需要回溯一步
        }
    }
};

题目描述4

在使用递归方法中，上述的方法无法解决出现重复数字的情况。比如[1,1,2]。因为在begin=0的情况中，i=0,1,2；而对于i=0得到[1,1,2]和i=1得到[1,1,2]得到的情况相同，后序的全排列重复。所以我们需要其他的方法来解决这个问题。其中之一就是哈希表。主要的思路是:我们用哈希表来记录数组中出现数字的次数，用vec来保存当前得到的全排列；每次从哈希表中找到一个数将其push到vec中，而哈希表中对应的出现个数减1；然后进入下一层递归即可。需要注意的是：我们每次push完一个数递归结束后，需要将这个数pop进行回溯；另外需要对哈希表中数字出现的个数进行增加和减少操作。

代码如下：

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;//保存结果
        map<int, int> hash;//记录个数
        vector<int>vec;//保存当前排列
        for (int i = 0; i < nums.size(); i++){
            hash[nums[i]]++;
        }//生成哈希表
        permutation(ans, vec, hash, nums.size());
        //递归找到全排列
        return ans;
        
    }
    void permutation(vector<vector<int>>& ans, vector<int>& vec, map<int,int>& hash, int end){
        if (end <= 0){
            ans.push_back(vec);
            return;
            //如果已经得到符合条件的全排列
        }
        for (auto &it: hash){
            if (it.second <= 0) continue;
            //如果当前元素已被使用完，查找下一个元素
            vec.push_back(it.first);
            //将当前元素导入保存
            it.second--;//对应元素个数减少
            permutation(ans, vec, hash, end - 1);
            //进行下一轮递归调用
            it.second++;
            //调用完记得恢复哈希表
            vec.pop_back();
            //恢复记录的排列
        }
    }
};

发表于 | 分类于

Game Life(生存游戏)

题目描述：

给定一个矩阵，矩阵中只包含着0，1数字。有如下游戏规则：

  • 如果矩阵中的一个点当前值为1，且其周围为1的个数大于3或者小于2的时候，下一轮这个点为0；
  • 如果矩阵中的一个点当前值为0，当且仅当周围为1的个数为3的时候，这个点下一轮为1；

要求在O(1)的空间下找到下一轮的每个点的生存情况。

例子：

详细说明见leetcode

解题思路：

本题主要是在于空间上我们不能利用保存一个和当前矩阵相同的矩阵用来判断下一轮的节点情况；所以这边主要利用的是哈希表，我们建立一个哈希表；分别表示由1变1，由0变0，由1变0，由0变1的4种情况。在遍历矩阵的过程中，找到周围的8个点，从哈希表中找到对应的上一轮的节点情况用来判断当前节点的下一轮的情况。

代码如下：

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        map<int, int> hash = {{-1, 0}, {-2, 1}, {1, 1}, {0, 0}};
        //表示4种变化情况
        int count = 0;
        int row = board.size();
        int col = board[0].size();
        //找到行和列
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                count = 0;
                count += (i - 1 >= 0 && j - 1 >= 0) ? hash[board[i - 1][j - 1]] : 0;
                count += (i - 1 >= 0) ? hash[board[i - 1][j]] : 0;
                count += (i - 1 >= 0 && j + 1 < col) ? hash[board[i - 1][j + 1]] : 0;
                count += (j - 1 >= 0) ? hash[board[i][j - 1]] : 0;
                count += (j + 1 < col) ? hash[board[i][j + 1]] : 0;
                count += (i + 1 < row && j - 1 >= 0) ? hash[board[i + 1][j - 1]] : 0;
                count += (i + 1 < row) ? hash[board[i + 1][j]] : 0;
                count += (i + 1 < row && j + 1 < col) ? hash[board[i + 1][j + 1]]: 0; 
                //计算周围8个节点的情况
                if (board[i][j] == 1 && (count > 3 || count < 2))
                    board[i][j] = -2;
                    //针对两种情况进行变化
                else if (board[i][j] == 0 && count == 3)
                    board[i][j] = -1;
            }
        }
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (board[i][j] == -1)
                    board[i][j] = 1;
                if (board[i][j] == -2)
                    board[i][j] = 0;
                    //根据哈希表重建当前表
            }
        }
    }
};

发表于 | 分类于

Valid Parentheses(括号构成的字符串有效)

题目描述：

给定一个字符串由括号构成；判断其是否有效。

例子：

具体描述见LeetCode20

解题思路：

对于这种题目；主要利用栈的数据结构来判断。我们可以将碰到左括号的字符全部入栈；然后一旦碰到右括号；就从栈顶弹出字符，并且判断这两个字符是否能够构成合法的字符串直到栈为空。需要注意的是，假设字符前部的字符都有效，但是末尾是一个左括号，这样需要在函数末尾判断当前栈是否为空，不为空的情况也是不合法的字符串。

代码如下：

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
class Solution {
public:
    bool isValid(string s) {
        if (s.size() <= 1) return false;
        stack<char> stk;//定义栈用于保存数据
        stk.push(s[0]);//先将首字符入栈
        int cur = 1; //记录当前遍历字符的位置
        while(cur < s.size()){
            if (s[cur] == '(' || s[cur] == '{' || s[cur] == '['){
                stk.push(s[cur]);
                cur++;
                //左括号入栈
            }else{
                if (stk.empty()||(s[cur] == ')' && stk.top() != '(') || (s[cur] == ']' && stk.top() != '[') || (s[cur] == '}' && stk.top() != '{'))//右括号判断三种不同的情况和空栈的情况
                    return false;
                else{
                    cur++;
                    stk.pop();
                }
            }
        }
        if (stk.empty()) return true;
        //需要在最后判断是否是空栈的情况
        else return false;
        
    }
};

发表于 | 分类于

Greater Tree

题目描述：

给定一颗二叉搜索树的头结点，将树中的每个节点变大；变大的规则在于：对于某个节点而言，找到树中大于该节点值的所有节点值的和，并将其加到该节点上。

例子：

这是leetcode上的题目

解题思路：

初看题目可能觉得比较麻烦，因为要找到所有的大于某个节点的和。但是注意题目中给定的：这棵树是二叉搜索树。我们可以利用右侧节点大于根节点；左侧节点小于根节点这个特性来解题。我们从最右侧节点开始，对于最右侧节点而言，其为最大，所以不需要改变；对于这个节点的父母节点我们需要将其右侧的节点的和加上即可；所以在遍历的过程中不断的将遍历的过程节点累加即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    int cur_sum = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        greater(root);
        return root;
        
    }
    void greater(TreeNode* &head){
        if (!head) return;
        if (head->right) greater(head->right);
        cur_sum += head->val;//计算累加和
        head->val = cur_sum;//将右侧的和加上到当前节点
        if (head->left) greater(head->left);
    }
};

发表于 | 分类于

Binary Search Tree

题目描述：

用C++语言构造搜索二叉树。包括基本的功能；先序遍历，中序遍历，后序遍历，取最大值，取最小值，插入，删除，查找。

代码如下：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
using namespace std;
template <typename T>
class TreeNode{
public:
    TreeNode* left;
    TreeNode* right;
    T value;
    TreeNode(T key): value(key), left(NULL), right(NULL){};
    TreeNode(T key, TreeNode* l, TreeNode* r): value(key), left(l), right(r){};
};
//构造二叉树的节点类
template <typename T>
class BSTree{
public:
    BSTree() = default;
    BSTree(TreeNode<T>* node): root(node) {};
    ~BSTree(){};
    void preOrder();
    void inOrder();
    void postOrder();
    void insert(T value);
//    void insert(TreeNode* node);
    void search(T value);
//    void del(T value);
    bool empty();
    TreeNode<T>* getMin();
    TreeNode<T>* getMax();
private:
    TreeNode<T>* root;
    void preOrder(TreeNode<T>* const node) const;
    void inOrder(TreeNode<T>* const node) const;
    void postOrder(TreeNode<T>* const node) const;
    void search(TreeNode<T>* node, T key);
    TreeNode<T>* getMin(TreeNode<T>* const node);
    TreeNode<T>* getMax(TreeNode<T>* const node);
    bool empty(TreeNode<T>* node);
    void insert(TreeNode<T>* node, T value);
};
template <typename T>
void BSTree<T>::preOrder(TreeNode<T>* const node) const {
    if (node) {
        cout << node->value << endl;
        preOrder(node->left);
        preOrder(node->right);
    }else{
        return;
    }
}
template <typename T>
void BSTree<T>::preOrder() {
    preOrder(root);
}
template <typename T>
void BSTree<T>::inOrder(TreeNode<T>* const node) const {
    if (node){
        inOrder(node->left);
        cout << node->value << endl;
        inOrder(node->right);
    }else{
        return;
    }
}
template <typename T>
void BSTree<T>::inOrder() {
    inOrder(root);
}
template <typename T>
void BSTree<T>::postOrder(TreeNode<T>* const node) const {
    if (node){
        postOrder(node->left);
        postOrder(node->right);
        cout << node->value << endl;
    }else{
        return;
    }
}
template <typename T>
void BSTree<T>::postOrder() {
    postOrder(root);
}
template <typename T>
void BSTree<T>::search(TreeNode<T> * node, T value) {
    if (!node) {
        if (value == node->value) {
            cout << "the value is in this tree" << endl;
            return;
        }
        if (value > node->value)
            search(node->right, value);
        if (value < node->value)
            search(node->left, value);
    }
    return;
}
template <typename T>
void BSTree<T>::search(T value) {
    search(root, value);
}
template <typename T>
TreeNode<T>* BSTree<T>::getMin(TreeNode<T> *const node) {
    TreeNode<T>* tmp = node;
    while(tmp->left){
        tmp = tmp->left;
    }
    return tmp;
}
template <typename T>
TreeNode<T>* BSTree<T>::getMin() {
    getMin(root);
}
template <typename T>
TreeNode<T>* BSTree<T>::getMax(TreeNode<T> *const node) {
    TreeNode<T>* tmp = node;
    while(tmp->right){
        tmp = tmp->right;
    }
    return tmp;
}
template <typename T>
TreeNode<T>* BSTree<T>::getMax() {
    getMax(root);
}
template <typename T>
bool BSTree<T>::empty(TreeNode<T>* node){
    return node == NULL;
}
template <typename T>
bool BSTree<T>::empty(){
    return empty(root);
}
template <typename T>
void BSTree<T>::insert(TreeNode<T>* node, T value) {
    if (node == NULL){
        TreeNode<T>* tmp = new TreeNode<T>(value);
        node = tmp;
    }
    if (node->value > value){
        if (node->left == NULL){
            TreeNode<T>* tmp = new TreeNode<T>(value);
            node->left = tmp;
        }else{
            insert(node->left, value);
        }
    }else{
        if (node->right == NULL){
            TreeNode<T>* tmp = new TreeNode<T>(value);
            node->right = tmp;
        }else{
            insert(node->right, value);
        }
    }
}
template <typename T>
void BSTree<T>::insert(T value) {
    insert(root, value);
}