CWIKIUS
  • 首页
  • 计算科学
  • 房地产
  • 文化旅游
  • 项目和网站
    • OSSEZ 计算技术
    • USRealEstate 社区
    • 地区文化
    • CWIKI.US
    • BUG.OSSEZ.COM
    • RSS.OSSEZ.COM
Algorithm(算法)
Algorithm(算法)
Algorithm(算法)

Minimum Coins(找到最小数量的硬币)

中文标题【找到最小数量的硬币】 题目的要求比较简单,要求找到最小数量的硬币。 给定的硬币数量是 1,3, 5 英文描述 英文题目的要求请参考下图: 中文描述 主要要求是你手上已经有 1,3,5 面值的硬币。 在给定金额情况下,找到最少需要多少个硬币能够等于给定的价值。 思路和点评 这个算法的主要目的是利用你已有的面值,主要考察你对除法中的除数和余数的理解和如何利用这 2 个数值进行计算。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/others/MinimumCoinsTest.java   https://www.ossez.com/t/minimum-coins/318

2020年07月25日 0Comments 454Browse 0Like Read more
Algorithm(算法)

Lambda Evens(Lambda 偶数)

英文题目 题目的英文表述成参考:   中文描述 题目要求比较简单,使用 Lambda 表达式写一个函数,找到给出字符串中的偶数。 思路点评 你需要对 Lambda 表达式比较熟悉,需要知道 Lambda 是什么。在 Java 世界中,Lambda 是在 Java 8 中引进的一个表达式。属于函数式。 近来也用得越来越多,最好对 Lambda 有所了解。 同时,你还要有基本的Java 字符拆分 API 的了解。很多题目可能不能允许你用第三方 API,所以你需要了解 String.split 有关的算法。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/others/LambdaEvensTest.java https://www.ossez.com/t/lambda-evens-lambda/317

2020年07月25日 0Comments 415Browse 0Like Read more
Algorithm(算法)

下一个斐波拉契数列

Write a program that takes input of integer N, followed by N more integers. For each integer, output the next fibonacci number after it. Fibonacci number: Any number that belongs to the fibonacci series. Constraints: Your program should run correctly for the first 69 Fibonacci numbers. Your output lines should not have any trailing or leading whitespace. Input 3 1 9 22 Output 2 13 34   Explanation: 2 is the next fibonacci number greater than 1, the fibonacci number that comes after 9 is 13. 34 is the next fibonacci number after 22. 英文描述 英文描述请参考下面的图。 中文描述 根据给定的值,返回这个值后面的下一个斐波拉契数列中的下一个数。 在斐波拉契数列中存储 60 个 斐波拉契数。 例如,给定整数 1,那么应该返回的结果是 2 。因为给定整数 1 后面的下一个斐波拉契数是 2。 如果给定的数值是 9 的话,那么下一个斐波拉契数应该是 13。 斐波拉契数列又译为菲波拿契数列、菲波那西数列、斐波那契数列、黄金分割数列。 用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的数列A000045) 思路和点评 首先计算斐波拉契数列,然后将数值存储到数组中。 定义一个数组,在这个数组中先存储 60 个从小到大的斐波拉契数。 然后将给定的数值与数值中存储的斐波拉契数进行对比,这个时候你需要对数组中的斐波拉契数进行遍历。当找到大于当前给定的整数以后,可以 Break 这次比对并且返回(输出)这个值。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/main/java/com/ossez/codebank/interview/ManNextFibonacciNumber.java 运行建议: 这个方法因为测试平台的问题,我们没有写到测试类中。我们是直接定义了一个可以运行的类。 你可以在你的 Eclipse 平台上,直接运行这个类。 在你运行类以后的 Console 控制台窗口,你首先需要输入数字 3 ,这个数字 3 表示这次运行你需要进行 3 次测试。 然后输入测试数字,例如,你可以输入测试数字 1,那么,程序将会输出 1 Next Fibonacci [2]。 这个与实际题目要求的有所差异,你需要进行调整,而且题目是需要使用 System.out.println 输出的,请注意我们在我们的源程序中注释掉了这个输出。 代码思路请参考: package com.ossez.codebank.interview; import java.io.BufferedReader; import java.io.InputStreamReader; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /**  *  * https://www.cwiki.us/display/ITCLASSIFICATION/Next+Fibonacci+Number  *  * @author YuCheng  *  */ public class ManNextFibonacciNumber {     private final static Logger logger = LoggerFactory.getLogger(ManNextFibonacciNumber.class);     public static void main(String[] args) throws java.lang.Exception {         int fArray[] = new int[60];         for (int i = 0; i < 60; i++) {             fArray[i] = getFib(i);         }         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String input = br.readLine();         // System.out.println(fib(Integer.valueOf(input)));         for (int i = 0; i < Integer.valueOf(input); i++) {             Integer inputInt = Integer.valueOf(br.readLine());             // System.out.println(inputInt);             for (int j = 0; j < fArray.length; j++) {                 if (fArray[j] > inputInt) {                     // System.out.println(fArray[j]);                     logger.debug("{} Next Fibonacci [{}]", inputInt, fArray[j]);                     break;                 }             }         }     }     /**      * Get Fibonacci Number      *      * @param n      * @return      */     private static int getFib(int n) {         if (n < 0) {             return -1;         } else if (n == 0) {             return 0;         } else if (n == 1 || n == 2) {             return 1;…

2019年02月09日 0Comments 498Browse 0Like Read more
Algorithm(算法)

Binomial Coefficient(二项式系数)

In mathematics, any of the positive integers that occurs as a coefficient in the binomial theorem is a binomial coefficient. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written {\displaystyle {\tbinom {n}{k}}.} {\displaystyle {\tbinom {n}{k}}.} It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and it is given by the formula. 英文描述 英文描述请参考下面的图。 中文描述 根据给定的公式计算二项式的值。 在这里有一个说明需要注意的是,如果结果超过 1,000,000,000 你的程序应该返回 -1。 如果结果没有定义的话,那么你的程序应该也要返回 -1。 思路和点评 在这里的计算,公式比较简单,就是计算 N,K N-K 的阶乘,在阶乘中,你可以使用递归进行计算。 但是需要注意的是对这个数字的阶乘计算量,程序是很容易溢出的,如果从出题者的意图来看就是要考察大数值的计算和计算中的溢出。 如果你使用的是 Java 的话,你应该使用类 BigDecimal,进行计算。如果你可以使用 Apache Common Math 的话,你就直接使用 CombinatoricsUtils.factorialDouble 进行计算。在计算中允许的最大参数值为 170,超过这个值以后就超过程序能够计算的最大值了。 如果你希望直接计算二项式系数的话,你可以使用 CombinatoricsUtils.binomialCoefficientDouble(40, 20) 直接进行计算。 源代码 源代码和有关代码的更新请访问 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/Binomial+Coefficient * * Binomial Coefficient */ @Test public void testBinomialCoefficient() { int n = 40; int k = 20; BigDecimal bc = factorial(n).divide(factorial(k).multiply(factorial(n - k))); // a.compareTo(new BigDecimal(1000000000)) logger.debug("{}", bc); logger.debug("Check for Compare To - [{}]", bc.compareTo(new BigDecimal(1000000000))); logger.debug("Value - [{}]", bc); logger.debug("Apache CombinatoricsUtils Factorial - [{}]", CombinatoricsUtils.factorialDouble(20)); logger.debug("Apache CombinatoricsUtils Binomial Coefficient - [{}]", CombinatoricsUtils.binomialCoefficientDouble(40, 20)); } /** * for factorial * * @param x * @return */ private static BigDecimal factorial(int x) { if (x == 1 || x == 0) { return BigDecimal.valueOf(1); } else { return BigDecimal.valueOf(x).multiply(factorial(x - 1)); } }   测试结果 上面程序的测试结果如下: 2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - 137846528820 2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Check for Compare To - [1] 2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Value - [137846528820] 2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Apache CombinatoricsUtils Factorial - [2.43290200817664E18] 2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Apache CombinatoricsUtils Binomial Coefficient - [1.3784652882E11]  

2018年12月29日 0Comments 605Browse 0Like Read more
Algorithm(算法)

Build Castles(构建城堡)

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 -…

2018年12月29日 0Comments 528Browse 0Like Read more
Algorithm(算法)

Flatten Nested Arrays(展平嵌套数组)

这个题目是在一个公司现场面谈的时候的一个题目。虽然对这种找工作上来就做题目的现象比较反感。 但是大环境如此,也只能被蹂躏了。 中文描述 题目要求比较简单:[1,2,[3],[[4]],5,6] -> [1,2,3,4,5,6] 就是数组中嵌套数组,考察一个数组[1,2,[3],[[4]],5,6]。 你怎么能够输出 1,2,3,4,5,6(并不要求按照顺序输出)。 这里是一个嵌套数组,你需要将这个数组中的值全部取出来。 思路和点评 不清楚其他语言中这个数据结构怎么存储,我假设的是在 Java 中存储的对象。 可以采用队列的方式来实现,例如,在 Java 中存储了整数,1, 2, 对象,[3] 为一个数组对象。 你可以先遍历一次 List,将所有的 List 的对象都压入队列中,然后进行出队。 在出队时候,判断对象是否为整数对象,如果是整数对象,就输出,如果不是整数对象,然后将数组对象继续进行遍历,然后压入队列,然后再出队。 在这里讨论的问题比较多,还有 [[[2]5]] 这种多层嵌套的问题。 经过网站上的考古,这里有 2 个方法可以更快的实现。1 是递归的方法,2 是 利用 Java 8 的 Stream 特性。 在写测试代码之前,你需要明白下数据结构的定义,要不然你没有办法测试。在 Java 中你可以定义为对象数组,如下: Object[] array = { 1, 2, new Object[] { 3, 4, new Object[] { 5, new Object[] { new Object[] { 6 } } }, 7 }, 8, 9, 10 }; 然后可以利用递归,在对对象数组进行遍历的时候,如果你遇到了对象,那么你需要再次调用你的方法,对对象中的内容进行遍历,如果这个时候已经没有对象了,可以返回第二层遍历的结果,并且插入到上层 List 列表中。 如果你使用的 Java 8 的 Stream,你需要对 Stream 的使用和方法比较了解才可以。这里也涉及到了递归,只是写法有点不同罢了。 还有一个更加简单粗暴的方法,当然我不认为这个方法是出题人希望考察的目标,在 Java 中你可以将数组直接转换成 String 字符串进行输出,比如说上面的对象队列,你可以转换为: [1, 2, [3, 4, [5, [[6]]], 7], 8, 9, 10]  字符串进行输出,然后使用 Java 的 Split 函数,进行按照逗号拆分后,然后将多余 [ 和 ] 符号去掉,然后再将内容重新放回 List。 这个有点简单粗暴,但是也一样能够达到目的。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/PillPackTest.java 测试类请参考: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/PillPackTest.java 代码思路请参考: package com.ossez.codebank.interview.tests; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.stream.Stream; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * PillPack * * <pre> * https://www.cwiki.us/display/ITCLASSIFICATION/Flatten+Nested+Arrays * </pre> * * @author YuCheng * */ public class PillPackTest { private final static Logger logger = LoggerFactory.getLogger(PillPackTest.class); List<Integer> returnList = new ArrayList<Integer>(); /** * https://www.cwiki.us/display/ITCLASSIFICATION/Flatten+Nested+Arrays * * FlattenNestedArrays */ @Test public void testFlattenNestedArrays() { logger.debug("Test FlattenNestedArrays"); Object[] array = { 1, 2, new Object[] { 3, 4, new Object[] { 5, new Object[] { new Object[] { 6 } } }, 7 }, 8, 9, 10 }; logger.debug("LOOP: {} - > {}", Arrays.deepToString(array), Arrays.toString(loopFlatten(array))); logger.debug("Java 8: {} - > {}", Arrays.deepToString(array), Arrays.toString(java8Flatten(array).toArray())); } /** * Loop And Recursive * * @param inputArray * @return * @throws IllegalArgumentException */ private static Integer[] loopFlatten(Object[] inputArray) throws IllegalArgumentException { // NULL CHECK if (inputArray == null) return null; List<Integer> flatList = new ArrayList<Integer>(); for (Object element : inputArray) { if (element instanceof Integer) { flatList.add((Integer) element); } else if (element instanceof Object[]) { // Recursive flatList.addAll(Arrays.asList(loopFlatten((Object[])…

2018年12月27日 0Comments 610Browse 0Like Read more
Algorithm(算法)

PillPack Onsite 5 个小时

现在找 OnSite 面试时间都这么长了吗? 经历几次都是 5 - 6 个小时的。不多废话,PillPack 的面谈内容吧。 本人主要是 Java ,他们招聘的岗位说是 Sr Developer and Manager。在面试进行到 3 个小时的时候,他们突然提出了使用的技术栈不是 Java,他们使用的 Ruby and Rails。当时就蒙圈了,折腾了 4 个多小时讨论的完全不是一个技术栈的东西,虽然本人并不拒绝学习,但是这个差得还是有点远。 他们希望构建新的 API 系统和相关平台。本人只有 Jersey 的经验,只能拿 Java 掰了。 下面是完全的面试过程: 第一轮:介绍公司概况,这个也没啥说的,就是公司的大致架构,产品线。因为是新成立的公司,公司的面试说是 Amazon 组织负责的,但是感觉和 Amazon 关系不大。可能 Amazon 从面试中要获得一些反馈吧。至于面试结果,他们只会告诉你给你 Offer 或者不给。不会给你面试的评价和问题。这个在这里就明确表达清楚了。 第二轮:算法和介绍。这里不要求你写出实际的代码,题目是俄罗斯方块,你怎么用数据模型表示。 在这里,我采取的方法是先定义可能出现的各种可能性,使用的是 二维数组。 在这里需要定义一个功能就是翻转,有些下落的方块可能会出现翻转成不同的形状,那么你定义列表就变了。 所有可能的情况,我会存储到一个 HashMap 中,Key 使用的是 1@1,Value 存储的是二维数组。如果 1@1 翻转后还有其他图形的话,你可以在存储一个 key 1@2 ,这个表示翻转以后的情况。当然这个可能不是最优的情况。 后面,我需要一个List,这个 List 中存储了 10 列的 List。在这里你需要根据 Map 中存储的二维数组,下落后插入到 List 中。 在插入完成后,遍历上层 List 确定所有的子 List 中有值 1 ,以便于消除。 第三轮:让你设计一个 POST 和 评论 点赞的平台,并且根据你的设计,设计一个 API 这个应该来说还是不是很复杂的,主要是你数据库中表格怎么设计,在评论载入的时候,会有评论嵌套评论的方式,你可能在设计表的时候要设计一个主重键。 基本上来说,这个就是数据库的设计,API 很多时候还是根据你数据结构进行数据调用的,基本上数据库设计好了,API 和 UI 怎么设计都没有什么太多问题。 这里我就基本上按照通用的设计方式设计表就 OK 了。 第四轮:职场行为交谈 一个小姑娘,主要询问下你在职场中人和人怎么相处。你有什么值得介绍的。如果和同事冲突了怎么办,你是否和同事冲突过,这些问题。并且希望你能够具体举例说明下你遇到的问题。这个只要是正常的都应该不会有太多问题的。 第五轮:雇用经理 在这里的问题比较多。同时他也问了一个算法题,就是数组中嵌套数组,考察一个数组[1,2,[3],[[4]],5,6]。 你怎么能够输出 1,2,3,4,5,6(并不要求按照顺序输出)。 不清楚其他语言中这个数据结构怎么存储,我假设的是在 Java 中存储的对象。 可以采用队列的方式来实现,例如,在 Java 中存储了整数,1, 2, 对象,[3] 为一个数组对象。 你可以先遍历一次 List,将所有的 List 的对象都压入队列中,然后进行出队。 在出队时候,判断对象是否为整数对象,如果是整数对象,就输出,如果不是整数对象,然后将数组对象继续进行遍历,然后压入队列,然后再出队。 在这里讨论的问题比较多,还有 [[[2]5]] 这种多层嵌套的问题。 我不认为我的解答是最好的方案,但是至少能够提供一个解题思路吧。

2018年12月26日 0Comments 523Browse 0Like Read more
Algorithm(算法)

Count Up Down(上下计数)

这个题目是 Kayak 发布的代码挑战题目。 最简单的描述就是不使用循环,输出 0 到 5,然后同样不是会用循环的方式再次输出 5 到 0。 英文描述 Part 1 Write a program that counts in sequential order when given a start and end value - without using any iterative programing loops, i.e. while, for, do, for-each, etc. You can assume that both the start and end values will always be positive and that the start value will always be less then the end value. There should only be one method with the following signature: void countUp(int start, int end) { // All code exercise code should go here } Here is example output with start=0 and end=5: [ 0,1,2,3,4,5] Part 2 Continuing with part 1 change the output of the test, so that it now prints out in sequential order to the end value (only once), but then also counts down to the start value. Again, using no iterative loops, and assuming that both the start and end values will always be positive and that start value will always be less then the end value. There should only be one method with the following signature: void countUpAndDown(int start, int end) { // All code exercise code should go here } Here is example output with start=0 and end=5: [0,1,2,3,4,5,4,3,2,1,0] 中文描述 这里我不按照原文一字一字的翻译,但是尽量按照题目的要求把题目解释清楚。 最简单的描述就是不使用循环,输出 0 到 5,然后同样不是会用循环的方式再次输出 5 到 0。 本题目分 2 部分,第一部分是不使用循环的方式输出 0 到 5,第二部分是不使用循环的方式输出 0 到 5 以后,再输出 5 到 0。 其中需要注意的是 5 只能输出一次。 思路和点评 不使用 For 循环的方式输出 0 到 5 ,我们可以想到有几个方法。 第一个方法可能比较容易想到的就是递归调用,你可以根据输入的值,递归调用需要的次数就可以输出值了。你还可以采用计算机时钟的方式进行输出。 在这里我们采用递归调用的方式进行输出。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/main/java/com/ossez/codebank/interview/KayakCountUpDown.java 测试类请参考: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/KayakTest.java 代码思路请参考: package com.ossez.codebank.interview; import java.util.ArrayList; import java.util.List; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * * https://www.cwiki.us/display/ITCLASSIFICATION/Count+Up+Down *…

2018年12月25日 0Comments 599Browse 0Like Read more
Algorithm(算法)

Robot Movement(机器人移动)

中文标题【机器人移动】 这个题目是 Kayak 发布的代码挑战题目。 我认为题目本身描述的不是十分清楚,方法需要返回结果,但是结果没有说明是机器人最后的坐标位置,还是最后的坐标位置距离原点的距离。同时,机器人的初始化方向等都没有十分明确的定义。 根据测试数据,机器人应该是从下往上(初始化的方向)。因为如果初始化的方向不确定的话,最后的坐标值可能会不一致。 我这里假设程序应该返回的是机器人的最后坐标位置,并且初始化的位置为 (0,0),方向为从下往上。 英文描述 A robot lands on Mars, which happens to be a cartesian grid; assuming that we hand the robot these instructions, such as LFFFRFFFRRFFF, where "L" is a "turn 90 degrees left", "R" is a "turn 90 degrees right", and "F" is "go forward one space。 please write control code for the robot such that it ends up at the appropriate-and-correct destination, and include unit tests. Here is an example output with command "FF": [0, 2] 中文描述 这里我不按照原文一字一字的翻译,但是尽量按照题目的要求把题目解释清楚。 这里题目的要求是,假设一个机器人降落到火星上了,我们现在需要给机器人发布指令。指令包括有 L,R,F 3 个。 L 表示的意思是机器人向左转 90 度,R 的意思表示的是机器人向右转 90 度,F 表示的是机器人向前移动一个坐标单位。 题目的表达并是是十分明确也清晰,比如说 LFFFRFFFRRFFF 应该返回是什么没有说清楚。假设 指令 FF ,返回的结果是 [0, 2],我默认的是程序需要返回机器人最后的坐标位置,0 表示的是 X 坐标,2 表示的是 Y 坐标。 思路和点评 这个问题的思路,首先你需要明白几个点。如果需要进行坐标计算的话,请注意 L 和 F 是不会改变当前机器人的坐标位置的。 只有 F 的操作才会改变机器人的位置。考虑设置一个坐标系,那么这里需要存储 2 个信息,第一个信息为 F 移动时候机器人的位置,另外就是 L 和 F 对机器人方向的控制了。 所以你需要在程序中初始化一个二维数组,这个数组用于存储 F 操作时候的坐标变化。 同时你还需要存储一个 dir 变量,通常这个变量为每一次 L 和 R 操作的时候方向的变化。 F 存储的路径数组为:int[][] move = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 通过这个数组,你就明白为什么我在这个 WIKI 页面前面说的,初始化方向很重要,请参考下面的图(因为不太好用计算机画图,我们用手画了一个图)。 在这个图中比较明确的说明了,我们定义的初始化方向为从下往上,Dir 等于 0 。在 Dir 等于 0 的时候坐标数组为 int[][] move = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 按照顺时针的方向。 在图中,Dir 有 4 个反向,按照顺时针方向,分别为上,右,下,左,那么方向对应的值就分别为 0,1,2,3 。 当方向为 L 的时候,需要将方向值减 1 ,当方向为 R 的时候,需要将值 +1。 这里有个问题为循环,比如说,方向值为 RR,,dir 的值应该为 2。 如果方向为 RRRRRR,那么值应该也为 2。所以在算法中我们使用了  dir = (dir + 4) % 4;, 对方向进行取 余数。你可以看到 当你旋转 RRRRRR 后,dir 的值还是为 2。 针一次转向 + 移动的操作,不管你转向多少次,调整的方方向无非就是调整 X 或者 Y 的坐标系,在下一次移动的时候应该是 + 还是 - 所以到这里方法就相对简单了。一次移动的时候,都会改变 X 和 Y 坐标的值,前提是你是希望怎么加减而已。 源代码 源代码和有关代码的更新请访问 GitHub: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/main/java/com/ossez/codebank/interview/KayakRobotMovement.java 测试类请参考: https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/KayakTest.java 代码思路请参考: package com.ossez.codebank.interview; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * https://www.cwiki.us/display/ITCLASSIFICATION/Robot+Movement * * @author YuCheng *…

2018年12月25日 0Comments 585Browse 0Like Read more
Algorithm(算法)

Binary Gap(二进制空白)

中文标题【二进制空白】 英文描述 A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps. Write a function: class Solution { public int solution(int N); } that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap. For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps. Write an efficient algorithm for the following assumptions: N is an integer within the range [1..2,147,483,647]. 中文描述 这里我不按照原文一字一字的翻译,但是尽量按照题目的要求把题目解释清楚。 这里题目的要求是,将 N 为一个整数类型的数据,转换为一个 2 进制的字符串,然后在返回的字符串中返回最大的 0 的间隔数字。 例如 529 转换为 2 进制的字符串为:1000010001,在这里,将会存在以 1 为分割的字符串  0000 和 000,这 2 个字符串的长度分别为 4 和 3。 我们的算法需要返回的值诶 4。 思路和点评 这个题目的思路其实比较简单,你需要首先将 N 这个整数,转换为 0 和 1 的字符串。然后在转换成功的字符串中返回以 1 分分割的 0 的长度。 这里可能需要考虑下面的几种情况。 情况 结果 11 这个情况应该返回的长度为 0 10 这个情况因为没有被 1 这个字符串封闭,因此应该返回长度为 0 传统的思路应该是采取字符串分割的方式,进行遍历后获得结果。 我们在这里采取一种相对不是非常常规的方式,例如在 10000010001 字符串中插入 #,将字符串变为 #1#00000#1#000#1#。…

2018年12月23日 0Comments 538Browse 0Like Read more
123
Categories
  • Algorithm(算法)
  • AMQP
  • Angular
  • CI
  • Compile And CI
  • Computer Science
  • Confluence
  • DataBase
  • Gradle
  • Hibernate
  • IDE
  • Java
  • Jersey
  • Jira
  • MariaDB
  • PrestaShop
  • Spring
  • Spring Batch
  • U.S.
  • U.S. Travel
  • USRealEstate
  • VisaFn

COPYRIGHT © 2020 CWIKIUS. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

湘ICP备2020018253号-1