`
mabusyao
  • 浏览: 252612 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

BlockStructure

J# 
阅读更多

/*Problem Statement

A group of vertical blocks are placed densely one after another on the ground. The blocks each have a width of 1, but their heights may vary.

For example, if the heights of the vertical blocks are given as {1,5,5,1,6,1}, the configuration would look like the following picture:


    ×
 ×× ×
 ×× ×
 ×× ×
 ×× ×
××××××

Your task is to reproduce the exact shape of this structure using some number of non-intersecting rectangles.

You will be given a int[] heights representing the heights of the vertical blocks from left to right.

Return the minimal number of rectangles necessary to perform this task with the given configuration of blocks.

Definition
Class: BlockStructure
Method: cover
Parameters: int[]
Returns: int
Method signature: int cover(int[] heights)
(be sure your method is public)

Constraints
- heights will have between 1 and 50 elements, inclusive.
- Each element of heights will be between 1 and 1000, inclusive.
Examples
0) {1,5,5,1,6,1} Returns: 3
We can use rectangles with sizes 6x1, 2x4 and 1x5.

    ×
 ×× ×
 ×× ×
 ×× ×
 ×× ×
××××××

1) {2,2,2,4,4} Returns: 2
We can use a 3x2 rectangle and a 2x4 rectangle.

   ××
   ××
×××××
×××××

2) {6,6,6,6,6,6} Returns: 1
The structure is a rectangle.

××××××
××××××
××××××
××××××
××××××
××××××

3){71,44,95,16,10,80,12,17,98,61} Returns: 10
It's impossible to use less than 10 rectangles.

4){100,100,97,100,100,100,97,98,99,99}
Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc.
Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved.*/

package blockStructure;

import java.util.ArrayList;

public class BlockStructure {

public static int cover(int[] heights) {

int[][] records = markRecords(heights);

int result = 0;

int i = 0;
int j = 0;
while(i < records.length && j < records[i].length) {
if(records[i][j] == 1) {
int start_i = i;
int start_j = j;
while(j < records[i].length && records[i][j] == 1) j++;
j--;

while(i < records.length && rangeExist(records, i, start_j, j)) i++;
i--;

result++;
records = removeRecords(records, start_i, start_j, i, j);
i = j = 0;
} else if(records[i][j] == 0) {
if(j < records[i].length - 1) j++;
else {
j = 0;
i++;
}
}
}

return result;
}

//private static int result = 0;

public static int cover_2(int[] heights) {
int result = 0;

if(heights.length == 1) return 1;

deduct(heights);

result++;

if(isEmpty(heights)) return result;

ArrayList zeroList = zeroPos(heights);

int i = 0;
int temp = -1;
while(i < zeroList.size()) {
int position = ((Integer)zeroList.get(i)).intValue();
if(position == 0 || position - temp == 1) {
temp = position;
}
else {
int[] subtree = new int[position - temp - 1];
for(int j = temp + 1; j < position; j++){
subtree[j - temp - 1] = heights[j];
}
result += cover_2(subtree);

temp = position;

}
i++;
}

int position = ((Integer)zeroList.get(zeroList.size() - 1)).intValue();
if(position != heights.length - 1) {
int[] subtree = new int[heights.length - position - 1];
for(int j = position + 1; j < heights.length; j++){
subtree[j - position - 1] = heights[j];
}
result += cover_2(subtree);
}

return result;
}

private static boolean isEmpty(int[] array) {
for(int k = 0; k < array.length; k++) {
if(array[k] != 0) return false;
}

return true;
}

private static ArrayList zeroPos(int[] array) {
ArrayList list = new ArrayList();

for(int i = 0; i < array.length; i++) {
if(array[i] == 0) list.add(i);
}

return list;
}

private static int maxium(int[] array) {
int maxium = 0;
for(int i : array) {
if(i > maxium) maxium = i;
}

return maxium;
}

private static void deduct(int[] array) {
int min = minum(array);

for(int i = 0; i < array.length; i++) {
array[i] = array[i] - min;
}
}

private static int minum(int[] array) {
int min = Integer.MAX_VALUE;
for(int i : array) {
if(i < min) min = i;
}

return min;
}

private static int[][] markRecords(int[] array) {
int largestNum = maxium(array);

int[][] result = new int[largestNum][array.length];

for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[i].length; j++) {
try{
if(array[j] > i ) result[i][j] = 1;
else result[i][j] = 0;
}catch(Exception e){
e.printStackTrace();
}
}
}

return result;
}

private static int[][] removeRecords(int[][] records, int i, int j, int x, int y) {
for(int k = i; k <= x; k++) {
for(int m = j; m <= y; m++) {
records[k][m] = 0;
}
}
return records;
}

private static boolean rangeExist(int[][] records, int i, int start_j, int j) {
for(int k = start_j; k <= j; k++) {
if(records[i][k] == 0) return false;
}

return true;
}

}

分享到:
评论

相关推荐

    Data Types and block structure

    2. **结构体(Structure)**:将不同数据类型组合在一起,形成一个新的复合数据类型,可以更好地组织相关的数据。 3. **枚举(Enumeration)**:定义了一组命名的常量,这些常量通常是整数类型。 ### 块结构的作用 ...

    non-unique index branch and leaf block structure

    标题“非唯一索引分支和叶块结构”指的是数据库管理系统中的数据存储结构,特别是与B树(B-tree)或B+树(B+tree)相关的概念。这些数据结构在数据库索引中扮演着核心角色,特别是在关系型数据库系统中,如MySQL、...

    blockstructure:Jacopo Grilli和Stefano Allesina撰写的“生态社区的模块化和稳定性”手稿随附的代码

    块状结构 Jacopo Grilli和Stefano Allesina撰写的“生态社区的...文件“ BlockStructure.R”包含使用该代码的指南以及许多示例。 对于任何问题/评论/错误,请随时与我们联系 斯蒂法诺·阿莱西纳(Stefano Allesina)

    C程序设计语言第2版

    Block Structure Initialization Recursion The C Preprocessor File Inclusion Macro Substitution Conditional Inclusion Chapter 5: Pointers and Arrays Pointers and Addresses Pointers and ...

    Python Programming Decision Structures.ppt

    6. Indentation and Block Structure 缩进和块结构是 Python 编程的基本概念。在决策结构中,缩进和块结构用于表示指令序列的执行顺序。例如,在温度转换程序中,使用缩进来表示if语句的执行顺序。 7. Example: ...

    The C programming Language(chm格式完整版)

    Block Structure Initialization Recursion The C Preprocessor File Inclusion Macro Substitution Conditional Inclusion Chapter 5: Pointers and Arrays Pointers and Addresses Pointers and ...

    全定制FPGA求最大公约数设计文件

    而".bsf"文件是Block Structure Format,用于描述FPGA的布局面板,包括逻辑块的物理位置和连接方式。这些文件配合.bdf文件,共同定义了硬件电路的布局和布线。 最大公约数的求解算法有很多种,如欧几里得算法...

    超详细的有注释的pl0程序

    此外,PL/0还支持结构化编程的概念,如块结构(block structure),其中每个语句都必须在开始和结束括号之间,这有助于保持代码的整洁和易于理解。 在解压后的文件"超详细的有注释的pl0代码"中,你可能会发现一个...

    分块结构在三维地震数据处理中的应用.pdf

    传统的地震处理方法在面对大数据量时往往效率低下,因此,采用分块结构(Block Structure)成为了解决这一问题的有效手段。 【分块结构】在三维地震数据处理中,分块结构是一种优化存储和访问数据的方法。它将庞大...

    libfm手册1.4.2

    接着,文档还介绍了一个扩展模块——块结构(Block Structure,简称BS)。块结构主要用于处理具有多维块的大型数据集。它能够以更细粒度的方式来处理数据,使得libfm能够以块的形式来学习模型参数,提升模型的灵活性...

    PLSQL基础入门

    五、PL/SQL Block Structure PL/SQL块结构包括四部分:Header、Declarative、Executable和Exception。 六、PL/SQL Procedure和Function 1. Procedure是执行一个动作,可以返回一个值。 2. Function是计算一个值,...

    densenet1.zip

    2. **块结构(Block Structure)**:DenseNet由一系列的“稠密块”(Dense Block)和“过渡层”(Transition Layer)组成。稠密块内部的每一层都会接收到前面所有层的输出,而过渡层则负责下采样并控制网络的参数...

    PLSQL教學講義.doc

    PL/SQL Block Structure是PL/SQL程序的基础组成部分。一个PL/SQL块由声明部分(Declaring Section)、执行部分(Execution Section)和异常处理部分(Exception Handling Section)组成。声明部分用于定义变量和常量...

    mysql优化文档

    图片文件"InnoDB Page Structure.jpg"和"InnoDB Log Block Structure.jpg"可能详细解释了InnoDB的数据页结构和日志块结构,这些都是理解InnoDB性能的关键。InnoDB的页结构包括B+树索引,而日志块结构则与事务的ACID...

    Fortran 95程序设计【彭国伦】

    此外,它还支持更现代的编程结构,如子程序(Subroutine)、函数(Function)和块结构(Block Structure)。 2. **数据类型**:Fortran 95支持多种数据类型,包括基本类型(如实型、整型、字符型)和复杂类型(如数...

    HEVC Complexity and Implementation Analysis

    HEVC的一个关键特性是其采用的四叉树分割结构(Quadtree Block Structure)。这一结构允许每个编码单元(CU, Coding Unit)进一步细分为四个子单元,直至最小分割尺寸。这种灵活的块分割方法提高了编码效率,但同时也...

    SILK_RTP_PayloadFormat.pdf

    - **5.2 Storage Block Structure**:解释了如何将SILK编码的音频数据块存储在文件中,包括数据块的格式和组织方式。 #### 6. Congestion Control 为了应对网络拥塞问题,SILK采用了先进的拥塞控制算法。这些算法...

    C程序设计语言(英文第2版)The C Programming Language(2nd Edition)pdf

    - Block Structure (块结构) - Initialization (初始化) - Recursion (递归) - The C Preprocessor (C预处理器) - File Inclusion (文件包含) - Macro Substitution (宏替换) - Conditional Inclusion (条件...

Global site tag (gtag.js) - Google Analytics