Наибольшее количество фиксированной длины в последовательности цифр

-2

я решала алгоритмический проблема один день, который был, как:Наибольшее количество фиксированной длины в последовательности цифр

Учитывая массив цифр, найти наибольшее возможное число фиксированной длины в нем? Для экс-«43124911». Найдите наибольшее количество длин 4? Ответ был бы: 4911

Я попытался создать решение O (n) для этого в java ... Можете ли вы помочь мне улучшить мое решение/сообщить об ошибках/петлевых отверстиях/или лучшем решении? Заранее спасибо ..

Код:

class Solution { 

public static void main(String args[]) { 

    int arrayOfDigits[] = {4,3,2,4,3,9,1} ; 
    boolean newNumber = true ; 
    int requiredNumberLength = 4 ; 

    int maximumNumber = -1 ; 

    int firstDigitOfcurrentNumberNumber = -1 ; 
    int lengthOfcurrentNumberNumber = -1 ; 
    int currentNumber = -1; 
    int futureLargestNumber = -1; 
    int futureLargestNumberLength = -1; 

    int currentNumberSub = -1 ; 
    for(int i = 0 ; i < arrayOfDigits.length ; i++){ 

     if(newNumber){ 
      //System.out.println("In newNumber with " + arrayOfDigits[i]) ; 
      currentNumber = arrayOfDigits[i] ; 
      lengthOfcurrentNumberNumber = 1 ; 
      firstDigitOfcurrentNumberNumber = currentNumber ; 
      newNumber = false ; 

      if(isFeasible(i,arrayOfDigits.length ,requiredNumberLength)) 
       continue ; 
      else 
       break ; 
     } 
     currentNumber = nextNum(currentNumber , arrayOfDigits[i]) ; 
     futureLargestNumber = arrayOfDigits[i] ; 

     if(!isFeasible(i,arrayOfDigits.length,requiredNumberLength)){ 
      futureLargestNumber = -1 ; 
     } 

     if(firstDigitOfcurrentNumberNumber > futureLargestNumber){ 
      lengthOfcurrentNumberNumber++ ; 
      if(lengthOfcurrentNumberNumber == requiredNumberLength){ 
       newNumber = true ; 
       if(currentNumber > maximumNumber){ 
        maximumNumber = currentNumber ; 
       } 
      } 
      continue ; 
     } 
     //System.out.println(futureLargestNumber); 
     if(futureLargestNumber > firstDigitOfcurrentNumberNumber){ 
      newNumber = true ; 
      i-- ; 
      continue ; 
     } 

     //firstDigitOfcurrentNumberNumber == futureLargestNumber 
     lengthOfcurrentNumberNumber++ ; 
     futureLargestNumberLength = 1 ; 

     if(lengthOfcurrentNumberNumber == requiredNumberLength){ 
      if(currentNumber > maximumNumber){ 
       maximumNumber = currentNumber ; 
      } 
      currentNumber = futureLargestNumber ; 
      lengthOfcurrentNumberNumber = futureLargestNumberLength ; 
      continue; 
     } 
     for(int j = i+1 ; j < arrayOfDigits.length ; j++){ 

      futureLargestNumberLength++ ; 
      futureLargestNumber = nextNum(futureLargestNumber,arrayOfDigits[j]) ; 
      lengthOfcurrentNumberNumber++ ; 
      currentNumber = nextNum(currentNumber,arrayOfDigits[j]) ; 

      if(lengthOfcurrentNumberNumber == requiredNumberLength){ 
       if(currentNumber > maximumNumber){ 
        maximumNumber = currentNumber ; 
       } 
       currentNumber = futureLargestNumber ; 
       lengthOfcurrentNumberNumber = futureLargestNumberLength ; 
       i = j ; 
       break ; 
      } 

      currentNumberSub = calculateSub(currentNumber , lengthOfcurrentNumberNumber , futureLargestNumberLength) ; 

      if(currentNumberSub > futureLargestNumber){ 
       i = j ; 
       break ; 
      } 
      if(futureLargestNumber > currentNumberSub){ 
       currentNumber = futureLargestNumber ; 
       lengthOfcurrentNumberNumber = futureLargestNumberLength ; 
       i = j ; 
       break ; 
      } 
     } 

    } 

    System.out.println(maximumNumber) ; 
} 
public static boolean isFeasible(int i , int arrayOfDigitslengthOfcurrentNumberNumbergth , int requiredNumberLength){ 
    if(i-1+requiredNumberLength < arrayOfDigitslengthOfcurrentNumberNumbergth){ 
     return true ; 
    }else{ 
     return false ; 
    } 
} 
public static int nextNum(int currentNumber , int digit){ 
    return (10*currentNumber)+digit ; 
} 
public static int calculateSub(int currentNumber , int lengthOfcurrentNumberNumber , int futureLargestNumberLength){ 
    return (int)(currentNumber/Math.pow(10,lengthOfcurrentNumberNumber-futureLargestNumberLength)); 
} 
}

источник

2015-03-30 Sanchit Handa

Итак, вам «Ищите обзор кода? Для этого есть специальная страница для стека (codereview.stackexchange.com). Вы должны спросить об этом. – Tom

Обратите внимание, что код, который не работает должным образом, не соответствует теме обзора кода - мы * можем * находить ошибки или проблемы, но ваш код должен, насколько вам известно, работать точно так, как предполагалось. Другими словами, CR не изменит * что * ваш код делает, только * как * он это делает. –

Ограничена ли фиксированная длина? – MBo

Простой и прямой O (п) алгоритм - просто перебрать все Len-цифр чисел, формируется из последовательных элементов массива

Len = 4 
Arr = [4,3,1,2,4,9,1,1] 
N = Arr.Length 
Max = Arr[0] 
PowerTen = 1; 
for i = 1 to Len - 1 
     Max = Max * 10 + Arr[i] 
     PowerTen = PowerTen * 10 
//Now Max = 4312, PowerTen = 1000 

Current = Max 
for i = 0 to N - Len - 1 
     //construct next Len-digit number 
     Current = (Current - Arr[i] * PowerTen) * 10 + Arr[i + Len] 
     //4312 - 4000 = 312; 312 * 10 = 3120; 3120 + 4 = 3124 
     if Max < Current 
      Max = Current

источник

2015-03-30 18:35:18 MBo

Мне нравится, что вы использовали псевдокод; что дает объяснение, не давая полного решения. – GhostCat

@MBo! Спасибо - хорошее решение –

Наибольшее количество фиксированной длины в последовательности цифр

ответ

Смежные вопросы