- 浏览: 253307 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
mabusyao:
漠北空城 写道请问下,你这个是JDK版本是多少呢?!忘记了,应 ...
HashMap 源码解读 -
漠北空城:
请问下,你这个是JDK版本是多少呢?!
HashMap 源码解读 -
schumee:
完美团队~
项目沉思录 - 1.1 -
winie:
整理下 搞成引擎嘛 国产需要这样的engine
简单工作流引擎 -
mabusyao:
某位同学给我提供的堪称完美的解决方案:1. 将三个int数组放 ...
CraneWork
/*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;
}
}
发表评论
-
大数据下的实体解析
2016-07-07 12:03 671大数据时代的实体解析困境 <!--[if !sup ... -
中文相似度匹配算法
2015-12-30 14:44 1921基于音形码的中文字 ... -
各种语言写的wordcount
2015-09-24 16:07 0Java版本: String input ... -
数组双指针算法的研究
2015-07-14 16:59 2461双指针算法在数组/链 ... -
摩尔投票法
2015-06-30 20:13 18413摩尔投票法 提问: 给定一个int型数组,找出该数 ... -
(转)最长回文字串算法
2015-01-18 14:30 1438来自(http://blog.163.com/zhaohai ... -
STRUTS2 源码 - Logging System
2012-05-24 08:51 1405看了STRUTS2的源码,了解了它的logging系统,觉得还 ... -
在线词典的数据结构实现。
2012-05-18 08:37 0昨天在网上看到了一道百度的面试题: Baidu写道 ... -
存储中间计算结果的动态规划算法
2012-04-18 15:50 1217public class RodCutting { ... -
java写的四则运算器
2011-08-19 22:19 2723本打算做一个从RE到NFA的转换器,思路已经理清了,但是在动手 ... -
什么是最小二乘拟合
2007-09-14 21:27 963对于一个数据点(x1, y1), ... (xn, yn)的集 ... -
palindrome
2008-07-14 17:39 985package palindrome;/*Problem St ... -
CraneWork
2008-07-14 19:14 1031/*Problem Statement There are ... -
SalesRouting
2008-07-15 10:53 798package salesRouting;/*Problem ... -
FactorialSystem
2008-07-21 19:36 856/*Problem StatementIn the facto ... -
RecurringNumbers
2008-07-22 09:41 916/*Problem StatementA rational n ... -
HardDuplicateRemover
2008-07-23 15:17 935/*Problem StatementWe have a se ... -
SkipStones
2008-07-28 17:31 826/*Problem StatementWhen a stone ... -
TheaterVisit
2008-07-28 17:31 784/*Problem StatementYou want to ... -
SquareDigits
2010-07-06 12:36 1027Problem Statement ***Note: ...
相关推荐
2. **结构体(Structure)**:将不同数据类型组合在一起,形成一个新的复合数据类型,可以更好地组织相关的数据。 3. **枚举(Enumeration)**:定义了一组命名的常量,这些常量通常是整数类型。 ### 块结构的作用 ...
标题“非唯一索引分支和叶块结构”指的是数据库管理系统中的数据存储结构,特别是与B树(B-tree)或B+树(B+tree)相关的概念。这些数据结构在数据库索引中扮演着核心角色,特别是在关系型数据库系统中,如MySQL、...
块状结构 Jacopo Grilli和Stefano Allesina撰写的“生态社区的...文件“ BlockStructure.R”包含使用该代码的指南以及许多示例。 对于任何问题/评论/错误,请随时与我们联系 斯蒂法诺·阿莱西纳(Stefano Allesina)
Block Structure Initialization Recursion The C Preprocessor File Inclusion Macro Substitution Conditional Inclusion Chapter 5: Pointers and Arrays Pointers and Addresses Pointers and ...
6. Indentation and Block Structure 缩进和块结构是 Python 编程的基本概念。在决策结构中,缩进和块结构用于表示指令序列的执行顺序。例如,在温度转换程序中,使用缩进来表示if语句的执行顺序。 7. Example: ...
Block Structure Initialization Recursion The C Preprocessor File Inclusion Macro Substitution Conditional Inclusion Chapter 5: Pointers and Arrays Pointers and Addresses Pointers and ...
而".bsf"文件是Block Structure Format,用于描述FPGA的布局面板,包括逻辑块的物理位置和连接方式。这些文件配合.bdf文件,共同定义了硬件电路的布局和布线。 最大公约数的求解算法有很多种,如欧几里得算法...
此外,PL/0还支持结构化编程的概念,如块结构(block structure),其中每个语句都必须在开始和结束括号之间,这有助于保持代码的整洁和易于理解。 在解压后的文件"超详细的有注释的pl0代码"中,你可能会发现一个...
传统的地震处理方法在面对大数据量时往往效率低下,因此,采用分块结构(Block Structure)成为了解决这一问题的有效手段。 【分块结构】在三维地震数据处理中,分块结构是一种优化存储和访问数据的方法。它将庞大...
接着,文档还介绍了一个扩展模块——块结构(Block Structure,简称BS)。块结构主要用于处理具有多维块的大型数据集。它能够以更细粒度的方式来处理数据,使得libfm能够以块的形式来学习模型参数,提升模型的灵活性...
五、PL/SQL Block Structure PL/SQL块结构包括四部分:Header、Declarative、Executable和Exception。 六、PL/SQL Procedure和Function 1. Procedure是执行一个动作,可以返回一个值。 2. Function是计算一个值,...
2. **块结构(Block Structure)**:DenseNet由一系列的“稠密块”(Dense Block)和“过渡层”(Transition Layer)组成。稠密块内部的每一层都会接收到前面所有层的输出,而过渡层则负责下采样并控制网络的参数...
PL/SQL Block Structure是PL/SQL程序的基础组成部分。一个PL/SQL块由声明部分(Declaring Section)、执行部分(Execution Section)和异常处理部分(Exception Handling Section)组成。声明部分用于定义变量和常量...
图片文件"InnoDB Page Structure.jpg"和"InnoDB Log Block Structure.jpg"可能详细解释了InnoDB的数据页结构和日志块结构,这些都是理解InnoDB性能的关键。InnoDB的页结构包括B+树索引,而日志块结构则与事务的ACID...
此外,它还支持更现代的编程结构,如子程序(Subroutine)、函数(Function)和块结构(Block Structure)。 2. **数据类型**:Fortran 95支持多种数据类型,包括基本类型(如实型、整型、字符型)和复杂类型(如数...
HEVC的一个关键特性是其采用的四叉树分割结构(Quadtree Block Structure)。这一结构允许每个编码单元(CU, Coding Unit)进一步细分为四个子单元,直至最小分割尺寸。这种灵活的块分割方法提高了编码效率,但同时也...
- **5.2 Storage Block Structure**:解释了如何将SILK编码的音频数据块存储在文件中,包括数据块的格式和组织方式。 #### 6. Congestion Control 为了应对网络拥塞问题,SILK采用了先进的拥塞控制算法。这些算法...
- Block Structure (块结构) - Initialization (初始化) - Recursion (递归) - The C Preprocessor (C预处理器) - File Inclusion (文件包含) - Macro Substitution (宏替换) - Conditional Inclusion (条件...