我尝试做经典问题来实现一个算法来打印 n 对括号的所有有效组合。我找到了这个程序(完美运行):
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public static ArrayList<String> generateParens(int count) {
char[] str = new char[count*2];
ArrayList<String> list = new ArrayList<String>();
addParen(list, count, count, str, 0);
return list;
}
然后，当我搜索 Catalan Numbers 的应用程序时，我在这里找到了一个非常有趣的应用程序:https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics 它说:
We can use catalan numbers to form mountain ranges with n upstrokes and n down-strokes that all stay above the original line. The mountain range interpretation is that the mountains will never go below the horizon
因此，我尝试重用上面的代码来实现这个问题的解决方案。我不确定，但我认为我们可以重用这段代码，因为它们似乎具有相同的“逻辑”。 不幸的是，我尝试了很多方法来用 '/' 和 '\' 替换括号，但都失败了。
我试着做这样的事情:
str[count] = '/';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = '\\';
str[count+1] = '\n';
addParen(list, leftRem, rightRem - 1, str, count + 2);
对我来说，它们有相同的逻辑，比如在括号中，我们添加左括号'(' EACH time is possible，但是对于右括号')'我们只有在右括号的数量大于左边。我们可以在这里做同样的推理，不是吗？我们添加 '/' 每次都是可能的，但是对于 '\' 我们必须计算之前 '/' 的数量......
我发现这里特别困难的是我们如何在这里插入新行以获得所有正确的山脉？
如果可能的话，你能帮我重用这段代码吗？还是我应该从头开始编写另一个代码？
最佳答案
有趣的任务。计算可以并行进行。我将在“不回答”标签中显示代码，因为它不符合问题的语言标准(使用并行数组处理语言 Dyalog APL 制作，实际上它用一个行代码)。请根据需要忽略该部分。但是，我将显示数据以及发生的情况。它相当直观。
<不回答>
fn←{(∧/(0≤+\a-~a),(⍵÷2)=+/a)⌿a←⍉(⍵⍴2)⊤⍳2*⍵} // Dynamic function, generates boolean matrix
format←{⍉↑(-1+(0.5×⍴⍵)-+\⍵-0,¯1↓~⍵)↑¨'\/'[1+⍵]} // Dirty format function
/不回答>
假设参数(山脉的宽度)是 n=6。
第 1 步。生成 0 到 (2^6 - 1) 之间的所有数字
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
第 2 步:获取每个的 2 基(它们在垂直下方。0 在最左边，然后是 1，依此类推):
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
<子>1。事实上，只需要生成从 32 到 63 的数字，因为我们只需要以 1 开头的 2 基数。请参见上面数据中的最上面一行。顶部为零的列(数字)实际上什至不应该生成。)
2. 实际上只需要生成偶数，因为最后一位必须为0。请参见上面数据中的最下面一行。底部的列(数字)实际上什至不应该生成。)
第 3 步:计算每列中的个数:
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
并做一个 boolean 标记 = 1，其中总和是 N 的一半，即 3(即总共我们必须有与下坡一样多的上坡)。 这是我们的第一个 boolean 结果:
0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0
第 4 步:确保我们不会“低于地平线”:
这意味着我们必须首先计算每一列的累计和:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4
0 0 1 1 1 1 2 2 1 1 2 2 2 2 3 3 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 2 2 3 3 3 3 4 4 3 3 4 4 4 4 5 5
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
然后对于移位的位(0 变成 1，反之亦然):
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0
5 5 4 4 4 4 3 3 4 4 3 3 3 3 2 2 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 3 3 2 2 2 2 1 1 2 2 1 1 1 1 0 0
6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
然后用第一个减去第二个，得到
¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 1 1 1 1 1 1 1 1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3
¯4 ¯4 ¯4 ¯4 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 0 0 0 0 ¯2 ¯2 ¯2 ¯2 0 0 0 0 0 0 0 0 2 2 2 2 ¯2 ¯2 ¯2 ¯2 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 2 2 2 2 4 4 4 4
¯5 ¯5 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 1 1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 1 1 ¯1 ¯1 1 1 1 1 3 3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 1 1 ¯1 ¯1 1 1 1 1 3 3 ¯1 ¯1 1 1 1 1 3 3 1 1 3 3 3 3 5 5
¯6 ¯4 ¯4 ¯2 ¯4 ¯2 ¯2 0 ¯4 ¯2 ¯2 0 ¯2 0 0 2 ¯4 ¯2 ¯2 0 ¯2 0 0 2 ¯2 0 0 2 0 2 2 4 ¯4 ¯2 ¯2 0 ¯2 0 0 2 ¯2 0 0 2 0 2 2 4 ¯2 0 0 2 0 2 2 4 0 2 2 4 2 4 4 6
并查看哪些列没有负值； 这是第二个 boolean 结果:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
第 5 步:从上面的两个 boolean 结果中获取一个 AND:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0
这些是创建好山的二进制数据列的位置。下面按列向左，然后转置(为了便于阅读)向右。 1 是上坡， 2 编辑:0 是下坡:
1 1 1 1 1 1 0 1 0 1 0 // 1 0 1 0 1 0 means /\/\/\
0 0 1 1 1 1 0 1 1 0 0
1 1 0 0 1 1 1 0 0 1 0
0 1 0 1 0 1 1 0 1 0 0 // means //\/\\
1 0 1 0 0 1 1 1 0 0 0
0 0 0 0 0
这是很好的答案。如果需要，我们可以应用格式:
format [the boolean result]
┌──────┬──────┬──────┬──────┬──────┐
│ │ │ │ │ /\ │
│ │ /\ │ /\ │ /\/\ │ / \ │
│/\/\/\│/\/ \│/ \/\│/ \│/ \│
└──────┴──────┴──────┴──────┴──────┘
稍微大一点，n=10:
DISP format¨↓fn 10
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ /\ │ /\ │ /\ │ /\ │ /\/\ │ / \ │
│ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ │ /\ │ /\ │ /\ /\ │ /\/\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │
│ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ /\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \/\ │ / \ │ / \ │ /\ │ /\ /\ │ /\ /\ │ /\ /\/\ │ /\ / \ │ /\/\ │ /\/\ /\ │ /\/\/\ │ /\/\/\/\ │ /\/\/ \ │ /\/ \ │ /\/ \/\ │ /\/ \ │ /\/ \ │ / \ │ / \ /\ │ / \/\ │ / \/\/\ │ / \/ \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │
│/\/\/\/\/\│/\/\/\/ \│/\/\/ \/\│/\/\/ \│/\/\/ \│/\/ \/\/\│/\/ \/ \│/\/ \/\│/\/ \│/\/ \│/\/ \/\│/\/ \│/\/ \│/\/ \│/ \/\/\/\│/ \/\/ \│/ \/ \/\│/ \/ \│/ \/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
编辑:当然也可以在一个循环中完成所有这些。一次只取一个数字，并进行上面的检查(1 的数量 == n 的一半，不低于地平线)。如果任一检查失败则跳出。
关于java - 生成具有上冲程和下冲程的山脉的算法(java)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37389354/
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..
在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',
我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我是Rails的新手，所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格，我想要的三列是:公司名称、公司描述和Logo。对于名称，我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串，然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列？ 最佳答案 对于“文本”数
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些
我正在使用Rails3.1并在一个论坛上工作。我有一个名为Topic的模型，每个模型都有许多Post。当用户创建新主题时，他们也应该创建第一个Post。但是，我不确定如何以相同的形式执行此操作。这是我的代码:classTopic:destroyaccepts_nested_attributes_for:postsvalidates_presence_of:titleendclassPost...但这似乎不起作用。有什么想法吗？谢谢! 最佳答案 @Pablo的回答似乎有你需要的一切。但更具体地说...首先改变你View中的这一行对此#
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我