Блог пользователя rahulkhairwar

Автор rahulkhairwar, история, 9 лет назад, По-английски

I was solving this question on dp and I use Java as my preferred language for programming.

But, I got a stack overflow error when I submitted the solution in Java, while the same code when converted into C++, ran perfectly fine.

Here is the Java submission : link
and here is the C++ submission : link

So, I searched on the internet and found out that Java's stack space is very less. :/
So, is there any way I could solve this question recursively in Java? I don't want to switch to C++ as I am very comfortable with Java and really like to code in it.

Java users, do you always implement an iterative version of an algorithm which could be solved recursively?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by rahulkhairwar (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Here is the trick:


class Main implements Runnable { static void main(...){ new Thread(null, new Main(), "Main", 1<<28).start(); } public void run() { // your code here } }

1<<28 is the stack size, this is enough for most problems.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried this, but I'm unable to take any input in the run() method. :|

    As soon as I run the code, it throws InputMismatchException

    Screenshot : here (see line 39)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Share full code, plz (for example, in pastebin.org)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Here is the link to the code

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Your problem is that

          new Thread(null, new SamuAndShopping(), "SamuAndShopping", 1 <<28).start();
          

          Creates thread and send command to run thread. It's doesn't wait until thread run() method will be executed, so you concurrenlty close input stream in main thread and you can't read anything from input.

          You have to solutions for this — move all code about input/output into new instantiated thread or use join() method of the thread for blocking main thread until new thread do its job.