题目链接： https://www.acwing.com/blog/content/30368/
一. 二分查找次数
#include <bits/stdc++.h>
using namespace std;
/**
* Author ：Jaryn
* Time ：2023/3/19 4:34 下午
* Desc ：第一行输入一个整数N（N<=10000）。
第二行输入N个升序整数。
第三行输入一个待查找的整数（必定在第二行中出现过）。
输出二分查找该整数时，进行过多少次二分。
*/
const int N = 100010;
int a[N];
int main() {
int n, target, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cin >> target;
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
cnt++;
}
cout << cnt;
return 0;
}
二. 字符串距离编辑
https://www.acwing.com/problem/content/904/
三. 二叉树前中后序遍历
#include <bits/stdc++.h>
using namespace std;
/**
* Author ：Jaryn
* Time ：2023/3/19 4:34 下午
* Desc ：输入一棵二叉树，输出树的前、中、后序遍历结果。
输入一个整数N（N<= 10000)，表示树中有N个结点（编号0~N-1）。
接下来N行，依次为结点0~结点N-1的左右孩子情况。
每行3个整数，F,L,R。L,R为F的左右孩子。L,R如果为-1表示该位置上没有孩子。
分三行分别输出树的前中后序遍历。
同一行中的数字，用一个空格间隔。
*/
typedef struct TreeNode {
int val;
TreeNode *left = NULL, *right = NULL, *parent = NULL; // 父节点方便找到root
}TreeNode ;
const int N = 10010;
TreeNode* a[N];
void preOrder(TreeNode * p) {
if (p == NULL) return;
cout << p -> val << " ";
preOrder(p -> left);
preOrder(p -> right);
}
void inOrder(TreeNode * p) {
if (p == NULL) return;
inOrder(p -> left);
cout << p -> val << " ";
inOrder(p -> right);
}
void postOrder(TreeNode * p) {
if (p == NULL) return;
postOrder(p -> left);
postOrder(p -> right);
cout << p -> val << " ";
}
int main() {
int n; cin >> n;
// 先将树存在一个数组中，方便后续构造树
for (int i = 0; i < n; i++) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node -> val = i;
a[i] = node;
}
// 建树
for (int i = 0; i < n; i++) {
int parent, left, right;
cin >> parent >> left >> right;
TreeNode *p = a[parent];
if (left != -1) {
p -> left = a[left];
a[left] -> parent = p;
}
if (right != -1) {
p -> right = a[right];
a[right] -> parent = p;
}
}
TreeNode *root = a[0];
while (root -> parent) { // 0不一定是根，所以需要找到根节点
root = root -> parent;
}
preOrder(root); cout << endl;
inOrder(root); cout << endl;
postOrder(root);
return 0;
}
四.hanoi
#include <bits/stdc++.h>
using namespace std;
/**
* Author ：Jaryn
* Time ：2023/3/19 4:34 下午
* Desc ：Hanoi 塔问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，
* 第一根上面套着64 个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，
* 庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，
* 而且大的不能放在小的上面。
*
请编写程序，把A 柱上的n 个金片，搬动到C 柱（中间可以使用B 柱），使得搬动的次数最少。
输入金片的个数n（1<=n<=64），输出总搬动次数，以及最后100 次搬动。如果搬动次数小于等于100 则全部输出；
每个搬动占一行，加上是这第几次搬动的数字和”:”，格式见示例。
*/
int ans;
int f[70]; // f[i]表示有i个圆环时的搬动总次数
int nn;
void hanoi(int n, char a, char b, char c) { // 将a的通过b搬到c
if (n == 1) {
ans++;
if (f[nn] - ans <= 100)
cout << ans << ":" << a << "->" << c << endl;
return;
}
hanoi(n - 1, a, c, b); // 把a的前n-1个移到b先
hanoi(1, a, b, c); // 把a的最后一个移到c
hanoi(n - 1, b, a, c); // 把b的n-1个移到c
}
int main() {
cin >> nn;
// 计算f[i]
f[1] = 1;
for (int i = 2; i <= nn; i++) {
f[i] = f[i - 1] * 2 + 1; // 先把前i-1个搬到b，再把最大的搬到c，再把b的n-1个搬到c。所以是2* + 1
}
cout << f[nn] << endl;
hanoi(nn, 'A', 'B', 'C');
return 0;
}
