[LintCode] Binary Representation

you_De 发布于2019-08-14 15:21 / 3106人阅读

摘要：细节上还要考虑正负号和整数位的越界情况。然后在循环内判断，如果有重复出现的，或者中小数部分的长度超过，就说明该小数无法完全转换。如果之前的正负号为，就在左边加上负号。

Problem

Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.

Example

For n = "3.72", return "ERROR".

For n = "3.5", return "11.1".

Note

这道位操作的题目，主要分为整数部分和小数部分的转换。细节上还要考虑正负号和整数位的越界情况。首先，我们对字符串n用.split(".")把小数点前后的部分分离，存入String[] parts，整数部分为parts[0]，小数部分为parts[1]。然后将parts[0]通过Integer.parstInt()转化为int first，然后将first的正负设置为符号位boolean isNeg，建立StringBuilder sb。
下面开始整数部分的转换，首先考虑越界情况：当first的值为Integer.MIN_VALUE的时候，二进制表达为32个1，放入sb即可。否则对first的绝对值进行运算。对first（的最低位）和整数1做与运算，结果存入sb，然后右移一位，进行上一位和整数1的与运算，如此直到first为0，转换完毕。
小数部分相对更麻烦一些。首先，只有parts[]有两个元素且parts[1]不为0时，sb加入小数点"."，然后创建double value，使用Double.parseDouble("0." + parts[1])将小数部分存入value，和整数部分的操作基本一致。
然后我们要考虑两个问题，value是不是能够完全转换为二进制，以及保证能够在小数点后32位的范围内完成转换？
所以，我们针对这两点，写出返回ERROR的分支语句。首先在循环外部建立一个HashSet store，循环内会将出现过的value存入store。然后在while循环内判断，如果有重复出现的value，或者sb中小数部分的长度超过32，就说明该小数无法完全转换。
然后根据新的value大小进行十进制到二进制转换运算（value * 2(value < 0.5)或value * 2 - 1(value >= 0.5)），将结果加入sb。如果之前的正负号isNeg为true，就在sb左边加上负号"-"。
最后，返回sb.toString()。

Solution

import java.math.*;
public class Solution {
    public String binaryRepresentation(String n) {
        if (n == null || n.length() == 0) {
            return n;
        }
        String[] parts = n.split(".");
        StringBuilder sb = new StringBuilder();
        int first = Integer.parseInt(parts[0]);
        boolean isNeg = first < 0;
        if (first == Integer.MIN_VALUE) {
            for (int i = 0; i < 32; i++) {
                sb.append("1");
            }
        } else {
            first = Math.abs(first);
            while (first != 0) {
                sb.insert(0, first & 1);
                first >>= 1;
            }
        }
        if (sb.length() == 0) {
            sb.append("0");
        }
        //now nail the decimal part
        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {
            sb.append(".");
            double value = Double.parseDouble("0." + parts[1]);
            Set store = new HashSet<>();
            while (value > 0) {
                if (sb.substring(sb.indexOf(".")).length() + 1 > 32 || store.contains(value)) {
                    return "ERROR";
                }
                store.add(value);
                if (value >= 0.5) {
                    sb.append("1");
                    value = value * 2 - 1;
                } else {
                    sb.append("0");
                    value = value * 2;
                }
            }
        }
        if (isNeg == true) {
            sb.insert(0, "-");
        }
        return sb.toString();
    }
}

混合云 idc机房托管 Representation LintCode LintCode134_LRU Binary

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65673.html

[LintCode] Count 1 in Binary [典型位运算题目]

摘要：这道题，给我解决了两个疑问，还剩一个。首先是要用无符号右移运算符，其次是可以用一个不断左移的二进制作为参照。 Problem Count how many 1 in binary representation of a 32-bit integer. Example Given 32, return 1 Given 5, return 2 Given 1023, return 9 Ch...

ZHAO_ 2019-08-14 15:16 评论0 收藏0
[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0
[LintCode] Check Full Binary Tree

Description A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More in...

Keven 2019-08-15 17:46 评论0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0
[LintCode] Remove Node in Binary Search Tree [理解BS

Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

陈江龙 2019-08-14 15:33 评论0 收藏0