给出了三种颜色的数组。数组元素有一个特殊的属性。每当两种不同颜色的元素彼此相邻时，它们就会合并为第三种颜色的元素。在考虑了所有可能的变换后，数组中可以有多少个最小数量的元素。 例子：
null
Input : arr[] = {R, G}Output : 1G B -> {G B} R -> RInput : arr[] = {R, G, B}Output : 2Explanation : R G B -> [R G] B -> B BORR G B -> R {G B} -> R R
情节
在你们急于解决问题之前，我们建议你们尝试不同的例子，看看你们是否能找到任何模式。
Let us see few more scenarios: 1. R R R, Output 3 2. R R G B -> R [R G] B -> [R B] B -> [G B] -> R, Output 1 3. R G R G -> [R G] R G -> [B R] G ->G G, Output 2 4. R G B B G R -> R [G B] B G R ->R [R B] G R ->[R G] G R -> [B G] R ->R R, Output 2 5. R R B B G -> R [R B] [B G] -> R [G R] -> [R B] -> G, Output 1
你在输出中找到任何模式了吗？
可能的模式
设n为数组中的元素数。无论输入是什么，我们最终总会得到三种类型的输出：
- n: 当根本不可能发生转变时
- 2: 当每种颜色的元素数都是奇数或偶数时
- 1: 当每种颜色的元素数是奇数和偶数的混合时
步骤：
1) Count the number of elements of each color.2) Then only one out of the following four cases can happen:......1) There are elements of only one color, return n.......2) There are even number of elements of each color, return 2.......3) There are odd number of elements of each color, return 2.......4) In every other case, return 1. (The elements will combine with each other repeatedly until only one of them is left)
下面是上述算法的实现。
C++
// C++ program to find count of minimum elements // after considering all possible transformations. #include <iostream> using namespace std; // Returns minimum possible elements after considering // all possible transformations. int findMin( char arr[], int n) { // Initialize counts of all colors as 0 int b_count = 0, g_count = 0, r_count = 0; // Count number of elements of different colors for ( int i = 0; i < n; i++) { if (arr[i] == 'B' ) b_count++; if (arr[i] == 'G' ) g_count++; if (arr[i] == 'R' ) r_count++; } // Check if elements are of same color if (b_count==n || g_count==n || r_count==n) return n; // If all are odd, return 2 if ((r_count&1 && g_count&1 && b_count&1) ) return 2; // If all are even, then also return 2 if (!(r_count & 1) && !(g_count & 1) && !(b_count & 1) ) return 2; // If none above the cases are true, return 1 return 1; } // Driver code int main() { char arr[] = { 'R' , 'G' , 'B' , 'R' }; int n = sizeof (arr)/ sizeof (arr[0]); cout << findMin(arr, n); return 0; } |
JAVA
import java.util.*; // Java program to find count of minimum elements // after considering all possible transformations. class solution { // Returns minimum possible elements after considering // all possible transformations. static int findMin( char arr[], int n) { // Initialize counts of all colors as 0 int b_count = 0 , g_count = 0 , r_count = 0 ; // Count number of elements of different colors for ( int i = 0 ; i < n; i++) { if (arr[i] == 'B' ) b_count++; if (arr[i] == 'G' ) g_count++; if (arr[i] == 'R' ) r_count++; } // Check if elements are of same color if (b_count==n || g_count==n || r_count==n) return n; // If all are odd, return 2 if ((r_count& 1 ) == 1 ) { if ((g_count& 1 ) == 1 ) { if ((b_count& 1 ) == 1 ) return 2 ; } } // If all are even, then also return 2 if ((r_count & 1 ) == 0 ) { if ((g_count & 1 ) == 0 ) { if ((b_count & 1 ) == 0 ) return 2 ; } } // If none above the cases are true, return 1 return 1 ; } // Driver code public static void main(String args[]) { char arr[] = { 'R' , 'G' , 'B' , 'R' }; int n = arr.length; System.out.println(findMin(arr, n)); } } // This code is contributed byte // Surendra_Gangwar |
Python 3
# Python 3 program to find count of minimum elements # after considering all possible transformations. # Returns minimum possible elements after # considering all possible transformations. def findMin(arr, n): # Initialize counts of all # colors as 0 b_count = 0 g_count = 0 r_count = 0 # Count number of elements of # different colors for i in range (n): if (arr[i] = = 'B' ): b_count + = 1 if (arr[i] = = 'G' ): g_count + = 1 if (arr[i] = = 'R' ): r_count + = 1 # Check if elements are of same color if (b_count = = n or g_count = = n or r_count = = n): return n # If all are odd, return 2 if ((r_count& 1 and g_count& 1 and b_count& 1 )): return 2 # If all are even, then also return 2 if ( not (r_count & 1 ) and not (g_count & 1 ) and not (b_count & 1 )): return 2 # If none above the cases # are true, return 1 return 1 # Driver code if __name__ = = "__main__" : arr = [ 'R' , 'G' , 'B' , 'R' ] n = len (arr) print (findMin(arr, n)) # This code is contributed # by ChitraNayal |
C#
// C# program to find count of minimum elements // after considering all possible transformations. using System; class GFG { // Returns minimum possible elements after // considering all possible transformations. static int findMin( char []arr, int n) { // Initialize counts of all colors as 0 int b_count = 0, g_count = 0, r_count = 0; // Count number of elements of different colors for ( int i = 0; i < n; i++) { if (arr[i] == 'B' ) b_count++; if (arr[i] == 'G' ) g_count++; if (arr[i] == 'R' ) r_count++; } // Check if elements are of same color if (b_count == n || g_count == n || r_count == n) return n; // If all are odd, return 2 if ((r_count&1) == 1) { if ((g_count&1) == 1) { if ((b_count&1) == 1) return 2; } } // If all are even, then also return 2 if ((r_count & 1) == 0) { if ((g_count & 1) == 0) { if ((b_count & 1) == 0) return 2; } } // If none above the cases are true, // return 1 return 1; } // Driver code public static void Main() { char []arr = { 'R' , 'G' , 'B' , 'R' }; int n = arr.Length; Console.WriteLine(findMin(arr, n)); } } // This code is contributed byte // nitin mittal |
PHP
<?php // PHP program to find count of minimum elements // after considering all possible transformations. // Returns minimum possible elements after // considering all possible transformations. function findMin( $arr , $n ) { // Initialize counts of all colors as 0 $b_count = 0; $g_count = 0; $r_count = 0; // Count number of elements of // different colors for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] == 'B' ) $b_count ++; if ( $arr [ $i ] == 'G' ) $g_count ++; if ( $arr [ $i ] == 'R' ) $r_count ++; } // Check if elements are of same color if ( $b_count == $n || $g_count == $n || $r_count == $n ) return $n ; // If all are odd, return 2 if (( $r_count & 1 && $g_count & 1 && $b_count & 1)) return 2; // If all are even, then also return 2 if (!( $r_count & 1) && !( $g_count & 1) && !( $b_count & 1) ) return 2; // If none above the cases are // true, return 1 return 1; } // Driver code $arr = array ( 'R' , 'G' , 'B' , 'R' ); $n = count ( $arr ); echo findMin( $arr , $n ); // This code is contributed by 29AjayKumar ?> |
Javascript
<script> // Javascript program to find count of minimum elements // after considering all possible transformations. // Returns minimum possible elements after considering // all possible transformations. function findMin(arr,n) { // Initialize counts of all colors as 0 let b_count = 0, g_count = 0, r_count = 0; // Count number of elements of different colors for (let i = 0; i < n; i++) { if (arr[i] == 'B' ) b_count++; if (arr[i] == 'G' ) g_count++; if (arr[i] == 'R' ) r_count++; } // Check if elements are of same color if (b_count==n || g_count==n || r_count==n) return n; // If all are odd, return 2 if ((r_count&1) == 1) { if ((g_count&1) == 1) { if ((b_count&1) == 1) return 2; } } // If all are even, then also return 2 if ((r_count & 1) == 0) { if ((g_count & 1) == 0) { if ((b_count & 1) == 0) return 2; } } // If none above the cases are true, return 1 return 1; } // Driver code let arr=[ 'R' , 'G' , 'B' , 'R' ]; let n = arr.length; document.write(findMin(arr, n)); // This code is contributed by rag2127. </script> |
输出：
1
时间复杂性： O（n） 辅助空间： O（1） 练习：
- 上述问题需要进行多少次转换？
- 可以打印元素转换的顺序吗？如果是，将采取什么方法？讨论时间和空间的复杂性
本文由 阿希什·巴恩瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
