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]  

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

1、math包版本3.6 2、commons-math包解决哪些问题 math包由一组数据和统计的包组成，用于解决列表中列出的问题。列表虽不能覆盖math包全部的功能，但可以基本说明math包所能提供的方法。 计算一组数据的均值、方差，还有其他统计类指标。 使用线性回归将线拟合到一组数据点 将曲线拟合到一组数据点 找到通过点集合的平滑曲线（插值） 使用最小二乘法将参数模型拟合到一组测量 求解涉及实值函数的方程（即根查找） 求解线性方程组 求解常微分方程 最小化多维函数 生成具有比使用JDK的可能性更多的限制（例如分布，范围）的随机数生成跟输入文件中的数据相似的随机样本或数据集 统计检验 其他数学函数如阶乘，二项式系数和“特殊函数”（例如伽马，β函数） 3、commons-math包讲解 org.apache.commons.math3.analysis---根查找，积分，插值，多项式 org.apache.commons.math3.complex---复数 org.apache.commons.math3.dfp---十进制浮点数 org.apache.commons.math3.distribution---概率分布 org.apache.commons.math3.fitting---曲线拟合 org.apache.commons.math3.fraction---有理数 org.apache.commons.math3.genetics---遗传算法 org.apache.commons.math3.geometry---何（欧几里德空间和二进制空间分区） org.apache.commons.math3.linear---矩阵，求解线性系统 org.apache.commons.math3.ml---机器学习 org.apache.commons.math3.ode---普通微分方程积分 org.apache.commons.math3.optim---函数最大化还是最小化 org.apache.commons.math3.random---随机数，字符串和数据生成 org.apache.commons.math3.special---特殊函数（Gamma，Beta） org.apache.commons.math3.stat---统计，统计检验 org.apache.commons.math3.transform---变换（傅立叶） org.apache.commons.math3.util---通用数据或统计函数

这个题目是在一个公司现场面谈的时候的一个题目。虽然对这种找工作上来就做题目的现象比较反感。 但是大环境如此，也只能被蹂躏了。 中文描述 题目要求比较简单：[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[])…

现在找 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]] 这种多层嵌套的问题。 我不认为我的解答是最好的方案，但是至少能够提供一个解题思路吧。

这个题目是 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 *…

中文标题【机器人移动】 这个题目是 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 *…

中文标题【二进制空白】 英文描述 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#。…

描述 给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问） 样例 给一棵二叉树 {3,9,20,#,#,15,7} ： 3 / \ 9 20 / \ 15 7 返回他的分层遍历结果： [ [3], [9,20], [15,7] ] 挑战 挑战1：只使用一个队列去实现它 挑战2：用BFS算法来做 代码 GitHub 的源代码，请访问下面的链接： https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode0069LevelOrderTest.java   package com.ossez.lang.tutorial.tests.lintcode; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import com.ossez.lang.tutorial.models.TreeNode; /** * <p> * 69 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Binary+Tree+Level+Order+Traversal">https://www.cwiki.us/display/ITCLASSIFICATION/Binary+Tree+Level+Order+Traversal</a> * <li>@see<a href= * "https://www.lintcode.com/problem/binary-tree-level-order-traversal">https://www.lintcode.com/problem/binary-tree-level-order-traversal</a> * </ul> * </p> * * @author YuCheng * */ public class LintCode0069LevelOrderTest { private final static Logger logger = LoggerFactory.getLogger(LintCode0069LevelOrderTest.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); String data = "{3,9,20,#,#,15,7}"; TreeNode tn = deserialize(data); System.out.println(levelOrder(tn)); } /** * Deserialize from array to tree * * @param data * @return */ private TreeNode deserialize(String data) { // NULL CHECK if (data.equals("{}")) { return null; } ArrayList<TreeNode> treeList = new ArrayList<TreeNode>(); data = data.replace("{", ""); data = data.replace("}", ""); String[] vals = data.split(","); // INSERT ROOT TreeNode root = new TreeNode(Integer.parseInt(vals[0])); treeList.add(root); int index = 0; boolean isLeftChild = true; for (int i = 1; i < vals.length; i++) { if (!vals[i].equals("#")) { TreeNode node = new TreeNode(Integer.parseInt(vals[i])); if (isLeftChild) { treeList.get(index).left = node; } else { treeList.get(index).right = node; } treeList.add(node); } // LEVEL if (!isLeftChild) { index++; } // MOVE TO RIGHT OR NEXT LEVEL isLeftChild = !isLeftChild; } return root; } private List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> rs = new ArrayList<List<Integer>>(); // NULL CHECK if (root == null) { return rs; } queue.offer(root); while (!queue.isEmpty()) { int length = queue.size(); List<Integer> list = new ArrayList<Integer>(); for (int…

描述 设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。 如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。 对二进制树进行反序列化或序列化的方式没有限制，LintCode将您的serialize输出作为deserialize的输入，它不会检查序列化的结果。 样例 给出一个测试数据样例， 二叉树{3,9,20,#,#,15,7}，表示如下的树结构： 3 / \ 9 20 / \ 15 7 我们的数据是进行 BFS 遍历得到的。当你测试结果 wrong answer时，你可以作为输入调试你的代码。 你可以采用其他的方法进行序列化和反序列化。 代码 GitHub 的源代码，请访问下面的链接： https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode0007SerializeAndDeserialize.java package com.ossez.lang.tutorial.tests.lintcode; import java.util.ArrayList; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import com.ossez.lang.tutorial.models.TreeNode; /** * <p> * 7 * <ul> * <li>@see <a href= * "https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree">https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree</a> * <li>@see<a href= * "https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree">https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree</a> * </ul> * </p> * * @author YuCheng * */ public class LintCode0007SerializeAndDeserialize { private final static Logger logger = LoggerFactory.getLogger(LintCode0007SerializeAndDeserialize.class); /** * */ @Test public void testMain() { logger.debug("BEGIN"); String data = "{3,9,20,#,#,15,7}"; System.out.println(serialize(deserialize(data))); } /** * Deserialize from array to tree * * @param data * @return */ private TreeNode deserialize(String data) { // NULL CHECK if (data.equals("{}")) { return null; } ArrayList<TreeNode> treeList = new ArrayList<TreeNode>(); data = data.replace("{", ""); data = data.replace("}", ""); String[] vals = data.split(","); // INSERT ROOT TreeNode root = new TreeNode(Integer.parseInt(vals[0])); treeList.add(root); int index = 0; boolean isLeftChild = true; for (int i = 1; i < vals.length; i++) { if (!vals[i].equals("#")) { TreeNode node = new TreeNode(Integer.parseInt(vals[i])); if (isLeftChild) { treeList.get(index).left = node; } else { treeList.get(index).right = node; } treeList.add(node); } // LEVEL if (!isLeftChild) { index++; } // MOVE TO RIGHT OR NEXT LEVEL isLeftChild = !isLeftChild; } return root; } /** * * @param root * @return */ public String serialize(TreeNode root) { // write your code here if (root == null) { return "{}"; } ArrayList<TreeNode> queue = new ArrayList<TreeNode>(); queue.add(root); for (int i = 0; i < queue.size(); i++) { TreeNode node = queue.get(i); if (node == null) { continue;…