题目链接: https://www.acwing.com/blog/content/32376/
一. 1000名求前30
快排,其实应该用堆排的
#include <bits/stdc++.h>
using namespace std;
/**
* Author :Jaryn
* Time :2023/3/17 3:34 下午
* Desc :输入10个,按顺序打印3个
10
1 2 0 3 4 9 8 7 5 6
*/
int a[1000];
void quickSort (int a[], int l, int r) {
if (l >= r) return;
int mid = a[(l + r) >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++; while(a[i] < mid);
do j--; while(a[j] > mid);
if (i < j) swap(a[i], a[j]);
}
quickSort(a, l, j);
quickSort(a, j + 1, r);
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
quickSort(a, 0, n - 1);
for (int i = 0; i < n / 3; i++) {
cout << a[i] << " ";
}
return 0;
}
二. 二叉树最大叶子间距
先层序建树,再递归求直径
#include <bits/stdc++.h>
using namespace std;
/**
* Author :Jaryn
* Time :2023/3/17 3:34 下午
* Desc :最大叶子间距,就是求树的直径
* 思路:先建树,再递归求直径
*/
typedef struct TreeNode {
int val;
TreeNode *left = NULL, *right = NULL;
} TreeNode;
int diameter = 0;
// 求直径
int postOrder(TreeNode* p) {
if (p == NULL) return 0;
int lHigh = postOrder(p -> left);
int rHigh = postOrder(p -> right);
diameter = max(diameter, lHigh + rHigh + 1);
return max(lHigh, rHigh) + 1;
}
int main() {
int val;
cin >> val;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root -> val = val;
queue<TreeNode*> q;
q.push(root);
int preLeftVal, preRightVal;
// 建树
while (q.size()) {
int leftVal, rightVal;
cin >> leftVal >> rightVal;
// 出现两次-1 -1就结束
if (leftVal == -1 && rightVal == -1 && preLeftVal == -1 && preRightVal == -1) break;
// 当前结点
TreeNode *c = q.front();
q.pop();
if (leftVal != -1) {
TreeNode *node = new TreeNode();
node -> val = leftVal;
c -> left = node;
q.push(node);
} else c -> left = NULL;
if (rightVal != -1) {
TreeNode *node = new TreeNode();
node -> val = rightVal;
c -> right = node;
q.push(node);
} else c -> right = NULL;
preLeftVal = leftVal;
preRightVal = rightVal;
}
// 求直径
postOrder(root);
cout << diameter - 1; // -1是因为diameter求的结点数量,-1就是路径长度
return 0;
}
三. 字符串的重复输出
#include <bits/stdc++.h>
using namespace std;
/**
* Author :Jaryn
* Time :2023/3/17 3:34 下午
* Desc :给一个字符串比如ABC 再给一个整数比如3输出AAABBBCCC就行了。
*/
int main() {
string res = "";
string s;
cin >> s;
int x;
cin >> x;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < x; j++) res += s[i];
}
cout << res;
return 0;
}