魔法币_网易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

我的思路

除了内存超出规定外，其余都符合算法要求

思路如下:

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

码上有戏

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());
}
}
}