將字符串中表示的大數除以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; 
    }