标签: puzzle

最近,我在接受采访时遇到了以下问题.最初我认为这个问题是错的,但面试官提到有一个解决方案.鉴于此类:

public class BaseHome
{
    public static void Main()
    {
        Console.WriteLine("A");
    }
}

将以下内容写入控制台:

B
A
C

规则:

1. 请勿更改主要功能.
2. 不要创建任何其他类.

如何才能做到这一点？

我找到了一个有一些复杂的C拼图的网站.现在我正在处理这个问题:

以下是一段C代码,其目的是打印减号20次.但你可以注意到,它不起作用.

#include <stdio.h>
int main()
{
    int i;
    int n = 20;
    for( i = 0; i < n; i-- )
        printf("-");
    return 0;
}

Run Code Online (Sandbox Code Playgroud)

修好上面的代码很简单.要使问题变得有趣,您必须通过更改一个字符来修复上述代码.有三种已知的解决方案.看看你能不能得到这三个.

我无法弄清楚如何解决.我知道它可以通过改变--来修复++,但我无法弄清楚要改变哪个单个字符才能使它工作.

如果变量的值x最初为0,则表达式x += x += 1将在C中计算为2,在Javascript中计算为1.

C的语义对我来说似乎很明显:x += x += 1被解释为x += (x += 1)反过来相当于

x += 1
x += x  // where x is 1 at this point

Javascript解释背后的逻辑是什么？什么规范强制执行这种行为？(顺便说一句,应该注意Java在这里与Javascript一致).

更新: 事实证明,x += x += 1根据C标准,表达式具有未定义的行为(感谢ouah,John Bode,DarkDust,Drew Dormann),这似乎破坏了一些读者的问题的全部要点.通过在其中插入标识函数,可以使表达式符合标准:x += id(x += 1).可以对Javascript代码进行相同的修改,问题仍然如所述.假设大多数读者能够理解"非标准兼容"制定背后的观点,我会保留它,因为它更简洁.

更新2:事实证明,根据C99,身份函数的引入可能无法解决模糊性.在这种情况下,亲爱的读者,请将原始问题视为与C++而不是C99有关,其中"+ ="现在可能最安全地被视为具有唯一定义的操作序列的可重载运算符.也就是说,x += x += 1现在相当于operator+=(x, operator+=(x, 1)).对于通向标准的漫长道路感到抱歉.

嘿,这是星期五下午,让我们有一个有趣的拼图/算法问题来解决.

我最喜欢的任天堂DS游戏之一是Picross DS.游戏很简单,它涉及解决称为Nonograms的谜题.您可以在这里尝试一个简单的在线Picross克隆:TylerK的Picross.

非图是网格,为网格的每一行和每列定义数字序列.这些数字定义了该行/列的"填充"方块的块,但未定义块两侧的未填充区域.例如,如果您有一行如下所示:

http://steam-punk.net/images/picross1.jpg

该行的可能解决方案包括:

http://steam-punk.net/images/picross2.jpg http://steam-punk.net/images/picross3.jpg

等等

"4 5"只是告诉你,在行的某个地方,填充了4个连续的块,然后填充了5个连续的块.这些块将是填充的唯一块,并且它们之前/之后的空间量是没有定义的.

当所有行和列符合其定义时,拼图就完成了,没有任何矛盾.

概念上非常简单的游戏,但手动解决其中一些可能需要一段时间.Picross DS的谜题逐渐增加到25x20网格,这通常需要我花半个小时来解决.

但是,我总是想到编写一个程序来解决它是一个非常简单的游戏.我从未接触过它,但也许这里的一些人会喜欢这个挑战.如果发布了相当数量的解决方案,我会将它们作为一个大型拼图相互比较,类似于Paolo Bergantino在这里用他的Boggle问题做的.如果你想参考,那么在Nonogram Wikipedia页面上有很多关于攻击谜题的方法的信息.

这是TylerK的Picross中拼图#1的一个易于解析的定义,所以你可以为程序提供一些东西.第1行是拼图维度(可能是不必要的),第2行是行定义,第3行是列定义.这只是我想到的第一件事,所以如果有人能想到更好的输入格式,请随意评论或编辑这篇文章以包含它.

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 …

这种通用库方法的最佳实现是什么？

public static <K, V> boolean containsEntry(
    Map<K, V> map, K key, V value) {}

与大多数编码难题一样,判断此谜题的标准依次为:

1. 完整性
2. 正确性
3. 性能
4. 美女
5. 收到PayPal捐款

编辑:

好吧,既然关闭了,我不妨发布答案.我认为这可能是最佳的:

  V valueForKey = map.get(key);
  return (valueForKey == null)
      ? value == null && map.containsKey(key)
      : valueForKey.equals(value);

一个聪明的简单解决方案是:

  return map.entrySet().contains(
      new AbstractMap.SimpleImmutableEntry<K, V>(key, value));

它确实分配了一个实例,但它为地图实现提供了更多机会来做一些最佳的事情.

在此早期的问题中,OP询问了以下问题:

给定一个矩形网格,其中一些正方形是空的,有些正方形被填充,可以放入世界的最大数量的2x1多米诺骨牌是这样的,没有两个多米诺骨牌重叠,没有多米诺骨牌在填充的正方形上面？

(相当漂亮!)这个问题的答案认识到这相当于在特殊构造的图中找到最大的二分匹配.在此图中,每个空方块都有一个节点,该节点通过边链接到每个邻居.然后,每个多米诺骨牌对应于图中的边缘,使得其端点不被任何其他边缘覆盖.因此,不共享顶点(匹配)的任何边缘集合对应于多米诺骨牌的排列,反之亦然.

我的问题是对前一个问题的概括:

给定一个矩形网格,其中一些正方形是空的而一些是填充的,那么可以放入世界的M x N多米诺骨牌(对于给定的M和N)的最大数量是这样的,没有两个多米诺骨牌重叠并且没有多米诺骨牌在顶上一个满满的广场？

我无法看到如何将其转换为匹配问题,如前一种情况所做的那样.但是,我也没有看到为什么这个问题会立即成为NP难的特殊原因,因此可能存在一个多项式时间解决问题的方法.

有没有一种有效的算法来解决这个问题？或者是否有人有减少表明这个问题是NP难？

非常感谢!

我的女朋友在接受采访时得到了这个问题,我非常喜欢它,我以为我会分享它......写一个接收字典的算法(字数组).数组按字典顺序排序,但abc顺序可以是任何内容.例如,它可以是z,y,x,..,c,b,a.或者它可能完全搞砸了:d,g,w,y,......它甚至不需要包含所有的abc字母,最后它根本不必是字母.它可以是形成字符串的任何符号.例如,它可以由5,？,!,@,？组成......你明白了.由您的算法决定发现字母是什么(简单部分).

算法应返回符号的正确词典顺序.

注意事项/需要考虑的事项:1.对于给定的字典,您是否总能发现所有字母的完整顺序？考虑一个只有1个单词,多于1个符号的字典...... 2.你不能认为字典是没有错误的.该算法应确定字典是否包含矛盾并输出存在错误.3.提示:想一个好的数据结构来表示你在符号之间发现的关系.这应该使问题更容易.

我明天可能会发布我的解决方案.我绝不会声称它是最有效的.我想先看看其他人的想法.希望你喜欢这个问题

PS我认为发布解决方案的最佳格式是使用伪代码,但我将此留待您考虑

我想把这个挑战引起stackoverflow社区的注意.原始问题和答案在这里.顺便说一句,如果你之前没有按照它,你应该尝试阅读Eric的博客,这是纯粹的智慧.

摘要:

编写一个带有非null IEnumerable的函数,并返回一个具有以下特征的字符串:

1. 如果序列为空,则生成的字符串为"{}".
2. 如果序列是单个项"ABC",则结果字符串是"{ABC}".
3. 如果序列是两个项目序列"ABC","DEF",则结果字符串是"{ABC和DEF}".
4. 如果序列具有两个以上的项目,例如"ABC","DEF","G","H",则结果字符串为"{ABC,DEF,G和H}".(注意:没有牛津逗号!)

你甚至可以看到我们自己的Jon Skeet(是的,众所周知,他可以同时在两个地方)发布了一个解决方案,但他的(恕我直言)并不是最优雅的,尽管你可能无法击败它性能.

你怎么看？那里有很好的选择.我真的很喜欢其中一种涉及选择和聚合方法的解决方案(来自Fernando Nicolet).Linq非常强大,并且花了一些时间来应对这样的挑战让你学到很多东西.我扭曲了一下,所以它更高效一点(通过使用Count并避免反向):

public static string CommaQuibbling(IEnumerable<string> items)
{
    int last = items.Count() - 1;
    Func<int, string> getSeparator = (i) => i == 0 ? string.Empty : (i == last ? " and " : ", ");
    string answer = string.Empty;

    return "{" + items.Select((s, i) => new { Index = i, Value = s })
                      .Aggregate(answer, (s, a) => s + getSeparator(a.Index) + a.Value) + "}"; …

我正在尝试提出一些专注于多线程的编程难题.到目前为止,我能够提出的大部分问题都是针对特定领域的.对于试图学习多线程应用程序核心概念的开发人员,是否有任何人有任何体面的编程难题？

在下列情况下,如何确定函数返回0或1的概率:

让function_A返回0的概率为40%,1则概率为60%. 仅function_B使用仅生成具有50-50的概率function_A.

我想到了以下几点:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

什么组合可以给50-50？