算法研究:已知不重复的int集合,求最长递增子序列

简介: 算法研究

问题背景:最近换工作面试,面试官问了一道编程题,大体是已知不重复的int集合,求最长递增子集合,这个集合可以不是连续的,但顺序呢不能乱。

比如说:{2, 7, 3, 13, 6, 8}里最长递增子集合的就是{2,3,6,8}。

这道题感觉很有意思,于是回家就用代码实现了一遍。

主要代码:

package com.galaxy.fym.algorithm.maxsublist;

import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fengyiming on 2017/2/16.
 * @author fengyiming 对int集合转化成所有可能的递增子集合
 */
public class Search {

    public static List<List<Integer>> search(List<Integer> list) {
        List<List<Integer>> allList = new ArrayList<List<Integer>>();
        int size = list.size();
        for (int i = 0; i < size; i++) {
            int value = list.get(i);
            //这个集合用来存储如果当前value被加入到其他子集合的时候保存被加入的子集合的原值
            List<List<Integer>> newAllList = new ArrayList<List<Integer>>(allList.size());
            //对已存在的子集合集合遍历,判断当前元素是否小于子集合,是的话就加在结尾,另外保存当前子集合
            if(CollectionUtils.isNotEmpty(allList)) {
                for (List<Integer> subList : allList) {
                    int subSize = subList.size();
                    int last2Value = subList.get(subSize - 1);
                    if (last2Value < value) {
                        //如果仅次于,便不用添加了
                        if(value - last2Value > 1) {
                            newAllList.add(new ArrayList<Integer>(subList));
                        }
                        subList.add(value);
                    }
                }
            }
            //将被加入元素的子集合的原值放入到所有子集合里
            if(CollectionUtils.isNotEmpty(newAllList)){
                allList.addAll(newAllList);
            }
            //新建一个仅含当前元素的子集合
            List<Integer> newSubList = new ArrayList<Integer>(size - 1);
            newSubList.add(value);
            allList.add(newSubList);
        }
        return allList;
    }

    public static List<List<Integer>> getMaxList(List<List<Integer>> allList){
        System.out.println("---------------所有递增子集合-------------");
        int max = 0;
        List<List<Integer>> allSubList = new ArrayList<List<Integer>>();
        for (List<Integer> subList : allList) {
            for (Integer value : subList) {
                //System.out.print(value + " ");
            }
            if (subList.size() > max) {
                max = subList.size();
                allSubList = new ArrayList<List<Integer>>();
                allSubList.add(subList);
            } else if (subList.size() == max) {
                allSubList.add(subList);
            }
            //System.out.println();
        }
        System.out.println("---------------最长的子集合-------------");
        for (List<Integer> subList : allSubList) {
            for (Integer value : subList) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
        return allList;
    }
}

测试结果(我隐藏了输出所有集合的结果)(mac pro,i7 4核)

---------------随机数列-------------
17 13 16 8 5 25 10 18 14 0 27 3 2 9 7 4 44 29 12 30 
---------------随机数列-------------
消耗时间10ms
总集合长度538
去重后集合长度538
重复元素数量0
---------------最长的子序列-------------
13 16 25 27 29 30 
13 16 18 27 29 30 
8 10 18 27 29 30 
5 10 18 27 29 30 
8 10 14 27 29 30 
5 10 14 27 29 30 

Process finished with exit code 0

总结:花了1个多小时写这段代码,感觉这道题重要的难点就是不连续的子集合这点,因为所有子集合数量应该是集合大小的阶乘。但是递增子集合就会少很多。

目录
相关文章
|
27天前
|
机器学习/深度学习 数据采集 搜索推荐
机器学习在智能推荐系统中的个性化算法研究
机器学习在智能推荐系统中的个性化算法研究
|
28天前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的自适应学习算法研究与应用
在深度学习领域,传统的静态模型在处理动态环境和非平稳数据时面临挑战。本文探讨了自适应学习算法在深度学习中的重要性及其应用。通过分析自适应学习算法在模型参数、损失函数和数据分布上的应用,展示了其在提升模型鲁棒性和泛化能力方面的潜力。具体讨论了几种代表性的自适应学习方法,并探索了它们在现实世界中的应用案例,从而展示了其在处理复杂问题和动态数据中的效果。
35 0
|
11天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
181 1
|
1天前
|
算法 安全 搜索推荐
AES(Advanced Encryption Standard)是一种广泛使用的对称密钥加密算法,由美国国家标准技术研究所(NIST)制定。
AES(Advanced Encryption Standard)是一种广泛使用的对称密钥加密算法,由美国国家标准技术研究所(NIST)制定。
20 9
|
4天前
|
机器学习/深度学习 数据采集 算法
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
|
25天前
|
机器学习/深度学习 人工智能 算法
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
31 0
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
|
19天前
|
算法 Java
Java数据结构与算法:用于处理不相交集合的合并和查找问题
Java数据结构与算法:用于处理不相交集合的合并和查找问题
|
19天前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
18 0
|
1月前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
17 0
|
1月前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
19 0

热门文章

最新文章