破解编码采访-马戏团塔问题(17.8)
破解编码采访-马戏团塔问题(17.8)
提问于 2019-05-12 18:24:05
问题：
我正在破解第六版的编码采访，我遇到了马戏团大楼的问题(编号17.8)。我有一个我认为在O(N logN)时间运行的解决方案，但是这本书的解决方案(这是不同的)说O(N logN)解决方案非常复杂，但我的代码不是。我想得到一些帮助，找出我的解决方案是否正确，以及它是否在O(N logN)时间内运行。我想了解为什么我是错的(或对的)，所以任何细节都会有帮助。
以下是有问题的文本：
一个马戏团正在设计一种塔式套路，由站在对方肩膀上的人组成。出于实用和审美的考虑，每个人都必须比他或她下面的人更矮更轻。考虑到马戏团中每个人的身高和体重，写一种方法来计算在这样一个塔中尽可能多的人。
我的解决方案：
def circus_tower(people):
# People is a list of tuples of length 2, where item[0] is their height, and item[1] is their weight.
if len(people) == 0:
return 0
people = sorted(people, key=lambda x: x[0]) # Sort people by heights. O(P*logP).
start = 0
end = 0
longest_sequence = 0
for i in range(1, len(people)): # O(P).
if people[i][1] > people[i-1][1]: # Weight check.
end = i
else:
longest_sequence = end - start + 1
start = i
end = i
return max(longest_sequence, end - start + 1)下面是一些示例输入和我的代码返回的内容：
circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110)])
6
circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (65, 95), (68, 110)])
4
circus_tower([(56, 90), (65, 95), (72, 100), (68, 90), (70, 150), (75, 190)])
2
circus_tower([])
0回答 5
Stack Overflow用户
回答已采纳
发布于 2019-06-21 09:32:30
你的解决方案错了。如果你跑
circus_tower([[1,1],[1,7],[1,9],[2,2],[2,6],[3,3],[3,5],[4,4]])它返回2，而最长子序列([1,1]<[2,2]<[3,3]<[4,4])的长度为4。
代码的问题是，您只能找到连续的子序列。
Stack Overflow用户
发布于 2020-03-06 08:07:03
我还“找到”了一个简单的解决方案，无法理解我错在哪里：
module CircusTower
class Person
include Comparable
attr_reader :height, :weight
def initialize(height, weight)
@height = height
@weight = weight
end
def <=>(other)
res = height <=> other.height
if res == 0
weight <=> other.weight
else
res
end
end
end
# Time=O(n * log n) Mem=O(n)
def solve_b(people)
sorted = people.sort.reverse
res = []
sorted.each do |person|
if res.size == 0
res << person
else
if res.last.height > person.height && res.last.weight > person.weight
res << person
end
end
end
res.size
end
RSpec.describe 'CircusTower' do
include CircusTower
subject { solve_b(people) }
context 'book example' do
let(:people) do
[
Person.new(65, 100),
Person.new(70, 150),
Person.new(56, 90),
Person.new(75, 190),
Person.new(60, 95),
Person.new(68, 110),
]
end
it { is_expected.to eq 6 }
end
context 'tricky example' do
let(:people) do
[
Person.new(1,1),
Person.new(1,7),
Person.new(1,9),
Person.new(2,2),
Person.new(2,6),
Person.new(3,3),
Person.new(3,5),
Person.new(4,4),
]
end
it { is_expected.to eq 4 }
end
end
endStack Overflow用户
发布于 2020-03-07 10:37:57
有一个正确的解决方案
module CircusTowerSo
class Person
include Comparable
attr_reader :height, :weight
def initialize(height, weight)
@height = height
@weight = weight
end
def <=>(other)
res = height <=> other.height
if res == 0
weight <=> other.weight
else
res
end
end
def smaller?(other)
height < other.height && weight < other.weight
end
def to_s
"(#{height}, #{weight})"
end
def inspect
to_s
end
end
# Time=O(n * n) Mem=O(n * n)
def solve_b(people)
sorted = people.sort
find_lis_by_weight(sorted).size
end
def find_lis_by_weight(people)
longest_by_index_cache = people.each_with_index.map { |person, i| [i, [person]] }.to_h
longest = []
people.each_with_index do |person, index|
res = longest_for_index(longest_by_index_cache, index, person)
if res.size > longest.size
longest = res
end
longest_by_index_cache[index] = res
end
longest
end
def longest_for_index(longest_by_index_cache, index, person)
longest_prev_seq = []
index.times do |i|
prev_seq = longest_by_index_cache[i]
if prev_seq.last.smaller?(person) && prev_seq.size > longest_prev_seq.size
longest_prev_seq = prev_seq
end
end
longest_prev_seq + [person]
end
RSpec.describe 'CircusTower' do
include CircusTower
subject { solve_b(people) }
context 'book example' do
let(:people) do
[
Person.new(65, 100),
Person.new(70, 150),
Person.new(56, 90),
Person.new(75, 190),
Person.new(60, 95),
Person.new(68, 110),
]
end
it { is_expected.to eq 6 }
end
context 'tricky example' do
let(:people) do
[
Person.new(1, 1),
Person.new(1, 7),
Person.new(1, 9),
Person.new(2, 2),
Person.new(2, 6),
Person.new(3, 3),
Person.new(3, 5),
Person.new(4, 4),
]
end
it { is_expected.to eq 4 }
end
context 'more tricky example' do
let(:people) do
[
Person.new(1, 1),
Person.new(2, 2),
Person.new(3, 3),
Person.new(4, 1),
]
end
it { is_expected.to eq 3 }
end
end
end请参阅有关v6上CTCI的更多解决方案
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56102185
复制相关文章
相似问题
腾讯云开发者
