本文概述
- 建议:在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
- C ++
- Java
- Python3
- C#
- PHP
例子:
Input: m = 5 i = 5 n = 3
Output: 1
Explanation
In the first case m = 5, i = 5, n = 3.
Initially, the string is101( binary equivalent of 5 )
After 1st iteration -100110
After 2nd iteration - 100101101001
After 3rd iteration -100101100110100110010110
The character at index 5 is 1, so 1 is the answerInput: m = 11 i = 6 n = 4
Output: 1
推荐:请尝试使用{IDE}首先, 在继续解决方案之前。 一种天真的方法这个问题已经在以前发布。
高效算法:第一步将是查找执行N次迭代后第i个字符位于哪个块。在第n个迭代中, 任意两个连续字符之间的距离最初始终将等于2 ^ n。对于一般数字m, 块数将为ceil(log m)。如果M为3, 则字符串将分为3个块。找出第k个字符位于k /(2 ^ n)处的块号, 其中n是迭代次数。假设m = 5, 则二进制表示为101。则在第i次迭代中, 任意2个连续的标记字符之间的距离如下
第0次迭代:101, 距离= 0
第一次迭代:
1
0
0
1
1
0, 距离= 2
第2次迭代:1001
0
110
1
001, 距离= 4
第三次迭代:
1
0010110
0
1101001
1
0010110, 距离= 8
在示例中k = 5和n = 3, 所以当k为5时, Block_number将为0, 因为5 /(2 ^ 3)= 0
最初, 块号为
Original String :101
Block_number:012
无需生成整个字符串, 只需在存在第i个字符的块中进行计算即可得出答案。让这个角色成为根根= s [Block_number], 其中s是" m"的二进制表示。现在在最后一个字符串中, 找到第k个字符与程序段号的距离, 将此距离称为剩余距离。所以剩余= k%(2 ^ n)将是块中第i个字符的索引。如果剩余为0, 则根为答案。现在, 为了检查根是否是实际答案, 请使用布尔变量翻转无论我们是否需要翻转答案。遵循以下算法将在第i个索引处给出字符。
bool flip = true;
while(remaining >
1){
if( remaining is odd )
flip = !flip
remaining = remaining/2;
}
文章图片
下面是上述方法的实现:
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 % distances = [ 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 >
>
1if (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 . "\n" ;
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 . "\n" ;
}
else
{
echo $root . "\n" ;
}
}// Driver Code
$m = 5;
$k = 5;
$n = 3;
KthCharacter( $m , $n , $k );
// This code is contributed by ita_c
?>
输出如下:
1
【在n次迭代后获得的二进制字符串中找到第i个索引字符|s2】时间复杂度:O(log Z), 其中Z是N次迭代后初始连续位之间的距离
推荐阅读
- JavaScript声明提前介绍和示例解析
- 在数组中查找第二大元素(详细代码实现)
- Unix和Linux系统性能组件和性能工具详解教程
- Unix和Linux用户管理介绍和操作教程
- Unix和Linux文件系统管理基本操作教程
- Linux开发必备!vim编辑器中文手册和参考文档pdf下载
- Unix和Linux的vi编辑器操作和用法完全解读教程
- Unix和Linux常用网络通信工具使用介绍
- Unix和Linux进程管理操作和使用原理介绍