力扣春招100题——队列

字符串中的第一个唯一字符

题目

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

思路

这题根本没必要用队列，直接用哈希表就够了

• 使用哈希表记录字符出现的次数：遍历字符串，将每个字符及其出现的次数存储在哈希表中。
• 使用队列保存候选字符：将每个只出现一次的字符入队。
• 从队列中寻找第一个不重复字符：出队检查队列中第一个字符是否重复，如果重复则移除，直到找到第一个不重复的字符或者队列为空。

代码

public int firstUniqChar(String s) {
        Queue<int[]> q = new LinkedList<int[]>();
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
            q.offer(new int[]{c,i});
        }
        while(!q.isEmpty()){
            int[] arr = q.peek();
            char c = (char)arr[0];
            if(map.get(c)==1){
                return arr[1];
            }
            q.poll();
        }
        return -1;
    }

最近的请求次数

题目

933. 最近的请求次数 - 力扣（LeetCode）

思路

• 将时间戳添加到队列
• 每次都移除无效的队列元素，然后返回队列大小

代码

class RecentCounter {
    Queue<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<Integer>();
    }
    
    public int ping(int t) {
        queue.add(t);
        while(!queue.isEmpty()&&queue.peek() < t-3000) {
            queue.poll();
        }
        return queue.size();
    }
}

你可以安排的最多任务数目

题目

2071. 你可以安排的最多任务数目 - 力扣（LeetCode）

思路

• 排序：对任务和工人的力量值排序。
• 二分查找：二分查找可以完成的最大任务数。
• 贪心策略：判断给定的任务数是否能完成，优先用不需要药丸的工人来完成任务，必要时使用药丸。

代码

public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
       int l=0,r=Math.min(tasks.length,workers.length);
       while(l<r){
           int mid=(l+r+1)/2;
           if(fun(mid,tasks,workers,pills,strength)){
               l=mid;
           }else{
               r=mid-1;
           }
       }
       return l;
    }

    private boolean fun(int x, int[] tasks, int[] workers, int pills, int strength) {
        Deque<Integer> deque = new ArrayDeque<>();
        int sum=0;
        int j=workers.length-1;
        for(int i=x-1;i>=0;i--){
            while(j>=0&&workers[j]+strength>=tasks[i]){
                deque.addLast(workers[j]);
                j--;
            }
            if(deque.isEmpty()){
                return false;
            }
            if(deque.peekFirst()>=tasks[i]){
                deque.removeFirst();
            }else if(sum<pills){
                deque.removeLast();
                sum++;
            }else{
                return false;
            }
        }
        return true;
    }

结语

这个题组的难度，比原来的难度大多了，写的心碎了，好菜，怎么这么菜