首页 > 代码库 > 华为 合唱队 算法
华为 合唱队 算法
题目描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述:
整数N
输出描述:
最少需要几位同学出列
输入例子:
8186 186 150 200 160 130 197 200
输出例子:
4
最少几位同学出列，可以转换成查找 数组中，每个数组元素的最长增序列 跟最长减序列
package org.huawei.test;import org.junit.Test;import java.util.Arrays;/** * Created by Administrator on 2016/10/7 0007. */public class man {//合唱团 @Test public void que(){ int [] high = {186,186,150,200,160,130,197,200};//input输入 int [] tagUp = new int[high.length]; int [] tagDown = new int[high.length]; int [] tag = new int[high.length]; for ( int i = 0 ; i < high.length;i++){ for(int j = i ; j < high.length; j++){//求得每个位置的最长增序 if (j == high.length-1){ break; } if (high[j] > high[j+1]){ tagUp[i] +=1; }else{ break; } } for (int j = i; j > 0; j--){//求得每个位置的最长减序 if (j == 0){ break; } if (high[j]>high[j-1]){ tagDown[i] +=1; }else{ break; } } } for(int i = 0; i < tag.length;i++){ if (tagDown[i] == 0 || tagUp[i] ==0){ tag[i] = 0; }else{ tag[i] = tagUp[i] + tagDown[i]; } } for(int tmp : tag){ System.out.println(tmp); } Arrays.sort(tag); System.out.println(tag.length-tag[tag.length-1]-1); }}
预计有些极端情况没有被想到
华为 合唱队 算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。