时间戳

首页 > 解决方案 > 检查数组中给定的 K 元素

c++ - 检查数组中给定的 K 元素

问题描述

这个作业是关于湖上的赛船比赛。

我有一个 N 数组，我在其中输入风速。我必须给一个K数，它决定了连续多少天的风速在10到100之间。如果我找到K个连续元素，我必须调出这个序列的第一个元素的索引。

目标是找出哪一天可以开始“竞赛”。

例如：

S[10] = {50,40,0,5,0,80,70,90,100,120}
K=3

输出必须是 6，因为它是数组的第 6 个元素，这个序列从这里开始。

我不知道如何实施这项检查。

我试过这个：

for (int i=0; i<N-2; i++){
        if (((10<=S[i]) && (S[i]<=100)) && ((10<=S[i+1]) && (S[i+1]<=100)) && ((10<=S[i+2]) && (S[i+2]<=100))){
            canBeStarted = true;
            whichDayItCanBeStarted = i;
        }
    }

    cout << whichDayItCanBeStarted << endl;

但我意识到 K 可以是任意数字，所以我必须一次检查 K 个元素。

标签： c++algorithm

解决方案

利用算法标准库

（限制：以下答案提供了一种适用于 C++17 及更高版本的方法）

对于这样的问题，与其重新发明轮子，不如考虑转向标准库中的算法库，利用std::transform和std::search_n

  • 将integer -> bool风速转换为所述风速的有效性，然后是
  • 在转换结果中搜索多个 ( K) 子后续true（有效风速）元素，

分别。

例如：

#include <algorithm>  // std::search_n, std::transform
#include <cstdint>    // uint8_t (for wind speeds)
#include <iostream>   // std::cout
#include <iterator>   // std::back_inserter, std::distance
#include <vector>     // std::vector

int main() {
  // Wind data and wind restrictions.
  const std::vector<uint8_t> wind_speed{50U, 40U, 0U,  5U,   0U,
                                        80U, 70U, 90U, 100U, 120U};
  const uint8_t minimum_wind_speed = 10U;
  const uint8_t maximum_wind_speed = 100U;
  const std::size_t minimum_consecutive_days = 3;

  // Map wind speeds -> wind speed within limits.
  std::vector<bool> wind_within_limits;
  std::transform(wind_speed.begin(), wind_speed.end(),
                 std::back_inserter(wind_within_limits),
                 [](uint8_t wind_speed) -> bool {
                   return (wind_speed >= minimum_wind_speed) &&
                          (wind_speed <= maximum_wind_speed);
                 });

  // Find the first K (minimum_consecutive_days) consecutive days with
  // wind speed within limits.
  const auto starting_day =
      std::search_n(wind_within_limits.begin(), wind_within_limits.end(),
                    minimum_consecutive_days, true);
  if (starting_day != wind_within_limits.end()) {
    std::cout << "Race may start at day "
              << std::distance(wind_within_limits.begin(), starting_day) + 1
              << ".";
  } else {
    std::cout
        << "Wind speeds during the specified days exceed race conditions.";
  }
}

或者，我们可以将转换集成到std::search_n调用中的二元谓词中。这产生了一个更紧凑的解决方案，但与 imo 相比，语义和可读性稍差。

#include <algorithm>  // std::search_n
#include <cstdint>    // uint8_t (for wind speeds)
#include <iostream>   // std::cout
#include <iterator>   // std::distance
#include <vector>     // std::vector

int main() {
  // Wind data and wind restrictions.
  const std::vector<uint8_t> wind_speed{50U, 40U, 0U,  5U,   0U,
                                        80U, 70U, 90U, 100U, 120U};
  const uint8_t minimum_wind_speed = 10U;
  const uint8_t maximum_wind_speed = 100U;
  const std::size_t minimum_consecutive_days = 3;

  // Find any K (minimum_consecutive_days) consecutive days with wind speed
  // within limits.
  const auto starting_day = std::search_n(
      wind_speed.begin(), wind_speed.end(), minimum_consecutive_days, true,
      [](uint8_t wind_speed, bool) -> bool {
        return (wind_speed >= minimum_wind_speed) &&
               (wind_speed <= maximum_wind_speed);
      });
  if (starting_day != wind_speed.end()) {
    std::cout << "Race may start at day "
              << std::distance(wind_speed.begin(), starting_day) + 1 << ".";
  } else {
    std::cout
        << "Wind speeds during the specified days exceed race conditions.";
  }
}

鉴于您提供的特定（硬编码）风数据和限制，上述两个程序都会导致：

Race may start at day 6.

推荐阅读