leetcode 1545. 找出第 N 个二进制字符串中的第 K 位

╰+攻爆jí腚メ 2022-11-27 03:07 144阅读 0赞

给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：

S1 = "0"  
    当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）

例如，符合上述描述的序列的前 4 个字符串依次是：

S1 = "0"  
    S2 = "011"  
    S3 = "0111001"  
    S4 = "011100110110001"

请你返回  Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

示例 1：

输入：n = 3, k = 1  
输出："0"  
解释：S3 为 "0111001"，其第 1 位为 "0" 。

从字符串的构造方式可以看出，Si的长度大小为2^i-1。其中第2^(i-1)位一定是1，小于2^(i-1)位置的字符串和S(i-1)串的相同，因此可以转为在S(i-1)中找第k个。而大于2^(i-1)位置的字符串是S(i-1)字符串取反后反转的结果，因此也可以转化为在S(i-1)寻找。

k<=2^(i-1)的情况很容易处理。下面说一下如何处理k>2^(i-1)

因为需要将S(i-1)反转，那么在S(i)中的第k个位置，应该对应于S(i-1)中的第2^i-k个位置。（可以自己找样例测试）

至于取反操作，只需要将0变成1,1变成0即可。

因此，这题其实就是一个二分。

class Solution {
    private:
        char invert(char ch) {
            if(ch == '0') { return '1'; }
            else          { return '0'; }
        }
    public:
        char findKthBit(int n, int k) {
            if(n == 1) { return '0'; }
            int mid = (1<<(n-1));
            if(k == mid) { return '1'; }
            if(k < mid) { return findKthBit(n-1, k); }
            return invert(findKthBit(n-1, (1<<n) - k)); 
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关找出数组中第k大的数

package com.threeTop.www; /** * 找出数组中第k大的数 * @author wjgs ...

╰半夏微凉°/ 2024年04月17日 14:47/ 0 赞/ 57 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 170 阅读

相关 leetcode 400. 第N个数字

题解来自于 [https://leetcode-cn.com/problems/nth-digit/comments/][https_leetcode-cn.com_pro

刺骨的言语ヽ痛彻心扉/ 2022年12月13日 14:29/ 0 赞/ 152 阅读

相关 leetcode 1545. 找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下： S1 = "0" 当 i > 1 时，Si = Si-1 + "1" + rev

╰+攻爆jí腚メ/ 2022年11月27日 03:07/ 0 赞/ 145 阅读

相关 Find Kth Bit in Nth Binary String（C++找出第 N 个二进制字符串中的第 K 位）

（1）模拟法 class Solution { public: string helper(string s) {

我不是女神ヾ/ 2022年10月16日 15:24/ 0 赞/ 124 阅读

相关找出单向链表中倒数第k个节点的算法

有两种方式，使用递归和非递归算法一（非递归方式）：最简单的方式是从头开始遍历。算法二（递归方式）打印出第k个元素的值。 public static

小咪咪/ 2022年07月26日 00:05/ 0 赞/ 120 阅读

相关倒数第N个字符串

Problem Description：给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。

清疚/ 2022年05月28日 11:44/ 0 赞/ 162 阅读

相关找出第k个最小的元素

/\ \题目：编写程序，从数组x\[0...n-1\]中找出第k个最小的元素。算法可以对x中的元素进行排序 \/ \include<stdio.h> \inclu

电玩女神/ 2022年04月11日 14:25/ 0 赞/ 189 阅读

相关第十二天：《LeetCode一天一例》-----n个不同的数组成n!个序列，找出第k个（又名Permutation Sequence）（python实现）

n!个序列中找第k个 > 题目：给定一个n = 7，代表（1， 2， 3， 4， 5， 6， 7）。它们能组成7！个不同的序列。。在给定一个k值，找

古城微笑少年丶/ 2022年03月06日 15:05/ 0 赞/ 164 阅读

相关找出数组[1...n]中第k小元素

1 //问题描述：试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素) 2 3 includ

古城微笑少年丶/ 2022年01月08日 02:15/ 0 赞/ 252 阅读