LeetCode 1256 - Encode Number

https://www.acwing.com/file_system/file/content/whole/index/content/150815/

Given a non-negative integer num, Return its encoding string.

The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:

Example 1:

Input: num = 23
Output: "1000"

Example 2:

Input: num = 107
Output: "101100"

Constraints:

• 0 <= num <= 10^9

http://qiujiaqi.cn/leetcode/encode-number/

• 这题一开始我的思路是，加密后的字符串长度 len 可以用 𝑙𝑜𝑔2(𝑛+1)$lo{g}_2(n+1)$ 计算，而尾值即可用 (n + 1) 对 最大的 2 的幂的数求余得出，即 (𝑛+1)mod2𝑙𝑒𝑛$(n+1)\mathrm{mod}{2}^{len}$，将这个尾值转化为二进制，再往这个尾值头部插入 0，直至长度为 len
• 例如：
  6，加密后长度为 𝑙𝑜𝑔2(6+1)$lo{g}_2(6+1)$，即 2，尾值为 (6+1)mod22$(6+1)\mathrm{mod}{2}^2$，即为 11，长度已经足够不需补 0，得 11
  7，加密后长度为 𝑙𝑜𝑔2(7+1)$lo{g}_2(7+1)$，即 3，尾值为 (7+1)mod23$(7+1)\mathrm{mod}{2}^3$，即为 0，往头部补 0，得 000
  8，加密后长度为 𝑙𝑜𝑔2(8+1)$lo{g}_2(8+1)$，即 3，尾值为 (8+1)mod23$(8+1)\mathrm{mod}{2}^3$，即为 1，往头部补 0，得 001

    public String encode(int num) {
        if (num == 0) {
            return "";
        }
        int len = (int) (Math.log(num + 1) / Math.log(2));
        int r = (int) ((num + 1) % Math.pow(2, len));
        String res = "";
        String tail = Integer.toString(r, 2);
        for (int i = 0; i < len - tail.length(); i++) {
            res += "0";
        }
        res += tail;
        return res;
    }

(找规律) $O(\log n)$

1. 可以很容易发现，编码的字符串在每个长度 l 内都是按 0 到 $2^l-1$ 的方式排列的。
2. 首先寻找最终编码字符串的长度，寻找长度的过程中，让目标值减去当前长度能编码字符串的数量。

时间复杂度

• 寻找长度的时间复杂度为 $O(\log n)$，构造答案的时间复杂度为 $O(\log n)$。
• 故最终时间复杂度为 $O(\log n)$。

空间复杂度

• 需要额外 $O(\log n)$ 的空间存储答案。

    string encode(int num) {
        int len = 0;
        while (num >= (1 << len)) {
            num -= (1 << len);
            len++;
        }

        string ans;
        for (int i = 0; i < len; i++, num >>= 1)
            if (num & 1)
                ans += '1';
            else
                ans += '0';

        reverse(ans.begin(), ans.end());
        return ans;
    }




https://leetcode.jp/leetcode-1256-encode-number-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/

本题需要先观察出给定的加密规律，与普通的二进制数不同，当出现进位时，所有位数的值要变为0，比如：11加1后不是100，而应该是000，同理111加一后是0000，虽然在二进制中000与0000都代表0，但在本题中因为位数不同而所代表的的意义也是不同的。

接下来再看，1位数能代表2个数字，0和1，2位数能代表4个数，00，01，10，11。以此类推可得到：n位数能代表2的n次方个数字。通过题目给出的数字，首先我们可以算出该数字加密后的位数，方法很简单，在满足num大于等于0的前提下，不断的用num减去2的n次方（n>=0, n++），直到不能再相减为止，此时的n即为加密后数字的位数，同时num剩下的值即是当前位数长度下的二进制数字。（注意高位不足的地方需要补0）

public String encode(int num) {

    int length=0; // 加密后的位数

    while(true){

        // 计算当前位数下能有多少数字

        int n=(int)Math.pow(2,length);

        // 如果num不足以表示下n个数字，退出

        if(num-n<0) break;

        num-=n; // num减去n，继续循环

        length++; // 位数加一

    }

    String res=""; // 返回结果

    for(int i=0;i<length;i++){ // 循环位数计算二进制

        res = num % 2 + ""+ res;

        num /= 2;

    }

    return res;

}

X.

https://blog.csdn.net/qq_17550379/article/details/103109066

 找规律的问题，规律也非常的简单。通过观察

bin(0 + 1) -> 1
bin(1 + 1) -> 10
bin(2 + 1) -> 11
bin(3 + 1) -> 100
bin(4 + 1) -> 101

不难发现结果就是num+1的二进制取出第一位即可。当然也可以通过数学来得到，首先不难发现相同位数的数成等比数列

0位 -> 1
1位 -> 2
2位 -> 4

那么通过等于数列求和公式很容易得到每位的第一个数为2^n - 1（其中n表示位数），那么num显然就可以表示为bin(num + 1 - 2^n)，而n就是bin(num)的最高位1所在的位置+1，那么为了方便计算可以忽略2^n，最后的结果就是bin(num + 1)去除最高位的结果。

class Solution:
    def encode(self, num: int) -> str:
        return bin(num + 1)[3:]

• 一开始参赛写出来很开心，最后发现，原来一句话就能写出来了，桑心。
• num + 1 的二进制去掉首位就是了。

    public String encode(int num) {
        return Integer.toString(num + 1, 2).substring(1);
    }