警察抓小偷-yiteyi-C++库

给定一个大小为n的数组，其规格如下：

null

数组中的每个元素都包含一名警察或一名小偷。
每个警察只能抓一个小偷。
警察抓不到距离警察超过K个单位的小偷。

我们需要找出能抓到的最大数量的小偷。例如：

Input : arr[] = {'P', 'T', 'T', 'P', 'T'},            k = 1.Output : 2.Here maximum 2 thieves can be caught, firstpoliceman catches first thief and second police-man can catch either second or third thief.Input : arr[] = {'T', 'T', 'P', 'P', 'T', 'P'},             k = 2.Output : 3.Input : arr[] = {'P', 'T', 'P', 'T', 'T', 'P'},            k = 3.Output : 3.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 蛮力方法是检查所有可行的警察和小偷组合集，并返回其中的最大大小集。它的时间复杂度是指数的，如果我们观察到一个重要的性质，它可以被优化。一 有效率的 解决方法是使用贪婪算法。但哪个贪婪的财产使用可能很棘手。我们可以试着使用：“对于左边的每个警察，抓住最近的小偷。”这适用于上面给出的示例三，但在示例二中失败，因为它输出了不正确的2。 我们也可以试试 ：“对于左边的每个警察来说，抓住尽可能远的小偷”。这适用于上面给出的示例2，但在示例3中失败，因为它输出了不正确的2。可以应用对称参数来表明从数组右侧遍历这些对象也会失败。我们可以观察到这种想法，而不考虑警察和专注于分配工作： 1.获得警察p和小偷t的最低指数。分配如果| p-t |<=k，则增加到找到的下一个p和t。 2.否则，将min（p，t）增加到下一个p或t。 3.重复上述两个步骤，直到找到下一个p和t。 4.返回分配的数量。下面是上述算法的实现。它使用向量来将警察和小偷的索引存储在数组中并进行处理。

C++

                         // C++ program to find maximum number of thieves                       
                         // caught                       
                         #include <iostream>                       
                         #include <vector>                       
                         #include <cmath>                       
           
                         using                                     namespace                                     std;                       
           
                         // Returns maximum number of thieves that can                       
                         // be caught.                       
                         int                                     policeThief(                                     char                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     res = 0;                       
                                                 vector<                                     int                                     > thi;                       
                                                 vector<                                     int                                     > pol;                       
           
                                                 // store indices in the vector                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'P'                                     )                       
                                                 pol.push_back(i);                       
                                                 else                                     if                                     (arr[i] ==                                     'T'                                     )                       
                                                 thi.push_back(i);                       
                                                 }                       
           
                                                 // track lowest current indices of                       
                                                 // thief: thi[l], police: pol[r]                       
                                                 int                                     l = 0, r = 0;                       
                                                 while                                     (l < thi.size() && r < pol.size()) {                       
           
                                                 // can be caught                       
                                                 if                                     (                                     abs                                     (thi[l] - pol[r]) <= k) {                       
                                                 res++;                       
                                                 l++;                       
                                                 r++;                       
                                                 }                       
           
                                                 // increment the minimum index                       
                                                 else                                     if                                     (thi[l] < pol[r])                       
                                                 l++;                       
                                                 else                       
                                                 r++;                       
                                                 }                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     k, n;                       
           
                                                 char                                     arr1[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     };                       
                                                 k = 2;                       
                                                 n =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr1, n, k) << endl;                       
           
                                                 char                                     arr2[] = {                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 k = 2;                       
                                                 n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr2, n, k) << endl;                       
           
                                                 char                                     arr3[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 k = 3;                       
                                                 n =                                     sizeof                                     (arr3) /                                     sizeof                                     (arr3[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr3, n, k) << endl;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find maximum number of                       
                         // thieves caught                       
                         import                                     java.util.*;                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns maximum number of thieves                       
                                                 // that can be caught.                       
                                                 static                                     int                                     policeThief(                                     char                                     arr[],                                     int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 int                                     res =                                     0                                     ;                       
                                                 ArrayList<Integer> thi =                                     new                                     ArrayList<Integer>();                       
                                                 ArrayList<Integer> pol =                                     new                                     ArrayList<Integer>();                       
           
                                                 // store indices in the ArrayList                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'P'                                     )                       
                                                 pol.add(i);                       
                                                 else                                     if                                     (arr[i] ==                                     'T'                                     )                       
                                                 thi.add(i);                       
                                                 }                       
           
                                                 // track lowest current indices of                       
                                                 // thief: thi[l], police: pol[r]                       
                                                 int                                     l =                                     0                                     , r =                                     0                                     ;                       
                                                 while                                     (l < thi.size() && r < pol.size()) {                       
           
                                                 // can be caught                       
                                                 if                                     (Math.abs(thi.get(l) - pol.get(r)) <= k) {                       
                                                 res++;                       
                                                 l++;                       
                                                 r++;                       
                                                 }                       
                                   
                                                 // increment the minimum index                       
                                                 else                                     if                                     (thi.get(l) < pol.get(r))                       
                                                 l++;                       
                                                 else                       
                                                 r++;                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     k, n;                       
                                                 char                                     arr1[] =                                     new                                     char                                     [] {                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                       
                                                 'P'                                     ,                                     'T'                                     };                       
                                                 k =                                     2                                     ;                       
                                                 n = arr1.length;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 +policeThief(arr1, n, k));                       
                                   
                                                 char                                     arr2[] =                                     new                                     char                                     [] {                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'P'                                     ,                       
                                                 'T'                                     ,                                     'P'                                     };                       
                                                 k =                                     2                                     ;                       
                                                 n = arr2.length;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 +policeThief(arr2, n, k));                       
                                   
                                                 char                                     arr3[] =                                     new                                     char                                     []{                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ,                       
                                                 'T'                                     ,                                     'P'                                     };                       
                                                 k =                                     3                                     ;                       
                                                 n = arr3.length;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 +policeThief(arr3, n, k));                       
                                                 }                       
                         }                       
           
                         /* This code is contributed by Danish kaleem */                       

Python3

                         # Python3 program to find maximum                       
                         # number of thieves caught                       
           
                         # Returns maximum number of thieves                       
                         # that can be caught.                       
                         def                                     policeThief(arr, n, k):                       
                                                 i                                     =                                     0                       
                                                 l                                     =                                     0                       
                                                 r                                     =                                     0                       
                                                 res                                     =                                     0                       
                                                 thi                                     =                                     []                       
                                                 pol                                     =                                     []                       
           
                                                 # store indices in list                       
                                                 while                                     i < n:                       
                                                 if                                     arr[i]                                     =                                     =                                     'P'                                     :                       
                                                 pol.append(i)                       
                                                 elif                                     arr[i]                                     =                                     =                                     'T'                                     :                       
                                                 thi.append(i)                       
                                                 i                                     +                                     =                                     1                       
           
                                                 # track lowest current indices of                       
                                                 # thief: thi[l], police: pol[r]                       
                                                 while                                     l <                                     len                                     (thi)                                     and                                     r <                                     len                                     (pol):                       
                                   
                                                 # can be caught                       
                                                 if                                     (                                     abs                                     ( thi[l]                                     -                                     pol[r] ) <                                     =                                     k):                       
                                                 res                                     +                                     =                                     1                       
                                                 l                                     +                                     =                                     1                       
                                                 r                                     +                                     =                                     1                       
                                   
                                                 # increment the minimum index                       
                                                 elif                                     thi[l] < pol[r]:                       
                                                 l                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 r                                     +                                     =                                     1                       
           
                                                 return                                     res                       
           
                         # Driver program                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 arr1                                     =                                     [                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ]                       
                                                 k                                     =                                     2                       
                                                 n                                     =                                     len                                     (arr1)                       
                                                 print                                     ((                                     "Maximum thieves caught: {}"                                     .                       
                                                 format                                     (policeThief(arr1, n, k))))                       
           
                                                 arr2                                     =                                     [                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ]                       
                                                 k                                     =                                     2                       
                                                 n                                     =                                     len                                     (arr2)                       
                                                 print                                     ((                                     "Maximum thieves caught: {}"                                     .                       
                                                 format                                     (policeThief(arr2, n, k))))                       
           
                                                 arr3                                     =                                     [                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ]                       
                                                 k                                     =                                     3                       
                                                 n                                     =                                     len                                     (arr3)                       
                                                 print                                     ((                                     "Maximum thieves caught: {}"                                     .                       
                                                 format                                     (policeThief(arr3, n, k))))                       
           
                         # This code is contributed by `jahid_nadim`                       

输出

Maximum thieves caught: 2Maximum thieves caught: 3Maximum thieves caught: 3

时间复杂性： O（N） 辅助空间： O（N）

以下方法适用于O（1）空间复杂度

方法：

该方法采取以下步骤：

首先找到最左边的警察和小偷并存储索引。有两种情况：
案例1： 如果警察和小偷之间的距离<=k（给定），小偷可以被抓住，因此增加res计数器
案例2： 如果警察和小偷之间的距离>=k，则当前小偷无法被当前警察抓住
1. 对于 案例2 ，如果 警察是小偷的幕后黑手 ，我们需要找到下一个警察，并检查它是否能抓住当前的小偷
2. 如果 小偷在警察后面， 我们需要找到下一个小偷，并检查目前的警察是否能抓住小偷
重复这个过程，直到我们找到下一对警察和小偷，如果条件满足，增加结果计数器，即， 案例1。

算法： 1.将pol中警察和thi变量中小偷的当前最低指数初始化为-1。 2.找出警察和小偷的最低指数。 3如果警察或小偷的最低指数仍然为-1，则返回0。 4如果| pol–thi |<=k，则分配一部分，并找到下一个警察和小偷。 5否则将min（pol，thi）增加到发现的下一个警察或小偷。 6.重复以上两个步骤，直到找到下一个警察和小偷。 7.返回分配的数量。下面是上述算法的实现。

JAVA

                         // Java program to find maximum number of                       
                         // thieves caught                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // Returns maximum number of thieves that can                       
                                                 // be caught.                       
                                                 static                                     int                                     policeThief(                                     char                                     arr[],                                     int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 int                                     pol = -                                     1                                     , thi = -                                     1                                     , res =                                     0                                     ;                       
           
                                                 // store the first index of police in pol                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'P'                                     ) {                       
                                                 pol = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // store the first index of thief in thi                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'T'                                     ) {                       
                                                 thi = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // return 0 if no police OR no thief found                       
                                                 if                                     (thi == -                                     1                                     || pol == -                                     1                                     )                       
                                                 return                                     0                                     ;                       
           
                                                 // loop to increase res iff distance between                       
                                                 // police and thief <= k                       
                                                 while                                     (pol < n && thi < n) {                       
           
                                                 // thief can be caught                       
                                                 if                                     (Math.abs(pol - thi) <= k) {                       
           
                                                 pol++;                       
           
                                                 // to find the index of next police for next                       
                                                 // iteration                       
                                                 while                                     (pol < n && arr[pol] !=                                     'P'                                     ) {                       
                                                 pol++;                       
                                                 }                       
           
                                                 // to find the index of next thief for next                       
                                                 // iteration                       
                                                 thi = thi +                                     1                                     ;                       
                                                 while                                     (thi < n && arr[thi] !=                                     'T'                                     ) {                       
                                                 thi++;                       
                                                 ;                       
                                                 }                       
           
                                                 // increment res, as the thief has been                       
                                                 // caugh                       
                                                 res++;                       
                                                 }                       
           
                                                 // thief cannot be caught as dist > k                       
                                                 else                                     if                                     (thi < pol) {                       
           
                                                 // as index of thief is behind police,                       
                                                 // we need to find the next thief and check                       
                                                 // if it can be caught by the current police                       
                                                 //(it will be checked in the next iteration)                       
                                                 // Hence, find the index of next thief                       
                                                 thi++;                       
                                                 while                                     (thi < n && arr[thi] !=                                     'T'                                     ) {                       
                                                 thi++;                       
                                                 }                       
                                                 }                       
                                                 else                                     {                       
           
                                                 // as the index of police is behind the                       
                                                 // thief, it cannot catch the thief. Hence,                       
                                                 // we need the index of next police and                       
                                                 // check if it can catch the current thief                       
                                                 //(it will be checked in the next iteration)                       
                                                 pol++;                       
                                                 while                                     (pol < n && arr[pol] !=                                     'P'                                     ) {                       
                                                 pol++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver code starts                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 char                                     arr1[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     };                       
                                                 int                                     n = arr1.length;                       
                                                 int                                     k =                                     2                                     ;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 + policeThief(arr1, n, k));                       
           
                                                 char                                     arr2[] = {                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 n = arr2.length;                       
                                                 k =                                     2                                     ;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 + policeThief(arr2, n, k));                       
           
                                                 char                                     arr3[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 n = arr3.length;                       
                                                 k =                                     3                                     ;                       
                                                 System.out.println(                                     "Maximum thieves caught: "                       
                                                 + policeThief(arr3, n, k));                       
                                                 }                       
                         }                       
           
                         // Driver code ends                       

C++

                         // C++ program to find maximum number of thieves                       
                         // caught                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // Returns maximum number of thieves that can                       
                         // be caught.                       
                         int                                     policeThief(                                     char                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // Initialize the current lowest indices of                       
                                                 // policeman in pol and thief in thi variable as -1                       
                                                 int                                     pol = -1, thi = -1, res = 0;                       
           
                                                 // Find the lowest index of policemen                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'P'                                     ) {                       
                                                 pol = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Find the lowest index of thief                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] ==                                     'T'                                     ) {                       
                                                 thi = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // If lowest index of either policemen or thief remain                       
                                                 // -1 then return 0                       
                                                 if                                     (thi == -1 || pol == -1)                       
                                                 return                                     0;                       
           
                                                 while                                     (pol < n && thi < n) {                       
           
                                                 // can be caught                       
                                                 if                                     (                                     abs                                     (pol - thi) <= k) {                       
           
                                                 pol = pol + 1;                       
                                                 while                                     (pol < n && arr[pol] !=                                     'P'                                     ) {                       
                                                 pol = pol + 1;                       
                                                 }                       
           
                                                 thi = thi + 1;                       
                                                 while                                     (thi < n && arr[thi] !=                                     'T'                                     ) {                       
                                                 thi = thi + 1;                       
                                                 }                       
           
                                                 res++;                       
                                                 }                       
           
                                                 // increment the current min(pol , thi) to                       
                                                 // the next policeman or thief found                       
                                                 else                                     if                                     (thi < pol) {                       
                                                 thi = thi + 1;                       
                                                 while                                     (thi < n && arr[thi] !=                                     'T'                                     ) {                       
                                                 thi = thi + 1;                       
                                                 }                       
                                                 }                       
                                                 else                                     {                       
                                                 pol = pol + 1;                       
                                                 while                                     (pol < n && arr[pol] !=                                     'P'                                     ) {                       
                                                 pol = pol + 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Driver Code Starts.                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     k, n;                       
           
                                                 char                                     arr1[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     };                       
                                                 k = 2;                       
                                                 n =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr1, n, k) << endl;                       
           
                                                 char                                     arr2[] = {                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 k = 2;                       
                                                 n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr2, n, k) << endl;                       
           
                                                 char                                     arr3[] = {                                     'P'                                     ,                                     'T'                                     ,                                     'P'                                     ,                                     'T'                                     ,                                     'T'                                     ,                                     'P'                                     };                       
                                                 k = 3;                       
                                                 n =                                     sizeof                                     (arr3) /                                     sizeof                                     (arr3[0]);                       
                                                 cout <<                                     "Maximum thieves caught: "                       
                                                 << policeThief(arr3, n, k) << endl;                       
           
                                                 return                                     0;                       
                         }                       
           
                         // Driver Code Ends                       

输出

Maximum thieves caught: 2Maximum thieves caught: 3Maximum thieves caught: 3

时间复杂性： O（N） 辅助空间： O（1）

本文由 萨蒂什·斯里尼瓦斯 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章