全部评论
笔试的时候没写好,后来完善了一下(没有验证,不保证正确)。 思路是单调栈,栈中存放每一组的最大值。 如果当前元素比栈顶元素大,也就是当前元素可以自己分成一组,讲当前元素入栈。 如果当前元素比栈顶元素小,但是比栈中第二个大元素大,那么当前元素和栈顶元素可以分成一组,则不做处理即可。 如果当前元素小于栈中前两个元素,则先保存栈顶元素,讲栈中比当前元素大的都出栈,最后再将刚才保存的栈顶元素入站。最终栈中有几个元素,就可以分几组。 public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long a[] = new long[n];
for(int i=0;i<n;i++){
a[i] = sc.nextLong();
}
int top = -1;
long [] st= new long[n];
st[++top] = a[0];
for(int i=1;i<n;i++){
// 顶部元素
long tmp = st[top];
if(a[i]>=tmp){
st[++top] = a[i];
}else if(!(top>0&&a[i]>=st[top-1])){
while(top>=0&&st[top]>a[i]) {
top--;
}
st[++top] = tmp;
}
}
System.out.println(top+1);
}
送花
回复
分享
考场安排怎么写,一直0%😂😂😂
送花
回复
分享
滴滴
官网直投
18 18唉
送花
回复
分享
我中途登网站百度了下编程语法,算作弊吗
送花
回复
分享
判断当前这个数是否能够分组,如果可以分组必要条件是,组间数排序后是 排序后的数组的对应部分。就是数能够全部抵消的感觉,有点像碰碰对,分组的条件是能够碰完前面的所有数。
送花
回复
分享
还没写完代码 网炸了 再登上 结束了😓
送花
回复
分享
100 18
送花
回复
分享
第一题没懂😅是最长连续子序列吗
送花
回复
分享
合唱团 好像是最长递增子序列
送花
回复
分享
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int num[100001];
int Lmax[100001];
int Rmin[100001];
int main(){
int N;
cin>>N;
for (int i=1;i<=N;i++){
cin>>num[i];
}
stack<pair<int,int>> sta;
for (int i=1;i<=N;i++){
if (sta.empty()){
sta.push(make_pair(num[i],num[i]));
}
else{
pair<int,int> top;
bool isok=false;
while (!sta.empty()){
top=sta.top();
if (num[i]>=top.second){
sta.push(make_pair(num[i],num[i]));
isok=true;
break;
}
else{
sta.pop();
}
}
if (!isok)
sta.push(make_pair(min(num[i],top.first),max(num[i],top.second)));
}
}
cout<<sta.size();
}
36%感觉没什么问题
送花
回复
分享
100 18第二题最后5分钟发现错在哪里了。。结果没时间写了,难受
送花
回复
分享
第一题,合唱队 import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
String[] h=sc.nextLine().split(" ");
int[] height=new int[h.length];
for(int i=0;i<n;i++){
height[i]=Integer.parseInt(h[i]);
}
int[] poses=new int[h.length];
int result=0;
for(int i =0;i<h.length;i++){
int pos=i;
for(int j=i+1;j<h.length;j++){
if(height[i]>height[j]){
pos=j;
}
}
poses[i]=pos;
}
for(int i =0;i<h.length;i++){
if (poses[i]==i){
result+=1;
}else{
int start=i;
int end=poses[i];
for(int j=start;j<=end ;j++){
if(poses[j]>end) end=poses[j];
}
result+=1;
i=end;
}
}
System.out.println(result);
}
}
送花
回复
分享
#合唱队形(再修改了一下下) 我最后提交的时候是18,后面一直调,调着调着就自动交卷了 现在好像调出来了,请大佬们帮我看看有没有错的地方😥 import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList();
int N = 0;
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
while(N > 0){
list.add(sc.nextInt());
N--;
}
System.out.println(getGroupNum(list));
}
public static int getGroupNum(ArrayList<Integer> arr){
if(arr.size() <= 1){
return arr.size();
}
HashMap<Integer,Integer> map = new HashMap<>();
int max = arr.get(0);
int min = arr.get(0);
for(int i = 1; i < arr.size(); i++){
int cur = arr.get(i);
if(cur <= min){ //如果后面的值小于等于min,则说明前面最小值为min的组不能组成一队了,要和后面的一起
deleteMap(map,cur); //把大于cur的key都移除
map.put(cur,max);
min = max;
}else if(cur > max){ //如果遇到大于max的,则修改max的值
max = cur;
}
}
return map.size();
}
public static void deleteMap(HashMap<Integer,Integer> map,int k){
Set<Integer> set = map.keySet(); //获取keySet
Iterator<Integer> keys = set.iterator();
while(keys.hasNext()){ //遍历keySet,如果有最小值大于k的组,就把它移除
int key = keys.next();
if(key > k){
map.remove(key);
}
}
}
} 自己测试的一次效果:
送花
回复
分享
有没有大佬看看思路对不对。。。笔试没时间写了。。 class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int nums = in.nextInt();
int[] ids = new int[nums];
for (int i = 0; i < nums; i++) {
ids[i] = in.nextInt();
}
//两个栈存储每个分组的最大最小值
Stack<Integer> subMax = new Stack<>();
Stack<Integer> subMin = new Stack<>();
int min = 0;
for (int i = nums - 1; i >= 0; i--) {
int temp = ids[i];
if (i == nums - 1) {
subMax.add(temp);
subMin.add(temp);
continue;
}
if (temp <= subMin.peek()) {
subMin.add(temp);
subMax.add(temp);
}else {
int count = 0;
boolean modified = false;
while (!subMax.isEmpty() && temp > subMax.peek()) {
subMax.pop();
count++;
modified = true;
}
min = subMin.peek();
while (count != 0) {
subMin.pop();
count--;
}
if (modified) {
subMax.add(temp);
subMin.add(min);
}
}
}
System.out.println(subMax.size());
}
}
送花
回复
分享
我的思路,递归, 1、从头开始到最新分组位置找最大值, 2、然后从最大值到最新分组位置找最小值, 3、遍历前面,如果有比最小值大的数,更新分组坐标,循环再次重复2,3步骤,直到不发生改变 4、递归 我感觉这做法太暴力,时间复杂度很高,不知道大佬有没有指点?
送花
回复
分享
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int findleftmaxnum(vector<int> &nums,int l,int r)
{
int maxnum = nums[l];
for(int i=l;i<r;i++)
{
maxnum = maxnum<nums[i]?nums[i]:maxnum;
}
return maxnum;
}
int findrightindex(vector<int> &nums,int maxnum, int l)
{
int index = l;
for(int i = nums.size()-1;i>l;i--)
{
if(nums[i]<maxnum)
return i;
}
return l;
}
//10
//69079936 236011312 77957850 653604087 443890802 277126428 755625552 768751840 993860213 882053548
int main()
{
int n = 0;
cin>>n;
vector<int > nums,numa;
unordered_map<int, int> mp;
for(int i=0;i<n;i++)
{
int temp = 0;
cin>>temp;
nums.push_back(temp);
numa.push_back(temp);
mp[temp] = i;
}
sort(nums.begin(),nums.end());//排序用于定位当前区间的最小值
int count = 0;
for(int i=0;i<nums.size();i++)
{
int temp = nums[i];
int index = mp[temp];
int maxnum = findleftmaxnum(numa,i,index);//找到当前区间的最小值左侧的最大值元素的值
int right =findrightindex(numa,maxnum,index);//从当前区间的最右侧开始 找到第一个小于上一步找到的最大值的值
i = right;//划分区间
count++;
}
cout<<count<<endl;
return 1;
}
//12 18 14 11 15 6 7 14 20 6 19 20 23 22
//2 1 3 2 4 3 5 3 6 5 7 6 7 答题的时候A了18,后来发现判断条件的时候多了个等号,去掉后感觉能提高不少,思路类似快排,只不过每次先找当前区间的最小值,然后找最小值左侧的最大值,判断这个最小值和最大值确定的区间能覆盖的范围,该范围就是一个满足要求的区间,然后再进行后面区间的partition。 C++代码。
送花
回复
分享
说实话,合唱队的题我都没看懂。 我大概是语文不好
送花
回复
分享
我保证你们过18%的都是过的样例😂😂😂
送花
回复
分享
相关推荐
投递比亚迪精密制造等公司10个岗位 >
点赞 评论 收藏
转发