C++ 中检查所有 1 是否至少间隔 K 个位置

假设我们有一个包含 0 和 1 的数组 nums 和一个整数 k，我们需要检查所有 1 是否至少相隔 k 个位置，否则返回 False。

因此，如果输入类似于 nums = [1,0,0,0,1,0,0,1]，k = 2，则输出将为 true，因为每个 1 都至少相隔 2 个位置。

为了解决这个问题，我们将遵循以下步骤：

  • last := -1

  • for 初始化 i := 0，当 i < nums 的大小，更新（i 增加 1），执行：

    • 如果 nums[i] 等于 1，则：

      • 如果 last 等于 -1 或 (i - last - 1) >= k，则：

        • last := i

      • 否则

        • 返回 false

  • 返回 true

示例

让我们看看以下实现以获得更好的理解：

在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool kLengthApart(vector<int>& nums, int k) {
      int last = -1;
      for (int i = 0; i < nums.size(); i++) {
         if (nums[i] == 1) {
            if (last == -1 || (i - last - 1) >= k)
               last = i;
            else
               return false;
         }
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,0,0,1,0,0,1};
   cout << (ob.kLengthApart(v, 2));
}

输入

{1,0,0,0,1,0,0,1}

输出

1

更新于： 2020-11-17

137 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告