题目链接： 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;
}