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

简介: 本篇记录的是一道关于算法题的分析内容、

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方法即可。

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


微信图片_20220502084444.png

 

0x03:参考实现


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


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(" ");
        List<Integer> list = new ArrayList<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);
    }
}


相关文章
|
1月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
60 4
|
3月前
|
人工智能 算法 BI
第一周算法设计与分析 D : 两面包夹芝士
这篇文章介绍了解决算法问题"两面包夹芝士"的方法,通过找出两个数组中的最大最小值,计算这两个值之间的整数个数,包括特判不存在整数的情况。
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
25天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
2月前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
58 4
|
1月前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
2月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
41 1
|
2月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
126 19
下一篇
无影云桌面