一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
楼主: yyoung
收起左侧

[树/链表/图] 在leetcode面经上发现一道有意思的题目,大家可以一起讨论一下

[复制链接] |试试Instant~
我的人缘0
Wwwyyy 发表于 2019-6-16 09:19:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
rikoizz 发表于 2019-6-16 08:43
cf 3500 的大佬都没做出来....我觉得作为面试题八成是缺少某种约束条件

感觉这个题不像candy crush,更像祖玛啊哈哈。蛤蟆来决定哪段先消除。面试官少给一个参数frog。txtx
回复 微信

使用道具 举报

我的人缘0
337845818 发表于 2019-6-16 10:07:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   75% (239)
 
 
24% (79)    👎
这题真的挺有意思的哈哈
回复

使用道具 举报

我的人缘0
qqqzhouhk 发表于 2019-6-16 11:04:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   80% (25)
 
 
19% (6)    👎
感觉和488有点像,期待大神O(n)的解法!
回复

使用道具 举报

我的人缘0
magicsets 发表于 2019-6-16 14:40:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (769)
 
 
1% (8)    👎
magicsets 发表于 2019-6-16 02:56
这种情况之前确实没有考虑.. 要解决的话可以再加一个状态函数:

给定输入数组S,定义 H(i, j) 取值如 ...

之前描述状态转移方程的时候有点混乱..(但是关于 C(i, j) 和 H(i, j) 的定义应该还是比较明确的)

写了一份代码这样比较好参照:
[C++] 纯文本查看 复制代码
#include <algorithm>
#include <iostream>
#include <vector>

constexpr static int kNotSet = -1;
constexpr static int kInvalid = -2;
class MaxRepetition;

// Crushable(i, j) = true 当且仅当 data[i..j] 经过任意变换后可以被完全消除
class Crushable {
 public:
  explicit Crushable(const size_t length)
      : states_(length, std::vector<int>(length, kNotSet)) {}

  bool Get(int i, int j) {
    if (states_[i][j] == kNotSet) {
      states_[i][j] = Evaluate(i, j);
    }
    return static_cast<bool>(states_[i][j]);
  }

  void SetMaxRepetition(MaxRepetition* max_repetition) {
    max_repetition_ = max_repetition;
  }

 private:
  bool Evaluate(int i, int j);

  MaxRepetition* max_repetition_;
  std::vector<std::vector<int>> states_;
};

// (1) 如果 data[i] != data[j],那么 MaxRepetition(i, j) = kInvliad
// (2) 否则不妨设 data[i] == data[j] == X,那么 MaxRepetition(i, j)
//     取值为 data[i..j] 经过任意消除过程后可以得到的最长的"全X" 串的长度;
//     如果不能消除到只剩下X,那么 MaxRepetition(i, j) 取值仍然为kInvalid
class MaxRepetition {
 public:
  MaxRepetition(const std::vector<int>& data)
      : data_(data),
        states_(data.size(), std::vector<int>(data.size(), kNotSet)) {}

  int Get(int i, int j) {
    if (states_[i][j] == kNotSet) {
      states_[i][j] = Evaluate(i, j);
    }
    return states_[i][j];
  }

  void SetCrushable(Crushable* crushable) {
    crushable_ = crushable;
  }

 private:
  int Evaluate(int i, int j);

  const std::vector<int> &data_;
  Crushable* crushable_;
  std::vector<std::vector<int>> states_;
};

////////////////////////////////////////////////////////////////////////////////
/////////////////// Crushable 与 MaxRepetition 的状态转移方程 /////////////////////
////////////////////////////////////////////////////////////////////////////////

bool Crushable::Evaluate(int i, int j) {
  // 边界条件:区间长度小于3
  if (i + 1 >= j) {
    return false;
  }
  // 如果存在i < k < j,使得Crushable(i, k)且Crushable(k + 1, j),那么返回true
  for (int k = i + 2; k < j - 2; ++k) {
    if (Get(i, k) && Get(k + 1, j)) {
      return true;
    }
  }
  // 否则考虑是否可以Crush中间若干区间,然后剩下来的同一字符数量大于等于3
  return max_repetition_->Get(i, j) >= 3;
}

int MaxRepetition::Evaluate(int i, int j) {
  // 边界条件
  if (data_[i] != data_[j]) {
    return kInvalid;
  }
  // 区间大小为1或者2的情况
  if (i + 1 >= j) {
    return j - i + 1;
  }
  int max_count = kInvalid;
  // Case 1
  if (crushable_->Get(i + 1, j - 1)) {
    max_count = 2;
  }
  // Case 2
  const int target_value = data_[i];
  for (int k = i + 1; k < j; ++k) {
    if (data_[k] != target_value) {
      continue;
    }
    const int left_count = Get(i, k);
    const int right_count = Get(k, j);
    if (left_count != kInvalid && right_count != kInvalid) {
      max_count = std::max(max_count, left_count + right_count - 1);
    }
  }
  return max_count;
}

std::vector<int> ComputeShortestRemnant(const std::vector<int>& data) {
  const int length = data.size();
  if (length == 0) {
    return {};
  }

  Crushable crushable(length);
  MaxRepetition max_repetition(data);
  crushable.SetMaxRepetition(&max_repetition);
  max_repetition.SetCrushable(&crushable);

  // 外层的动态规划:找到总长度最大的Crushable区间集合
  std::vector<int> max_crush(length);
  std::vector<int> backtrack(length);
  backtrack[0] = -1;
  for (int j = 2; j < length; ++j) {
    max_crush[j] = max_crush[j - 1];
    backtrack[j] = j - 1;
    for (int i = 0; i < j - 1; ++i) {
      if (crushable.Get(i, j)) {
        const int total_crush = (i == 0 ? 0 : max_crush[i - 1]) + j - i + 1;
        if (total_crush > max_crush[j]) {
          max_crush[j] = total_crush;
          backtrack[j] = i - 1;
        }
      }
    }
  }

  // Backtrack收集无法消除的元素
  std::vector<int> result;
  int curr = length - 1;
  while (curr != -1) {
    const int prev = backtrack[curr];
    if (prev == curr - 1) {
      result.push_back(data[curr]);
    }
    curr = prev;
  }

  std::reverse(result.begin(), result.end());
  return result;
}

void PrintVector(const std::vector<int>& values) {
  std::cout << "[";
  bool first = true;
  for (int value : values) {
    std::cout << (first ? "" : " ") << value;
    first = false;
  }
  std::cout << "]\n";
}

int main(int argc, char* argv[]) {
  // [1 1]
  PrintVector(ComputeShortestRemnant({1,3,3,3,2,2,2,3,1}));

  // [1 1]
  PrintVector(ComputeShortestRemnant({1,3,3,3,2,2,2,3,1}));

  // [3 1 3 2 3]
  PrintVector(ComputeShortestRemnant(
      {3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3}));

  // [2]
  PrintVector(ComputeShortestRemnant({2,3,3,3,2,2,2,3,3}));

  // []
  PrintVector(ComputeShortestRemnant({5,1,1,1,5,1,1,1,5}));

  // []
  PrintVector(ComputeShortestRemnant({1,1,1,2,2,2,1,2,2,2,1}));

  // []
  PrintVector(ComputeShortestRemnant(
      {3,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,2,1,1,
       1,3,1,1,1,3,2,2,2,3,1,1,1,3,1,1,1,3}));

  return 0;
}


补充内容 (2019-6-16 14:47):
Crushable对应原帖描述的C(i, j),MaxRepetition对应原帖描述的H(i, j),都是用了memo的方法,总时间复杂度为O(n ^ 3)
回复

使用道具 举报

我的人缘0
loonreg 发表于 2019-6-17 02:57:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
magicsets 发表于 2019-6-15 12:40
这个问题可以用两阶段的动态规划做吧,时间是O(n^3),不知道可不可以进一步优化了

--

1. C(i, j)的计算可以参考POJ 1390的题解,用dfs + dp 求解。对于这道题,rlen的长度可以限制在0到3之间。时间复杂度O(n^3)
2. 不需要排序,C(i, j) 是个0/1矩阵,这个矩阵本身决定了区间的顺序。后面对区间做dp时,需要对右端点排序,但是在计算dp[j] 的时候,只需要枚举所有的 C(i, j) 即可。
3. 这题看起来似乎无论如何都无法避免计算C(i, j)。想要有更好的方法,不妨直接考虑如何求解所有的C(i, j)。因为剩下的部分可以在O(n^2)时间内解决
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-21 04:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表