首先我们来看一些String的特性。

String对象不可变！
在函数的参数传递中，String传进去时是一种拷贝
String之间用+号非常不好！（+号内部用的是StringBuilder）

StringBuilder

如果想实现将String[] words连接成一个String，那最土的方法就是：

String result = "";
for( int i = 0 ; i < words.length ; ++i ){
  result += words[i];
}

但由于每个+都调用了一次StringBuilder，这无疑增加了很多负担。较好的方式是：

StringBuilder stringBuilder = new StringBuilder();
for( int i = 0 ; i < words.length ; ++i ){
  stringBuilder.append(words[i]);
}
String result = stringBuilder.toString();

遍历String的元素

String a = "abc";
for(char c : a.toCharArray()){
  //c
}

一些操作

`B.indexOf(...)`

B.indexOf(A) : 从B的头看是查找是否存在A

B.indexOf(A, idx) : 从B的第idx个字符开始查找是否存在A

`B.startWith(A)`

判断B是否以A开头

`B.contains(A)`

A是否是B的子串

`B.trim()`

trim()方法返回调用字符串对象的一个副本，但是所有起始和结尾的空格都被删除了

相关题

Valid Palindrome

判断给定字符串（字符或数字，字母不分大小写）是否是回文（字符串中包含的其它字符可以跳过）

private boolean ifAlpha(char c){
    return !((c >= 'a' && c <= 'z') || (c - '0' >= 0 && c - '0' < 10));
}
private boolean helper(String s, int low, int high, boolean deleted){

    while (low < high){
        if(ifAlpha(s.charAt(low))){
            ++low;
            continue;
        }
        if(ifAlpha(s.charAt(high))){
            --high;
            continue;
        }
        if(s.charAt(low) == s.charAt(high)){
            ++low;
            --high;
        } else
            return false;
    }
    return true;
}
public boolean isPalindrome(String s) {
    if(s.length() <= 1)return true;
    return helper(s.toLowerCase(), 0, s.length() - 1,false);
}

Valid Palindrome II

判断给定字符串（只有字母）至多去掉一个后，是否是回文

private boolean helper(String s, int low, int high, boolean deleted){
    if(high >= s.length()) return false;
    while (low < high){
        if(s.charAt(low) == s.charAt(high)){
            ++low;
            --high;
        }else if(!deleted){
            return helper(s, low + 1, high, true)||
                    helper(s, low, high - 1, true);
        }else
            return false;
    }
    return true;
}
public boolean validPalindrome(String s) {
    if(s.length() <= 2)return true;
    return helper(s, 0, s.length() - 1,false);
}

Shortest Palindrome

给一个字符串，如果在前面加一些字符，使它变成回文串。求最短的回文串

暴力
    private boolean helper(String left, String right){
        int l = left.length() - 1;
        int r = 0;
        while (l >= 0 && left.charAt(l) == right.charAt(r)){
            l--;
            r++;
        }
        return l == -1;
    }
    public String shortestPalindrome(String s) {
        if(s.length() <= 1) return s;

        for(int i = s.length() / 2; i >= 0; --i){
            if(2*i + 2 <= s.length() && s.charAt(i) == s.charAt( i + 1)){
                // [0,i],[i+1,2*i + 1]
                // String left = s.substring(0, i + 1);
                // String right = s.substring(i + 1, 2*i + 2);
                if(helper(s.substring(0, i + 1), s.substring(i + 1, 2*i + 2))){
                    return new StringBuilder(s.substring(2*i + 2, s.length())).reverse().toString() + s;
                }
            }
            if(i > 0 && 2*i + 1 <= s.length() && s.charAt(i-1) == s.charAt(i+1)){
                //[0,i-1],[i],[i+1,2*i]
                // String left = s.substring(0,i);
                // String right = s.substring(i + 1,2*i + 1);
                if(helper(s.substring(0,i), s.substring(i + 1,2*i + 1))){
                    return new StringBuilder(s.substring(2*i + 1, s.length())).reverse().toString() + s;
                }
            }
        }
        return new StringBuilder(s.substring(1, s.length())).reverse().toString() + s;
    }

Largest Palindrome Product

给一个n，判断两个n位数的乘积最大的回文数，输出回文数mod 1337。

对我来说这并不一道easy的题。我自己写了程序，但不知道为什么不对！还超时！气炸了！

先贴上我的错误的 代码

private boolean ifPalindrome(String s, int low, int high){
        if(low >= high) return true;
        return s.charAt(low) == s.charAt(high) && ifPalindrome(s, low + 1, high - 1);
    }
    public int largestPalindrome(int n) {
        int max = (int)Math.pow(10,n) - 1;
        int min = (int)Math.pow(10, n - 1);
        int n1 = max,n2 = max;
        while (n1 >= min){
            n2 = n1;
            while (n2 >= min){
                BigInteger bigInteger = BigInteger.valueOf(n1).multiply(BigInteger.valueOf(n2));
                if(ifPalindrome(bigInteger.toString(),0, bigInteger.toString().length() - 1))
                    return bigInteger.mod(BigInteger.valueOf(1337)).intValue();
                --n2;
            }
            --n1;
        }
        return 0;
    }

看一下

正确的思路：

定理：输入范围n∈[1, 8]，除n = 1以外，其余n值最大回文数palindrome的位数均为偶数个，可以拆分为half与reversed(half)左右两半

思路：从上界high = pow(10, n) - 1向下界low = pow(10, n - 1)枚举half，构造回文，检查是否存在两个n位数的除数

public int largestPalindrome(int n){
        if(n == 1) return 9;

        int high = (int) Math.pow(10, n) - 1, low = high / 10;
        for (int i = high; i > low; i--) {
            long palindrome = createPalindrome(i);
            // 探测palindrome是否可以被整除，且除数和结果都在(low,high]之间
            for (long j = high; j > low; j--) {
                if (palindrome / j > high)  break;
                if (palindrome % j == 0) return (int) (palindrome % 1337);
            }
        }
        return -1;
    }
    private long createPalindrome(long num){
        // 构造 num + mun 的字符串
        String str = num + new StringBuilder(Long.toString(num)).reverse().toString();
        return Long.parseLong(str);
    }

优化

当然了，以上操作还可以优化！

就是在探索时，只需要探索一半啊我曹！

for (long j = high; j > low; j--) 这里！

改成！

for (long j = high; j*j > palindrome; j--)

速度提升了二倍啊！

骚操作

当然了，这些都没啥。下面这个骚操作，能把人气死。呵呵哒

public int largestPalindrome(int n) {
        switch(n){
            case 1:
                return 9;
            case 2:
                return 987;
            case 3:
                return 123;
            case 4:
                return 597;
            case 5:
                return 677;
            case 6:
                return 1218;
            case 7:
                return 877;
            case 8:
                return 475;
        }
        return 0;
    }

String to Integer (atoi)

这道题题意实在是太不明朗了！

大原则：将str转化为int

小原则：

忽略开始的空格
可能有正负号
如果出现了一个异常字符，就丢弃这个异常字符及其之后的东西
如果没有解，就返回0
如果正数溢出，就返回正整数INT_MAX (2147483647) ；如果负数溢出，就返回负整数INT_MIN (-2147483648)

代码：

public int myAtoi(String str) {
    // 丢弃空白
    int start = 0;
    while (start < str.length() && str.charAt(start) == ' ') ++start;
    if(start >= str.length()) return 0;
    // 判断符号
    int sig = 1;
    if(str.charAt(start) == '+'){++start;sig = 1;}
    else if(str.charAt(start) == '-'){++start; sig = -1;}
    StringBuilder sb = new StringBuilder();
    // 开始字符
    while (start < str.length()){
        int num = str.charAt(start) - '0';
        if(num >= 0 && num < 10){
            sb.append(str.charAt(start));
        }else {
            break;
        }
        ++start;
    }
    // 如果没有解，就返回0
    if(sb.length() == 0) return 0;
    // 如果溢出，就...
       try {
        return sig * Integer.valueOf(sb.toString());
    }catch (Exception e){
        if(sig > 0) return 2147483647;
        else return -2147483648;
    }
}

Roman to Integer

将罗马数字转化为整数

罗马数字的规则：

罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）
重复数次：一个罗马数字重复几次，就表示这个数的几倍
右加左减：
1. 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
2. 在较大的罗马数字的左边（只能有一位）记上较小的罗马数字，表示大数字减小数字。

思路：输入一个数后，我们可以来遍历这个数，用sum来总计和，比较i和i+1，如果，i+1比i小的话，直接相加，如果i大于i+1的话，则将总和sum减去i这个地方数的两倍，同时加上i+1 就相当于后边的数比左边的数大，则用右边的数减左边的数。但因为之前已经加过一次了，所以减两次

//罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、
    // Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）
    int[] nums = {1000,500,100,50,10,5,1};
    char[] chars = {'M','D','C','L','X','V','I'};
    HashMap<Character, Integer> roman = new HashMap<>();

    public int romanToInt(String s) {
        for(int i = 0; i < chars.length; ++i){
            roman.put(chars[i], nums[i]);
        }
        int sum = roman.get(s.charAt(0));
        for(int i = 1; i < s.length(); ++i){
            sum += roman.get(s.charAt(i));
            if(roman.get(s.charAt(i)) > roman.get(s.charAt(i-1))){
                sum -= 2*roman.get(s.charAt(i-1));
            }
        }
        return sum;
    }

Integer to Roman

将整数转化为罗马数字

罗马数字规律：

大部分时候用字符相叠加来表示数字。I是1， II是2， III是3。VI是6（挨个看来，是“5 和 1”的组合），VII是7，VIII是8。
含有10的字符（I，X，C和M）最多可以重复出现三个。为了表示4，必须用同一位数的下一个更大的数字5来减去一。不能用IIII来表示4，而应该是IV（意思是比5小1）。40写做XL（比50小10），41写做XLI，42写做XLII，43写做XLIII，44写做XLIV（比50小10并且比5小1）。
有些时候表示方法恰恰相反。为了表示一个中间的数字，需要从一个最终的值来减。比如：9需要从10来减：8是VIII，但9确是IX（比10小1），并不是VIII（I字符不能重复4次）。90是XC，900是CM。
表示5的字符不能在一个数字中重复出现。10只能用X表示，不能用VV表示。100只能用C表示，而不是LL。
罗马数字是从左到右来计算，因此字符的顺序非常重要。DC表示600，而CD完全是另一个数字400（比500小100）。CI是101，IC不是一个罗马数字（因为你不能从100减1，你只能写成XCIX，表示比100小10，且比10小1）。

有了以上规则，按照规则挨个位置计算就好啦

public String intToRoman(int num) {
    char[][] roman = {
            {'M','D','C'},
            {'C','L','X'},
            {'X','V','I'}
    };

    StringBuilder sb = new StringBuilder();
    //千分位
    int digit = num/1000;
    num -= digit*1000;
    while (digit > 0){
        sb.append('M');
        --digit;
    }

    int[] divisor = {100,10,1};
    for(int i = 0; i < 3; ++i) {
        // 500/100分位
        digit = num / divisor[i];
        num -= digit * divisor[i];
        // 900 -> digit = 9 -> CM
        if (digit == 9) {
            //sb.append("CM");
            sb.append(roman[i][2]);
            sb.append(roman[i][0]);
        }
        // 700 -> digit = 7 -> DCC
        else if (digit >= 5) {
            //sb.append("D");
            sb.append(roman[i][1]);
            digit--;
            while (digit >= 5) {
                //sb.append("C");
                sb.append(roman[i][2]);
                digit--;
            }
        }
        // 400 -> digit = 4 -> CD
        else if (digit == 4) {
            //sb.append("CD");
            sb.append(roman[i][2]);
            sb.append(roman[i][1]);
        }
        // 300 -> digit = 3 -> CCC
        else {
            while (digit > 0) {
                //sb.append("C");
                sb.append(roman[i][2]);
                digit--;
            }
        }
    }
    return sb.toString();
}

Integer to English Words

将数字转化为英文读音

读音规则：

三位一体，每三位都是同一个读法，只是在后面加thunsand/Million/Billion即可。例如123,456,789可以分解为：123 million, 456 thunsand, 789
三位数字读法：百位直接就是数字 + thunsand；十位和个位比较麻烦。20以下的数字直接读，20以上的数字用几十 + 几的方法

if(num == 0) return "Zero";
        String[] splitWords = {"","Thousand","Million","Billion"};
        String[] key1 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten",
        "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen","Twenty"};
        String[] key2 = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
        int counter = 0;
        StringBuilder sb_global = new StringBuilder();
        while (num > 0){
            StringBuilder sb = new StringBuilder();
            int last = num - 1000*(num/1000); // 后三位
            if(last == 0){
                counter += 1;
                num = num/1000;
                continue;
            }
            int hundred_digit = last/100;
            if(hundred_digit > 0){
                sb.append(" ");
                sb.append(key1[hundred_digit]);
                sb.append(" Hundred");
            }
            int low_two_digit = last - hundred_digit*100;
            if(low_two_digit > 0) {
                if (low_two_digit <= 20) {
                    sb.append(" ");
                    sb.append(key1[low_two_digit]);
                } else {
                    int tens = low_two_digit / 10;
                    int units = low_two_digit - tens * 10;
                    if (tens > 0) {
                        sb.append(" ");
                        sb.append(key2[tens]);
                    }
                    if (units > 0) {
                        sb.append(" ");
                        sb.append(key1[units]);
                    }
                }
            }
            if (counter > 0) {
                sb.append(" ");
                sb.append(splitWords[counter]);
            }
            sb_global.insert(0, sb.toString());
            counter += 1;
            num = num/1000;

        }
        return sb_global.subSequence(1, sb_global.length()).toString();
    }

代码简化：

private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};

public String numberToWords(int num) {
    if (num == 0) return "Zero";

    int i = 0;
    String words = "";
    
    while (num > 0) {
        if (num % 1000 != 0)
    	    words = helper(num % 1000) +THOUSANDS[i] + " " + words;
    	num /= 1000;
    	i++;
    }
    
    return words.trim();
}

private String helper(int num) {
    if (num == 0)
        return "";
    else if (num < 20)
        return LESS_THAN_20[num] + " ";
    else if (num < 100)
        return TENS[num / 10] + " " + helper(num % 10);
    else
        return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
}

Group Anagrams

给str[] ，将同一排列组合的str分为一组。

一开始想多了，其实挺简单的

private String toHash(String s){
    int[] hash = new int[26];
    for(int i = 0; i < s.length(); ++i){
        ++hash[s.charAt(i) - 'a'];
    }
    StringBuilder sb = new StringBuilder();
    for(int i : hash)sb.append(i);
    return sb.toString();
}
public List<List<String>> groupAnagrams(String[] strs) {
    if(strs.length == 0) return new  LinkedList<List<String>>();
    HashMap<String, List<String>> set = new HashMap<>();
    for(String s:strs){
        String hash = toHash(s);
        if(set.containsKey(hash)){
            set.get(hash).add(s);
        }else{
            List<String> list = new LinkedList<>();
            list.add(s);
            set.put(hash,list);
        }
    }
    return new LinkedList<List<String>>(set.values());
}

Mini Parser

好复杂的一题。将括号的lists反序列化。很复杂！

class Node{
        NestedInteger nestedInteger;
        int end;
        Node(NestedInteger nestedInteger, int end){
            this.nestedInteger = nestedInteger;
            this.end = end;
        }
    }
    private Node helper(String s, int idx){
        if(idx == s.length()) return null;
        //System.out.println(idx);
        NestedInteger obj = new NestedInteger();
        int start = idx;
        int addCounter = 0;
        int i = idx;
        for(i = idx; i < s.length(); ++i){
            //System.out.println(idx + "\t" + s.charAt(i));
            if(s.charAt(i) == ','){
                addCounter+= 1;
                if(start < i)obj.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));
                start = i + 1;
            }else if(s.charAt(i) == '['){
                Node next = helper(s, i + 1);

                if(next != null) {
                    obj.add(next.nestedInteger);
                    addCounter+= 1;
                    i = next.end;
                    if(i < s.length())--i;//因为for循环会+1
                    start = next.end + 1;
                }
            }else if(s.charAt(i)== ']'){
                addCounter+= 1;
                if(start < i)obj.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));
                ++i;
                break;
            }
        }
         // if(addCounter == 0)
         //     obj.setInteger(Integer.valueOf(s.substring(0, s.length())));

        return new Node(obj, i);
    }
    public NestedInteger deserialize(String s) {
        if(s.length() == 0) return  new NestedInteger();
        if(s.length() == 1 || s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
        return helper(s,1).nestedInteger;
    }

又用栈写了一遍：

public int getNumEnd(String s, int idx){
    while (idx < s.length() && (s.charAt(idx) == '+' || s.charAt(idx) == '-' || Character.isDigit(s.charAt(idx)))){
        ++idx;
    }
    return idx;
}
public NestedInteger deserialize(String s) {
    if(s.length() == 0 || s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
    Stack<NestedInteger> stack = new Stack<>();
    NestedInteger result = null;
    for(int i = 0; i < s.length();){
        if(s.charAt(i) == ','){
            ++i;
        }else if(s.charAt(i) == '['){
            NestedInteger curr = new NestedInteger();
            if(!stack.empty()) stack.peek().getList().add(curr);
            stack.push(curr);
            ++i;
        }else if(s.charAt(i) == ']'){
            result = stack.pop();
            ++i;
        }else{
            // 取数字
            int numEnd = getNumEnd(s, i);
            int sig = 1;
            if(s.charAt(i) == '-'){
                sig = -1;
                ++i;
            }else if(s.charAt(i) == '+'){
                ++i;
            }
            //System.out.println(i + "\t" + numEnd);
            int num = sig * Integer.valueOf(s.substring(i, numEnd));
            //System.out.println(num);
            NestedInteger curr = new NestedInteger(num);
            stack.peek().getList().add(curr);
            i = numEnd;
        }
    }
    while(!stack.empty()){
        result = stack.pop();
    }
    return result;
}

Validate IP Address

验证给定字符串是否是IPV4或IPV6地址

这道题实在是太心酸了。主要有以下几个注意点：

split操作会忽略最后一个字符为分隔符的情况
IPv4 ：
1. 长度必须为4
2. 每个字符不可有有前导0
3. 第一个字符不可以为0
4. 不可以出现其他字符
5. 值不可以大于255
IPv6：
1. 长度要么为8，要么只存在一个:: 。（通过使用双冒号（::）替换一系列零来指定 IPv6 地址。例如，IPv6 地址 ff06:0:0:0:0:0:0:c3 可写作 ff06::c3。一个 IP 地址中只可使用一次双冒号。
2. 可以有前导零

private String validIPv4(String[] ipv4){
        try {
            for(int i = 0; i < ipv4.length; ++i){
                // 空字符，错误
                if(ipv4[i].length() == 0)return "Neither";
                // 前导零，错误
                if(ipv4[i].length() > 1 && ipv4[i].charAt(0) == '0')return "Neither";
                // 有其他字符，错误
                for(char c : ipv4[i].toCharArray()) if(c < '0' || c > '9') return "Neither";
                int val = Integer.valueOf(ipv4[i]);
                // 第一个字符为0，错误
                if(i == 0 && val == 0)return "Neither";
                // 值错误
                if(val < 0 || val >= 256) return "Neither";
            }
            return "IPv4";
        }catch (NumberFormatException e){
            return "Neither";
        }
    }
    private String validIPv6(String[] IPv6){
        boolean lenOK = false;
        for(int i = 0; i < IPv6.length; ++i){
            if(IPv6[i].length()==0) {
                if(lenOK) return  "Neither";
                lenOK = true;
                //检查左边是否存在0
                if(i > 0){
                    //IPv6[i-1]
                    if(IPv6[i-1].length() == 0)return "Neither";
                    else if(IPv6[i-1].length() == 1) {
                        if (IPv6[i - 1].equals("0")) return "Neither";
                    }else{ // 长度大于0
                        boolean allZero = true;
                        for(char c : IPv6[i - 1].toCharArray()){
                            if(c != '0'){
                                allZero = false;
                                break;
                            }
                        }
                        if(allZero)return "Neither";
                    }

                }
            }
            if(IPv6[i].length() > 4)return "Neither";
            for(char c : IPv6[i].toCharArray()){
                if((c >= 'a' && c <= 'f')||
                    (c >='0' && c <= '9')||
                    (c >= 'A' && c <= 'F')){
                    // 合法
                }else{
                    return "Neither";
                }
            }
        }
        if((lenOK && IPv6.length < 8) || IPv6.length == 8) return "IPv6";
        else return  "Neither";
    }
    public String validIPAddress(String IP) {
        if(IP.length() == 0) return "Neither";
        // 因为split操作检测不到最后一个.或者：
        char last = IP.charAt(IP.length() - 1);
        if(!((last >= 'a' && last <= 'f')||
            (last >='0' && last <= '9')||
            (last >= 'A' && last <= 'F'))){
            return "Neither";
        }
        String[] ipv4 = IP.split("\\."); // .是转义字符，必须用\\.
        if(ipv4.length == 4){
            return  validIPv4(ipv4);
        }
        String[] IPv6 = IP.split(":");
        if(IPv6.length > 0){
            return validIPv6(IPv6);
        }
        return  "Neither";
    }

自己写的代码好乱，学习一下别人的：

    public String validIPAddress(String IP) {
        if (IP.length() == 0) return "Neither";
        int lastChar = IP.charAt(IP.length() - 1);
        if (lastChar == ':' || lastChar == '.') return "Neither";
        String[] groups = IP.split("\\.");
        if (groups.length == 1) {
            groups = IP.split(":");
            if (validateIPv6(groups)) return "IPv6";
            else return "Neither";
        } else {
            if (validateIPv4(groups)) return "IPv4";
            else return "Neither";
        }
    }
    // 验证v4单个组
    private boolean validateIPv4Group(String group) {
        if (group.length() > 3 || group.length() == 0) return false;
        if (group.length() > 1 && group.charAt(0) == '0') return false;
        int res = 0;
        for (int i = 0; i < group.length(); i++) {
            char c = group.charAt(i);
            if (c >= '0' && c <= '9') res = res * 10 + c - '0';
            else return false;
        }
        return res < 256;
    }
    // 验证v4整个组
    private boolean validateIPv4(String[] groups) {
        //System.out.println(Arrays.toString(groups));
        if (groups.length != 4) return false;
        for (int i = 0; i < groups.length; i++) {
            if (!validateIPv4Group(groups[i])) return false;
        }
        return true;
    }
     // 验证v6单个组
    private boolean validateIPv6Group(String group) {
        if (group.length() > 4 || group.length() == 0) return false;
        for (int i = 0; i < group.length(); i++) {
            char c = Character.toLowerCase(group.charAt(i));
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f')) continue;
            else return false;
        }
        return true;
    }
    // 验证v6整个组
    private boolean validateIPv6(String[] groups) {
        //System.out.println(Arrays.toString(groups));
        if (groups.length != 8) return false;
        for (int i = 0; i < 8; i++) {
            if (!validateIPv6Group(groups[i])) return false;
        }
        return true;
    }
}

Compare Version Numbers

比较两个str的版本号的大小。

注意：有1.0000.00 与1.0 的这种变态样例

public int compareVersion(String version1, String version2) {
    String[] v1 = version1.split("\\.");
    String[] v2 = version2.split("\\.");
    int v1_idx = 0, v2_idx = 0;
    while (v1_idx < v1.length && v2_idx < v2.length){
        if(Integer.valueOf(v1[v1_idx]) == Integer.valueOf(v2[v2_idx])){++v1_idx; ++v2_idx;}
        else if(Integer.valueOf(v1[v1_idx]) > Integer.valueOf(v2[v2_idx])){return 1;}
        else return -1;
    }

    if(v1_idx < v1.length){
        while(v1_idx < v1.length && Integer.valueOf(v1[v1_idx]) == 0){++v1_idx;}
        if(v1_idx == v1.length) return 0;
        else return 1;
    }
    if(v2_idx < v2.length){
        while(v2_idx < v2.length && Integer.valueOf(v2[v2_idx]) == 0){++v2_idx;}
        if(v2_idx == v2.length) return 0;
        else return -1;
    }
    return 0;
}

Reverse Words in a String

将string里的单词顺序搞反。需要注意的是：如果有多个连续空格，则认为是一个空格。结果不可以出现前导空格或者后缀空格。

这道题一开始想多了。其实挺简单的。

public String reverseWords(String s) {
    if(s.length() == 0) return s;
    String[] strs = s.split(" +"); // 分割时可以有多个空格
    StringBuilder sb = new StringBuilder();
    for(int i = strs.length - 1; i >= 0; --i){
        if(strs[i].length() == 0)continue;
        sb.append(' ');
        sb.append(strs[i]);
    }
    return sb.length() == 0 ? "": sb.subSequence(1, sb.length()).toString();
}

Reverse Words in a String II

将输入的string改成char[]的形式，要求用O(1)空间复杂度将单词顺序搞反。这次没有多个空格，也没有前导和后缀空格。

思路：

先将全部字符串翻转
然后对每个单词进行翻转

private void swap(char[] str, int low, int high){
        char temp =str[low];
        str[low] = str[high];
        str[high] = temp;
    }
    public void reverseWords(char[] str) {
        // 1. 将整个str反转
        int low = 0, high = str.length - 1;
        while (low < high){
            swap(str, low, high);
            ++low;
            --high;
        }
        // 2. 逐个单词内部反转
        int i = 0;
        low = i;high = i;
        char space = ' ';
        while (i < str.length){
            if(str[i] == space){++i;}
            else{
                // str[i]不是space
                low = i; ++i;
                while (i < str.length && str[i] != space){
                    ++i;
                }
                // [low, i) 都不是space，反转low到i
                high = i - 1;
                while (low < high){
                    swap(str, low, high);
                    ++low; --high;
                }
            }
        }


    }

其实以上代码可以简化：

public void reverseWords(char[] str) {
    reverse(str, 0, str.length-1);
    int r = 0;
    while(r < str.length){
        int l = r;
        while(r < str.length && str[r] != ' ')
            r++;
        reverse(str, l, r-1);
        r++;
    }
}
public void reverse(char[] s, int l, int r){
    while(l < r){
        char tmp = s[l];
        s[l++] = s[r];
        s[r--] = tmp;
    }
}

Reverse Words in a String III

这道题其实是上一题的easy版。要将字符串内的每个单词的单词内部顺序搞反。

private void reverse(char[] str, int low, int high){
    while (low < high) {
        char temp = str[low];
        str[low] = str[high];
        str[high] = temp;
        ++low;
        --high;
    }
}
public String reverseWords(String s) {
    char[] str = s.toCharArray();
    // 1. 逐个单词内部反转
    int i = 0;
    int low = i; int high = i;
    char space = ' ';
    while (i < str.length){
        if(str[i] == space){++i;}
        else{
            // str[i]不是space
            low = i; ++i;
            while (i < str.length && str[i] != space){
                ++i;
            }
            // [low, i) 都不是space，反转low到i
            high = i - 1;
            reverse(str, low, high);
        }
    }
    return String.valueOf(str);
}

Excel Sheet Column Title

将数字表示成Excel中的字母：

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

这道题的棘手之处在于没有0元素

private String helper(int n){
        if (n > 26){
            if(n%26 == 0){
                return helper(n/26 - 1) +
                        helper((n - 26*(n/26) == 0 ? 25 :n - 26*(n/26) ) + 1);
            }else {
                return helper(n/26) + helper(n - 26*(n/26));
            }

        }else{
            return String.valueOf((char)(n+64));
        }
    }
    public String convertToTitle(int n) {
        return helper(n);
    }

代码写的太绕了，看看别人的：

public String convertToTitle(int n) {
       StringBuilder sb = new StringBuilder();
       while(n>0){
           n--; // 这个处理非常巧妙，将所有的字符表示统统减了1
           sb.insert(0,(char)('A'+n%26));
           n=n/26;
       }
       return sb.toString();
       
   }

Excel Sheet Column Number

将Excel中的字母表示成数字。

做完上一题，这一题就简单很多。

public int titleToNumber(String s) {
        int num = 0;
        for(char c : s.toCharArray()){
            num *= 26;
            num += (c - 'A' + 1);
        }
        return num;
    }

Bulls and Cows

甲乙二人玩猜数字游戏。甲心里默认一个数字，乙去猜。令A = 乙完全猜中（位置和数字都猜中）的个数。B = 乙猜中数字但没猜对位置的个数。统计A和B。

Secret number:  "1123"
Friend's guess: "0111"

输出 "1A1B"

思路很简单，就是hash。

public String getHint(String secret, String guess) {
        int[] secret_hash = new int[10];
        int[] guess_hash = new int[10];
        int A = 0;
        for(int i = 0; i < secret.length(); ++i){
            if(secret.charAt(i) == guess.charAt(i)){
                ++A;
            }else {
                ++secret_hash[secret.charAt(i) - '0'];
                ++guess_hash[guess.charAt(i) - '0'];
            }
        }
        // 统计B的个数
        int B = 0;
        for(int i = 0; i < 10; ++i){
            if(secret_hash[i] > 0 && guess_hash[i] > 0){
                B += Math.min(secret_hash[i], guess_hash[i]);
            }
        }
        return String.valueOf(A)+"A" + String.valueOf(B) + "B" ;

    }

Is Subsequence

给两个str : s 和t 。判断s是否是t的子序列

思路：如果s中的每个元素在t中的idx可以构成一个升序的话，那么s就是t的子序列

private int[][] toHash(String s){
        int[][] hash = new int[26][s.length() + 1]; // 最多一个字符重复s.length()次
        // hash[i][0] :字符i的重复次数
        // hash[i][k] : 字符i的第k个idx
        for(int i = 0; i < s.length(); ++i){
            ++hash[s.charAt(i) - 'a'][0];
            hash[s.charAt(i) - 'a'][hash[s.charAt(i) - 'a'][0]] = i;

        }
        return hash;
    }
    public boolean isSubsequence(String s, String t) {
        if(s.length() > t.length()) return false;
        int[][] t_hash = toHash(t);
        // 遍历s的每个字符
        int last = -1;
        for(char c : s.toCharArray()){
            if(t_hash[c-'a'][0] == 0) return false;
            int curr = findLarger(t_hash[c-'a'], last);
            if(curr > last){
                //System.out.println(t.charAt(curr));
                last = curr;
            }
            else return false;
        }
        return true;
    }
    private int findLarger(int[] tIdxs, int last){
        // 在tIdxs里寻找一个刚好比last大的数
        if(tIdxs[tIdxs[0]] < last) return -1;
        return bitSeach(tIdxs, 1, tIdxs[0], last);
    }
    private int bitSeach(int[] nums, int low, int high, int target){
        // 搜索比target稍微大一点的数
        int mid;
        while (low + 1 < high){
            mid = low + (high - low) / 2;
            if(nums[mid] > target){
                high = mid;
            }else{
                low = mid;
            }
        }
        if(nums[low] > target) return nums[low];
        if(nums[high] > target) return nums[high];
        return -1;
    }

优化

在集合里寻找较大的值，可以用treeset

public boolean isSubsequence1(String s, String t) {
        if (s == null || t == null) return false;
        if (s.length() > t.length()) return false;
        if (s.equals("")) return true;
        HashMap<Character, TreeSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            TreeSet<Integer> list = map.getOrDefault(ch, new TreeSet<Integer>());
            list.add(i);
            map.put(ch, list);
        }
        Integer pre = -1;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch)) return false;
            Integer temp = pre;
            pre = map.get(ch).ceiling(pre);
            if (pre != null && pre.equals(temp)) {
                pre = map.get(ch).ceiling(pre + 1);
            }
            
            if (pre == null || pre.intValue() <= temp.intValue()) {
                return false;
            }
        }
        return pre != -1;
    }

Longest Substring with At Least K Repeating Characters

给一个字符串和一个k。求子串的最大长度：子串的每个字符的出现次数都大于等于k。

思路：分治

private int helper(int low, int high){
        if(high - low + 1 < k) return 0;
        for(int i = low; i <= high; ++i){
            int charNum = hash[high][s_chars[i] - 'a'] - (low > 0 ? hash[low - 1][s_chars[i] - 'a'] : 0);
            if(charNum > 0 && charNum < k){
                int left = helper(low, i-1);
                int right = helper(i + 1, high);
                return Math.max(left, right); // 这一步很重要哇
            }
        }
        return high - low + 1;
    }
    int[][] hash;
    char[] s_chars;
    int k;

    public int longestSubstring(String s, int k) {
        if(s.length() == 0 || k == 0) return 0;
        if(s.length() == 1){
            if(k == 1) return 1;
            else return 0;
        }
        s_chars = s.toCharArray(); // 如果把string s传入helper，就会爆栈
        this.k = k;
        hash = new int[s.length()][26]; // hash[i][k] = 前[0,i]的字符k出现了多少次
        ++hash[0][s.charAt(0) - 'a'];
        for(int i = 1; i < s.length(); ++i){
            for(int j = 0; j < 26; ++j){
                hash[i][j] = hash[i-1][j];
            }
            ++hash[i][s.charAt(i) - 'a'];
        }
        return helper(0, s.length() - 1);
    }

骚操作：双指针

是真的没看懂。

public int longestSubstring(String s, int k) {
    char[] str = s.toCharArray();
    int[] counts = new int[26];
    int h, i, j, idx, max = 0, unique, noLessThanK;
    
    for (h = 1; h <= 26; h++) {
        Arrays.fill(counts, 0);
        i = 0; 
        j = 0;
        unique = 0;
        noLessThanK = 0;
        while (j < str.length) {
            if (unique <= h) {
                idx = str[j] - 'a';
                if (counts[idx] == 0)
                    unique++;
                counts[idx]++;
                if (counts[idx] == k)
                    noLessThanK++;
                j++;
            }
            else {
                idx = str[i] - 'a';
                if (counts[idx] == k)
                    noLessThanK--;
                counts[idx]--;
                if (counts[idx] == 0)
                    unique--;
                i++;
            }
            if (unique == h && unique == noLessThanK)
                max = Math.max(j - i, max);
        }
    }
    
    return max;
}

巧用unicode编码做Hash

小写字符只有26个。因此可以申请长度为26的int[]做hash。

如果不一定大小写，可以用256大小的数组做hash。因为最大的Z的unicode不超过256.

Isomorphic Strings

判断两个字符串是否是同构的。

思路：如果是同构的，那么如果第i位置的字符曾经出现过，那么两个字符的曾经出现过的位置一定是一样的。

public boolean isIsomorphic(String s, String t) {
        int[] s_hash = new int[256];
        int[] t_hash = new int[256];
        Arrays.fill(s_hash, -1);
        Arrays.fill(t_hash, -1);
        for(int i = 0; i < s.length(); ++i){
            if(s_hash[s.charAt(i)] != t_hash[t.charAt(i)]) return false;
            s_hash[s.charAt(i)] = i;
            t_hash[t.charAt(i)] = i;
        }
        return true;

    }

加减乘除问题

Additive Number

给一个字符串，判断它是否是additive序列。其中additive序列的含义是前两个元素的和等于本元素。

要点：一个元素可能由多位的char组成。因此比较麻烦。

private String add(String a, String b){
        int a_idx = a.length() - 1, b_idx = b.length() - 1;
        StringBuilder sb = new StringBuilder();
        int lastMod = 0;
        while (a_idx >= 0 || b_idx >= 0){
            int sum = lastMod;
            if(a_idx >= 0){
                sum += Integer.valueOf(a.charAt(a_idx) - '0');
                --a_idx;
            }
            if(b_idx >= 0){
                sum += Integer.valueOf(b.charAt(b_idx) - '0');
                --b_idx;
            }
            lastMod = sum/10;
            sum %= 10;
            sb.append(sum);
        }
        if(lastMod > 0) sb.append(lastMod);
        return sb.reverse().toString();
    }
    private boolean dfs(String num, String lastNum, String currNum, int end){
        if(end == num.length()) return true;
        if((lastNum.length() > 1 && lastNum.charAt(0) == '0') ||
            (currNum.length() > 1 && currNum.charAt(0) == '0')) return false;
        String sum = add(currNum, lastNum);
        if(end + sum.length() <= num.length() && sum.equals(num.substring(end, end + sum.length()))){
            if(dfs(num, currNum, sum , end + sum.length())) return true;
        }
        return false;
    }
    public boolean isAdditiveNumber(String num) {
        if(num.length() < 3) return false;
        // 遍历第一个和第二个数字
        for(int i = 1; i < num.length(); ++i){
            for(int j = i + 1; j < num.length(); ++j){
                if(dfs(num, num.substring(0,i), num.substring(i,j),j)){
                    return true;
                };
            }
        }
        return false;
    }

Different Ways to Add Parentheses

给一个算式 "2-1-1". 这个算式可能有两种解法：

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

那么就输出[0,2]。实现这个功能

思路：分治。一个符号将两边的数字分成了两部分！这道题还是做了比较久的。

[  left  ]  +  [ right ]
 上面所示的加号就把运算分成了两部分，一个是left，一个是right
 而left和right的内部也可以这么分
 
     private int getNumEndIdx(String s, int idx){
        while (idx < s.length() && Character.isDigit(s.charAt(idx))){
            ++idx;
        }
        return idx;
    }
    private int operation(int a, int b, char operator){
        switch (operator){
            case '+':{return a+b;}
            case '-':{return a-b;}
            case '*':{return a*b;}
        }
        return 0;
    }
    char[] operators_arr;
    int[] nums_arr;
    private void split(String s){
        List<Character> operators = new ArrayList<>();
        operators.add('+'); // 默认一开始有一个正号
        List<Integer> nums = new ArrayList<>();
        int i = 0;
        int numEnd;
        while (i < s.length()){
            if(!Character.isDigit(s.charAt(i))){
                operators.add(s.charAt(i));
                ++i;
            }else{
                numEnd = getNumEndIdx(s, i);
                nums.add(Integer.valueOf(s.substring(i, numEnd)));
                i = numEnd;
            }
        }
        operators_arr = new char[operators.size()];
        nums_arr = new int[nums.size()];
        for(i = 0; i < operators_arr.length; ++i){
            operators_arr[i] = operators.get(i);
            nums_arr[i] = nums.get(i);
        }
    }
    List<Integer>[][][] memo;
    private List<Integer> divide(int start, int end, int operatorIdx){
        if(memo[start][end][operatorIdx] != null) return memo[start][end][operatorIdx];
        List<Integer> all = new LinkedList<>();
        if(start == end){
            all.add(nums_arr[start]);
            memo[start][end][operatorIdx] = all;
            return all;
        }
        if(start == end - 1){
            // 只有两个数字+一个符号
            all.add(operation(nums_arr[start], nums_arr[end], operators_arr[end]));
            memo[start][end][operatorIdx] = all;
            return all;
        }
        // 分解问题：对于符号operatorIdx来说，它将左右两边的运算分解成了两部分
        // [start,operatorIdx) , [operatorIdx, end]

        // [start,operatorIdx)
        List<Integer> left = new LinkedList<>();
        for(int leftOperatorIdx = start + 1; leftOperatorIdx < operatorIdx; ++leftOperatorIdx){
            left.addAll(divide(start, operatorIdx - 1,leftOperatorIdx));
        }
        if(left.size() == 0){
            left.add(nums_arr[start]);
        }
        // [operatorIdx, end]
        List<Integer> right = new LinkedList<>();
        for(int rightOperatorIdx = operatorIdx + 1; rightOperatorIdx <= end; ++rightOperatorIdx){
            right.addAll(divide(operatorIdx, end, rightOperatorIdx));
        }
        if(right.size() == 0 && operatorIdx == end){
            right.add(nums_arr[end]);
        }
        //合并
        for(int leftElement : left){
            for(int rightElement : right){
                all.add(operation(leftElement, rightElement, operators_arr[operatorIdx]));
            }
        }
        memo[start][end][operatorIdx] = all;
        return all;
    }
    public List<Integer> diffWaysToCompute(String input) {

        List<Integer> result = new LinkedList<>();
        if(input.length() == 0) return result;
        // 把input拆解成 符号 + 数字的形式
        split(input);
        memo = new List[operators_arr.length][operators_arr.length][operators_arr.length];
        for(int operatorIdx = 1; operatorIdx < operators_arr.length; ++operatorIdx){
            result.addAll( divide(0, operators_arr.length - 1, operatorIdx));
        }
        if(result.size() == 0){
            result.add(Integer.valueOf(input));
        }
        return result;
    }

我的代码好复杂。。。因为我总觉得字符串截取的复杂度很高，因此将字符串预处理为数组。

看看别人的

public List<Integer> diffWaysToCompute(String input) {
    List<Integer> ret = new LinkedList<Integer>();
    for (int i=0; i<input.length(); i++) {
        if (input.charAt(i) == '-' ||
            input.charAt(i) == '*' ||
            input.charAt(i) == '+' ) {
            String part1 = input.substring(0, i);
            String part2 = input.substring(i+1);
            List<Integer> part1Ret = diffWaysToCompute(part1);
            List<Integer> part2Ret = diffWaysToCompute(part2);
            for (Integer p1 :   part1Ret) {
                for (Integer p2 :   part2Ret) {
                    int c = 0;
                    switch (input.charAt(i)) {
                        case '+': c = p1+p2;
                            break;
                        case '-': c = p1-p2;
                            break;
                        case '*': c = p1*p2;
                            break;
                    }
                    ret.add(c);
                }
            }
        }
    }
    if (ret.size() == 0) {
        ret.add(Integer.valueOf(input));
    }
    return ret;
}

Fraction Addition and Subtraction

计算分数的加减。例如给"-1/2+1/2+1/3" ，要给出结果"1/3"

class Solution {
    public String fractionAddition(String expression) {
        // 先把第一项提出来
        int firstEnd = getFraction(expression, 1);
        String first = expression.substring(0, firstEnd);
        
        while(firstEnd < expression.length()){
            // 运算符
            char sig = expression.charAt(firstEnd);
            // 第二项末尾
            int secondEnd = getFraction(expression, firstEnd + 1);
            
            //System.out.println(first + "\t"  +sig+ "\t"+  expression.substring(firstEnd + 1, secondEnd));
            // 计算 first ± second
            first = operator(first, expression.substring(firstEnd + 1, secondEnd), sig);
            firstEnd = secondEnd;
        }
        return first;
    }
    char add = '+';
    char sub = '-';
    private String operator(String first, String second, char sig){
        int[] firsts = getInt(first);
        int[] seconds = getInt(second);
        
        // System.out.println(Arrays.toString(firsts));
        // System.out.println(Arrays.toString(seconds));
        
        // 计算
        int[] result = new int[2];
        // 分母
        result[1] = firsts[1]*seconds[1];
        // 分子
        firsts[0] = firsts[0] * seconds[1];
        seconds[0] = seconds[0] * firsts[1];

        // 计算
        if(sig == add){
            result[0] = firsts[0] + seconds[0];
        }else{
            result[0] = firsts[0] - seconds[0];
        }
        
        
        if(result[1] < 0){
            result[0] = -result[0];
            result[1] = -result[1];
        }
        
        // 求分子分母绝对值的最大公约数
        int d = Gcd(Math.abs(result[0]), Math.abs(result[1]));
        result[0] /= d;
        result[1] /= d;
        return result[0] + "/" + result[1];
    }
    
    private int Gcd(int a, int b){
        while(b != 0){
            int r = b;
            b = a % b;
            a = r;
        }
        return a;
    }
    
    private int[] getInt(String str){
        int[] result = new int[2];
        String[] strs = str.split("/");
        result[0] = Integer.valueOf(strs[0]);
        if(strs.length > 1)result[1] = Integer.valueOf(strs[1]);
        else result[1] = 1;
        return result;
    }
    
    private int getFraction(String expression, int idx){
        while(idx < expression.length()){
            if(expression.charAt(idx) == add || expression.charAt(idx) == sub){
                break;
            }
            ++idx;
        }
        return idx;
    }
}

甲乙小朋友的房子

Java-String