17年百度校招

题目

1. 给定一个字符串，计算出字典序最大的子串
2. 输入n个字符串，对于第i个字符串，需要返回在前面i-1个字符串中，有多少个字符串的字典序严格比第i个字符串小
3. 给定一个字符串s1和两个子串s2，s3；找出s2在s1中出现的最小位置和s3在s1中出现的最大位置
4. 给定一些在x轴正半轴上的线段，规定选取一个点可以去除掉过这个点得所有线段，问这样的点最少选取多少个，可以将全部线段去除？

思路与解答

第一题

给定一个字符串，计算出字典序最大的子串

字典排序不论长度，只看当前字符大小：比如fdavdsdsd 和fga，后者就比前者要大，因为第二个字符g大于d
对于如下字符串 abcdefg和abcdefga，由于比较完了，则长的字符串大，即第二个字符串字典序大
我们在选取子串的时候，最笨的方法是把所有的子串都找出来，每次和最大的比较，如果大就替换之；这种暴力方法一定要避免，不到迫不得已不要用；
简化的方法就是找到一种规则，把满足规则的字符留下，不满足规则的字符去掉，遍历一遍就会得到最大子串；这个问题在于找到规则以及从哪个方向遍历，可以知道对于一个最大子串，一定包含母串的最后一个元素；然后从最后开始遍历，把最后一个元素添加到子串中，如果当前元素大于等于子串中第一个元素，则添加进子串
代码如下：

public static void MaxDictSub(String s){
        int index=s.length()-1;
        String subStr="";
        char c;
        if(s.length()>0){
            c=s.charAt(index);
            while (index>=0){
                if(s.charAt(index)>=c){
                    subStr=s.charAt(index)+subStr;
                    c=s.charAt(index);
                }
                index--;
            }
            System.out.println(subStr);
        }else {
            System.out.println("");
        }

    }

第二题

输入n个字符串，对于第i个字符串，需要返回在前面i-1个字符串中，有多少个字符串的字典序严格比第i个字符串小

思路：暂时没相当简单的方法，只想到，当前字符串和前面所有字符串比较

第三题

给定一个字符串s1和两个子串s2，s3；找出s2在s1中出现的最小位置和s3在s1中出现的最大位置

思路：从s1的前面遍历，直到找到全部的s2，停止；从s1的后面遍历，直到找到全部的s3，停止；

第四题

给定一些在x轴正半轴上的线段，规定选取一个点可以去除掉过这个点得所有线段，问这样的点最少选取多少个，可以将全部线段去除？

时间复杂度是O(n)

代码：

public static int putCatalyst(int numOfLines, List<Integer> startXPoints,List<Integer> endXPoints){
        Map<Integer,Integer> map=new HashMap<>();
        int start;
        int index=0;
        int num,maxnum;
        int result=0;
        for(int i=0;i<startXPoints.size();i++){
            map.put(startXPoints.get(i),endXPoints.get(i));
        }

        Collections.sort(startXPoints);
        start=startXPoints.get(index);
        while (index<startXPoints.size()){
            maxnum=0;
            while (start<=map.get(startXPoints.get(index))){
                num=0;
                for(int i=index+1;i<startXPoints.size();i++){
                    if(startXPoints.get(i)<=start){
                        num++;
                    }else {
                        break;
                    }
                }
                if(num>maxnum){
                    maxnum=num;
                }
                start++;
            }
            index=index+maxnum+1;
            result++;
        }
        return result;
    }