HoneyMoose
  • 首页
  • Java
  • Jersey
  • Jira
  • Confluence
  • U.S.
    • USRealEstate
    • U.S. Travel
    • H1B
  • 项目和网站
    • CWIKI.US
    • OSSEZ 社区
    • WIKI.OSSEZ.COM
    • BUG.OSSEZ.COM
    • RSS.OSSEZ.COM
BLOG.OSSEZ.COM
A responsive blog theme focused om user reading experience
  1. Home
  2. Computer Science
  3. Algorithm(算法)
  4. This article

Build Castles(构建城堡)

2018年12月29日 531Browse 0Like 0Comments

Charlemagne, the King of Frankie,

英文描述

请参考图片中的说明。

中文描述

根据给出的数组确定能够盖多少城堡。

思路和点评

我不能确定我的思路是正确的,也欢迎大家参与讨论。

根据给出的数组,因为有重复的值,我首先想到的是将给出的数组进行一次过滤和处理,去掉重复的值。

例如,给出的数组为:int[] A = { 2, 2, 3, 4, 3, 3, 2, 2, 1, 1, 2, 5 };,那么我希望处理为:int[] A = { 2, 3, 4, 3, 2, 1, 2, 5 }; 去掉重复的值,因为重复的值在这里没有意义。

然后根据新的数组进行判断,需要判断的是 2 个端点,你需要将 2 个端点考虑为 0。

那么根据上面已经处理过的数组,你在进行遍历的时候,针对第一个值 2 ,你需要判读左侧的值和右侧的值,因为默认左侧的值一直为 0 ,那么右侧的值为 3 的话,那么这里需要 v 需要 +1;

第 2 个值,因为第二个值的左侧,3 > 2, 但右侧 3 < 4。因此这个值不适合。

第 3 个值,左侧:4 > 3, 右侧 4 >3 这个值是合适的。

从这里我们找到的规律是,进行一次遍历,找到,如果只的左侧和右侧同时小于这值,或者左侧和右侧都同时大于这个值,那么这个值是合适的取值。

需要注意一个情况就是 {-3, -3},你初始化数组的时候,这个值为 {-3},那么这个地方是最少有一个合适的值。

源代码

源代码和有关代码的更新请访问 GitHub:

https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/WayfairTest.java

测试类请参考:

https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/WayfairTest.java

代码思路请参考:

/**
   * https://www.cwiki.us/display/ITCLASSIFICATION/Build+Castles
   */
  @Test
  public void testBuildCastles() {

    // int[] A = { -3, -3 };
    int[] A = { 2, 2, 3, 4, 3, 3, 2, 2, 1, 1, 2, 5 };

    int h = 0;
    int v = 0;

    List<Integer> nList = new ArrayList<Integer>();

    // Rebuild List
    nList.add(A[0]);
    for (int i = 0; i < A.length - 1; i++) {

      if (A[i] != A[i + 1]) {
        nList.add(A[i + 1]);
      }

    }

    // LOOP List to find right location
    for (int i = 0; i < nList.size() - 1; i++) {

      // COUNT 0
      if (i == 0) {
        if (nList.get(i) < nList.get(i + 1)) {
          v++;
        }
      } else {
        if (nList.get(i) < nList.get(i - 1) && nList.get(i) < nList.get(i + 1)) {
          v++;
        }

        if (nList.get(i) > nList.get(i - 1) && nList.get(i) > nList.get(i + 1)) {
          h++;
        }
      }
    }

    if (nList.size() == 1) {
      h++;
    } else if (nList.size() > 2 && nList.get(nList.size() - 1) > nList.get(nList.size() - 2)) {
      h++;
    }

    // CHECK
    logger.debug("V - [{}]", v);
    logger.debug("H - [{}]", h);

    logger.debug("H + V - [{}]", (h + v));

  }

 

测试结果

上面程序的测试结果如下:

2018/12/29 00:43:16 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - V - [2]
2018/12/29 00:43:16 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - H - [2]
2018/12/29 00:43:16 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - H + V - [4]
Tags: 算法
Last updated:2018年12月29日

Kratos

stay absorbed stay excellent

Like
< Previous
Next >

Comments

Cancel reply

Newest Hotspots Random
Newest Hotspots Random
Java Optional 初始为空 Java 8 开始新增的 Optional 类 - Optional 对象中的返回 Java 8 开始新增的 Optional 类 - Optional 对象中的异常 Java 8 开始新增的 Optional 类 - Optional 中的方法 Java 8 开始新增的 Optional 类 - 检查 Optional 的值 Java 8 开始新增的 Optional 类 - 创建 Optional 对象
Confluence OGNL 注入漏洞的严重安全问题Java 中的 NaN如何用 Java 判断一个给定的数是不是素数IntelliJ IDEA 如何针对Java 代码快速打印 println是应该是用 Log 还是 Logger 来定义 LogDom4j 如何输出 Document 中的内容到文本
导入 Gradle 项目到 IntelliJ IDEA Intellij 显示树连接线 一个 Confluence 安装实例图例 Hibernate 5 Maven 仓库的 Artifacts IntelliJ IDEA 第一个 Scala 程序 Confluence 6 数据库问题解除
Categories
  • Akka
  • Algorithm(算法)
  • AMQP
  • Angular
  • CI
  • Compile And CI
  • Computer Science
  • Confluence
  • DataBase
  • Gradle
  • H1B
  • Hibernate
  • IDE
  • Java
  • Jersey
  • Jira
  • MariaDB
  • PrestaShop
  • Spring
  • Spring Batch
  • U.S.
  • U.S. Travel
  • USRealEstate
  • 我的小厨

COPYRIGHT © 2020 HoneyMoose. ALL RIGHTS RESERVED.

THEME CWIKIUS.CN MADE BY VTROIS