魔法币_网易2018校招编程题

问题描述

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。
输入描述:
输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9),表示小易需要的魔法币数量。
输出描述:
输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符’1’和’2’。
输入例子1:
10
输出例子1:
122

我的思路

除了内存超出规定外,其余都符合算法要求
Alt text
思路如下:

1.先构造并初始化一个完全二叉树,如图所示
2.然后从左子树开始遍历二叉树,同时将遍历的结点放到一个集合中,并且将该集合也就是到该节点的路径放到另一个集合中,如果没有找到该节点,则向上(父节点)开始遍历,同时删掉向下遍历的结点和路径,然后右递归
3.找到指定结点后,对应也找到对应的结点路径,剩下就是观察发现,如果路径中结点的值为偶数(右子树)对应2,左子树对应1,放在一个可变字符串中
4.本地测试(不考虑内存消耗过大),ok

码上有戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class Main{
public static class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
public static void main(String[] args) throws Exception{
Main m=new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in ));
int n=Integer.parseInt(br.readLine());
String s=m.getpa(n,new ArrayList<Integer>(),new ArrayList<List<Integer>>());
System.out.println(s);
}
public String getpa(int n,List<Integer> nodes,List<List<Integer>> paths){
TreeNode root=new TreeNode(0);
if(n<=0)return null;
paths=getPath(root,n,nodes,paths);
List<Integer> target=paths.get(0);
StringBuilder s=new StringBuilder();
target.remove(0);
for(Integer val:target){
if((val&0x1)==0) {
s.append("2");
}
else{
s.append("1");
}
}
return s.toString();
}
List<List<Integer>> getPath(TreeNode root,int n,List<Integer> nodes,List<List<Integer>> paths){
if(root==null)
return paths;
init(root,n);
nodes.add(root.val);
if(root.val==n){
List<Integer> temp=new ArrayList<Integer>();
for(Integer t:nodes){
temp.add(t);
}
paths.add(temp);
}
if(root.left!=null)
getPath(root.left,n,nodes,paths);
if(root.right!=null)
getPath(root.right,n,nodes,paths);
Integer tt=nodes.remove(nodes.size()-1);
return paths;
}
void init(TreeNode root,int n){
if(root==null)
return;
if(root.val<n)
{
if(2*root.val+1<=n)
root.left=new TreeNode(2*root.val+1);
if(2*root.val+2<=n)
root.right=new TreeNode(2*root.val+2);
}
init(root.left,n);
init(root.right,n);
}
}

奇偶倒退法

核心思路就是从最后一个数,通过判断最后一个数是否是奇偶,来倒推,直至为0为止

public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int Count = in.nextInt();
StringBuilder sb = new StringBuilder();
while (Count > 0) {
if (Count % 2 == 0) {
Count = (Count - 2) / 2;
sb.append(“2”);
} else {
Count = (Count - 1) / 2;
sb.append(“1”);
}
}
System.out.println(sb.reverse().toString());
}
}
}