算法练习(13)-打印纸条对折的折痕类型（凹痕?凸痕？）
算法练习(13)-打印纸条对折的折痕类型（凹痕?凸痕？）
菩提树下的杨过
发布于 2021-11-02 16:43:14
发布于 2021-11-02 16:43:14
从左神视频上看到一个有趣的题目，据说是微软的算法面试题：一个长纸条，对折后再展开，中间会有一个凹痕，然后同样的方式，再继续对折， 又会多出2条折痕（不过新折痕会有凸有凹），如此反复对折，纸条上就会留下一系列的折痕，见下图：
要求：输入1个数字(n)，表示对折的次数， 从上而下， 打印每1条拆痕的类型（即：凹痕?凸痕？）
思路：咋一看， 好象无从下手， 但是参考上图中的标记，尝试几次后，把这些痕迹画成一颗二叉树，纸条从上到向的痕迹类型，正好是中序遍历！不得不感叹这题出得巧妙
找到规律后，就好办了，不过题目只要求打印节点值，并不需要根正建立一颗二叉树，而且观察上图， 可以发现每个节点的左子节点，全是“凹”，右子节点全是“凸”， 所以代码可以精减些:
/**
* 打印折痕
* @param level 当前层序号(根节点层序为1)
* @param maxLevel 总层数（即：对折次数）
* @param bulge 本层痕迹是否为“凸”痕
*/
static void printFolder(int level, int maxLevel, boolean bulge) {
if (level > maxLevel) {
return;
}
//分析发现，左侧全是凹痕
printFolder(level + 1, maxLevel, false);
//递归序第2次打印时机，正好对应中序遍历
System.out.printf(level + "" + (bulge ? "凸\t" : "凹\t"));
//分析发现，右侧全是凸痕
printFolder(level + 1, maxLevel, true);
}调用时（假设对折3次）：
printFolder(1, 3, false);输出：
3凹 2凹 3凸 1凹 3凹 2凸 3凸
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-10-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读