10. 字符串

10. 字符串

单纯考String的问题主要考一些基本操作，比如：

• How to split String into a String array?

  • LC165. compare version numbers

• How to get indexOf()

• How to convert String into int?

  • Integer.parseInt()

繁琐的字符串处理

Fraction to Recurring Decimal

• check sign

• Long type

public String fractionToDecimal(int numerator, int denominator) {
        //handle exception
        if(denominator == 0) return "NaN";
        if(numerator == 0) return "0";

        //build a StringBuilder
        StringBuilder sb = new StringBuilder();

        //check the sign
        Long n = new Long(numerator);
        Long d = new Long(denominator);
        if(n * d < 0){
            sb.append("-");
        }
        //make n and d all positive
        n = Math.abs(n);
        d = Math.abs(d);

        //get the divide result
        sb.append(n/d);
        //if no remainder, return 
        if(n % d == 0){
            return sb.toString();
        }

        sb.append(".");
        long r = n % d;
        Map<Long, Integer> map = new HashMap<>();//key is the remainder, value is the index of this remainder in StringBuilder

        while(r > 0){
            if(map.containsKey(r)){
                sb.insert(map.get(r), "(");
                sb.append(")");
                break;
            }else{
                map.put(r, sb.length());//put into hashmap first
                r *= 10;
                sb.append(r / d);

                r %= d;
            }
        }
        return sb.toString();
    }

Binary Representation

• 这里有篇帖子思路分析的很清晰
• 各种corner case,处理的很好

  public String binaryRepresentation(String n) {
        // write your code here
        if (n == null || n.length() == 0) {
            return "";
        }
        n = n.trim();
        if (n.indexOf(".") == -1) {
            return parseInteger(n);
        }
        String[] strs = n.split("\\.");
        String f = parseFloat(strs[1]);
        if (f.equals("ERROR")) {
            return "ERROR";
        }
        if (f.equals("") || f.equals("0")) {
            return parseInteger(strs[0]);
        }
        return parseInteger(strs[0]) + "." + f;
    }
    private String parseInteger(String s) {
        if (s.equals("") || s.equals("0")) {
            return "0";
        }
        int d = Integer.parseInt(s);
        String res = "";
        while (d != 0) {
            res = Integer.toString(d % 2) + res;
            d /= 2;
        }
        return res;
    }
    private String parseFloat(String s) {
        if (s.equals("") || s.equals("0")) {
            return "0";
        }
        double d = Double.parseDouble("0." + s);
        String res = "";
        HashSet<Double> set = new HashSet<Double>();
        while(d != 0){
            //出现循环
            if(res.length() > 32 || set.contains(d)){
                return "ERROR";
            }
            set.add(d);
            d = d * 2;
            if(d >= 1){
                res += "1";
                d = d - 1;
            }else{
                res += "0";
            }
        }
        return res;
    }

Validate IP address

• 巨多edge case, 全文背诵吧

• 这题还有个小技巧：IP.split("\:", -1)

class Solution {
    /*
    e.x."2001:0db8:85a3:0:0:8A2E:0370:7334:"
    IP.split("\\:", -1) --> length = 9
    IP.split("\\:", 0) == IP.split("\\:") --> remove trailing empty string, length = 8
    */
    public String validIPAddress(String IP) {
        if (IP == null || IP.length() == 0) return "Neither";
        if (isIPv4(IP)) {
            return "IPv4";
        }
        if (isIPv6(IP)) {
            return "IPv6";
        }
        return "Neither";
    }
    
    private boolean isIPv4(String IP) {
        String[] IPs = IP.split("\\.", -1);
        if (IPs.length != 4) return false;
        for (String addr: IPs) {
            int val = 0;
            try {
                val = Integer.parseInt(addr);
            } catch (NumberFormatException e) {
                return false;
            }
            if (!addr.equals(String.valueOf(val)) || val < 0 || val > 255) return false; //"002", "-12", 256"
        }
        return true;
    }
    
    private boolean isIPv6(String IP) {
        String[] IPs = IP.split("\\:", -1);
        if (IPs.length != 8) return false;
        for (String addr : IPs) {
            if (addr.length() == 0 || addr.length() > 4) return false;
            int val = 0;
            try {
                val = Integer.parseInt(addr, 16);
            } catch (NumberFormatException e) {
                return false;
            }
            if (val < 0 || addr.charAt(0) == '-') return false;
        }
        return true;
    }
}

Detect Capital

• 这题放进来纯粹是为了对比自己写的code和别人的clean code的差距

• 主要还是solution不同

class Solution {
    /*
    seen-> capital
    firstCaptital
    */
    public boolean detectCapitalUse(String word) {
        if (word == null || word.length() < 2) return true;
        boolean firstCapital = isCapital(word.charAt(0));
        boolean secondCapital = isCapital(word.charAt(1));
        if (!firstCapital) {
            return isAllLow(word.substring(1));
        } else {
            if (secondCapital) {
                return isAllHigh(word.substring(2));
            } else {
                return isAllLow(word.substring(2));
            }
        }
    }
    
    private boolean isCapital(char c) {
        return c >= 'A' && c <= 'Z';
    }
    
    private boolean isAllHigh(String word) {
        for (int i = 0; i < word.length(); i++) {
            if (!isCapital(word.charAt(i))) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isAllLow(String word) {
        for (int i = 0; i < word.length(); i++) {
            if (isCapital(word.charAt(i))) {
                return false;
            }
        }
        return true;
    }
}

//clean code
class Solution {
    /*
    count num of caps
    1. caps == 0 || caps == word.length()
    2. caps == 1 && Character.isUpperCase(word.charAt(0))
    */
    public boolean detectCapitalUse(String word) {
        int caps = 0;
        for (int i = 0; i < word.length(); i++) {
            if (Character.isUpperCase(word.charAt(i))) {
                caps++;
            }
        }
        if (caps == 0 || caps == word.length()) {
            return true;
        }
        return caps == 1 && Character.isUpperCase(word.charAt(0));
    }
}