警察抓小偷

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

null
  1. 数组中的每个元素都包含一名警察或一名小偷。
  2. 每个警察只能抓一个小偷。
  3. 警察抓不到距离警察超过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. 首先找到最左边的警察和小偷并存储索引。有两种情况:
  2. 案例1: 如果警察和小偷之间的距离<=k(给定),小偷可以被抓住,因此增加res计数器
  3. 案例2: 如果警察和小偷之间的距离>=k,则当前小偷无法被当前警察抓住
    1. 对于 案例2 ,如果 警察是小偷的幕后黑手 ,我们需要找到下一个警察,并检查它是否能抓住当前的小偷
    2. 如果 小偷在警察后面, 我们需要找到下一个小偷,并检查目前的警察是否能抓住小偷
  4. 重复这个过程,直到我们找到下一对警察和小偷,如果条件满足,增加结果计数器,即, 案例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
喜欢就支持一下吧
点赞8 分享