在经过n次迭代后获得的二进制字符串中查找第i个索引字符|集2-yiteyi-C++库

给定一个十进制数m，将其转换为二进制字符串，并应用n次迭代，每次迭代0变为“01”，1变为“10”。在第n次迭代后，在字符串中查找第i个（基于索引）索引字符。例子 :

null

Input: m = 5 i = 5 n = 3Output: 1ExplanationIn the first case m = 5, i = 5, n = 3. Initially, the string is  101  ( binary equivalent of 5 )After 1st iteration -   100110After 2nd iteration - 100101101001After 3rd iteration -   100101100110100110010110 The character at index 5 is 1, so 1 is the answerInput: m = 11 i = 6 n = 4Output: 1

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 幼稚的方法 关于这个问题的讨论已经在以前的邮递 高效算法 ：第一步是确定在执行N次迭代后，第i个字符将位于哪个块。在第n次迭代中，任何两个连续字符之间的初始距离始终等于2^n。对于一般数字m，块数将为ceil（对数m）。如果M是3，字符串将被分成3个块。通过k/（2^n）查找第k个字符所在的块号，其中n是迭代次数。考虑m＝5，则二进制表示为101。然后，在任何第i次迭代中，任意两个连续标记字符之间的距离将如下所示第0次迭代：101，距离=0 第一次迭代： 1. 0 0 1. 1. 0，距离=2 第二次迭代：1001 0 110 1. 001，距离=4 第三次迭代： 1. 0010110 0 1101001 1. 0010110，距离=8 在这个例子中，k=5，n=3，所以当k为5时，Block_数将为0，因为5/（2^3）=0 最初，区块编号将是

Original String :    1   0    1Block_number    :    0   1    2

不需要生成整个字符串，只有在第i个字符所在的块中进行计算才能给出答案。让这个角色成为根 根=s[块编号] ，其中s是“m”的二进制表示形式。现在在最后一个字符串中，找到第k个字符与块号的距离，将此距离称为剩余距离。所以 剩余=k%（2^n） 将是块中第i个字符的索引。如果剩余为0，则根将是答案。现在，为了检查根是否是实际答案，请使用布尔变量轻弹无论我们是否需要翻转答案。下面的算法将给出第i个索引处的字符。

bool flip = true;while(remaining > 1){   if( remaining is odd )         flip = !flip       remaining = remaining/2;}

图片[1]-在经过n次迭代后获得的二进制字符串中查找第i个索引字符|集2-yiteyi-C++库

以下是上述方法的实施情况：

C++

                         // C++ program to find i’th Index character                       
                         // in a binary string obtained after n iterations                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find the i-th character                       
                         void                                     KthCharacter(                                     int                                     m,                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // distance between two consecutive                       
                                                 // elements after N iterations                       
                                                 int                                     distance =                                     pow                                     (2, n);                       
                                                 int                                     Block_number = k / distance;                       
                                                 int                                     remaining = k % distance;                       
           
                                                 int                                     s[32], x = 0;                       
           
                                                 // binary representation of M                       
                                                 for                                     (; m > 0; x++) {                       
                                                 s[x] = m % 2;                       
                                                 m = m / 2;                       
                                                 }                       
           
                                                 // kth digit will be derived from root for sure                       
                                                 int                                     root = s[x - 1 - Block_number];                       
           
                                                 if                                     (remaining == 0) {                       
                                                 cout << root << endl;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Check whether there is need to                       
                                                 // flip root or not                       
                                                 bool                                     flip =                                     true                                     ;                       
                                                 while                                     (remaining > 1) {                       
                                                 if                                     (remaining & 1) {                       
                                                 flip = !flip;                       
                                                 }                       
                                                 remaining = remaining >> 1;                       
                                                 }                       
           
                                                 if                                     (flip) {                       
                                                 cout << !root << endl;                       
                                                 }                       
                                                 else                                     {                       
                                                 cout << root << endl;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     m = 5, k = 5, n = 3;                       
                                                 KthCharacter(m, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find ith                       
                         // Index character in a binary                       
                         // string obtained after n iterations                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to find                       
                         // the i-th character                       
                         static                                     void                                     KthCharacter(                                     int                                     m,                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 // distance between two                       
                                                 // consecutive elements                       
                                                 // after N iterations                       
                                                 int                                     distance = (                                     int                                     )Math.pow(                                     2                                     , n);                       
                                                 int                                     Block_number = k / distance;                       
                                                 int                                     remaining = k % distance;                       
           
                                                 int                                     s[] =                                     new                                     int                                     [                                     32                                     ];                       
                                                 int                                     x =                                     0                                     ;                       
           
                                                 // binary representation of M                       
                                                 for                                     (; m >                                     0                                     ; x++)                       
                                                 {                       
                                                 s[x] = m %                                     2                                     ;                       
                                                 m = m /                                     2                                     ;                       
                                                 }                       
           
                                                 // kth digit will be                       
                                                 // derived from root                       
                                                 // for sure                       
                                                 int                                     root = s[x -                                     1                                     -                       
                                                 Block_number];                       
           
                                                 if                                     (remaining ==                                     0                                     )                       
                                                 {                       
                                                 System.out.println(root);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Check whether there is                       
                                                 // need to flip root or not                       
                                                 Boolean flip =                                     true                                     ;                       
                                                 while                                     (remaining >                                     1                                     )                       
                                                 {                       
                                                 if                                     ((remaining &                                     1                                     ) >                                     0                                     )                       
                                                 {                       
                                                 flip = !flip;                       
                                                 }                       
                                                 remaining = remaining >>                                     1                                     ;                       
                                                 }                       
           
                                                 if                                     (flip)                       
                                                 {                       
                                                 System.out.println((root >                                     0                                     )?                                     0                                     :                                     1                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 System.out.println(root);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     m =                                     5                                     , k =                                     5                                     , n =                                     3                                     ;                       
                                                 KthCharacter(m, n, k);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

Python3

                         # Python3 program to find                       
                         # i’th Index character in                       
                         # a binary string obtained                       
                         # after n iterations                       
           
                         # Function to find                       
                         # the i-th character                       
                         def                                     KthCharacter(m, n, k):                       
           
                                                 # distance between two                       
                                                 # consecutive elements                       
                                                 # after N iterations                       
                                                 distance                                     =                                     pow                                     (                                     2                                     , n)                       
                                                 Block_number                                     =                                     int                                     (k                                     /                                     distance)                       
                                                 remaining                                     =                                     k                                     %                                     distance                       
           
                                                 s                                     =                                     [                                     0                                     ]                                     *                                     32                       
                                                 x                                     =                                     0                       
           
                                                 # binary representation of M                       
                                                 while                                     (m >                                     0                                     ) :                       
                                                 s[x]                                     =                                     m                                     %                                     2                       
                                                 m                                     =                                     int                                     (m                                     /                                     2                                     )                       
                                                 x                                     +                                     =                                     1                       
                                   
                                                 # kth digit will be derived                       
                                                 # from root for sure                       
                                                 root                                     =                                     s[x                                     -                                     1                                     -                                     Block_number]                       
                                   
                                                 if                                     (remaining                                     =                                     =                                     0                                     ):                       
                                                 print                                     (root)                       
                                                 return                       
                                   
                                                 # Check whether there                       
                                                 # is need to flip root                       
                                                 # or not                       
                                                 flip                                     =                                     True                       
                                                 while                                     (remaining >                                     1                                     ):                       
                                                 if                                     (remaining &                                     1                                     ):                       
                                                 flip                                     =                                     not                                     (flip)                       
                                   
                                                 remaining                                     =                                     remaining >>                                     1                       
                                   
                                                 if                                     (flip) :                       
                                                 print                                     (                                     not                                     (root))                       
                                   
                                                 else                                     :                       
                                                 print                                     (root)                       
                                   
                         # Driver Code                       
                         m                                     =                                     5                       
                         k                                     =                                     5                       
                         n                                     =                                     3                       
                         KthCharacter(m, n, k)                       
           
                         # This code is contributed                       
                         # by smita                       

C#

                         // C# program to find ith                       
                         // Index character in a                       
                         // binary string obtained                       
                         // after n iterations                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to find                       
                         // the i-th character                       
                         static                                     void                                     KthCharacter(                                     int                                     m,                       
                                                 int                                     n,                       
                                                 int                                     k)                       
                         {                       
                                                 // distance between two                       
                                                 // consecutive elements                       
                                                 // after N iterations                       
                                                 int                                     distance = (                                     int                                     )Math.Pow(2, n);                       
                                                 int                                     Block_number = k / distance;                       
                                                 int                                     remaining = k % distance;                       
           
                                                 int                                     []s =                                     new                                     int                                     [32];                       
                                                 int                                     x = 0;                       
           
                                                 // binary representation of M                       
                                                 for                                     (; m > 0; x++)                       
                                                 {                       
                                                 s[x] = m % 2;                       
                                                 m = m / 2;                       
                                                 }                       
           
                                                 // kth digit will be                       
                                                 // derived from root                       
                                                 // for sure                       
                                                 int                                     root = s[x - 1 -                       
                                                 Block_number];                       
           
                                                 if                                     (remaining == 0)                       
                                                 {                       
                                                 Console.WriteLine(root);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Check whether there is                       
                                                 // need to flip root or not                       
                                                 Boolean flip =                                     true                                     ;                       
                                                 while                                     (remaining > 1)                       
                                                 {                       
                                                 if                                     ((remaining & 1) > 0)                       
                                                 {                       
                                                 flip = !flip;                       
                                                 }                       
                                   
                                                 remaining = remaining >> 1;                       
                                                 }                       
           
                                                 if                                     (flip)                       
                                                 {                       
                                                 Console.WriteLine(!(root > 0));                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 Console.WriteLine(root);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     m = 5, k = 5, n = 3;                       
                                                 KthCharacter(m, n, k);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to find i’th Index character                       
                         // in a binary string obtained after n iterations                       
           
                         // Function to find the i-th character                       
                         function                                     KthCharacter(                                     $m                                     ,                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 // distance between two consecutive                       
                                                 // elements after N iterations                       
                                                 $distance                                     = pow(2,                                     $n                                     );                       
                                                 $Block_number                                     =                                     intval                                     (                                     $k                                     /                                     $distance                                     );                       
                                                 $remaining                                     =                                     $k                                     %                                     $distance                                     ;                       
           
                                                 $s                                     =                                     array                                     (32);                       
                                                 $x                                     = 0;                       
           
                                                 // binary representation of M                       
                                                 for                                     (;                                     $m                                     > 0;                                     $x                                     ++)                       
                                                 {                       
                                                 $s                                     [                                     $x                                     ] =                                     $m                                     % 2;                       
                                                 $m                                     =                                     intval                                     (                                     $m                                     / 2);                       
                                                 }                       
           
                                                 // kth digit will be derived from                       
                                                 // root for sure                       
                                                 $root                                     =                                     $s                                     [                                     $x                                     - 1 -                                     $Block_number                                     ];                       
           
                                                 if                                     (                                     $remaining                                     == 0)                       
                                                 {                       
                                                 echo                                     $root                                     .                                     ""                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Check whether there is need to                       
                                                 // flip root or not                       
                                                 $flip                                     = true;                       
                                                 while                                     (                                     $remaining                                     > 1)                       
                                                 {                       
                                                 if                                     (                                     $remaining                                     & 1)                       
                                                 {                       
                                                 $flip                                     = !                                     $flip                                     ;                       
                                                 }                       
                                                 $remaining                                     =                                     $remaining                                     >> 1;                       
                                                 }                       
           
                                                 if                                     (                                     $flip                                     )                       
                                                 {                       
                                                 echo                                     !                                     $root                                     .                                     ""                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 echo                                     $root                                     .                                     ""                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         $m                                     = 5;                       
                         $k                                     = 5;                       
                         $n                                     = 3;                       
                         KthCharacter(                                     $m                                     ,                                     $n                                     ,                                     $k                                     );                       
           
                         // This code is contributed by ita_c                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find ith                       
                         // Index character in a binary                       
                         // string obtained after n iterations                       
           
                         // Function to find                       
                         // the i-th character                       
                         function                                     KthCharacter(m, n, k)                       
                         {                       
           
                                                 // distance between two                       
                                                 // consecutive elements                       
                                                 // after N iterations                       
                                                 let distance = Math.pow(2, n);                       
                                                 let Block_number = Math.floor(k / distance);                       
                                                 let remaining = k % distance;                       
                                   
                                                 let s =                                     new                                     Array(32).fill(0);                       
                                                 let x = 0;                       
                                   
                                                 // binary representation of M                       
                                                 for                                     (; m > 0; x++)                       
                                                 {                       
                                                 s[x] = m % 2;                       
                                                 m = Math.floor(m / 2);                       
                                                 }                       
                                   
                                                 // kth digit will be                       
                                                 // derived from root                       
                                                 // for sure                       
                                                 let root = s[x - 1 -                       
                                                 Block_number];                       
                                   
                                                 if                                     (remaining == 0)                       
                                                 {                       
                                                 document.write(root);                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Check whether there is                       
                                                 // need to flip root or not                       
                                                 let flip =                                     true                                     ;                       
                                                 while                                     (remaining > 1)                       
                                                 {                       
                                                 if                                     ((remaining & 1) > 0)                       
                                                 {                       
                                                 flip = !flip;                       
                                                 }                       
                                                 remaining = remaining >> 1;                       
                                                 }                       
                                   
                                                 if                                     (flip)                       
                                                 {                       
                                                 document.write((root > 0)?0:1);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 document.write(root);                       
                                                 }                       
                         }                       
           
                         // driver program                       
                                                 let m = 5, k = 5, n = 3;                       
                                                 KthCharacter(m, n, k);                       
                                   
                                                 // This code is contributed by susmitakundugoaldanga.                       
                         </script>                       

输出：

时间复杂性： O（logz），其中Z是N次迭代后初始连续位之间的距离 辅助空间： O（1）

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

THE END

技术文章