破解编码面试 - 马戏团塔问题 (17.8)
Cracking The Coding Interview - Circus Tower Problem (17.8)
问题：
我正在完成 Cracking the Coding Interview 第 6 版，但遇到了 Circus Tower 问题（编号 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)
这里有一些示例输入和我的代码 returns:
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
你的解决方案是错误的。如果你运行
circus_tower([[1,1],[1,7],[1,9],[2,2],[2,6],[3,3],[3,5],[4,4]])
它 returns 2 而最长的子序列 ([1,1]<[2,2]<[3,3]<[4,4]) 的长度为 4。
你的代码的问题是你只能找到连续的子序列。
我也"found"一个简单的解决方案，无法理解我哪里错了：
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
end
有一个正确的解决方案
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
上查看更多 CTCI 解决方案
我把问题分成了三个部分。
插入数据HeightWeight对象，然后按高度或宽度排序。我用高度
排序
之后将值插入地图以获得具有最小权重的唯一高度。
之后我找到了权重的最长递增子序列。
import java.util.*;
public class CircusTower {
private class HeightWeight implements Comparable<HeightWeight>{
int height;
int weight;
HeightWeight(int height, int weight) {
this.height = height;
this.weight = weight;
}
@Override
public int compareTo(HeightWeight other) {
if(this.height == other.height){
return this.weight - other.weight;
}else{
return this.height - other.height;
}
}
}
public static void main(String[] args) {
int[][] arr = {{1,1},{1,7},{1,9},{2,2},{2,6},{3,3},{3,5},{4,4}};
CircusTower ct = new CircusTower();
System.out.println(ct.getMaxHeightTower(arr));
}
public int getMaxHeightTower(int[][] arr){
List<HeightWeight> list = new ArrayList<>();
int i =0;
for(i =0; i<arr.length; i++){
list.add(new HeightWeight(arr[i][0], arr[i][1]));
}
Collections.sort(list);
Map<Integer, Integer> map = new HashMap<>();
for(i =0; i<list.size(); i++){
HeightWeight current = list.get(i);
if(!map.containsKey(current.height)){
map.put(current.height, current.weight);
}
}
int[] nums = map.values().stream().mapToInt(Integer::intValue).toArray();
return getLIS(nums);
}
public int getLIS(int[] nums){
int _l = nums.length;
int[] out = new int[_l];
int mx = Integer.MIN_VALUE;
/*
we initialize the array with ones because
a single character has a subsequence of length one
*/
Arrays.fill(out, 1);
for(int i = 0; i < _l; i++)
for(int j = i + 1; j < _l; j++){
/*
every iteration, all we're doing is checking what is the longest
increasing subsequence so far, till this point
*/
if(nums[j] > nums[i])
out[j] = Math.max(out[j], out[i] + 1);
/*
we keep checking for a max value because the longest
subsequence could exist before the end of the string
*/
mx = Math.max(out[j], mx);
}
return mx == Integer.MIN_VALUE ? 1 : mx;
}
}
我浏览了这个帖子，决定尝试澄清一下。将此视为贪婪方法不起作用的情况的示例，因为我们无法确定采用特定元素是否总是 不 采用它的更好解决方案。我们在 Knapsack 0/1 问题中看到了类似的问题。
如果给定权重：[1,2,3,4] 和利润 [80, 100, 20, 60] 并且您的容量为 5，那么您可以贪婪地选择 120（100+20），但随后您会意识到省略 100 是更好的选择，因为你可以得到 140 (60+80)。
为了解决这个问题，我们需要假设一个有点类似的方法：首先让我们对人的数组进行排序，因为与 Knapsack 的情况不同，这里的获取元素的顺序事项。但是这两种方法都归结为一个相似的想法：为了优化输出，你应该取第 n 个元素还是保留它?
这是我的 Java 递归解决方案，其 运行 复杂度为 O(2^n)：
方法一：Recusrive/Backtracking解决方案
public static void makeTower(List<Person> list, List<Person> tower, int index)
{
//Base case
if(index==-1)
{
printTower(tower);
return;
}
if(tower.get(tower.size()-1).height > list.get(index).height && tower.get(tower.size()-1).weight > list.get(index).weight) {
tower.add(list.get(index));
//if it is possible to add this person to the tower, add him
makeTower(list, new ArrayList<>(tower), index - 1);
}
//OR, choose to exclude the person
tower.remove(list.get(index));
makeTower(list, new ArrayList<>(tower), index-1);
}
其中“人物”class只是身高体重的封装
public class Person {
int height;
int weight;
public Person(int _h, int _w)
{
this.height = _h;
this.weight = _w;
}
}
而“printTower”方法什么都不做，只是在每次组合后将可能的塔打印给您
public static void printTower(List<Person> t)
{
for(Person p : t)
System.out.println(p.height+" , "+p.weight);
System.out.println("-----END-----");
}
测试输入输出：
所以如果我们考虑这个例子：
人（身高、体重）：[20, 80] [10, 40] [80, 40]
第一步，按高度排序 -> [10, 40] [20, 80] [80, 40]
然后，我们可以建造这些塔：
[10, 40] 在 [20, 80]
之上
这是所有组合中唯一可能的塔。
最后，主要（驱动程序）方法：
public static void main(String args[])
{
List<Person> people = new ArrayList();
people.add(new Person(20,80));
people.add(new Person(10, 40));
people.add(new Person(80, 40));
Collections.sort(people, new Comparator<Person>()
{
@Override
public int compare(Person one, Person two)
{
return (one.height-two.height);
}
});
List<Person> t = new ArrayList<>();
t.add(new Person(1000,1000));
makeTower(people, t, people.size()-1);
}
如前所述，该算法的 运行 时间复杂度是指数级的，但事实证明有更好的方法只适用于这个问题。此解决方案在 Cracking the coding interview 中有解释。
方法 2 - 动态规划
第二种方法 运行 的复杂度为 O(n^2)，虽然不是很好，但绝对比指数有很大的改进。做法是我们会轮流考虑每个人作为塔中的最后一个人。如果person-0是最后一个人，塔运行要多长时间？以此类推，直到 person-n。在我们的例子中，
塔的长度（给定的人 0 在底部）：2（最高）
塔的长度（给定的人 1 在底部）：1
塔的长度（给定的人 2 在底部）：1
所以 2 是我们的答案（最大塔尺寸）。砰！这就是我们的答案。大惊小怪，但与大多数 DP 方法一样，这种方法的问题在于它是一种更具体的解决方案类型 may/may 不适合其他类似类型的问题，因此更难提出与.
由于这个 post 已经 运行 这么久了，如果有人需要 approach-2 的代码和解释，请告诉我，我们很乐意提供帮助！ :)
问题：
我正在完成 Cracking the Coding Interview 第 6 版，但遇到了 Circus Tower 问题（编号 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)
这里有一些示例输入和我的代码 returns:
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
你的解决方案是错误的。如果你运行
circus_tower([[1,1],[1,7],[1,9],[2,2],[2,6],[3,3],[3,5],[4,4]])
它 returns 2 而最长的子序列 ([1,1]<[2,2]<[3,3]<[4,4]) 的长度为 4。
你的代码的问题是你只能找到连续的子序列。
我也"found"一个简单的解决方案，无法理解我哪里错了：
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
end
有一个正确的解决方案
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
我把问题分成了三个部分。
插入数据HeightWeight对象，然后按高度或宽度排序。我用高度
排序之后将值插入地图以获得具有最小权重的唯一高度。
之后我找到了权重的最长递增子序列。
import java.util.*; public class CircusTower { private class HeightWeight implements Comparable<HeightWeight>{ int height; int weight; HeightWeight(int height, int weight) { this.height = height; this.weight = weight; } @Override public int compareTo(HeightWeight other) { if(this.height == other.height){ return this.weight - other.weight; }else{ return this.height - other.height; } } } public static void main(String[] args) { int[][] arr = {{1,1},{1,7},{1,9},{2,2},{2,6},{3,3},{3,5},{4,4}}; CircusTower ct = new CircusTower(); System.out.println(ct.getMaxHeightTower(arr)); } public int getMaxHeightTower(int[][] arr){ List<HeightWeight> list = new ArrayList<>(); int i =0; for(i =0; i<arr.length; i++){ list.add(new HeightWeight(arr[i][0], arr[i][1])); } Collections.sort(list); Map<Integer, Integer> map = new HashMap<>(); for(i =0; i<list.size(); i++){ HeightWeight current = list.get(i); if(!map.containsKey(current.height)){ map.put(current.height, current.weight); } } int[] nums = map.values().stream().mapToInt(Integer::intValue).toArray(); return getLIS(nums); } public int getLIS(int[] nums){ int _l = nums.length; int[] out = new int[_l]; int mx = Integer.MIN_VALUE; /* we initialize the array with ones because a single character has a subsequence of length one */ Arrays.fill(out, 1); for(int i = 0; i < _l; i++) for(int j = i + 1; j < _l; j++){ /* every iteration, all we're doing is checking what is the longest increasing subsequence so far, till this point */ if(nums[j] > nums[i]) out[j] = Math.max(out[j], out[i] + 1); /* we keep checking for a max value because the longest subsequence could exist before the end of the string */ mx = Math.max(out[j], mx); } return mx == Integer.MIN_VALUE ? 1 : mx; }}
我浏览了这个帖子，决定尝试澄清一下。将此视为贪婪方法不起作用的情况的示例，因为我们无法确定采用特定元素是否总是 不 采用它的更好解决方案。我们在 Knapsack 0/1 问题中看到了类似的问题。 如果给定权重：[1,2,3,4] 和利润 [80, 100, 20, 60] 并且您的容量为 5，那么您可以贪婪地选择 120（100+20），但随后您会意识到省略 100 是更好的选择，因为你可以得到 140 (60+80)。
为了解决这个问题，我们需要假设一个有点类似的方法：首先让我们对人的数组进行排序，因为与 Knapsack 的情况不同，这里的获取元素的顺序事项。但是这两种方法都归结为一个相似的想法：为了优化输出，你应该取第 n 个元素还是保留它?
这是我的 Java 递归解决方案，其 运行 复杂度为 O(2^n)：
方法一：Recusrive/Backtracking解决方案
public static void makeTower(List<Person> list, List<Person> tower, int index)
{
//Base case
if(index==-1)
{
printTower(tower);
return;
}
if(tower.get(tower.size()-1).height > list.get(index).height && tower.get(tower.size()-1).weight > list.get(index).weight) {
tower.add(list.get(index));
//if it is possible to add this person to the tower, add him
makeTower(list, new ArrayList<>(tower), index - 1);
}
//OR, choose to exclude the person
tower.remove(list.get(index));
makeTower(list, new ArrayList<>(tower), index-1);
}
其中“人物”class只是身高体重的封装
public class Person {
int height;
int weight;
public Person(int _h, int _w)
{
this.height = _h;
this.weight = _w;
}
}
而“printTower”方法什么都不做，只是在每次组合后将可能的塔打印给您
public static void printTower(List<Person> t)
{
for(Person p : t)
System.out.println(p.height+" , "+p.weight);
System.out.println("-----END-----");
}
测试输入输出：
所以如果我们考虑这个例子：
人（身高、体重）：[20, 80] [10, 40] [80, 40] 第一步，按高度排序 -> [10, 40] [20, 80] [80, 40] 然后，我们可以建造这些塔：
[10, 40] 在 [20, 80]
之上这是所有组合中唯一可能的塔。
最后，主要（驱动程序）方法：
public static void main(String args[])
{
List<Person> people = new ArrayList();
people.add(new Person(20,80));
people.add(new Person(10, 40));
people.add(new Person(80, 40));
Collections.sort(people, new Comparator<Person>()
{
@Override
public int compare(Person one, Person two)
{
return (one.height-two.height);
}
});
List<Person> t = new ArrayList<>();
t.add(new Person(1000,1000));
makeTower(people, t, people.size()-1);
}
如前所述，该算法的 运行 时间复杂度是指数级的，但事实证明有更好的方法只适用于这个问题。此解决方案在 Cracking the coding interview 中有解释。
方法 2 - 动态规划
第二种方法 运行 的复杂度为 O(n^2)，虽然不是很好，但绝对比指数有很大的改进。做法是我们会轮流考虑每个人作为塔中的最后一个人。如果person-0是最后一个人，塔运行要多长时间？以此类推，直到 person-n。在我们的例子中，
塔的长度（给定的人 0 在底部）：2（最高） 塔的长度（给定的人 1 在底部）：1 塔的长度（给定的人 2 在底部）：1
所以 2 是我们的答案（最大塔尺寸）。砰！这就是我们的答案。大惊小怪，但与大多数 DP 方法一样，这种方法的问题在于它是一种更具体的解决方案类型 may/may 不适合其他类似类型的问题，因此更难提出与.
由于这个 post 已经 运行 这么久了，如果有人需要 approach-2 的代码和解释，请告诉我，我们很乐意提供帮助！ :)