2

问题：

我正在完成第 6 版的《Cracking the Coding Interview》，但遇到了 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)

以下是一些示例输入以及我的代码返回的内容：

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
4

5 回答 5

2

你的解决方案是错误的。如果你跑

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 时返回。

您的代码的问题是您只能找到连续的子序列。

于 2019-06-21T09:32:30.677 回答
0

我还“找到”了一个简单的解决方案，无法理解我错在哪里：

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
于 2020-03-06T08:07:03.823 回答
0

有一个正确的解决方案

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

在https://github.com/holyketzer/ctci_v6上查看更多 CTCI 解决方案

于 2020-03-07T10:37:57.377 回答
0

我把问题分成三个部分。

  1. 插入数据 HeightWeight 对象，然后按高度或宽度排序。我已经按身高排序

  2. 之后将值插入地图以获得具有最小重量的独特高度。

  3. 之后，我找到了体重的最长增加子序列。

    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;
}

    }

于 2021-05-23T15:33:34.470 回答
0

我浏览了这个线程并决定我可以尝试澄清这一点。将此视为贪婪方法不起作用的示例，因为我们无法确定采用特定元素是否总是比不采用它更好的解决方案。我们已经看到与背包 0/1问题类似的问题。如果给你权重：[1,2,3,4] 和利润 [80, 100, 20, 60] 并且你的容量是 5，那么你可以贪婪地选择 120 (100+20)，但是你会意识到省略 100 是更好的选择，因为您可以得到 140 (60+80)。

为了解决这个问题，我们需要假设一个有点类似的方法：首先让我们对人员数组进行排序，因为与背包的情况不同，这里取元素的顺序很重要。但是这两种方法都归结为一个相似的想法：为了优化输出，你应该取第 n 个元素还是离开它？

这是我以 O(2^n) 复杂度运行的 Java 递归解决方案：

方法一：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);

}

其中“Person”类只是对他的身高和体重的封装

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);
}

如前所述，该算法的运行时复杂度是指数级的，但事实证明，有一种更好的方法只适合这个问题。破解编码面试中解释了这个解决方案。

方法 2 - 动态规划

第二种方法以 O(n^2) 复杂度运行，虽然不是很漂亮，但绝对比指数方法有很多改进。方法是我们将轮流将每个人视为塔中的最后一个人。如果 person-0 是最后一个人，塔会运行多长时间？依此类推，直到 person-n。在我们的案例中，

塔的长度（给定的人 0 在底部）：2（最高）塔的长度（给定的人 1 在底部）：1 塔的长度（给定的人 2 在底部）：1

所以 2 是我们的答案（最大塔尺寸）。砰！这就是我们的答案。少得多大惊小怪，但与大多数 DP 方法一样，这种方法的问题在于它是一种更具体的解决方案类型，可能/可能不适合其他类似类型的问题，因此更难以提出。

由于这篇文章已经运行了这么长时间，请告诉我是否有人需要方法 2 的代码和解释，很乐意提供帮助！:)

于 2022-01-23T12:28:41.623 回答