自学内容网 自学内容网

今天刷两题(day2)

题目一:最长公共前缀

题目描述:
给你一个大小为 n的字符串数组 strs ,其中包含n个字符串 ,
编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。
输入输出描述:
输入:"abca","abc","abca","abc","abcc"
输出:abc

思路解析:

step 1:处理数组为空的特殊情况。
step 2:因为最长公共前缀的长度不会超过任何一个字符串的长度,因此我们逐位就以第一个字符串为标杆,遍历第一个字符串的所有位置,取出字符。
step 3:遍历数组中后续字符串,依次比较其他字符串中相应位置是否为刚刚取出的字符,如果是,循环继续,继续查找,如果不是或者长度不足,说明从第i位开始不同,前面的都是公共前缀。
step 4:如果遍历结束都相同,最长公共前缀最多为第一个字符串。

作答情况(部分答案错误):

写成了

虽然是或者的关系,但是要先判断是不是长度不足,说明从第i位开始不同,前面的都是公共前缀,不然会抛出StringIndexOutOfBoundsException。

②从键盘中输入字符串数组要掌握。

代码:

public class Main {
    /*题目描述:
    给你一个大小为 n的字符串数组 strs ,其中包含n个字符串 ,
     编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。
     输入输出描述:
     输入:"abca","abc","abca","abc","abcc"
     输出:abc
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //从键盘中输入字符串数组(以”,“分割)
   /*  String str=sc.nextLine();
     String[] s=str.split(",");*/
        String[] s=sc.nextLine().split(",");
        System.out.println( longest(s));
    }

    private static String longest(String[] s) {
        if(s.length<=0||s==null) return "";
        int len=s[0].length();
        int count=s.length;
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<len;i++){
            for(int j=0;j<count;j++){
                if(i==s[j].length()||s[0].charAt(i)!=s[j].charAt(i)){
                    return  sb.toString();
                }
            }
            sb.append(s[0].charAt(i));
        }
        return sb.toString();
    }

题目二:合并区间

 题目描述:

给出一组区间,请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列

 输入输出描述:
  输入:[[10,30],[20,60],[80,100],[150,180]]
  输出:[[10,60],[80,100],[150,180]]

解题思路:

step 1:既然要求重叠后的区间按照起点位置升序排列,我们就将所有区间按照起点位置先进行排序。使用优先级队列进行排序重载比较方式为比较interval结构的start变量

step 2:排序后的第一个区间一定是起点值最小的区间,我们将其计入返回数组res,然后遍历后续区间。

step 3:后续遍历过程中,如果遇到起点值小于res中最后一个区间的末尾值的情况,那一定是重叠,取二者最大末尾值更新res中最后一个区间即可。

step 4:如果遇到起点值大于res中最后一个区间的末尾值的情况,那一定没有重叠,后续也不会有这个末尾的重叠区间了,因为后面的起点只会更大,因此可以将它加入res。

作答情况(部分答案错误):

写成了这是困扰我的一个关键因素,下一组要是需要和上一组合并的话,在while循环中,就不能进行二次弹出。

②没有重新toString()方法,导致结果显示成了一个引用类型的地址。

③在给Intervals里添加元素时,没有通过(new +类名)来实例化对象,正确的写法是

代码:

 public static class Interval{
        int start;int end;
        public Interval(int start,int end){
            this.start=start;
            this.end=end;
        }
}
public static  ArrayList<Interval> merge(ArrayList<Interval> Intervals){
        PriorityQueue<Interval> queue=new PriorityQueue<>((o1,o2)->(o1.start-o2.start));
        for(int i=0;i<Intervals.size();i++){
            queue.add(Intervals.get(i));
        }
    ArrayList<Interval> res=new ArrayList<>();
        while (!queue.isEmpty()){
            Interval temp=queue.poll();
            while(!queue.isEmpty()&&temp.end>queue.peek().start){
                temp.end=Math.max(temp.end,queue.poll().end);
            }
            res.add(temp);
        }
        return  res;
}
    public static void main(String[] args) {
        ArrayList<Interval> Intervals=new ArrayList<>();
        Intervals.add(new Interval(10,30));
        Intervals.add(new Interval(20,60));
        Intervals.add(new Interval(80,100));
        Intervals.add(new Interval(150,180));
     ArrayList<Interval> result=merge(Intervals);
        System.out.print(result);
    }


原文地址:https://blog.csdn.net/qq_66767167/article/details/137833927

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!