1. 合并区间
2. 字符串操作

1. 合并区间

1.1 做题思路

要找到合并区间的规律而进一步对区间进行合并。

1.2 Leetcode实例

q56 合并区间

    /**
     * 一组interval合并重复的部分
     * 重合的区间的特点，后面的那个区间的较小值在另一个区间之中，
     * 那么新形成的区间特点是取两个区间的较小值是区间的开始，两个区间的较大值是区间的结束
     *
     * 解题思路:
     * 1. 先把区间重新排序，按首元素从小到大排序
     * 2. 从前往后一步步进行区间合并
     * @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之中最后一个区间的最后一个值
                res.get(res.size()-1)[1] =  Math.max(res.get(res.size()-1)[1],interval[1]);
            }
        }
        return res.toArray(new int[0][]);
    }

以上题目的其他解题思路请参考: https://www.jianshu.com/p/b7f62349a423

2. 字符串操作

2.1 常用的关于字符串操作的函数

public String substring(int beginIndex, int endIndex) //该方法从beginIndex位置起，从当前字符串中取出到endIndex-1位置的字符作为一个新的字符串返回。

public String concat(String str) //将参数中的字符串str连接到当前字符串的后面，效果等价于"+"。

public int indexOf(int ch/String str) //用于查找当前字符串中字符或子串，返回字符或子串在当前字符串中从左边起首次出现的位置，若没有出现则返回-1。

boolean startsWith(String prefix)或boolean endWith(String suffix) //用来比较当前字符串的起始字符或子字符串prefix和终止字符或子字符串suffix是否和当前字符串相同，重载方法中同时还可以指定比较的开始位置offset。

2.2 Leetcode实例

q6 Z字形变换

    /**
     * 建立Math.min(numRows, s.length())那么多的StringBuilder
     * 然后遍历原字符串把字符串按规律放到指定的StringBuilder中
     * 然后把StringBuilder连接起来得到结果
     * @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： 每次都把字符数组分成两部分，知道细分成只有两个String的时候计算出来公共子串，然后递归返回上一层。
• 二分法： 先找到所有字符串中最短的长度，然后从中间分开，比对前半部分是否所有的字符都是相同的，如果是的话就重复在后半部分二分查找，如果不是就在前半部分继续二分查找。

q763 划分字母区间

    /**
     * 记录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;

    }

以上题目的其他解题思路请参考: https://www.jianshu.com/p/a051b89a6855