-2

有一天我正在解决一个算法问题，就像：

给定一个数字数组，找到其中最大可能的固定长度数？例如-“43124911”。找到长度为 4 的最大数？答案是：4911

我尝试在 java 中为此创建 O(n) 解决方案...您能帮我改进我的解决方案/报告错误/漏洞/或更好的解决方案吗？提前致谢..

代码：

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

1 回答 1

1

简单直接的 O(n) 算法 - 只需遍历由顺序数组元素形成的所有 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-30T18:35:18.497 回答