N皇后问题——记录下那些老死不相往来的N个女人的位置吧

于是在N个女人的老死不相往来-n皇后问题代码的基础上,增加了输出那N个老死不相往来的女人的位置的代码~

简单来说就是在每次尝试第 i 行新的摆法、并且递归的 trying 了它的下一行之后,需要还原第 i 行的状态。输出棋盘则可以直接在每次判断是可行解之后w

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

// total:记录解;finishline:确认的行
int total = 0, finishline = 1;

// row:竖直攻击; ls:斜杠攻击; rs:反斜杠攻击
void trying(long row, long ls, long rs, int current_row, vector<vector<bool>> &board)
{
    if (row != finishline) // 开始新行
    {
        long position = finishline & ~(row | ls | rs);
        while(position) // 若行间无位可放...
        {
            long pointline = position & -position;
            position -= pointline;
            
            // 放上皇后
            board[current_row][(int)log2(pointline)] = 1;
            trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1, current_row + 1, board);
            // 不论上面的 trying 是否成功
            // 我们都需要把这一行还原到之前的状态
            board[current_row][(int)log2(pointline)] = 0;
        }
    }
    else
    {
        total++;
        // 输出棋盘
        for (auto &row : board)
        {
            for (auto col : row)
            {
                cout << col;
            }
            cout << '\n';
        }
        cout << '\n';
    }
}

int main(int argc, char *argv[]) {
    int grid = 8; // 修改grid的话,1~31皇后都能解w
    finishline = (finishline << grid) - 1;
    
    // 初始化棋盘 调整好棋盘的大小
    vector<vector<bool>> board;
    board.resize(grid);
    for_each(board.begin(), board.end(), [grid](vector<bool> &row) {
        row.resize(grid);
    });
    
    trying(0, 0, 0, 0, board);
    cout << total << endl;
}

由前序遍历和中序遍历重构二叉树w

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode * rebin(vector<int> pre, vector<int> in) {
    // 首先看看有米有东西吧
    // 一个元素都没有的话
    // 这个二叉树就只有一个NULL节点
    // 直接返回即可w
    if (pre.size() == 0) return nullptr;
    
    // 根据前序遍历的定义 根节点一定在前序遍历结果的第一个位置上
    // 而中序遍历的话 根结点必然需要等到它的左子树都输出完才会出现
    // 利用这一点我们分开左右子树
    int root_value = pre[0];
    TreeNode * root = new TreeNode(root_value);
    // 找到根节点在中序遍历里的下标
    // 以此分开左右子树
    int root_index_of_in = 0;
    for (int i = 0; i < in.size(); i++) {
        if (in[i] == root_value) {
            root_index_of_in = i;
            break;
        }
    }
    // 分开左右子树
    // 按原始的顺序分别保存左右子树的前序遍历和中序遍历
    vector<int> left_pre, left_in, right_pre, right_in;
    // 先是左子树
    for (int i = 0; i < root_index_of_in; i++) {
        // 这里需要+1
        // 因为前序遍历的话 第一个元素是根节点
        // 所以需要跳过当前(下标为0)的这个元素
        left_pre.emplace_back(pre[i+1]);
        left_in.emplace_back(in[i]);
    }
    // 然后是右子树
    for (int i = root_index_of_in + 1; i < in.size(); i++) {
        right_pre.emplace_back(pre[i]);
        right_in.emplace_back(in[i]);
    }
    // 既然左右子树的前序遍历和中序遍历都有了
    // 和我们一开始拿到的初始条件很相似吧~
    // 那么递归吧w
    root->left = rebin(left_pre, left_in);
    root->right = rebin(right_pre, right_in);
    return root;
}

// 三种遍历方式~/
typedef enum {
    PRE_ORDER,
    IN_ORDER,
    POST_ORDER,
} TreeTraversal;

void print_with_order(TreeNode * root, TreeTraversal order) {
    // 如果根节点是空的
    // 那啥都不用说直接返回吧
    if (root == nullptr) return;
    
    // 看看使用什么序来遍历
    // 本质上仅仅只是输出当前root节点的位置不一样
    if (order == PRE_ORDER) {
        cout << root->val << ' ';
        print_with_order(root->left, order);
        print_with_order(root->right, order);
    } else if (order == IN_ORDER) {
        print_with_order(root->left, order);
        cout << root->val << ' ';
        print_with_order(root->right, order);
    } else {
        print_with_order(root->left, order);
        print_with_order(root->right, order);
        cout << root->val << ' ';
    }
}

int main(int argc, const char * argv[]) {
    vector<int> pre = {1,2,4,7,3,5,6,8};
    vector<int> in  = {4,7,2,1,5,3,8,6};
    TreeNode * head = rebin(pre, in);
    
    // 用构建好的树输出前序和中序遍历来验证~
    cout << "pre: ";
    print_with_order(head, PRE_ORDER);
    cout << endl;
    
    cout << "in:  ";
    print_with_order(head, IN_ORDER);
    cout << endl;
}