给定一个大小为n的数组,其规格如下:
- 数组中的每个元素都包含一名警察或一名小偷。
- 每个警察只能抓一个小偷。
- 警察抓不到距离警察超过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,则当前小偷无法被当前警察抓住
- 对于 案例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主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。