X

LEETCODE 1256. Encode Number 解题思路分析

题目大意:

加密数字

给你一个非负整数 num,返回它的 加密字符串。

加密的过程是把一个整数用某个未知函数进行转化,你需要从下表推测出该转化函数:

示例1:

输入: num = 23
输出: "1000"

示例2:

输入: num = 107
输出: "101100"

提示:

  • 0 <= num <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1256

解题思路分析:

本题需要先观察出给定的加密规律,与普通的二进制数不同,当出现进位时,所有位数的值要变为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;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 68.07% of Java online submissions for Encode Number.

Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Encode Number.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1256-encode-number-解题思路分析/
Categories: leetcode
kwantong: