Tag: algorithm

我们为什么要使用Base64？

维基百科说 Base64编码scheme通常用于需要对需要存储和传输的二进制数据进行编码以处理文本数据的介质。 这是为了确保数据在运输过程中保持完整无需修改。 但是不是数据总是以二进制forms存储/传输，因为我们的机器存储二进制文件的内存，这取决于你如何解释它？ 因此，无论您将位模式010011010110000101101110编码为ASCII为Man还是在Base64中编码为TWFu ，您最终都将存储相同的位模式。 如果最终的编码是以零和1来表示的，而每一台机器和媒体都可以处理这些编码，那么数据是以ASCII还是Base64来表示，怎么样？ 这是什么意思是“旨在处理文本数据的媒体”？ 他们可以处理二进制=>他们可以处理任何事情。 谢谢大家，我想我现在明白了。 当我们发送数据时，我们不能确定数据将被解释为与我们预期的相同的格式。 所以我们发送双方都知道的某种格式的数据（比如Base64）。 这样，即使发送者和接收者以不同的方式解释相同的事物，但是因为他们对编码格式达成一致，数据也不会被错误地解释。 从马克·拜尔例子 如果我想发送 Hello world! 一种方法是像ASCII一样发送它 72 101 108 108 111 10 119 111 114 108 100 33 但是字节10可能不会被正确解释为另一端的换行符。 所以，我们使用ASCII的一个子集来对它进行编码 83 71 86 115 98 71 56 115 67 110 100 118 99 109 120 107 73 61 61 以相同数量的信息传输更多的数据为代价，即使接收者碰巧对字符集的其余部分有不同的解释，也能确保接收者能够以预定的方式解码数据。

克鲁斯卡尔vs Prim

我想知道什么时候应该使用Primalgorithm ，什么时候Kruskalfind最小生成树？ 他们都有简单的逻辑，同样的最坏的情况，只有不同的是可能涉及有点不同的数据结构的实现。 那么决定因素是什么？

树的深度和高度有什么区别？

这是一个来自algorithm理论的简单问题。 它们之间的区别在于，在一种情况下，您可以统计根节点和具体节点之间最短path上的节点数量和其他数量的边界。 哪个是哪个？

如果该行或列包含0，则将matrix中的每个单元格设置为0

给定一个0和1的N×Nmatrix。 将包含0的所有行全部设置为0 ，并将每个包含0列全部设置为0 。 例如 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 结果是 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 […]

如何检查两个列表是否在Python中循环相同

例如，我有名单： a[0] = [1, 1, 1, 0, 0] a[1] = [1, 1, 0, 0, 1] a[2] = [0, 1, 1, 1, 0] # and so on 他们似乎有所不同，但如果假定起始和结束是连接的，那么它们是循环相同的。 问题是，我有一个长度为55的列表，每个列表只包含三个和52个零。 没有循环条件，有26,235（55选3）名单。 但是，如果条件“循环”存在，则有大量循环相同的列表 目前我通过以下方式查看循环身份： def is_dup(a, b): for i in range(len(a)): if a == list(numpy.roll(b, i)): # shift b circularly by i return True return False 该function在最坏的情况下需要55次循环移位操作。 有26,235个名单可以相互比较。 […]

从一个集合中挑选一个随机元素

我如何从一组中随机select一个元素？ 我特别感兴趣的是从Java中的HashSet或LinkedHashSet中select一个随机元素。 其他语言的解决scheme也是受欢迎的。

地图拼贴algorithm

地图 我正在用Javascript制作一个基于图块的RPG游戏，使用perlin noise heightmaps，然后根据噪音的高度分配一个图块types。 地图最终看起来像这样（在小地图视图）。 我有一个相当简单的algorithm，它提取图像上的每个像素的颜色值，并根据其对应于平铺字典中的平铺的（0-255）之间的位置将其转换为整数（0-5）。 然后这个200×200数组传递给客户端。 然后，引擎根据数组中的值确定拼贴，并将其绘制到canvas上。 所以，我最终会看到有趣的世界，这些世界具有逼真的外表特征：山脉，海洋等 现在接下来我要做的是应用某种混合algorithm， 如果邻居不是同一types的话 ，就会导致图块无缝融合到邻居中。 上面的示例地图是玩家在小地图中看到的。 在屏幕上，他们看到由白色矩形标记的部分的渲染版本; 其中瓷砖是与他们的图像，而不是单一的彩色像素呈现。 这是用户在地图上看到的示例，但与上面显示的视口不同。 正是在这种观点下，我希望过渡发生。 algorithm 我想出了一个简单的algorithm，它将遍历视口内的地图，并在每个图块的顶部渲染另一个图像，并将其提供给不同types的图块。 （不改变地图！只是渲染一些额外的图像。）algorithm的想法是分析当前瓦片的邻居： 这是引擎可能需要渲染的一个示例场景，当前的tile是用X标记的。 一个3×3数组被创build，并且它周围的值被读入。所以对于这个例子，数组看起来像。 [ [1,2,2] [1,2,2] [1,1,2] ]; 然后，我的想法是为可能的瓷砖configuration制定一系列案例。 在一个非常简单的层面上： if(profile[0][1] != profile[1][1]){ //draw a tile which is half sand and half transparent //Over the current tile -> profile[1][1] … } 这给出了这个结果： 它从[0][1]到[1][1] ，但不是从[1][1]到[2][1]的过渡，其中硬边缘仍然存在。 所以我想，在这种情况下，一个angular落瓦片将不得不被使用。 我创build了两个3×3的精灵图表，我认为这些图表将会包含所有可能需要的图块组合。 […]

把猫扔出窗外

想象一下，你正在一座带猫的高层build筑里。 猫可以从低矮的窗户里摔下来，但是如果从高处落下，它将会死亡。 如何用最less的尝试次数找出猫能够存活的最长时间？ 显然，如果你只有一只猫，那么你只能线性search。 先从一楼扔掉猫。 如果它幸存下来，从第二个扔掉。 最后，从地板f扔掉后，猫会死亡。 然后你知道f-1楼是最大的安全楼层。 但是如果你有一只以上的猫呢？ 你现在可以尝试某种对数search。 假设这个build筑有100层，你有两个相同的猫。 如果你把第一只猫从第50层扔出去，那么你只需要线性search50层。 如果您首次尝试select较低的楼层，则可以做得更好。 假设您select一次处理20个楼层的问题，而第一个致命楼层是＃50。 在那种情况下，你的第一只猫在从第60层死亡之前将从第20层和第40层的飞行中幸存下来。你只需要单独检查第41层到第49层。 总共有12次尝试，比你试图使用二进制消除时需要的50次要好得多。 一般来说，最好的策略是什么，对于有两只猫的n层build筑来说，这是最糟糕的复杂性？ 那么n层和m猫呢？ 假设所有的猫都是相同的：它们都会从某个窗口的落下中生存或死亡。 而且，每一次尝试都是独立的，如果一只猫幸免于难，完全没有受到伤害。 这不是家庭作业，虽然我可能一旦解决了它的学校作业。 这只是一个突发奇想的问题，我今天突然想起，我不记得解决scheme。 如果有人知道这个问题或解决schemealgorithm的名称，奖励点。

给定一组数字，返回所有其他数字的产品数组（无分区）

在面试中我被问到了这个问题，我想知道别人怎么解决这个问题。 我对Java非常满意，但是欢迎使用其他语言的解决scheme。 给定一组数字num，返回数组products ，其中products[i]是所有nums[j], j != i的乘积。 Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] 你必须在O(N)做这个，而不使用划分。

为什么在计算数组的中间值时比较喜欢start +（end – start）/ 2 over（start + end）/ 2？

我见过程序员使用公式 mid = start + (end – start) / 2 而不是使用更简单的公式 mid = (start + end) / 2 用于查找数组或列表中的中间元素。 为什么他们使用前者？