在给定最小子序列长度的序列中具有最大成功率的连续子序列 [英] Contiguous sub sequence with max success rate in a sequence given a minimum sub sequence length

问题描述

我正在尝试解决一个算法问题，其中前提围绕由 0 和 1 以及输出子序列的最小长度 l 组成的输入序列.该问题要求具有最高 1s 率的子序列(子序列中 1 的数量除以子序列的长度).可以在此处找到问题的更多背景和示例输入/输出.

I'm trying to solve an algorithmic problem where the premises revolves around an input sequence that consists of 0s and 1s along with a minimum length l for the output subsequence. The problem asks for the subsequence which has the highest rate of 1s (number of ones in the subsequence divided by the length of the subsequence). Further background and sample input/output to the problem can be found here.

我想出了一个解决方案，它通过了除最后一个测试之外的所有测试，我正在尝试找出我当前的实现缺少什么.我的方法是使用动态可调整大小的滑动窗口，同时存储滑动窗口的最大速率以及最大额定窗口的长度.我认为我移动(扩大和缩小)窗口的方式是问题所在，但我无法弄清楚要改变什么.

I have come up with a solution that passes all tests except for the last one and I am trying to figure out what my current implementation is lacking. My approach is to use a dynamically resizeable sliding window while storing the maximum rate of the sliding window along with the length of that maximum rated window. I think the way that I'm moving (growing and shrinking) my window is the problem, but I'm having trouble figuring out what to change.

这就是我移动窗口的方式:

This is how I move my window:

static void max_rate(long min_len, string sequence) {
  long left_window = 0, right_window = min_len - 1;

  long best_left = 0, best_len = 0, most_ones = 0;
  long double best_success_rate = -1;
  for (;;) {
    auto tmp = sequence.substr(left, right - left + 1);

    long n_ones = count_ones(tmp);
    long double success_rate = (long double)n_ones / (long double)tmp.length();

    if (success_rate >= best_success_rate) {
      best_success_rate = success_rate;
      best_left = left;
      best_len = right - left + 1;
      most_ones = n_ones;
    }

  // Window sliding starts here
  bool can_move_right = (right + 1) < (long)sequence.length();
  bool can_move_left = (right - left + 1 - 1) >= min_len;

    if (can_move_right && sequence.at(right + 1) == '1') {
    ++(right);
    } else if (can_move_right && sequence.at(right + 1) == '1') {
    ++(right);
    } else if (can_move_left && (sequence.at(left + 1) == '0')) {
    ++left;
    } else if (can_move_right) {
      ++(right);
    } else {
      break;
    }

  cout << best_left + 1 << " ";
  cout << best_len << endl;

我基本上是在检查:

1. 如果可以提高比率，请扩大窗口
2. 否则，如果可能(考虑到我们的最小尺寸要求)，如果可以提高速率，请缩小窗口
3. 否则，如果可能的话 (-)，缩小窗口
4. 否则，如果可能(我们不在序列的末尾)扩大窗口

我想我一定在这里遗漏了一些东西

I must be missing something here I think

推荐答案

根据你贴的代码，供输入

According to the code you posted, for input

8, "0011101011"

顺序似乎是

0 0 1 1 1 0 1 0 1 1
l             r
l               r
l                 r
  l               r

这给了我们:

zero-based index 1, interval length 9
and ratio 6 / 9 = 0.6666666666666666

但正确答案是

ratio 0.75
zero-based index 2, interval length 8

这篇关于在给定最小子序列长度的序列中具有最大成功率的连续子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！