Hi，大家好，我是Gibbon，感谢同学们这么晚还坚持来看题解，对于同学们的求知精神，我仿佛又看到了当年自己求职的那一幕~欢迎大家选择并加入去哪儿！

在我的个人介绍中，HR姐姐给我扣上了全栈的帽子，感觉亚历山大，但本人还是更专注于后端开发的工作。所以，今天的题解我还是主要给大家进行后端开发的答疑，前端测试的编程题题解在下面的真题链接中有详细说明，同学们可以进行查看，请同学们理解~

废话不多说，进入正题，以下是编程题的真题链接：

按层打印二叉树：http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4172&konwledgeId=169 

单词变换：http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4378&konwledgeId=169 

进制转换：http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4377&konwledgeId=169 

酒店评分：http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4382&konwledgeId=169 

1. 按层打印二叉树

解题思路：根据输入的前序和中序遍历结果唯一重构一颗二叉树，然后借用队列实现按层打印。

示例代码：

package main

import (
"bufio"
"container/list"
"fmt"
"os"
"strconv"
"strings"
)

type Node struct {
left  *Node
right *Node
data  int
}

type Queue list.List

func NewQueue() *Queue {
q := list.New()
return (*Queue)(q)
}

func (q *Queue) Push(node *Node) {
(*list.List)(q).PushBack(node)
}

func (q *Queue) Pop() *Node {
e := (*list.List)(q).Front()
(*list.List)(q).Remove(e)
return e.Value.(*Node)
}

func (q *Queue) Len() int {
return (*list.List)(q).Len()
}

func NewNode(v int) *Node {
return &Node{data: v}
}

func createBTree(pOrder, mOrder []int) *Node {
if len(pOrder) == 0 || len(mOrder) == 0 {
return nil
}

v := pOrder[0]
root := NewNode(v)
i := 0
for ; i < len(mOrder); i++ {
if v == mOrder[i] {
break
}
}

root.left = createBTree(pOrder[1:i+1], mOrder[:i])
root.right = createBTree(pOrder[i+1:], mOrder[i+1:])

return root
}

func levelPrint(root *Node) {
if root == nil {
return
}

q := NewQueue()
q.Push(root)
nextCnt := 1

first := true
for q.Len() != 0 {
curCnt := nextCnt
nextCnt = 0
for ; curCnt > 0; curCnt-- {
node := q.Pop()
if node.left != nil {
q.Push(node.left)
nextCnt += 1
}
if node.right != nil {
q.Push(node.right)
nextCnt += 1
}
if first {
first = false
} else {
fmt.Printf(" ")
}
fmt.Printf("%d", node.data)
}
}
}

func parse(str string) []int {
ss := strings.Split(str, " ")

var m []int
for _, s := range ss {
if len(s) != 0 {
n, _ := strconv.Atoi(s)
m = append(m, n)
}
}
return m
}

func main() {
r := bufio.NewReader(os.Stdin)
r.ReadLine()
line1, _, _ := r.ReadLine()
pOrder := parse(string(line1))

line2, _, _ := r.ReadLine()
mOrder := parse(string(line2))

root := createBTree(pOrder, mOrder)
levelPrint(root)
}

2. 单词变换

寻找最短路径相关算法。一种解题思路为：

以初始单词A为起点，找出单词列表D中所有满足变化规则的单词，构成列表A‘；再以A’中的单词为起点，找到单词列表（D-A‘）中满足变换规则的单词A‘’……，直到到达最终单词B，统计变换最短的路径长度。有点类似于树的层序遍历搜索。

示例代码：

# -*- coding: utf-8 *-*

# 题目描述
# 有一个单词列表，一个初始单词和一个最终单词，初始单词需要通过单词列表逐步变换到最终单词，求变换所需的最短变换路径长度
# 变换规则：每次只能变动1个字母（不可交换位置，如：从abc变成cad属于变动了2个字母），每次变换只能从单词列表中选取
# 例如：初始单词hot，最终单词dog，单词列表[got, god, dog, lot, log]，最短变换路径为[hot,dot,dog]，最短变换路径长度为3
# 注：单词列表中包含最终单词，不包含初始单词；列表中每一项单词长度与初始单词、最终单词相同；列表中单词不重复

def check(start, end, keywords):
	start_list = list(start)
	result = []
	min_count = len(keywords) + 1
	min_count = _next(list(start), end, min_count, 1, keywords, [])
	return min_count

def _next(start, end, min_count, count, keywords, steps):
	if count == min_count:
		# print '---too long %s---' % min_count
		return min_count
	if ''.join(start) == end:
		# print '[lucky]'
		# print steps
		# print '[lucky]'
		return count
	for i in xrange(0, len(keywords)):
		item = list(keywords[i])
		d = _diffrernce(start, item)
		if d == 1:
			flag = True
			new_keywords = keywords[:]
			new_keywords.remove(keywords[i])
			new_steps = steps[:]
			new_steps.append(keywords[i])
			# print new_keywords, item, count
			result = _next(item, end, min_count, count + 1, new_keywords, new_steps)
			min_count = result if result < min_count else min_count
	return min_count


def _diffrernce(a, b):
	count = 0
	for i in xrange(0, len(a)):
		if a[i] != b[i]:
			count += 1
	return count


if __name__ == '__main__':
	# result = check('hot', 'dog', ['dot', 'god', 'dog', 'lot', 'got', 'log'])
	# result = check('hot', 'dog', ['got', 'god', 'dog', 'lot', 'log'])
	import sys
	start = sys.stdin.readline().replace('\r\n', '').replace('\n', '')
	end = sys.stdin.readline().replace('\r\n', '').replace('\n', '')
	words = sys.stdin.readline().replace('\r\n', '').replace('\n', '').split(' ')
	result = check(start, end, words)
	print result

3. 进制转换

解题思路：

a-z的ascii是一个递增的uchar类型， 所以a-z对应到0-26的简单方法是减去a的ascii值，然后按照26进制的幂计算方式计算出对应的10进制值。

示例代码：

import sys

base = ord('a')

def convert(line):
numArr = [ord(c) - base for c in line]
numArr.reverse()
s = 0
for (i, n) in enumerate(numArr):
# print i, n
s += (n * (26 ** i))

return s
pass

if __name__ == '__main__':
line = sys.stdin.readline()
while len(line) > 0:
line = line.replace('\r\n', '').replace('\n', '')

print convert(line)
line = sys.stdin.readline()
pass

同学们还有其他疑问可以在下面留言，我会尽快进行答疑。再次诚挚邀请同学们加入去哪儿！