2014 年机考试题

1、二分查找

#include <iostream>
#include<vector>
using namespace std;

int main() {
    int n;
    scanf_s("%d", &n);
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        scanf_s("%d", &nums[i]);
    int target;
    scanf_s("%d", &target);
    int left = 0, right = n - 1;
    int cnt = 0;
    while (left < right) {
        int mid = (left + right) / 2;
        cnt++;
        if (nums[mid] == target) break;
        else if (nums[mid] > target)
            right = mid - 1;
        else left = mid + 1;
    }
    cout << cnt << endl;
    return 0;
}

2、编辑距离

dp[i][j] 表示将 s1 前 i 个字符转换为 s2 前 j 个字符所使用的最少操作数

• s1[i - 1] == s2[j - 1]，dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1))
• s1[i - 1] != s2[j - 1]，dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int dist = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = min(dp[i - 1][j - 1], dist);
            else dp[i][j] = min(dp[i - 1][j - 1] + 1, dist);
        }
    }
    return dp[m][n];
}

int main() {
    string word1, word2;
    cin >> word1 >> word2;
    cout << minDistance(word1, word2) << endl;
    return 0;
}

3、二叉树遍历

构建二叉树

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left, * right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};
// 先序构建二叉树
int pos = 0;
TreeNode* createTree(string s) {
    char c = s[pos++];
    if (c == '#') return NULL;
    TreeNode* root = new TreeNode(c - '0');
    root->left = createTree(s);
    root->right = createTree(s);
    return root;
}
// 二叉排序树
TreeNode* insert(TreeNode* root, int num) {
    if (root == NULL) return new TreeNode(num);
    if (root->val > num)
        root->left = insert(root->left, num);
    else root->right = insert(root->right, num);
    return root;
}
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}
int main() {
    string s;
    cin >> s;
    //TreeNode* root = createTree(s);
    int num;
    cin >> num;
    TreeNode* root = new TreeNode(num);
    for (int i = 0; i < 4; i++) {
        cin >> num;
        root = insert(root, num);
    }
    preOrder(root);
    return 0;
}

4、Hanoi 塔

move(n, A, C) 相当于 move(n - 1, A, B) => move(1, A, C) => move(n - 1, B, C)

总次数 nums[n] = 2*nums[n - 1] + 1 = 2^n - 1

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int cnt = 0;
void move(int n, int total, char a, char b, char c) {
    if (n == 1) {
        cnt++;
        if(total - cnt < 100)
            printf("%d:%c->%c\n", 100 - total + cnt, a, c);
    }
    else {
        move(n - 1, total, a, c, b);
        move(1, total, a, b, c);
        move(n - 1, total, b, a, c);
    }
}
int main() {
    int n;
    cin >> n;
    int total = pow(2, n) - 1;
    printf("%d\n", total);
    move(n, total, 'A', 'B', 'C');
    return 0;
}