1
我現在正在進行代碼挑戰。即使我已經優化了它，我的解決方案也得到了「超時」我正在尋求更高效的解決方案或更多地優化我的解決方案。將字符串中表示的大數除以2，加1或減1 1
問題描述爲： 編寫一個函數，它將一個正整數作爲一個字符串，並返回將該數字轉換爲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();
}
你能不能簡單地算到最近的2的冪的距離，並添加到兩個指數？ – StardustGogeta
因爲它可能需要更多時間。如果你有2^10到2^11之間的數字，你應該走多少步？ – Anderson