魔法币

时间限制：1秒
空间限制：32768K
小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入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
==================================
来源：https://www.nowcoder.com/test/question/32c71b52db52424c89a565e4134bfe4e?pid=6910869&tid=11897604
上面是题目，今晚用java写了个双向链表来解决这个问题，但内存超标了，以后再考虑下怎么优化吧，按理说双向链表不大吧，难道要把类型换成short?

package niuke;

import java.util.Scanner;

/**
 * @author chenfh
 * @date 2017年10月17日 下午10:21:31
 */
public class Main_1 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        String answer = findAns(n);
        System.out.println(answer);
        System.out.println("测试结果:" + test(answer, n));
//      for(int i = 0; i < 999999; i++) {
//          String answer = findAns(i);
//          System.gc();
//          if(!test(answer, i)) {
//              System.out.println("发生一处错误");
//              break;
//          } 
//      }
    }
    public static boolean test(String answer, int n) {
        int seed = 0;
        for(int i = 0; i < answer.length(); i++) {
            String select = String.valueOf(answer.charAt(i));
            if(select.equals("1")) {
                seed = meachine_1(seed);
            } else if (select.equals("2")) {
                seed = meachine_2(seed);
            }
        }
        return seed == n;
    }
    public static String findAns(int n) {
        class Node{
            public Node pre = null;
            public Node next = null;
            public int seed;
            public int select;
            public Node(int seed, int select) {
                this.seed = seed;
                this.select = select;
            }
        }
        Node node = new Node(0, 1);
        Node root = node;
        while(node.seed != n) {
            if(node.seed < n) {
                Node node_1 = null;
                if(node.select == 1) {
                    node_1 = new Node(meachine_1(node.seed), 1);
                } else if (node.select == 2) {
                    node_1 = new Node(meachine_2(node.seed), 1);
                }
                node.next = node_1;
                node_1.pre = node;
                node = node_1;
            } else if (node.seed > n) {
                node = node.pre;
                if(node.select == 1) {
                    node.select = 2;
                } else if (node.select ==2) {
                    node = node.pre;
                    while(node.select == 2) {
                        node = node.pre;
                    }
                    node.select = 2;
                }
            }
        }
        node.next = null;
        String result = "";
        while(root.next != null) {
            result += root.select;
            root = root.next;
        }
        return result;
    }
    public static int meachine_1(int x) {
        return 2 * x + 1;
    }
    public static int meachine_2(int x) {
        return 2 * x + 2;
    }
}