LeetCode第1441题 – 用栈操作构建数组

90 views

题目

给你一个目标数组 target 和一个整数 n。每次迭代,需要从  list = {1,2,3…, n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target :

  • Push:从 list 中读取一个新元素, 并将其推入数组中。
  • Pop:删除数组中的最后一个元素。
  • 如果目标数组构建完成,就停止读取更多元素。

题目数据保证目标数组严格递增,并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

解答

public class Solution {

	public static final String PUSH = "Push";
	public static final String POP = "Pop";

	public List<String> buildArray(int[] target, int n) {
		if (target == null || target.length == 0) {
			return Collections.emptyList();
		}

		int length = target.length;

		List<String> operations = new ArrayList<>();

		for (int i = 0, j = 1; i < length; ++j) {

			if (target[i] == j) {
				operations.add(PUSH);
				++i;
			}
			else {
				operations.add(PUSH);
				operations.add(POP);
			}
		}

		return operations;
	}
}

要点
比较简单,但没有使用到栈对象来解题。
后面有空了要看下网友的解答方法。

准备的用例,如下

    @Test
    public void test101() {
        assertEquals(Arrays.asList("Push", "Push", "Pop", "Push"), new L1441().buildArray(new int[] { 1, 3 }, 3));
    }

    @Test
    public void test102() {
        assertEquals(Arrays.asList("Push", "Push", "Push"), new L1441().buildArray(new int[] { 1, 2, 3 }, 3));
    }

    @Test
    public void test103() {
        assertEquals(Arrays.asList("Push", "Push"), new L1441().buildArray(new int[] { 1, 2 }, 4));
    }

    @Test
    public void test104() {
        assertEquals(Arrays.asList("Push", "Pop", "Push", "Push", "Push"),
                new L1441().buildArray(new int[] { 2, 3, 4 }, 4));
    }

    @Test
    public void test201() {
        assertEquals(Arrays.asList(), new L1441().buildArray(new int[] {}, 4));
    }

    @Test
    public void test202() {
        assertEquals(Arrays.asList("Push"), new L1441().buildArray(new int[] { 1 }, 4));
    }

    @Test
    public void test203() {
        assertEquals(Arrays.asList("Push", "Pop", "Push"), new L1441().buildArray(new int[] { 2 }, 4));
    }

    @Test
    public void test204() {
        assertEquals(Arrays.asList("Push", "Pop", "Push", "Pop", "Push", "Pop", "Push"),
                new L1441().buildArray(new int[] { 4 }, 4));
    }

    @Test
    public void test301() {
        assertEquals(Arrays.asList("Push", "Pop", "Push", "Push", "Pop", "Push"),
                new L1441().buildArray(new int[] { 2, 4 }, 4));
    }


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第1441题 – 用栈操作构建数组

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud