1. 合并區(qū)間
2. 字符串操作

1. 合并區(qū)間

1.1 做題思路

要找到合并區(qū)間的規(guī)律而進一步對區(qū)間進行合并。

1.2 Leetcode實例

q56 合并區(qū)間

    /**
     * 一組interval合并重復的部分
     * 重合的區(qū)間的特點，后面的那個區(qū)間的較小值在另一個區(qū)間之中，
     * 那么新形成的區(qū)間特點是取兩個區(qū)間的較小值是區(qū)間的開始，兩個區(qū)間的較大值是區(qū)間的結(jié)束
     *
     * 解題思路:
     * 1. 先把區(qū)間重新排序，按首元素從小到大排序
     * 2. 從前往后一步步進行區(qū)間合并
     * @param intervals
     * @return
     */
    public int[][] mergeTwo(int[][] intervals) {
        ArrayList<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        for (int[] interval:intervals){
            if (res.isEmpty() || res.get(res.size()-1)[1] < interval[0]){
                res.add(interval);
            }else {
                //當前條件可以合并，更新ArrayList之中最后一個區(qū)間的最后一個值
                res.get(res.size()-1)[1] =  Math.max(res.get(res.size()-1)[1],interval[1]);
            }
        }
        return res.toArray(new int[0][]);
    }

以上題目的其他解題思路請參考: http://www.itdecent.cn/p/b7f62349a423

2. 字符串操作

2.1 常用的關于字符串操作的函數(shù)

public String substring(int beginIndex, int endIndex) //該方法從beginIndex位置起，從當前字符串中取出到endIndex-1位置的字符作為一個新的字符串返回。

public String concat(String str) //將參數(shù)中的字符串str連接到當前字符串的后面，效果等價于"+"。

public int indexOf(int ch/String str) //用于查找當前字符串中字符或子串，返回字符或子串在當前字符串中從左邊起首次出現(xiàn)的位置，若沒有出現(xiàn)則返回-1。

boolean startsWith(String prefix)或boolean endWith(String suffix) //用來比較當前字符串的起始字符或子字符串prefix和終止字符或子字符串suffix是否和當前字符串相同，重載方法中同時還可以指定比較的開始位置offset。

2.2 Leetcode實例

q6 Z字形變換

    /**
     * 建立Math.min(numRows, s.length())那么多的StringBuilder
     * 然后遍歷原字符串把字符串按規(guī)律放到指定的StringBuilder中
     * 然后把StringBuilder連接起來得到結(jié)果
     * @param s
     * @param numRows
     * @return
     */
    public static String convertTwo(String s, int numRows) {

        if (numRows == 1) return s;

        ArrayList<StringBuilder> res = new ArrayList<>();
        for (int i=0;i<Math.min(numRows, s.length());i++){
            res.add(new StringBuilder());
        }

        boolean goDown = false;
        int curRow = 0;
        for (char c:s.toCharArray()){
            res.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows-1) goDown = !goDown;
            curRow += goDown?1:-1;
        }

        StringBuilder ans = new StringBuilder();
        for (StringBuilder stringBuilder:res){
            ans.append(stringBuilder);
        }

        return ans.toString();
    }

q14 最長公共前綴

    /**
     * 橫向掃描，第一個與第二個計算出來公共的subStr
     * 然后拿common的后面的進行比對，一點點更新公共的subStr
     * @param strs
     * @return
     */
    public String longestCommonPrefixTwo(String[] strs) {
        if (strs.length == 0) return "";

        String prex = strs[0];
        for (int i=1;i<strs.length;i++){
            while (strs[i].indexOf(prex) != 0){
                prex = prex.substring(0, prex.length()-1);
                if (prex.isEmpty()) return "";
            }
        }

        return prex;
    }

這道題除了橫向掃描之外還有三種想法也很好，我在這里簡述一下:

• 縱向掃描: 從第一個字母開始，讓所有的字符串進行比對這個字母是不是有公共的字母，如果是的話就往后移動，如果不是就返回從首字母到當前位置的subString
• divide and conquer： 每次都把字符數(shù)組分成兩部分，知道細分成只有兩個String的時候計算出來公共子串，然后遞歸返回上一層。
• 二分法： 先找到所有字符串中最短的長度，然后從中間分開，比對前半部分是否所有的字符都是相同的，如果是的話就重復在后半部分二分查找，如果不是就在前半部分繼續(xù)二分查找。

q763 劃分字母區(qū)間

    /**
     * 記錄String之中所有字母每個字母的最遠距離
     * 然后遍歷String所有字母，更新最遠的距離
     * @param S
     * @return
     */
    public List<Integer> partitionLabelsTwo(String S) {

        int[] dict = new int[26];
        for (int i=0;i<S.length();i++){
            dict[S.charAt(i)-'a'] = i;
        }

        int j=0, anchor = 0;
        List<Integer> res = new ArrayList<>();

        for (int i=0;i<S.length();i++){
            j = Math.max(j, dict[S.charAt(i)-'a']);
            if (i==j){
                res.add(j-anchor+1);
                anchor = j+1;
            }
        }

        return res;

    }

以上題目的其他解題思路請參考: http://www.itdecent.cn/p/a051b89a6855