算法题汇总：其三

Z字形扫描

源码与注释

初始化一维数组和二维数组的指针，使用全局变量的指针，就懒得传参了

int *twoDimensionArray = NULL;
int *oneDimensionArray = NULL;

确认已经遍历过的数据

int add(int n)
{
    int result = 0;
    for (int i = 1; i <= n; i++)
        result += i;
    return result;
}

进行扫描的具体过程

void zigzagScan(int n)
{
    int temp = 0;
    /*
    * 坐标和从0扫到n - 1
    */
    for (int i = 0; i < n; i++)
    {
        //从i = 0开始扫描，附初值
        if (!i)
            *oneDimensionArray = *twoDimensionArray;
        //若坐标和为奇数
        else if (i % 2)
        {
            temp = add(i);
            for (int j = 0; j <= i; j++)
                *(oneDimensionArray + temp + j) = *(twoDimensionArray + j * n + (i - j));
        }
        //若坐标和为偶数
        else
        {
            temp = add(i);
            for (int j = 0; j <= i; j++)
                *(oneDimensionArray + temp + j) = *(twoDimensionArray + (i - j) * n + j);
        }
    }
    /*
    * 从n扫到最后
    */
    for (int i = n; i <= (n - 1) * 2; i++)
    {
        //若是最后一个
        if (i == (n - 1) * 2)
        {
            temp = add(n) + add(n - 1) - 1;
            *(oneDimensionArray + temp) = *(twoDimensionArray + (n - 1) * n + n - 1);
        }
        //若坐标和为偶数
        else if (!(i % 2))
        {
            temp = add(n) + add(n - 1) - add(2 * n - i - 1);
            for (int j = 0; j <= 2 * n - i - 2; j++)
                *(oneDimensionArray + temp + j) = *(twoDimensionArray + (n - 1 - j) * n + (i - (n - 1 - j)));
        }
        //若坐标和为奇数
        else
        {
            temp = add(n) + add(n - 1) - add(2 * n - i - 1);
            for (int j = 0; j <= 2 * n - i - 2; j++)
                *(oneDimensionArray + temp + j) = *(twoDimensionArray + (i - (n - 1 - j)) * n + (n - 1 - j));
        }
    }
}

main函数

int main()
{
    int n = 0;
    scanf("%d", &n);

    /*
    * 分配好需要的内存。如果不用(int *)的话编译器认，oj不认
    */
    oneDimensionArray = (int *)malloc(n * n * sizeof(int));
    twoDimensionArray = (int *)malloc(n * n * sizeof(int));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", twoDimensionArray + i * n + j);

    zigzagScan(n);

    for (int i = 0; i < n * n; i++)
        printf("%d ", *(oneDimensionArray + i));

    free(oneDimensionArray);
    free(twoDimensionArray);
    return 0;
}

迷宫问题

输入样例

8 8
1 1
8 8
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0

输出样例

(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),(4,1,2),(5,1,1),(5,2,1),(5,3,2),(6,3,1),(6,4,1),(6,5,2),(7,5,2),(8,5,1),(8,6,1),(8,7,1),(8,8,1)

个人写法

设置方向与地图状况常量

enum direction
{
    failed,
    right,
    down,
    left,
    up
};
enum surroundings
{
    uncover,
    blocked,
    covered
};
surroundings map[105][105] = {uncover};// 地图初始化
int m, n;                               // 地图大小

小人的初始化和方向判断

typedef struct Axis
{
    int x;
    int y;
    surroundings is_right;
    surroundings is_left;
    surroundings is_up;
    surroundings is_down;
    direction dir;
} axis;

主函数的输入

axis begin, end, temp;
int num;
std::stack<axis> track; // 足迹用栈保存

std::cin >> m >> n >> begin.x >> begin.y >> end.x >> end.y;
begin.x--, begin.y--, end.x--, end.y--;

for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
    {
        std::cin >> num;
        switch (num)
        {
        case 0:
            map[i][j] = uncover;
            break;
        case 1:
            map[i][j] = blocked;
        }
    }
temp = begin;

进行操作的具体流程

while (true)
{
    temp.dir = right;
    if (temp.x == end.x && temp.y == end.y) // 如果到达了终点则直接结束，防止弹出栈或跑了
    {
        track.push(temp);
        break;
    }
    temp = judge(temp);                     // 判断小人周遭的情况
    temp = direction_confirmed(temp, true); // 判断小人接下来要走的方向
    if (temp.dir)   // 反向不是failed，说明可以走，则向指定方向走一步
    {
        track.push(temp);
        temp = step_forwards(temp);
    }
    else    // 方向是failed，寻路失败
    {
        if (temp.x == begin.x && temp.y == begin.y) // 回到了起点，说明无路可走
            break;
        else                                        // 原路返回
        {
            map[temp.x][temp.y] = blocked;          // 将死路堵上
            temp = track.top();
            temp = direction_confirmed(temp, false);
            track.pop();
        }
    }
}

由于足迹中的栈弹出来是倒序的，因此需要再来一个栈把它弹成正常顺序

if (!track.empty() && track.top().x == end.x && track.top().y == end.y)
{
    std::stack<axis> temp;
    std::string s;
    while (!track.empty())
    {
        temp.push(track.top());
        track.pop();
    }
    while (!temp.empty())
    {
        s.append("(").append(std::to_string(temp.top().x + 1)).append(",").append(std::to_string(temp.top().y + 1)).append(",").append(std::to_string(temp.top().dir)).append("),");
        temp.pop();
    }
    s.pop_back();
    std::cout << s << std::endl;
}
else
    std::cout << "no" << std::endl;

judge函数，用于判断小人周遭情况

axis judge(axis target)
{

    if (target.y == n - 1)
        target.is_right = blocked;
    else
        target.is_right = map[target.x][target.y + 1];

    if (!target.y)
        target.is_left = blocked;
    else
        target.is_left = map[target.x][target.y - 1];

    if (!target.x)
        target.is_up = blocked;
    else
        target.is_up = map[target.x - 1][target.y];

    if (target.x == m - 1)
        target.is_down = blocked;
    else
        target.is_down = map[target.x + 1][target.y];

    return target;
}

direction_confirm函数，用于判断方向，分向前和回溯两种功能

axis direction_confirmed(axis target, bool is_forward)
{
    surroundings status;
    if (is_forward)
        status = uncover;
    else
        status = covered;

    if (target.is_right == status)
        target.dir = right;
    else if (target.is_down == status)
        target.dir = down;
    else if (target.is_left == status)
        target.dir = left;
    else if (target.is_up == status)
        target.dir = up;
    else
        target.dir = failed;
    return target;
}

step_forwards函数，用于向前迈出一步

axis step_forwards(axis target)
{
    if (target.dir == right)
    {
        map[target.x][target.y] = covered;
        target.y++;
    }
    else if (target.dir == down)
    {
        map[target.x][target.y] = covered;
        target.x++;
    }
    else if (target.dir == left)
    {
        map[target.x][target.y] = covered;
        target.y--;
    }
    else if (target.dir == up)
    {
        map[target.x][target.y] = covered;
        target.x--;
    }
    return target;
}

二叉树的遍历

样例输入

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

样例输出

4 1 6 3 5 7 2

个人写法

以样例为例，解释如何由两种遍历得到唯一指定的树

1. 后序遍历的最后一位是根节点为4。
2. 在中序遍历中找到4，其左侧是左子树，右侧是右子树。
3. 在左子树中，其后序遍历是[2,3,1]，中序遍历为[1,2,3]。循环以上操作继续。

但该思路中节省了不少细节，比如如何匹配到对应的字串，如何在子树为空是跳过，等等

首先定义树的节点

typedef struct TREE
{
    int value;
    struct TREE *left;
    struct TREE *right;
} node, *tree;

进行模糊匹配，只要两个vector数字相同即可匹配成功，为中序遍历的子树遍历寻找合适的后序遍历。但该匹配方法应该不是最优的。

bool unclear_match(vector<int> v1, vector<int> v2)
{

    for(auto it = v1.begin(); it != v1.end(); ++it)
        if(find(v2.begin(), v2.end(), *it) == v2.end())
            return false;
    if(v1.size() != v2.size())
        return false;
    return true;
}

生成树的主体函数。

tree make_tree(vector<int> after, vector<int> middle)
{
    int root_node = after.back(); // 后序遍历的最后一个是根节点
    after.pop_back();
    auto index_root_node = find(middle.begin(), middle.end(), root_node); // 找到根节点在中序遍历中的位置，返回其迭代器
    vector<int> left_middle, right_middle, left_after, right_after; // 左子树、右子树的后序、中序遍历

    left_middle.assign(middle.begin(), index_root_node); // 将中序遍历分开为左子树遍历和右子树遍历
    right_middle.assign(index_root_node + 1, middle.end());

    auto index_after_node = after.begin(); // 以下均为为子树的中序遍历寻找合适的后序遍历
    for(int i = 0; i != left_middle.size() && index_after_node != after.end(); ++index_after_node, ++i);
    left_after.assign(after.begin(), index_after_node);
    if(unclear_match(left_middle, left_after))
        right_after.assign(index_after_node, after.end());
    else
    {   index_after_node = after.begin();
        for(int i = 0; i != right_middle.size() && index_after_node != after.end(); ++index_after_node, ++i);
        left_after.assign(after.begin(), index_after_node);
        right_after.assign(index_after_node + 1, after.end());
    }

    tree new_node = (tree)malloc(sizeof(node)); // 生成新的子树节点
    new_node->value = root_node;

    if(!left_middle.empty() && !left_after.empty()) // 递归生成子树
        new_node->left = make_tree(left_after, left_middle);
    else
        new_node->left = nullptr;

    if(!right_middle.empty() && !right_after.empty())
        new_node->right = make_tree(right_after, right_middle);
    else
        new_node->right = nullptr;
    
    return new_node;
}

进行层序遍历。步骤如下

1. 指定队列q，开始时先往里面弹入根节点。
2. 若节点中有子树，则弹入。
3. 每次固定弹出一位，直到队列为空为止。

vector<int> print_queue(tree certain_tree)
{
    queue<tree> q;
    vector<int> v;
    if(certain_tree)
        q.push(certain_tree);
    while(!q.empty())
    {
        tree temp = q.front();
        v.push_back(temp->value);
        if(temp->left)
            q.push(temp->left);
        if(temp->right)
            q.push(temp->right);
        q.pop();
    }
    return v;
}

main函数

int main()
{
    vector<int> after, middle, result;
    int quantity, temp;
    cin >> quantity;
    for(int i = 0; i < quantity; i++)
    {
        cin >> temp;
        after.push_back(temp);
    }
    for(int i = 0; i < quantity; i++)
    {
        cin >> temp;
        middle.push_back(temp);
    }
    tree certain_tree = make_tree(after, middle);
    result = print_queue(certain_tree);
    for(auto it = result.begin(); it != result.end(); ++it)
        cout << *it << " ";
    return 0;
}