题解 | #合唱队#

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

解题思路

  1. 这是一道最长上升下降子序列问题
  2. 对于每个位置i,需要求:
    • 左边的最长上升子序列长度(LIS)
    • 右边的最长下降子序列长度(LDS)
  3. 最后用总人数减去最大的(LIS + LDS - 1)即为需要出列的最少人数

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> heights(n);
        for (int i = 0; i < n; i++) {
            cin >> heights[i];
        }
        
        // 计算每个位置左边的最长上升子序列长度
        vector<int> left(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (heights[i] > heights[j]) {
                    left[i] = max(left[i], left[j] + 1);
                }
            }
        }
        
        // 计算每个位置右边的最长下降子序列长度
        vector<int> right(n, 1);
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j > i; j--) {
                if (heights[i] > heights[j]) {
                    right[i] = max(right[i], right[j] + 1);
                }
            }
        }
        
        // 找出最大的合唱队形长度
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = max(maxLen, left[i] + right[i] - 1);
        }
        
        // 需要出列的最少人数
        cout << n - maxLen << endl;
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = sc.nextInt();
            }
            
            // 计算每个位置左边的最长上升子序列长度
            int[] left = new int[n];
            Arrays.fill(left, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (heights[i] > heights[j]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }
            
            // 计算每个位置右边的最长下降子序列长度
            int[] right = new int[n];
            Arrays.fill(right, 1);
            for (int i = n-1; i >= 0; i--) {
                for (int j = n-1; j > i; j--) {
                    if (heights[i] > heights[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }
            
            // 找出最大的合唱队形长度
            int maxLen = 0;
            for (int i = 0; i < n; i++) {
                maxLen = Math.max(maxLen, left[i] + right[i] - 1);
            }
            
            System.out.println(n - maxLen);
        }
    }
}
while True:
    try:
        n = int(input())
        heights = list(map(int, input().split()))
        
        # 计算每个位置左边的最长上升子序列长度
        left = [1] * n
        for i in range(n):
            for j in range(i):
                if heights[i] > heights[j]:
                    left[i] = max(left[i], left[j] + 1)
        
        # 计算每个位置右边的最长下降子序列长度
        right = [1] * n
        for i in range(n-1, -1, -1):
            for j in range(n-1, i, -1):
                if heights[i] > heights[j]:
                    right[i] = max(right[i], right[j] + 1)
        
        # 找出最大的合唱队形长度
        max_len = max(left[i] + right[i] - 1 for i in range(n))
        
        print(n - max_len)
    except:
        break

算法及复杂度

  • 算法:动态规划(最长上升/下降子序列)
  • 时间复杂度:,其中n为学生总数
  • 空间复杂度:,需要两个长度为n的数组存储dp值
全部评论

相关推荐

点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:35
虽然不怎么光彩,经过这件事,可能我真的要去认同“面试八股文早该淘汰!不会用AI作弊的程序员=新时代文盲!”这句话了
HellowordX:Ai的出现是解放劳动力的,不是用来破坏公平竞争环境的,这样下去,轻则取消所有线上面试,严重了会影响整个行业对所有人产生影响,企业会拉高入职考核各种离谱考核会层出不穷
你找工作的时候用AI吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务