秋招笔试收获

素颜马尾好姑娘i 2022-09-11 04:14 173阅读 0赞

## 题目：有一组整型数据，里面有正数负数。从前往后遍历该数字，该数组每个节点可以选择取或者不取，在取的过程中，所取的数的和不能为负数。问最多能取多少个数？ ##

1.  可以使用优先级队列，把已经取了的值都加入小根堆，一旦遇到添加某个值，和为负数，就将该值加入小根堆，然后从小根堆移出一个数（也就是移除最小数），再调整所取的值的和，这样就相当于将到目前为止选择的数里面的最小值和当前值进行了交换。  
    通过数字替换，这个我倒是没想到，确实很神奇。如果当前值是所取的值里面的最小值，加入最小堆之后再移除出来还是该值。这样就能保证不应该取的数据会被替换掉。这样只需要遍历一遍就可以获得结果。
2.  也可以直接暴力，把所有情况都列出来再求每个情况是否可以全部取。更新最大值。

import java.util.*;
    public class Main{
        
        public int[] getNum(List<List<Long>> lists){
        
            int[] res=new int[lists.size()];
            int m=0;
            for(int i=0;i<lists.size();i++){
        
                List<Long> list=lists.get(i);
                int count=0;
                long tem=0;
                PriorityQueue<Long> queue=new PriorityQueue<>((a,b)->{
        
                    if(a>b){
        
                        return 1;
                    }else if(a<b){
        
                        return -1;
                    }else{
        
                        return 0;
                    }
                });
                for(int j=0;j<list.size();j++){
        
                    queue.offer(list.get(j));
                    tem+=list.get(j);
                    if(tem<0){
        //重点逻辑看这里，这样只需要遍历一遍就可以求出结果
                        long key=queue.poll();
                        tem-=key;
                    }else{
        
                        count++;
                    }
                }
                res[m]=count;
                m++;
            }
            return res;
        }
        public static void main(String[] args){
        
            Scanner sc=new Scanner(System.in);
            int t=sc.nextInt();
            List<List<Long>> lists=new ArrayList<>();
            for(int i=0;i<t;i++){
        
                int m=sc.nextInt();
                List<Long> list=new ArrayList<>();
                for(int j=0;j<m;j++){
        
                    list.add(sc.nextLong());
                }
                lists.add(list);
            }
            Main main=new Main();
            int[] res=main.getNum(lists);
            for(int i=0;i<res.length;i++){
        
                System.out.println(res[i]);
            }
        }
    }

## 题目：给很多组时间片，每组有一个开始时间和结束时间，求最大并发度。 ##

*  这不就是[求最少会议室][Link 1]吗？但是我居然没看出来。然后就直接用了暴力，估计就超时了。用最小堆估计就不会超时。

## 给一个字符串，字符串只含有小写字母，可以对字符串添加字母，或者删除字母，添加或者删除一次就记一次操作，问最少操作多少次能把字符串弄成回文字符串。 ##

该题考察的是动态规划，通过动规求出该字符串的最长回文子序列，字符串长度减最长回文子序列长度就是最少操作次数。需要注意处理特殊输入，输入字符串长度为0或者1.

## 数据库类型题 ##

公司最喜欢考的是分组函数。  
分组可以按照多个字段进行分组，单个字段进行分组。  
如果求前几大，可以去重，然后求出前几大的数据，再拿这些数据去做连接查询。  
查询某个时间之前或者之后，时间记得要加上单引号。

更新中…

[Link 1]: https://blog.csdn.net/weixin_43975276/article/details/120211769