前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >撬动offer:基于一道算法题​的分析

撬动offer:基于一道算法题​的分析

作者头像
BUG弄潮儿
发布2020-11-03 10:56:36
1800
发布2020-11-03 10:56:36
举报
文章被收录于专栏:JAVA乐园

0x01:算法题给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 1,2,3,4为连续的自然数)

示例1

输入 {100,4,200,1,3,2}

输出 4

示例2 输入 {200,201,202,100,4,200,1,3,2,204,203}

输出 5

0x02:分析

从题目分析我认为主要有两个考点:

  • 排序
  • 连续数字最长子串

但是具体要看面试官的阐述,比如如果面试官说可以使用系统自带的排序,那么就不要纠结到底使用冒泡排序,还是快速排序;直接使用Collections的sort方法即可。

从力扣上看下,有不少跟子串相关的算法题

0x03:参考实现

如下这个答案应该也算是一个暴力破解了,看看大家有没有更优的解法

代码语言:javascript
复制
import java.util.Scanner;
import java.util.*;
import java.lang.Integer;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String lineStr = scanner.nextLine();
        String[] elements = lineStr.split(" ");
        Vector<Integer> list = new Vector<Integer>();
        for (int i = 0; i < elements.length; i++) {
            Integer val = Integer.parseInt(elements[i]);
            if(!list.contains(val)){
                list.add(val);
            }
        }
        Collections.sort(list);
        System.out.println(list);
        int targetLen = 0;
        int startNum = list.get(0);
        int currentMaxLen = 1;
        for (int k = 1; k < list.size(); k++) {
            int e = list.get(k);
            startNum = startNum + 1;
            if ( e == startNum) {
                currentMaxLen = currentMaxLen + 1;
            } else {
                if (currentMaxLen > targetLen) {
                    targetLen = currentMaxLen;
                }
                startNum = list.get(k);
                currentMaxLen = 1;
                System.out.println(startNum);
            }

            if(k == list.size()-1){
                if (currentMaxLen > targetLen) {
                    targetLen = currentMaxLen;
                }
            }
        }
        System.out.println(targetLen);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-10-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 BUG弄潮儿 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档