[LintCode] Binary Representation

you_De 發布于2019-08-14 15:21 / 3206人閱讀

摘要：細節上還要考慮正負號和整數位的越界情況。然后在循環內判斷，如果有重復出現的，或者中小數部分的長度超過，就說明該小數無法完全轉換。如果之前的正負號為，就在左邊加上負號。

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();
    }
}

GPU云服務器云服務器 Representation LintCode LintCode134_LRU Binary

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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