Ruby challange:有经验的开发者请回复
我正在研究面向新开发人员的一些ruby问题,但我希望有经验的开发人员对此有所意见。 对不起,我很感激你的时间和意见。
问题问题
编写一个函数, nearest_larger(arr, i)
,它接受一个数组和一个索引。 该函数应该返回另一个索引, j
:这应该满足:
arr[i] < arr[j]
,AND arr[i] < arr[j]
地方没有比j
更接近i
j2
。 如果有关系(请参阅下面的示例),请选择两个索引中最早的(最左边的)。 如果arr
没有数字大于arr[i]
,则返回nil
。
难度:2/5
Rspec测试
describe "#nearest_larger" do
it "handles a simple case to the right" do
nearest_larger([2,3,4,8], 2).should == 3
end
it "handles a simple case to the left" do
nearest_larger([2,8,4,3], 2).should == 1
end
it "treats any two larger numbers like a tie" do
nearest_larger([2,6,4,8], 2).should == 1
end
it "should choose the left case in a tie" do
nearest_larger([2,6,4,6], 2).should == 1
end
it "handles a case with an answer > 1 distance to the left" do
nearest_larger([8,2,4,3], 2).should == 0
end
it "handles a case with an answer > 1 distance to the right" do
nearest_larger([2,4,3,8], 1).should == 3
end
it "should return nil if no larger number is found" do
nearest_larger( [2, 6, 4, 8], 3).should == nil
end
end
解
def nearest_larger arr, idx
diff = 1
loop do
l = idx - diff
r = idx + diff
return l if (l >= 0) && (arr[l] > arr[idx])
return r if (r < arr.length) && (arr[r] > arr[idx])
return nil if (l < 0) && (r >= arr.length)
diff += 1
end
end
反馈
我决定发布这个问题,因为我知道对于新开发人员来说,解决问题有多容易,而不知道首先写什么。 我希望你的回答能够让你了解你将如何解决你认为是一个挑战的问题。
你将如何去解决这个问题? (你的过程是什么?)
从一个简单的例子开始,例如其中一个测试。 发现如果数组元素arr[i-1]
大于arr[i]
那么你可以立即返回i-1
作为答案。 因此,您可以继续检查: i-1, i+1, i-2, i+2, i-3, i+3
等,并返回满足不等式的第一个索引。
在你看来,确实发现问题问题清晰易懂?
是; 测试帮助,但它只证实了我对措辞问题的理解。
需要多长时间才能解决这个问题? (10分钟,20分钟,...?)
对于在考试/教室环境中的学生,不超过10分钟。 根据他们之前有多少准备材料,可能更少。
是否同意难度? (请记住,这是面向新开发人员的)
是的,2/5看起来是正确的。
如果愿意:请张贴您自己的解决方案,展示您解决此问题的风格。
def nearest_larger( a, i )
2.upto([i,a.length-i].max << 1) do |k|
j = (k&1).zero? ? i - (k>>1) : i + (k>>1)
return j if 0 <= j && j < a.length && a[i] < a[j]
end
return nil
end
附录:在比特中的思考
本附录将更详细地介绍解决上述问题的解决方案,以便为新程序员提供帮助。
如答案提到对问题上述#1,的返回值nearest_larger
是第一索引j
为其a[i] < a[j]
作为j
通过序列迭代
i-1, i+1, i-2, i+2, i-3, i+3, ...
这为打开一个子问题的方式,这是如何生成这个序列的数字。 在实际编写程序时,我将评论用作“便笺簿”,并且在代码中有这样的内容:
# -1, 1, -2, 2, -3, 3, ... (Sequence G)
通过将每个项加上i
就构成了前面的序列。 调用这个序列G.现在这是一个“二元直觉”将发挥作用的地方。 考虑一个简单的二进制数序列,每列后增加1,如列A所示,熟悉的十进制表示形式在列B中显示:
A B C D E F
----------------------------
0000 0 000 0 0 0
0001 1 000 1 0 0
0010 2 001 0 1 -1
0011 3 001 1 1 1
0100 4 010 0 2 -2
0101 5 010 1 2 2
0110 6 011 0 3 -3
0111 7 011 1 3 3
现在将每个数字中的位分成两组:除列0以外的所有位(最右边的位),如列C所示,列0显示在列D中。换句话说,连接C和D得到A 。C的十进制表示在E列中。注意,D列方便地在0和1之间翻转,就像序列G中的数字在负值和正值之间翻转一样。 我们将用它来构造列F,它与E相同,除非D是0时F使得F为负数。 最后,如果我们刚开始在A = 0010(或B = 2)的上表中,则列F给出了上述序列G.
那么现在我们如何从代码中获得列F的列F? 这是位操作进行的地方。
C = A >> 1
- >>
右移运算符通过RHS(右侧)移动LHS(左侧)上的位。 在这种情况下,每个值A被移到右边的一个地方。 最右边的位丢失了。 在数学上,它与除以2并在此情况下删除余数相同(B / 2 == E,其余部分被删除)。
D = A & 1
- &
是按位AND运算符。 通过用1来“和”A,我们只选择位0; 有关更多详细信息,请参阅前一句中的链接。 这给了我们专栏D.
把它们放在代码中,我们将有k
是迭代变量,从2开始,每次增加1。 然后上面的分析给我们j
:
j = (k&1).zero? ? i - (k>>1) : i + (k>>1)
j
的第一个值在边界内并且a[i] < a[j]
成立,这自动成为答案,因此它可以立即返回:
return j if 0 <= j && j < a.length && a[i] < a[j]
最后,如果没有有效的j
值,则返回nil
。 除了计算k
的较低上界,这是nearest_larger
功课的问题,也就是nearest_larger
函数的整体。
在实际操作中,对于这样的问题,在OP中提出的可读解决方案是更可取的,因为它对更广泛的程序员群体更清楚和更易于访问。 目前的这种方法受到了展示位操作使用的机会的启发。
我没有经验丰富的开发人员,甚至没有经验丰富的开发人员,但我仍然会给你我的想法。
1你将如何去解决这个问题? (你的过程是什么?)
我希望闯进一块,但每个人都会这样做。 例如,这里数组中的值只用于提取更大的元素的索引,所以我将第一个问题看作是提取索引,第二个问题是单独处理索引。 我会通过从每个索引中减去i
来进一步简化后者,以便将j
和k
比较如下: if j.abs < k.abs ...
,而不是if (ji).abs < (ki).abs...
在选择不同的方法时,我倾向于寻找最容易理解的方法(“最佳阅读”)。
2.在你看来,问题问题清楚易懂吗?
是。
3.你需要多久才能解决这个问题?
我拒绝回答,理由是它肯定会导致我入罪。
4.你是否同意难度级别?
这似乎是正确的。 这将是rubeque.com上的一个“初学者”问题。
5.如果愿意:请张贴您自己的解决方案,展示您解决此问题的风格。
当然。
def nearest_larger(arr, i)
ret = nearest_to_zero( arr.each_with_index
.select { |e,j| e > arr[i] }
.map { |_,j| j-i } )
ret ? ret + i : nil
end
我看了两种写作nearest_to_zero()
。 首先是简短,直接和清晰,但效率低下,使用sort!
:
def nearest_to_zero(a)
a.sort! { |j,k| (j.abs == k.abs) ? j <=> k : j.abs <=> k.abs }
a.any? ? a.first : nil
end
效率更高,但不尽人意:
def nearest_to_zero(a)
neg, pos = a.partition { |e| e < 0 }
case
when neg.empty?
pos.empty? ? nil : pos.first
when pos.empty?
neg.last
else
pos.last.abs < neg.last.abs ? pos.first : neg.last
end
end
对于arr = [2,5,4,8,10], i = 2
,以下步骤由nearest_larger()
执行:
a = arr.each_with_index.select { |e,j| e > arr[i] } # => [[5,1],[8,3],[10,4]]
b = a.map { |_,j| j-i } # => [-1,1,2]
ret = nearest_to_zero(b) # => -1
ret ? ret + i : nil # => 1
在第一个nearest_to_zero()
,如果两个指数具有相等的绝对值(意味着它们在变换之前与i
相等),则该指数以较低的值进入指数; 否则它是绝对值较小的索引。
在第二个nearest_to_zero()
:
neg, pos = [-1,1,2].partition {|e| e < 0} # => [[-1],[1,2]]
其余的应该是不言自明的。
我曾阅读过rspec,但之前没有使用过。 现在是时候了。 我的代码通过了。
链接地址: http://www.djcxy.com/p/25651.html