題目

• Problem: 100160. 價值和小于等于 K 的最大數(shù)字
• 給你一個整數(shù) k 和一個整數(shù) x 。
• 令 s 為整數(shù) num 的下標(biāo)從 1 開始的二進(jìn)制表示。我們說一個整數(shù) num 的 價值 是滿足 i % x == 0 且 s[i] 是 設(shè)置位 的 i 的數(shù)目。
• 請你返回 最大 整數(shù) num ，滿足從 1 到 num 的所有整數(shù)的 價值 和小于等于 k 。
• 注意：
  • 一個整數(shù)二進(jìn)制表示下 設(shè)置位 是值為 1 的數(shù)位。
  • 一個整數(shù)的二進(jìn)制表示下標(biāo)從右到左編號，比方說如果 s == 11100 ，那么 s[4] == 1 且 s[2] == 0 。
  • 1 <= k <= 10 ^ 15
  • 1 <= x <= 8

思路

Java + 二分答案 + 規(guī)律

第 1 步：

• 首先 [1, maxNum] 在確定 x 后顯然滿足"價值和"單調(diào)非遞減，因此可以二分最大值 maxNum
• 其次需要確定 [1, maxNum] 在確定 x 的"價值和"就行

第 2 步：

• 二分答案確定上下界：
  • k 最小為 1，x 最小為 1 代表每一位均統(tǒng)計，此時結(jié)果最小、即下界為 1
  • k 最大為 1e15，x 最大為 8 代表每 8 位統(tǒng)計一次、即每 2^8 個數(shù)最少會記錄 1 次，此時結(jié)果最大，而開始的 [1, 2^8-1] 在 x=8 時不統(tǒng)計，因此上界就是 (k+1)*2^8-1

第 3 步：

• [1, maxNum] 在 x 下的"價值和"可以找規(guī)律，我們先寫出 [1, 8] 的二進(jìn)制：
• 0001
• 0010
• 0011
• 0100
• 0101
• 0110
• 0111
• 1000
• 按題意最后一位往前看（可以多寫幾位來看）：
  • 第 1 位是先零位 0 然后"一位 1 一位 0"的 10 依次循環(huán)
  • 第 2 位是先一位 0 然后"兩位 1 兩位 0"的 10 依次循環(huán)
  • 第 3 位是先三位 0 然后"四位 1 四位 0"的 10 依次循環(huán)
  • 第 4 位是先七位 0 然后"八位 1 八位 0"的 10 依次循環(huán)
• 如果我們前面加上 0，可以得到第 i 位是 “2^(i-1) 位 0 與 2^(i-1) 位 1” 的 01 依次循環(huán)

第 4 步：

• 對于 [1, maxNum] 先轉(zhuǎn)化為 [0, maxNum] 總共 maxNum+1 個數(shù)，
• 然后循環(huán) long 總共的 63 位 i，當(dāng)滿足 (i % x == 0) 時，記錄第 i 位"價值和"，
• 分為前面循環(huán)的 1 + 可能有的最后一個不完整的循環(huán) 1
• 前面循環(huán)的 1，先除循環(huán)再乘完整的 1：(maxNum + 1) / 2^i * 2^(i-1)
• 可能有的最后一個不完整的循環(huán) 1，先減去完整循環(huán)再減去開頭的 0：max((maxNum + 1) % 2^i - 2^(i-1), 0)

復(fù)雜度

時間復(fù)雜度:

時間復(fù)雜度： $O(63?log(k<<x))$

空間復(fù)雜度:

空間復(fù)雜度： $O(n)$文章來源地址http://www.zghlxwxcb.cn/news/detail-805692.html

Code

class Solution {
    /**
     * Java + 二分答案 + 規(guī)律：
     *
     * 第 1 步：
     * 首先 [1, maxNum] 在確定 x 后顯然滿足"價值和"單調(diào)非遞減，因此可以二分最大值 maxNum，
     * 其次需要確定 [1, maxNum] 在確定 x 的"價值和"就行
     *
     * 第 2 步：
     * 二分答案確定上下界：
     *     * k 最小為 1，x 最小為 1 代表每一位均統(tǒng)計，此時結(jié)果最小、即下界為 1
     *     * k 最大為 1e15，x 最大為 8 代表每 8 位統(tǒng)計一次、即每 2^8 個數(shù)最少會記錄 1 次，此時結(jié)果最大，而開始的 [1, 2^8-1] 在 x=8 時不統(tǒng)計，因此上界就是 (k+1)*2^8-1
     *
     * 第 3 步：
     * [1, maxNum] 在 x 下的"價值和"可以找規(guī)律，我們先寫出 [1, 8] 的二進(jìn)制：
     * 0001
     * 0010
     * 0011
     * 0100
     * 0101
     * 0110
     * 0111
     * 1000
     * 按題意最后一位往前看（可以多寫幾位來看）：
     *     * 第 1 位是先零位 0 然后"一位 1 一位 0"的 10 依次循環(huán)
     *     * 第 2 位是先一位 0 然后"兩位 1 兩位 0"的 10 依次循環(huán)
     *     * 第 3 位是先三位 0 然后"四位 1 四位 0"的 10 依次循環(huán)
     *     * 第 4 位是先七位 0 然后"八位 1 八位 0"的 10 依次循環(huán)
     * 如果我們前面加上 0，可以得到第 i 位是 "2^(i-1) 位 0 與 2^(i-1) 位 1" 的 01 依次循環(huán)，
     *
     * 第 4 步：
     * 對于 [1, maxNum] 先轉(zhuǎn)化為 [0, maxNum] 總共 maxNum+1 個數(shù)，
     * 然后循環(huán) long 總共的 63 位 i，當(dāng)滿足 (i % x == 0) 時，記錄第 i 位"價值和"，
     * 分為前面循環(huán)的 1 + 可能有的最后一個不完整的循環(huán) 1
     * 前面循環(huán)的 1，先除循環(huán)再乘完整的 1：(maxNum + 1) / 2^i * 2^(i-1)
     * 可能有的最后一個不完整的循環(huán) 1，先減去完整循環(huán)再減去開頭的 0：max((maxNum + 1) % 2^i - 2^(i-1), 0)
     * 時間復(fù)雜度：O（63*log（k<<x）），空間復(fù)雜度：O（1）
     *
     */
    public long findMaximumNumber(long k, int x) {
        // 二分答案，確定上下界
        long left = 1;
        long right = (k + 1) << x - 1;

        long res = 1;
        while (left <= right) {
            // 避免加法溢出
            long mid = ((right - left) >> 1) + left;
            // 獲取 [1, mid] 在 x 下的"價值和"
            long count = getCount(mid, x);
            if (count <= k) {
                res = mid;
                left = mid + 1;

            } else {
                right = mid - 1;
            }
        }

        return res;
    }

    /**
     * 獲取 [1, maxNum] 在 x 下的"價值和"
     */
    private long getCount(long maxNum, int x) {
        long res = 0;
        // long 的最大值有 63 位
        for (int i = 1; i <= 63; i++) {
            if (i % x == 0) {
                // 獲取每個循環(huán)之和
                res += (maxNum + 1) / (1L << i) * (1L << i - 1);
                // 獲取可能有的最后一個不完整的循環(huán)
                res += Math.max((maxNum + 1) % (1L << i) - (1L << i - 1), 0);
            }
        }

        return res;
    }
}

到了這里，關(guān)于Leetcode 第 380 場周賽 Problem C 價值和小于等于 K 的最大數(shù)字（Java + 二分答案 + 規(guī)律）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！