|
|
вернуться в форумMaybe an interesting idea to solve this Instead of copying actually data, we might put a marked-number (index to copy) in the array. For example, if (x > 0) { stack[q ++] = x; } else if (x == -1) { int y = stack[q - 1]; if (y > 0) { System.out.println(y); q--; } else { y = -y; System.out.println(stack[y]); stack[q - 1] = -(y - 1); if (y == 0) { q--; } } } else { stack[q] = -(q - 1); // negative numbers mean a copy. q ++; } of course, this doesn't work for multiple continuous copy (e.g. 0, 0, 0 ..). Re: Maybe an interesting idea to solve this I pursued this idea at first before I noted the easier approach based on the input constraints. The problem with storing markers representing copies in the stream is that it gets complicated when you have many combinations of partially consumed copies which are then copied, over and over again. You basically need a tree to represent the state, and the tree must be walked when popping, which takes longer. There probably is a simplified partial implementation of this, but given the constraints of the problem, it's not necessary. Re: Maybe an interesting idea to solve this I agree. It gets complicated when there are copies inside copies.. so, this is not necessary because there are simpler and straightforward solutions. |
|
|