将字符串中表示的大数除以2，加1或减1 1

Question

我现在正在进行代码挑战。即使我已经优化了它，我的解决方案也得到了“超时”我正在寻求更高效的解决方案或更多地优化我的解决方案。

问题描述为： 编写一个函数，它将一个正整数作为一个字符串，并返回将该数字转换为1所需的最小操作数。该数字长达309位数，你不能用太多的数字表达太多的性格。 变换过程仅限于三种操作： 1.添加1 2减1 3.把数由2（仅偶数让这里）

我的想法是使用DFS遍历所有可能的解决方案用记忆来加速它。但它确实超过了时间限制。这个问题不能使用dp，因为dp需要一个非常大的数组来记忆。下面是我的代码：

private static int dfs(String num, int step,Map<String,Integer> memory){ 
     if(num.equals("1")){ 
      return step; 
     } 
     Integer size = memory.get(num); 
     if(size != null && size < step){ 
      return Integer.MAX_VALUE; 
     } 
     memory.put(num, step); 
     int min = Integer.MAX_VALUE; 
     int lastDigit = num.charAt(num.length() - 1) - '0'; 
     if(lastDigit % 2 == 0){ 
      min = Math.min(min, dfs(divideBy2(num), step + 1, memory)); 
     }else{ 
      min = Math.min(min, dfs(divideBy2(num), step + 2, memory)); 
      min = Math.min(min, dfs(divideBy2(plusOne(num)), step + 2, memory)); 
     } 
     return min; 
    } 
    private static String plusOne(String num){ 
     StringBuilder sb = new StringBuilder(); 
     int carry = 1; 
     for(int i = num.length() - 1; i >=0; i--){ 
      int d = (carry + num.charAt(i) - '0') % 10; 
      carry = (carry + num.charAt(i) - '0')/10; 
      sb.insert(0, d); 
     } 
     if(carry == 1){ 
      sb.insert(0, carry); 
     } 
     return sb.toString(); 
    } 
    private static String divideBy2(String num){ 
     StringBuilder sb = new StringBuilder(); 
     int x = 0; 
     for(int i = 0; i < num.length(); i++){ 
      int d = (x * 10 + num.charAt(i) - '0')/2 ; 
      x = (num.charAt(i) - '0') % 2 ; 
      if(i > 0 || (i == 0 && d != 0)) 
       sb.append(d); 
     } 

     return sb.toString(); 
    } 

注：测试几种情况后：我得到了一些道理，但不能一概而论的规则。 如果当前的数字是奇数。我们在这里得到了两个选择：加1或减1.操作后的数字可以再除以2，步数会更短。

更新：嗨，伙计们，我整夜工作，并找到一个解决方案，通过测试。这个想法是把问题分成两个子问题：1.如果数字是偶数，就把它除以二。 2.如果数字是奇数，请选择让数字在其比特表示中具有更多拖尾零的方式。我将更多地解释奇数情况：如果数字是奇数，最后两位可以是“01”或“11”。当它是“01”时，将其减1，这使最后两位变为“00”。如果是“11”，则增加1，生成“00”。通过这样做，由奇数产生的下一个偶数可以被多次分割，这在实践中是非常快的。下面是我的代码，如果您有关于实施的几个问题，请随时给我一个信息：

public static int answer(String n) { 

     // Your code goes here. 
     int count = 0; 
     while(!n.equals("1")){ 
      if((n.charAt(n.length() - 1) - '0') % 2 == 0){ 
       n = divideBy2(n); 
      }else if(n.equals("3") || lastTwoBit(n)){ 
       n = subtractOne(n); 
      }else{ 
       n = plusOne(n); 
      } 
      count++; 
     } 
     return count; 
    } 
     private static boolean lastTwoBit(String num){ 
      int n = -1; 
      if(num.length() == 1){ 
       n = Integer.valueOf(num); 
      }else{ 
       n = Integer.valueOf(num.substring(num.length() - 2, num.length())); 
      } 
      if(((n >>> 1) & 1) == 0){ 
      return true; 
      } 
      return false; 
     } 
     private static String subtractOne(String num){ 
     if(num.equals("1")){ 
      return "0"; 
     } 
     StringBuilder sb = new StringBuilder(); 
     int carry = -1; 
     for(int i = num.length() - 1; i >= 0; i--){ 
      int d = carry + num.charAt(i) - '0'; 
      if(d < 0){ 
       carry = -1; 
       sb.insert(0, '9'); 
      }else if((d == 0 && i != 0) || d > 0){ 
       carry = 0; 
       sb.insert(0, d); 
      } 
     } 
     return sb.toString(); 
    } 
    private static String plusOne(String num){ 
     StringBuilder sb = new StringBuilder(); 
     int carry = 1; 
     int i = 0; 
     for(i = num.length() - 1; i >=0; i--){ 
      if(carry == 0){ 
       break; 
      } 
      int d = (carry + num.charAt(i) - '0') % 10; 
      carry = (carry + num.charAt(i) - '0')/10; 
      sb.insert(0, d); 
     } 
     if(carry ==0){ 
      sb.insert(0, num.substring(0, i + 1)); 
     } 
     if(carry == 1){ 
      sb.insert(0, carry); 
     } 
     return sb.toString(); 
    } 
    private static String divideBy2(String num){ 
     StringBuilder sb = new StringBuilder(); 
     int x = 0; 
     for(int i = 0; i < num.length(); i++){ 
      int d = (x * 10 + num.charAt(i) - '0')/2 ; 
      x = (num.charAt(i) - '0') % 2 ; 
      if(i > 0 || (i == 0 && d != 0)) 
       sb.append(d); 
     } 

     return sb.toString(); 
    } 

Answer 1

虽然没有在1 ... 如果奇...减1 =>即使 如果连..除以2.

只是将操作和返回。

例如5593
5593 -1 = 5592 /2 = 2796 /2 = 1398 /2 = 699 -1 = 698 /2 = 349 -1 = 348 /2 = 174 /2 = 87 -1 = 86 /2 = 43 -1 = 42 /2 = 21 -1 = 20 /2 = 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1

19 Operations -///-/-//-/-/-//-//

编辑：时间复杂度为O(logN)，因为我们两个把数/减然后再分割。 和空间是O(1)

public int make1(string s) 
    { 
     int n = 0; 
     while(s != "1") 
     { 
      switch(s[s.Length-1]) 
      { 
       case '0': 
       case '2': 
       case '4': 
       case '6': 
       case '8': 
        s = div2(s); 
        ++n; 
        break; 
       case '1': 
       case '3': 
       case '5': 
       case '7': 
       case '9': 
        s = minus1(s); 
        s = div2(s); 
        n += 2; 
      } 
     } 
     return n; 
    }