java - noAdajacentDuplicates 使用堆栈

Question

我一直在努力解决程序的这一部分，我需要实现以下目标。

3. “消除相邻重复”：

一个。给定一个整数数组，创建 ArrayList，其中包含使用一个堆栈一次通过消除所有相邻重复项后剩余的所有数字

湾。分析样品运行

C。用伪代码描述算法

d。实施和测试

e. 您只能使用一个循环。

样品运行：

*** ELIMINATING ADJACENT DUPLICATES ***
--> testcase #1
input = [1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [1] CORRECT

---> testcase #2
input = [1, 9, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [1, 9, 5] CORRECT

---> testcase #3
input = [1, 1, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [5] CORRECT

---> testcase #4
input = [1, 1, 1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [] CORRECT
Done!

这是我的代码，但我使用了两个循环，因为这是我能找到的使代码工作的唯一方法。你们有什么技巧可以摆脱第二个循环吗？还是我应该把这一切都废弃并使用不同的算法？

public ArrayList<Integer> noAdjacentDuplicates(int... input)
{
    // TODO PROJECT #1 - Complete
    ArrayList<Integer> result = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();

    System.out.println("input = " + Arrays.toString(input));
    int loop = input.length - 1; //initialize array index

            while(loop >= 0)
            {
                if(!stack.empty())
                {
                    int topElement = stack.peek();

                    if(topElement == input[loop])
                    {
                        while(loop >= 0 && input[loop] == topElement){loop--;}
                        stack.pop();
                    }
                    else
                    {
                        stack.push(input[loop]);
                        loop--;
                    }
                }
                else
                {
                    stack.push(input[loop]);
                    loop--;
                }
            }

    while(!stack.empty())
    {
        result.add(stack.pop());
    }

    return result;
}

标签： javaarrayssetstack

Answer 1

我已经修改了您的代码，以便它只使用 1 个循环，正如这所暗示的那样。

e. 您只能使用一个循环。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Main {

    public static String[] array = new String[5];

    public static void main(String args[]) {
        int[] input = { 1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5 };
        System.out.println("input = " + Arrays.toString(input));
        ArrayList<Integer> result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 9, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 1, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 1, 1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 0, 0, 1 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 0, 0, 2 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

        input = new int[] { 1, 0, 0, 0, 1, 1 };
        System.out.println("input = " + Arrays.toString(input));
        result = noAdjacentDuplicates(input);
        System.out.println("result = " + result.toString());
        System.out.println("----------------------------------");

    }

    public static ArrayList<Integer> noAdjacentDuplicates(int[] input) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        boolean hasAdjacent = false;
        for (int i = 0; i < input.length; i++) {
            int value = input[i]; // get current value
            if (stack.isEmpty()) { // if stack is empty then just push the value
                stack.push(value);
                result.add(value);
            } else {
                int top = stack.peek(); // get the top of the stack
                if (value == top) { // if current value is equal to the top of the stack meaning it has an adjacent
                    hasAdjacent = true;
                }
                // if value is not equal to top but it has an adjacent before
                // example [8, 8, 8, 1], this will trigger on the current value is 1
                else if (value != top && hasAdjacent) {
                    stack.pop(); // pop the stack
                    result.remove(result.size() - 1); // remove the head of the list
                    hasAdjacent = false; // revert has adjacent to false since it starts a new value
                }

                // this checking is required inorder to know if the current value is the same as
                // the top of the stack
                if (!stack.isEmpty()) {
                    top = stack.peek();
                }

                // check if the value is equal to the new top of the stack
                // example [1, 0, 0, 2], the cursor is currently at the last value of 1
                // the stack contains [1, 0], the 0 will be deleted in the elseif above,
                // the new top of the stack is 1 and the value is 2, thus you should add the
                // value in the stack and in the list
                if (value != top && !hasAdjacent) {
                    stack.push(value);
                    result.add(value);
                }
                // example [1, 0, 0, 1], the cursor is currently at the last value of 1
                // the stack contains [1, 0], the 0 will be deleted in the elseif above,
                // the new top of the stack is 1 and the value is 1, thus you should pop the
                // stack and remove the head of the list
                else if (value == top && !hasAdjacent) {
                    stack.pop();
                    result.remove(result.size() - 1);
                }
            }

            // System.out.println(stack); // Uncomment this line so that you'll see the
            // movement of the stack
        }

        return result;
    }

}

输出

input = [1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [1]
----------------------------------
input = [1, 9, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [1, 9, 5]
----------------------------------
input = [1, 1, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = [5]
----------------------------------
input = [1, 1, 1, 5, 6, 8, 8, 8, 0, 1, 1, 0, 6, 5]
result = []
----------------------------------
input = [1, 0, 0, 1]
result = []
----------------------------------
input = [1, 0, 0, 2]
result = [1, 2]
----------------------------------
input = [1, 0, 0, 0, 1, 1]
result = [1]
----------------------------------