【上海校区】搜狗19年校招编程题(一)——找区间

python 未结 0 162
太原网络营销
太原网络营销 2021-07-22 15:26
悬赏:88
注:笔试时并没有AC,线下修改后可以输出示例结果。

问题:从一个序列中找出所有包含全部数字的最小索引区间,若有多个则按出现的顺序输出。

输入输出示例:

输入:1 1 3 4 6 6 5 1 1 3 3

输出:[2,7] [3,8] [4,9]

分析:先用一个list1来记录数组所有不重复的数字,再以0作为区间开始点,遍历数组(双重for循环),用一个list2来记录遍历过程中所有不重复的数字,遍历过程中判断list2的大小是否与list1相同,若相同则停止该轮遍历,并将停留点作为区间结束点。一趟结束后,再以该区间的开始点的下一个点作为新开始点进行遍历,重复直到新起点超过数组界限。需要注意的是在刚开始遍历时,可能出现类似“1,1,1”这样连续相同数字,为了求最小区间,应该把区间的开始点设为最后一个“1”的索引。

代码:

import java.util.ArrayList;
import java.util.Stack;
public class Main{

    public static void main(String[] args){

            int N = 10;
            int[] num ={1,1,2,2,3,2,1,3,2,1};
            //记录num中不重复的数
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i=0; i<N; i++){
                if(!list.contains(num)){
                    list.add(num);
                }
            }
            //记录遍历过程中不重复的数
            ArrayList<Integer> list2 = new ArrayList<Integer>();
            //记录每趟遍历的起点,用于应付“1,1,1”这样的情况
            Stack<Integer> stack = new Stack<Integer>();
            //记录每趟的起点
            Stack<Integer> startStack = new Stack<Integer>();
            //记录每趟的终点
            Stack<Integer> endStack = new Stack<Integer>();
            //为了按顺序输出,而准备,栈的逆序
            Stack<Integer> startStack2 = new Stack<Integer>();
            //为了按顺序输出,而准备,栈的逆序
            Stack<Integer> endStack2 = new Stack<Integer>();
            int start = -1;
            int end = -1;
            //第一趟从0开始,之后从start+1开始遍历
            for(int i=0; i<N; i++){
                    start = start+1;
                    end = -1;
                    //判断是否刚开始遍历,用于应付“1,1,1”这样的情况
                boolean begin1 = true;
               //用于判断是否连续,用于应付“1,1,1”这样的情况
                int idx = start;
                //如果开始遍历到结束的长度小于list,则说明之后的遍历无意义,故停止遍历
                if(N-start<list.size()){
                    break;
                }
                for(int j=start; j<N; j++){
                        //list2也只记录不重复的数字
                   if(!list2.contains(num[j])){
                       if(begin1){
                           stack.push(num[j]);
                           begin1 = false;

                       }
                       list2.add(num[j]);
                   }else{
                           //判断刚开始遍历时的连续情况“1,1,1”
                       if(stack.peek() == num[j] && j == idx+1){
                           start = j;
                           idx++;
                       }
                   }
                   //若已经全部找到数字,则结束该趟遍历
                   if(list.size() == list2.size()){
                        end = j;
                        list2.clear();//需要清空list2,以为下次所用
                        break;
                   }
                }
                //如果end不是初始值,说明遍历有意义
                if(end != -1){
                    startStack.push(start+1);
                    endStack.push(end+1);
                }
            }
            int size = startStack.size();
            //反转栈
            while(!startStack.isEmpty()){
                startStack2.push(startStack.pop());
                endStack2.push(endStack.pop());
            }
            //最终输出结果
            String res = "";
            int index = 0;
            while(!startStack2.isEmpty()){
                res += "["+startStack2.pop()+","+endStack2.pop()+"]";
                index++;
                //最后一个区间后面不加空格
                if(index == size){

                }else{
                    res +=" ";
                }

            }
            System.out.println(res);
    }
}
输出:[2,5] [4,7] [5,7] [6,8] [7,9] [8,10]
---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/82707595
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复