力扣第236场周赛

题一数组元素积的符号

描述

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

如果 x 是正数，返回 1 。如果 x 是负数，返回 -1 。如果 x 是等于 0 ，返回 0 。给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

思路

本题可以转换成求负数个数。

代码

class Solution {
    public int arraySign(int[] nums) {
        int cnt1=0;
        for (int i:nums)
        {
            if(i==0)return 0;
            if(i<0)cnt1++;
        }
        if(cnt1%2==0)return 1;
        return -1;
    }   
}

题二找出游戏的获胜者

描述

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按顺时针顺序从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则：

从第 1 名小伙伴所在位置开始。沿着顺时针方向数 k 名小伙伴，计数时需要包含起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的顺时针下一位小伙伴开始，回到步骤 2 继续执行。否则，圈子中最后一名小伙伴赢得游戏。给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

思路

看成队列
模拟游戏规则

代码

class Solution {
    public int findTheWinner(int n, int k) {
        Queue<Integer> queue=new ArrayDeque<>();
        for (int i=1;i<=n;i++){
            queue.add(i);
        }
        int cur=k;
        while (queue.size()>1){
            cur--;
            int p=queue.poll();
            if(cur!=0)queue.add(p);
            else cur=k;
        }
        return queue.poll();
    }
}

题三

描述

给你一个长度为 n 的 3 跑道道路，它总共包含 n + 1 个点，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道出发，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中最多有一个障碍。

比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在同一个点处侧跳到另外一条跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的任一跑道，请你返回最少侧跳次数。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

思路

动态规划:

dp[number][idx] 表示 在number跑道的idx位置到终点最少还需要几次

代码

class Solution {
    public int minSideJumps(int[] obstacles) {
        int[][] dp=new int[3][obstacles.length];
        for (int i=0;i<3;i++) Arrays.fill(dp[i],-1);
        int res=slove(2, 0, obstacles, dp);
        return res;
    }

    private int slove(int number, int idx, int[] obstacles, int[][] dp) {
        if(dp[number-1][idx]!=-1)return dp[number-1][idx];
        int res=Integer.MAX_VALUE>>1;
        if(idx==obstacles.length-1)return 0;
        if(obstacles[idx+1]!=number)res=slove(number,idx+1,obstacles,dp);
        else {
            for (int i=1;i<=3;i++)
            {
                if(obstacles[idx]==i||obstacles[idx+1]==i)continue;
                res=Math.min(res,1+slove(i,idx,obstacles,dp));
            }
        }
        return dp[number-1][idx]=res;
    }
}

题四求出 MK 平均值

描述

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值。

MK 平均值按照如下步骤计算：

如果数据流中的整数少于 m 个，MK 平均值为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。从这个容器中删除最小的 k 个数和最大的 k 个数。计算剩余元素的平均值，并向下取整到最近的整数。请你实现 MKAverage 类：

MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。 void addElement(int num) 往数据流中插入一个新的元素 num 。 int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数，结果需向下取整到最近的整数。

思路

用4颗TreeSet树，一颗维护最小的K个值，一颗维护小的临时值，一颗维护最大的K个值，一颗维护最大的临时K个值。
临时值的两颗树存在的意义：用来存储未过期的值，在对应的小树和大树个树不够的时候补充。
用一个队列维护没有过期的值。
对最小树、最大树和队列操作的同时维护各自的sum。

代码

import java.util.*;

/**
 * author: fangjie
 * email: syfangjie@live.cn
 * date: 2021/4/11 11:03 上午
 */
public class N4 {
    //["MKAverage","addElement","addElement","calculateMKAverage","addElement","addElement","calculateMKAverage","addElement","addElement","calculateMKAverage","addElement"]
    //[[3,1],[58916],[61899],[],[85406],[49757],[],[27520],[12303],[],[63945]]
    public static void main(String[] args) {
        MKAverage mkAverage = new MKAverage(3, 1);
        mkAverage.addElement(58916);
        mkAverage.addElement(61899);
        System.out.println(mkAverage.calculateMKAverage());
        mkAverage.addElement(85406);
        mkAverage.addElement(49757);
        System.out.println(mkAverage.calculateMKAverage());
        mkAverage.addElement(27520);
        mkAverage.addElement(12303);
        System.out.println(mkAverage.calculateMKAverage());
        mkAverage.addElement(63945);
    }
}
class MKAverage {

    private final int m;
    private final int k;

    private int sum;
    private int size;

    private Queue<int[]> queue;
    private int minSum;
    private TreeSet<int[]> min;
    private TreeSet<int[]> minT;

    private int maxSum;
    private TreeSet<int[]> max;
    private TreeSet<int[]> maxT;


    public MKAverage(int m, int k) {
        this.m=m;
        this.k=k;
        this.sum=this.maxSum=this.minSum=this.size=0;
        this.queue=new ArrayDeque<>();
        min=new TreeSet<>((o1, o2) -> {
            if(o1[0]==o2[0])return Integer.compare(o1[1],o2[1]);
            return Integer.compare(o1[0],o2[0]);
        });
        minT=new TreeSet<>((o1, o2) -> {
            if(o1[0]==o2[0])return Integer.compare(o1[1],o2[1]);
            return Integer.compare(o1[0],o2[0]);
        });
        max=new TreeSet<>((o1, o2) -> {
            if(o1[0]==o2[0])return Integer.compare(o1[1],o2[1]);
            return Integer.compare(o2[0],o1[0]);
        });
        maxT=new TreeSet<>((o1, o2) -> {
            if(o1[0]==o2[0])return Integer.compare(o1[1],o2[1]);
            return Integer.compare(o2[0],o1[0]);
        });
    }

    public void addElement(int num) {
        size++;
        int[] cur = {num, size};
        sum+=num;
        queue.add(cur);
        if(queue.size()>m){
            int[] c = queue.poll();
            sum-=c[0];
            minT.remove(c);
            if(min.remove(c))minSum-=c[0];
            maxT.remove(c);
            if(max.remove(c))maxSum-=c[0];

        }
        minSum+=help(min,minT,cur);
        maxSum+=help(max,maxT,cur);
    }
    private int help(TreeSet<int[]> set,TreeSet<int[]>tSet,int[] cur){
        int res=0;
        while (set.size()<k&&!tSet.isEmpty()){
            int[] c=tSet.pollFirst();
            res+=c[0];
            set.add(c);
        }
        set.add(cur);
        res+=cur[0];
        while (set.size()>k){
            int[] c=set.pollLast();
            res-=c[0];
            tSet.add(c);
        }
        return res;
    }

    public int calculateMKAverage() {
        if(queue.size()<m)return -1;
        //System.out.println(Arrays.toString(new int[]{sum,minSum,maxSum}));
        return (sum-minSum-maxSum)/(m-2*k);
    }
}
/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage obj = new MKAverage(m, k);
 * obj.addElement(num);
 * int param_2 = obj.calculateMKAverage();
 */
/*

力扣第236场周赛

题一 数组元素积的符号

描述

思路

代码

题二 找出游戏的获胜者

描述

思路

代码

题三

描述

思路

代码

题四 求出 MK 平均值

描述

思路

代码

题一数组元素积的符号

题二找出游戏的获胜者

题四求出 MK 平均值