当前位置:网站首页>LeetCode 1545. Find the k-th bit in the nth binary string
LeetCode 1545. Find the k-th bit in the nth binary string
2022-07-06 16:42:00 【Daylight629】
1545. Find out the N Of the binary strings K position
Here are two positive integers n
and k
, Binary string Sn
The formation rules of are as follows :
S1 = "0"
- When
i > 1
when ,Si = Si-1 + "1" + reverse(invert(Si-1))
among +
Indicates series operation ,reverse(x)
Return to reverse x
The resulting string , and invert(x)
Will flip x Every one of you (0 Turn into 1, and 1 Turn into 0).
for example , The first of the sequences described above 4 The strings are :
S1 = "0"
S2 = "0**1**1"
S3 = "011**1**001"
S4 = "0111001**1**0110001"
Please return Sn
Of The first k
Bit character , Topic data assurance k
It must be Sn
Within the length range .
Example 1:
Input :n = 3, k = 1
Output :"0"
explain :S3 by "0111001", Its first 1 Position as "0" .
Example 2:
Input :n = 4, k = 11
Output :"1"
explain :S4 by "011100110110001", Its first 11 Position as "1" .
Example 3:
Input :n = 1, k = 1
Output :"0"
Example 4:
Input :n = 2, k = 3
Output :"1"
Tips :
1 <= n <= 20
1 <= k <= 2n - 1
Two 、 Method 1
recursive
class Solution {
public char findKthBit(int n, int k) {
if (k == 1) {
return '0';
}
int mid = 1 << (n - 1);
if (k == mid) {
return '1';
} else if (k < mid) {
return findKthBit(n - 1, k);
} else {
k = mid * 2 - k;
return invert(findKthBit(n - 1, k));
}
}
public char invert(char a) {
return (char) ('0' + '1' - a);
}
}
Complexity analysis
Time complexity :O(n). character string S_n The length of is 2^n-1, Each recursive call can reduce the search range by half , So the time complexity is zero O(log2n)=O(n).
Spatial complexity :O(n). The space complexity mainly depends on the stack space generated by recursive calls , The number of recursive call layers will not exceed n.
边栏推荐
- Log statistics (double pointer)
- 生成随机密码/验证码
- Installation and configuration of MariaDB
- 提交Spark应用的若干问题记录(sparklauncher with cluster deploy mode)
- Educational Codeforces Round 130 (Rated for Div. 2)A~C
- Codeforces Round #798 (Div. 2)A~D
- Chapter III principles of MapReduce framework
- Kubernetes集群部署
- 300th weekly match - leetcode
- Codeforces round 797 (Div. 3) no f
猜你喜欢
Chapter 1 overview of MapReduce
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
Business system compatible database oracle/postgresql (opengauss) /mysql Trivia
音视频开发面试题
视频压缩编码和音频压缩编码基本原理
CMake速成
两个礼拜速成软考中级软件设计师经验
业务系统从Oracle迁移到openGauss数据库的简单记录
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
ffmpeg命令行使用
随机推荐
Educational Codeforces Round 130 (Rated for Div. 2)A~C
ffmpeg命令行使用
Basic principles of video compression coding and audio compression coding
Hbuilder x format shortcut key settings
第2章 HFDS的Shell操作
Research Report on market supply and demand and strategy of China's four seasons tent industry
去掉input聚焦时的边框
MP4格式详解
Summary of game theory
Market trend report, technical innovation and market forecast of tabletop dishwashers in China
Summary of FTP function implemented by qnetworkaccessmanager
Codeforces Round #802(Div. 2)A~D
Useeffect, triggered when function components are mounted and unloaded
Cmake Express
解决Intel12代酷睿CPU【小核载满,大核围观】的问题(WIN11)
Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
js时间函数大全 详细的讲解 -----阿浩博客
Codeforces Round #797 (Div. 3)无F
使用jq实现全选 反选 和全不选-冯浩的博客
< li> dot style list style type