18

私はインタビューで次の質問をされました: Integers のスタックがある場合、Collections.max を使用せず、スタックを反復処理して要素を比較せずに、スタックの最大値を見つけるにはどうすればよいでしょうか。コレクションAPIを使用するか、スタックを反復処理して比較を使用する以外の方法がわからないため、以下のコードで回答しました。何か案は？

import java.util.Collections;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args){
        Stack lifo = new Stack();
        lifo.push(new Integer(4));
        lifo.push(new Integer(1));
        lifo.push(new Integer(150));
        lifo.push(new Integer(40));
        lifo.push(new Integer(0));
        lifo.push(new Integer(60));
        lifo.push(new Integer(47));
        lifo.push(new Integer(104));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max.toString());
        }
    }
}
4

14 に答える 14

31

代わりに使用することによりCollections.min():

if (!lifo.isEmpty()) {
  Integer max = Collections.min(lifo, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
      return o2.compareTo(o1);
    }
  });
  System.out.println("max=" + max.toString());
}

カスタムComparatorは比較を反転するため、Collections.min()実際には最大値が返されることに注意してください。

于 2013-07-24T18:09:24.143 に答える
10

これで質問のニーズが満たされるかどうかはわかりませんが、このようにmax()andを使用するiterationことは回避できますが、バックグラウンドでandをsort使用 します。iterationComparable

if (!lifo.isEmpty()) {
    Stack sc = (Stack) lifo.clone();
    Collections.sort(sc);
    System.out.println("max=" + sc.get(sc.size() - 1));
}
于 2013-07-24T18:15:51.780 に答える
10

編集：

スタックを反復せずに

実際にはすべての反復を禁止しているわけではありません。むしろ、質問は単純なことを禁止するだけです

for (Integer i : lifo)

したがって、このソリューションは質問の制限を満たしています。

スタックのコピーを空にするだけです。コピーから各要素をポップし、その間ずっと整数に対して max をチェックします。

Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;

while (!lifoCopy.isEmpty())
{
    max = Math.max(lifoCopy.pop(), max);
}

System.out.println("max=" + max.toString());

これは、インタビュアーがより制限的になり、組み込み関数 (max、min、sort など) を許可しないことにした場合でも、O(n) 時間で機能します。

さらに、オリジナルを無傷にする必要があるが、クローンを使用できない場合は、追加のスタックを使用して行うことができます。

Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;

while (!lifo.isEmpty())
{
    int val = lifo.pop();

    max = Math.max(val, max);

    reverseLifo.push(val);
}

while (!reverseLifo.isEmpty())
{
    lifo.push(reverseLifo.pop());
}

System.out.println("max=" + max.toString());

最後に、これは一時変数との比較が許容されることを前提としています。比較がまったく許可されていない場合は、この方法と組み合わせてこのソリューションが機能します。

于 2013-07-24T18:05:17.313 に答える
7

このコード:

public static Integer max(Stack stack) {
    if (stack.isEmpty()) {
        return Integer.MIN_VALUE;
    }
    else {
        Integer last = (Integer)stack.pop();
        Integer next = max(stack);
        stack.push(last);
        if (last > next) {
            return last;
        }
        else {
            return next;
        }            
    }
}

public static void main(String[] args){
    Stack lifo = new Stack();
    lifo.push(new Integer(4));
    lifo.push(new Integer(1));
    lifo.push(new Integer(150));
    lifo.push(new Integer(40));
    lifo.push(new Integer(0));
    lifo.push(new Integer(60));
    lifo.push(new Integer(47));
    lifo.push(new Integer(104));

    System.out.println(Arrays.deepToString(lifo.toArray()));
    System.out.println(max(lifo));
    System.out.println(Arrays.deepToString(lifo.toArray()));
}

出力:

[4, 1, 150, 40, 0, 60, 47, 104]
150
[4, 1, 150, 40, 0, 60, 47, 104]

これは特定のスタックでの再帰であり、最大の要素を見つけ、スタックの順序を変更しません。

ただし、反復は、そのように定義した場合にのみ再帰とは異なります。また、最大値を見つけるには、何らかの方法ですべての要素を比較する必要があります-どんな数学的形式でも、Anirudhのような関係演算子またはビットごとの演算子を使用して. 私見、かなり漠然と定義されたタスク。

于 2013-07-24T18:41:37.310 に答える
4

既成概念にとらわれずに考える時です。Wolfram Alpha REST APIを使用して、次の結果を計算するように依頼します。

"maximum of " + Arrays.deepToString(lifo.toArray())

150を返します。

于 2013-07-24T18:52:55.337 に答える
1

これが私の解決策です：

import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args){
        Stack lifo = new Stack();
        lifo.push(new Integer(4));
        lifo.push(new Integer(1));
        lifo.push(new Integer(150));
        lifo.push(new Integer(40));
        lifo.push(new Integer(0));
        lifo.push(new Integer(60));
        lifo.push(new Integer(47));
        lifo.push(new Integer(104));

        Object lifoArray[] = lifo.toArray();
        Arrays.sort(lifoArray);
        System.out.println(lifoArray[lifoArray.length-1]);
    }
}

Arrays.sort()昇順に並べるため、ソートされた配列の最後の値が最大値になります。

于 2013-07-24T22:50:11.660 に答える
1

要素をスタックにプッシュするときは、最大値を更新します

void main()
    int max = Integer.min
    lifo.push(1)

その間

   void push(Integer value) {
       //push into stack
       //update max value
   }
于 2013-07-24T18:06:13.753 に答える
1

次のように変換できますTreeSet。

int myMax = new TreeSet<Integer>(lifo).last();
于 2013-07-24T18:07:34.790 に答える
1

Collections.sort を Comparator と共に使用して降順で並べ替え、スタックから一番上の要素をピークします。

于 2013-07-24T18:07:51.477 に答える
0

繰り返しがなければ、再帰呼び出しを行うことができます。宿題でなければ、そうするのは論理的ではありません。または、反復と再帰なしでこれを行うこともできます。

ただし、簡単な簡単なアプローチは次のとおりです。

public class StackDemo {
    public static int max = 0; //set this to least, may be negative
    public static Stack lifo = new Stack();
    public static void main(String[] args){        
        pushToStack(new Integer(4));
        pushToStack(new Integer(1));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max);
        }
    }
    void static int pushToStack(Integer value){
        lifo.push(value);
        if(max<value){
        max = value;
        }
        return max;
    }    

}
于 2013-07-24T18:10:39.993 に答える