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

繁琐的字符串处理

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

  • 这里有篇帖子思路分析的很清晰

  • 各种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));
    }
}

Last updated

Was this helpful?