1
1 | 输入一个链表,输出该链表中倒数第k个结点。 |
1 | ListNode* findkth(ListNode* head, int k) { |
2
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
void oddBeforeEven(vector<int>& v) {
int odd = 0, even = 0;
while (odd < v.size() && v[odd]%2 == 1) {
odd++;
}
for (int i = odd; i < v.size(); i++) {
if (v[i]%2 == 1) {
swap(v[odd], v[i]);
odd++;
}
}
}
void oddBeforeEven(vector<int> &v) {
vector<pair<int,int>> arr;
for (int i = 0; i < v.size(); i++) {
arr.emplace_back(v[i], i);
}
sort(arr.begin(), arr.end(), cmp);//或者用stable_sort
for (int i = 0; i < arr.size(); i++) {
v[i] = arr[i].first;
}
}
bool cmp(const pair<int,int> &l, const pair<int,int> &r) {
if (l.first%2 == 1 && r.first%2==0) {
return true;
}
return l.second < r.second;
}
3
1 | 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)。 |
递归写法1
2
3
4
5
6
7
8
9
10bool subStruture(TreeNode* A, TreeNode* B) {
if (!A || !B) return false;
return isSame(A, B) || subStruture(A->left, B) || subStruture(A->right, B);
}
bool isSame(TreeNode* A, TreeNode* B) {
if (!B) return true;
if (!A && B)return false;
return A->val == B->val && isSame(A->left, B->left) && isSame(A->right, B->right);
}
4
1 | 操作给定的二叉树,将其变换为源二叉树的镜像。 |
1 | void Mirror(TreeNode *pRoot) { |
5
1 | 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 |
1 | TreeNode *convert(TreeNode* root, TreeNode*& pre) { |
非递归写法,其实类似非递归中序遍历,记录好上一个输出的节点即可
1 | TreeNode* convert(TreeNode* root) { |
6
1 | 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 |
使用next_permutation1
2
3
4
5
6
7
8
9
10
11
12
13vector<string> permu(string str) {
vector<string> res;
if (str.size() == 0) {
return {};
}
set<string> se;
sort(str.begin(), str.end());
do {
se.insert(str);
} while (next_permutation(str.begin(), str.end()));
for (auto it = se.begin(); it != se.end(); res.push_back(*it++));
return res;
}
使用递归解法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
39struct Sol {
int MapToIndex(char c) {
return c-'a';
}
void dfs(vector<int> &cnt, vector<string> &ret, string str, int n) {
if (str.size() == n) {
ret.push_back(str);
return;
}
for (int i = 0; i < cnt.size(); i++) {
if (cnt[i]) {
cnt[i]--;
dfs(cnt, ret, str+string(1, i+'a'), n);
cnt[i]++;
}
}
}
vector<string> Permutation(string str) {
vector<string> ret;
if (str.size() == 0)
return {};
vector<int> cnt(26, 0);
for (auto k : str) {
cnt[k-'a']++;
}
dfs(cnt, ret, "", str.size());
return ret;
}
};
void printV(vector<string> v) {
for (auto k : v) {
cout << k << endl;
}
}
求子集1
2
3
4
5
6
7
8
9
10
11void subset(vector<int> v, vector<vector<int>> &ret) {
for (int i = 0; i < (1<<v.size()); i++) {
vector<int> tmp;
for (int j = 0; j < v.size(); j++) {
if (i & (1 << j)) {
tmp.push_back(v[j]);
}
}
ret.push_back(tmp);
}
}