编程之美中有趣的问题

motivation

准备下个月投微软, 先学一下编程之美. 这本书和其他的算法题书有很大不同, 很多问题很有意思, 记录一下.

中国象棋将帅问题

问题描述: 将 和 帅 只能在象棋棋盘上3 x 3区域内活动, 并且将 和 帅 不能照面, 问所有将和帅可能出现的位置, 限制: 代码中只能使用一个字节存储变量

分析:

• 可以将3 x 3 区域进行编码1 ~ 9, 将 和 帅 都在同一个3 x 3区域内考虑
• 不能打照面, 即 列 不能相同, 亦即 mod 3 的 结果不能相同
• 只能一个字节存储变量, 需要用到高级技巧位域

代码:

#include <iostream>

using namespace std;
void jiangShuai() {
    struct {
        unsigned char a : 4;  // 因为只有9个位置, 所以4个bit编码够用
        unsigned char b : 4;  // 两个4 bits 合起来刚好1B
    } i;
    for (i.a = 1; i.a <= 9; ++i.a) {
        for (i.b = 1; i.b <= 9; ++i.b) {
            if (i.a % 3 != i.b % 3) {
                cout << "A = " << (int)i.a << ", B = " << (int)i.b << endl;
            }
        }
    }
}

扩展: 字节跳动面试题: 如何定义一个bit?

使用位域:

struct {
  unsigned char a : 1;
} i;  // 一定要使用struct, 直接写unsigned char a :1; 会报错
i.a = 1; // 一个bit表示范围是0 和 1, 如果设置i.a = 2; 会隐式转换为0;
cout << (int) i.a << endl;  // 需要转成int 不然cout乱码

一摞烙饼的排序

• 问题描述: 一只手端着一叠未排序(大小)的烙饼, 另一只手可以一次性翻转上面的n个烙饼, 问最少多少次翻转能够将烙饼排序;
• 分析:
  • 太难了! 暴力都不太会写…
  • 实际思想是前缀翻转排序, 如果最大的烙饼在第i块(i != n - 1即最大烙饼不在最底下), 那么我们可以通过两次翻转来将这块烙饼放到最底下:
    • 1 翻转第 0 ~ i块烙饼, 这个过程完成后最大的烙饼在最上面(第0块)
    • 2 翻转所有烙饼(0 ~ n - 1), 这个过程完成后最大的烙饼在最下面(第n - 1块)
  • 由此递归即可解决, 最多翻转2 x (n - 1)次
  • 其实同徐云老师第一节算法课讲的前缀反转排序, 从右向左有序化

赏

谢谢你请我吃糖果