logo标签列表

用最少的矩形覆盖“曼哈顿天际线”。

javaarraysalgorithm
6

我来翻译一道 Codility 给出的问题：

你需要建造一堵石墙。这堵墙应该是直的，长度为 N 米，厚度应该保持不变；但是，它在不同的地方应该有不同的高度。墙的高度由一个由 N 个正整数组成的数组 H 指定。H[I] 是从其左端到右侧 I+1 米处的墙的高度。特别地，H[0] 是墙的左端的高度，H[N−1] 是墙的右端的高度。

这堵墙应该由长方体石块建造（即，这些块的所有侧面都是矩形）。你的任务是计算建造这堵墙所需的最小石块数。

编写一个函数：

class Solution { public int solution(int[] H); }

根据一个由N个正整数组成的数组H，指定了墙的高度，需要返回建造该墙所需最少砖块的数量。

例如，给定包含N = 9个整数的数组H：

  H[0] = 8    H[1] = 8    H[2] = 5
  H[3] = 7    H[4] = 9    H[5] = 8
  H[6] = 7    H[7] = 4    H[8] = 8

该函数应返回7。下图显示了七个块的一种可能排列方式。

假设:

N是[1..100,000]范围内的整数; 数组H中的每个元素都是[1..1,000,000,000]范围内的整数。 复杂度:

预期最坏时间复杂度为O(N); 预期最坏空间复杂度为O(N)(不包括所需的输入参数存储)。

enter image description here

我为所提供的问题编写了一个解决方案。以下是算法和代码，

算法

i. 将块计数设置为1，并从数组的第二个元素开始迭代

ii. 如果当前深度与上一个相同，则继续

iii. 如果当前深度更高，则将其推入堆栈并增加计数

iv. 如果当前深度更低，则保持弹出直到当前深度>=peek。之后，如果堆栈大小=0或更高，则将块计数增加1

代码如下，

public static int solution(int[] H) {

    Stack<Integer> stack = new Stack<>();

    stack.push(H[0]);
    int count = 1;

    int N = H.length;

    for (int i = 1; i < N; i++) {

        if (H[i] == stack.peek()) {
            continue;
        } else if (H[i] > stack.peek()) {
            stack.push(H[i]);
            count++;
        } else {

            while (!stack.isEmpty() && H[i] < stack.peek()) {
                stack.pop();
            }

            stack.push(H[i]);
            count++;
        }
    }

    return count;
}

这个解决方案没有提供正确的答案，即使我花了一些时间进行调试，也无法找到错误。有人能看出来吗？

下面提供了测试数据集，答案是7（但我得到了8）。

    int[] H = new int[9];

    H[0] = 8;
    H[1] = 8;
    H[2] = 5;
    H[3] = 7;
    H[4] = 9;
    H[5] = 8;
    H[6] = 7;
    H[7] = 4;
    H[8] = 8;

谢谢您。
当关闭一个块时，您正在递增+1。在您的情况下，在索引6上将7添加到堆栈时，您不应该递增。之后是while块：if (heights.size() > 0 && heights.top() == H[i]) { heights.push(H[i]); } else { heights.push(H[i]); blocks++; } - Martin Berger
10个回答
2

另一个Java示例。更简单，因为我假设高度 > 0。

    public int solution(int[] hs) {
        int squares = 0;
        Stack<Integer> s = new Stack<>();
        s.push(0);

        for (int h: hs) {
            while (s.peek() > h) {
                s.pop();
            }
            if (s.peek() != h) {
                s.push(h);
                ++squares;
            }
        }

        return squares;
    }
它在Codility上能运行吗？如果真的能运行，这看起来会更加清晰。 - Arefe
@ChakladerAsfakArefe 是的，百分之百。 - Cichy
2

Python解决方案

这是我的解决方案 包含步骤详细说明的解决方案

Codility Python 100%

def solution(H):
"""
Codility 100%
https://app.codility.com/demo/results/trainingQKD6JP-PHA/

Idea is to use stack concept
Compute the minimum number of blocks needed to build the wall.
To build the wall start taking blocks of height one by one.
We need to take care of -
 - the blocked should not be used again
 - this is done only up to blocks height is greater than current
 - why we are using last 8 height block if there is already 8 height block used in previous step?
    reason is 8 is not present in stack top


8,
 8,----- can not use because on stack top 8 is already there
  5,
   7,
    9,
     8,
      7,------ can not use because on stack top 7 is already there
       4,
        8,

This is just example with height, see steps of output for details
 skip8           skip7
            |           |
|           |   |       |
|       |   |   |       |
|       |   |   |       |
|   |   |   |   |       |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |

已使用的区块 - 8 5 7 9 8 4 8

"""

block_count = 0
# stack is used to hold height used to building and remove all the blocks from it,
#  if any of the block of stack is greater than current block(to be added for building)
stack = []
for height in H:
    print(" ")
    print("Current Height " + str(height))
    print("Current stack " + str(stack))
    # Remove all blocks that are bigger than current height, stack should not be empty
    while stack and stack[-1] > height:
        stack.pop()
    print("After remove bigger blocks than current height " + str(stack))

    # stack is not empty and top item of stack is equal to current height
    if stack and stack[-1] == height:
        # Already used this size of block
        print("Already used this size of block " + str(height))
        continue
    else:
        # new block is required, push it's size to the stack
        block_count += 1
        stack.append(height)
        print("Add this block.... " + str(height) + " Minimum Blocks " + str(block_count))

return block_count
1
我找到了一个bug，觉得分享一下可能会有好处。原因是新的高度小于peek值，我们将继续弹出实体。因此，如果堆栈不为空，则新高度将与堆栈顶部的值相同或更高。
如果新高度将相同，则意味着我们已经为高度添加了一个块，并且不会再添加新块。需要针对这种情况设置条件。
               if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

下面提供的代码提供了100%分数。

enter image description here

public int solution(int[] H) {

        Stack<Integer> stack = new Stack<>();

        stack.push(H[0]);
        int count = 1;

        int N = H.length;

        for (int i = 1; i < N; i++) {

            if (H[i] == stack.peek()) {
                continue;
            } else if (H[i] > stack.peek()) {
                stack.push(H[i]);
                count++;
            } else {

                while (!stack.isEmpty() && H[i] < stack.peek()) {
                    stack.pop();
                }

                /*
                 * the new entity is either in same elevation or higher
                 * */

                /*
                * if in same elevation, we already added the block, so keep iterating
                * */
                if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

                stack.push(H[i]);
                count++;
            }
        }

        return count;
    }
1

我提供了一个100% JavaScript的解决方案，时间复杂度为O(N)：

function solution(H) {

    let numBlocks = 0;
    const blocksHeights = [0];

    for (const height of H) {

        while (blocksHeights[blocksHeights.length - 1] > height) {
            blocksHeights.pop();
        }

        if (blocksHeights[blocksHeights.length - 1] !== height) {
            blocksHeights.push(height);
            numBlocks++;
        }

    }

    return numBlocks;

}
1

Ruby 100%

def solution(h)
  h.inject([1, [h.first]]) do |(blocks, stack), n|
    next [blocks+1, stack.push(n)]    if stack.last < n
    stack.pop while stack.any? && stack.last > n
    next [blocks, stack] if stack.last == n

   [blocks+1, stack.push(n)]
  end.first
end
1

如果有人仍然对这个练习感兴趣，我分享我的Python解决方案（在Codility上100%通过）

def solution(H):
    stack, count = [], 1
    for i in H:
        if stack:
            if i == stack[-1]:
                continue
            if i < stack[-1]:
                while stack and stack[-1] > i:
                    stack.pop()
            if stack:
                if i > stack[-1]:
                    count+=1
                    stack.append(i)
            else:
                count+=1
                stack.append(i)
        else:
            stack.append(i)
    return count
1
一个更简单的Java解决方案。
public int solution(int[] H) {
    //block count
    int count = 0;
    // stack is used to hold height used to building and remove all the blocks from it,
    // if any of the block of stack is greater than current block(is to be added for building)
    Deque<Integer> stack = new ArrayDeque<>();

    for (int a : H) {
        // Remove all blocks that are bigger than current height, stack should not be empty
        while (!stack.isEmpty() && a < stack.peek()) {
            stack.pop();
        }
        //new block is required, push it's size to the stack
        if (stack.isEmpty() || a > stack.peek()) {
            count++;
            stack.push(a);
        }

    }
    return count;
}
0

我的Python解决方案（在Codility上有100％的成功率）

import math

def solution(H):
    nb_blocks = 0
    horizon = [math.inf]

    for h in H:
        while horizon and h < horizon[-1]:
            horizon.pop()

        if (horizon and h > horizon[-1]) or (not horizon):
            horizon.append(h)
            nb_blocks += 1


    return nb_blocks
0

在Codility中100%使用C++

#include <stack>

int solution(vector<int> &H) {
    int cnt{0};
    std::stack<int> reusedStone;

    for (auto h : H) {
        if (reusedStone.empty() || (h > reusedStone.top())) {
            reusedStone.push(h); cnt++;
        } else if (h < reusedStone.top()) {
            while ((!reusedStone.empty()) && (h < reusedStone.top())) {
                reusedStone.pop();
            }
            if ((!reusedStone.empty()) && (h == reusedStone.top())) {
                continue;
            } else {
                reusedStone.push(h); cnt++;
            }
        }
    }

    return cnt;
}
0

使用C#编程（在Codility上达到100%）

public int solution(int[] H) {

        Stack<int> stack = new Stack<int>();

        stack.Push(H[0]);
        int count = 1;



        for (int i = 1; i < H.Length; i++)
        {

            if (H[i] == stack.Peek())
            {
                continue;
            }
            else if (H[i] > stack.Peek())
            {
                stack.Push(H[i]);
                count++;
            }
            else
            {

                while (!(stack.Count==0) && H[i] < stack.Peek())
                {
                    stack.Pop();
                }
            if (!(stack.Count==0) && H[i] == stack.Peek()) {
                continue;
            }


                stack.Push(H[i]);
                count++;
            }
        }

        return count;
}
感谢您提供的这段代码片段，可能会在短期内提供一些有限的帮助。一个合适的解释会大大提高它的长期价值，因为它会说明为什么这是一个好的解决方案，并且会让它对其他类似问题的未来读者更加有用。请编辑您的答案，添加一些解释，包括您做出的假设。 - Toby Speight
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接