【京东笔试】Java交流

京东笔试】Java
合唱队形&&考场安排
#京东##笔试题目##Java工程师#
全部评论
笔试的时候没写好,后来完善了一下(没有验证,不保证正确)。 思路是单调栈,栈中存放每一组的最大值。 如果当前元素比栈顶元素大,也就是当前元素可以自己分成一组,讲当前元素入栈。 如果当前元素比栈顶元素小,但是比栈中第二个大元素大,那么当前元素和栈顶元素可以分成一组,则不做处理即可。 如果当前元素小于栈中前两个元素,则先保存栈顶元素,讲栈中比当前元素大的都出栈,最后再将刚才保存的栈顶元素入站。最终栈中有几个元素,就可以分几组。 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); }
3 回复
分享
发布于 2019-08-25 09:12
考场安排怎么写,一直0%😂😂😂
点赞 回复
分享
发布于 2019-08-24 21:06
小红书
校招火热招聘中
官网直投
18 18唉
点赞 回复
分享
发布于 2019-08-24 21:07
我中途登网站百度了下编程语法,算作弊吗
点赞 回复
分享
发布于 2019-08-24 21:09
判断当前这个数是否能够分组,如果可以分组必要条件是,组间数排序后是 排序后的数组的对应部分。就是数能够全部抵消的感觉,有点像碰碰对,分组的条件是能够碰完前面的所有数。
点赞 回复
分享
发布于 2019-08-24 21:29
还没写完代码 网炸了 再登上 结束了😓
点赞 回复
分享
发布于 2019-08-24 21:40
100 18
点赞 回复
分享
发布于 2019-08-24 21:08
第一题没懂😅是最长连续子序列吗
点赞 回复
分享
发布于 2019-08-24 21:09
合唱团 好像是最长递增子序列
点赞 回复
分享
发布于 2019-08-24 21:09
#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%感觉没什么问题
点赞 回复
分享
发布于 2019-08-24 21:09
100 18第二题最后5分钟发现错在哪里了。。结果没时间写了,难受
点赞 回复
分享
发布于 2019-08-24 21:11
第一题,合唱队 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);     } }
点赞 回复
分享
发布于 2019-08-24 21:38
#合唱队形(再修改了一下下) 我最后提交的时候是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);             }         }     } } 自己测试的一次效果:
点赞 回复
分享
发布于 2019-08-24 21:50
有没有大佬看看思路对不对。。。笔试没时间写了。。 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());     } }
点赞 回复
分享
发布于 2019-08-24 21:53
我的思路,递归, 1、从头开始到最新分组位置找最大值, 2、然后从最大值到最新分组位置找最小值, 3、遍历前面,如果有比最小值大的数,更新分组坐标,循环再次重复2,3步骤,直到不发生改变 4、递归 我感觉这做法太暴力,时间复杂度很高,不知道大佬有没有指点?
点赞 回复
分享
发布于 2019-08-24 21:54
#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++代码。
点赞 回复
分享
发布于 2019-08-24 23:05
说实话,合唱队的题我都没看懂。 我大概是语文不好
点赞 回复
分享
发布于 2019-08-25 10:24
我保证你们过18%的都是过的样例😂😂😂
点赞 回复
分享
发布于 2019-08-25 10:58

相关推荐

3 21 评论
分享
牛客网
牛客企业服务