Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1545. Find Kth Bit in Nth Binary String

---

參考資訊：
https://algo.monster/liteproblems/1545
https://www.cnblogs.com/cnoodle/p/18486891

題目：


解答一：

class Solution {
public:
    char findKthBit(int n, int k) {
        string s = "0";

        for (int i = 1; i <= n; ++i) {
            string t = s;
            string r = s;

            for (int j = 0; j < r.size(); ++j) {
                r[j] = (r[j] == '0') ? '1' : '0';
            }
            reverse(r.begin(), r.end());

            s = t + "1" + r;
        }

        return s[k - 1];
    }
};

解法二：

class Solution {
public:
    char findKthBit(int n, int k) {
        function<int(int, int)> dfs = [&](int n, int k) {
            if (k == 1) {
                return 0;
            }

            if ((k & (k - 1)) == 0) {
                return 1;
            }

            int len = 1 << n;
            if ((k << 1) < (len - 1)) {
                return dfs(n - 1, k);
            }

            return dfs(n - 1, len - k) ^ 1;
        };

        return '0' + dfs(n, k);
    }
};