前缀与后缀

发表于 | 更新于: | 分类于 |

259周赛

第二题

  • prefix-array suffix-array 前缀数组保存当前下标之前的最大值 后缀数组保存当前下标之后的最小值
  • 答案
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public int sumOfBeauties(int[] nums) {
        int n=nums.length;
        int[] l_max=new int[n];
        int[] r_min=new int[n];
        int Lmax=nums[0];
        int Rmin=nums[n-1];

        int beauty=0;

        for(int i=1;i<=n-2;i++){
            Lmax=Math.max(nums[i-1],Lmax);
            l_max[i]=Lmax;
        }

        for(int i=n-2;i>=1;i--){
            Rmin=Math.min(Rmin,nums[i+1]);
            r_min[i]=Rmin;
        }

        for(int i=1;i<=n-2;i++){
            if(nums[i]>l_max[i] && nums[i]<r_min[i]) beauty+=2;
            else if(nums[i]>nums[i-1] && nums[i]<nums[i+1]) beauty+=1;
        }
        return beauty;
    }
  • 超时
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public int sumOfBeauties(int[] nums) {
                int tempF=0,maxF=0,minB=2,tempB=2;
                int beauty=0;
                int n=nums.length;
                for(int i=1;i<n-1;i++){
                    if(nums[i-1]>nums[maxF]) maxF=i-1;

                    if(minB==i){
                        minB=i+1;
                        for(int k=i+1;k<n;k++){
                            if(nums[minB]>nums[k]) minB=k;
                        }
                    }else{
                        for(int k=tempB;k<n;k++){
                            if(nums[minB]>nums[k]) minB=k;
                            tempB++;
                        }
                    }
                    if(nums[i]>nums[maxF] && nums[i]<nums[minB]) beauty+=2;
                    else if(nums[i]>nums[i-1] && nums[i]<nums[i+1]) beauty+=1;
                }
                return beauty;
            }

    反思:

    代码中定义的变量过多，容易引起混淆
    for循环的堆叠增加了时间复杂度
    对前缀和的应用还不是很灵活，前缀数组既可以保存之和，也可以保存最大最小值
    通过这道题，明白了有时候需要对数据进行预处理,用最少的变量，先理清思路再code.

Question1 && Question560

  • 对于求子数组和的问题，先找关系式.Question1中的关系式为nums[i]+nums[j]=target
  • Question560中的关系式为subArraySum[i]-subArraySum[j]=k
  • 基于关系式，定义关系变量diff.

    Question1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int[] twoSum(int[] nums, int target) {
            HashMap<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<nums.length;i++){
                // 此处也可以写成 int diff=target-nums[i];  map.put(nums[i],i);
                int diff=nums[i]-target;
                if(map.containsKey(diff)) return new int[]{map.get(diff),i};
                map.put(-nums[i],i);
            }
            return null;
        }

Question560

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int sum=0;
        int n=nums.length;
        int res=0;
        map.put(0,1);
        for(int i=0;i<n;i++){
            sum+=nums[i];
            int diff=sum-k;
            if(map.containsKey(diff)) res+=map.get(diff);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return res;
    }

Question974

  • 思路：同余定理,(a-b)%k==0,则a%k=b%k. 特例，-1和9对5取余数。-1余数是-1，9的余数是4.但是(9+1)%5=0.
  • 所以本题需要避免为负数的情况 (sum%k+k)%k
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int subarraysDivByK(int[] nums, int k) {
            HashMap<Integer,Integer> map=new HashMap<>();
            int sum=0;
            int n=nums.length;
            int res=0;
            map.put(0,1);
            for(int i=0;i<n;i++){
                sum+=nums[i];
                int prefix=(sum%k+k)%k; // 避免之和为负数的情况
                res+=map.getOrDefault(prefix,0);
                map.put(prefix,map.getOrDefault(prefix,0)+1);

            }
            return res;
        }

    Question525

  • 思路：0和1的数量相同转换为 1的数量减去0的数量为0 可以将数组中的0视为-1. 问题转换为求和为0的最长子数组、
  • 出发点：1的数量减去0的数量为0. 1的数量即为所有1之和. 0之和由于没有意义 将0转化为-1之和
  • 延申1：求1的数量比0的数量多n的问题。 也就是求和为n的问题。
  • 延申2：求1的数量比0的数量多n倍的问题？
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int findMaxLength(int[] nums) {
            int n=nums.length;
            HashMap<Integer,Integer> map=new HashMap<>();
            int sum=0;
            int maxLen=Integer.MIN_VALUE;
            for(int i=0;i<n;i++){
                if(nums[i]==0) nums[i]=-1;
                else nums[i]=1;
            }
            map.put(0,0);
            for(int i=0;i<n;i++){
                sum+=nums[i];
                if(map.containsKey(sum)) maxLen=Math.max(maxLen,i+1-map.get(sum));
                else map.put(sum,i+1);
            }
            return maxLen==Integer.MIN_VALUE?0:maxLen;
        }

前缀和 竞赛题5882

  • 我的思路：先找出机器A的最大值的所有路径，分别遍历所有路径，求出每个路径下的最大值，再求出所有最大值中的最小值
  • 反思点：
    1. 不要以为机器A拿到了最大值，就可以限制B拿到最大值
    2. 数据格式限制 long型
    3. 在遍历过程中，每次遍历求出B两条路的最大值，最后再将res与该最大值进行比较，res取其中的最小值。而不是res=Math.max(max,res);
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      public long gridGame(int[][] grid) {
              int n=grid[0].length;
              long[] prefixArr1=new long[n+1];
              long[] prefixArr2=new long[n+1];
              long res=Long.MAX_VALUE;
              long sum=0;
              long sum1=0;
              for(int i=1;i<n+1;i++){
                  sum+=grid[0][i-1];
                  sum1+=grid[1][i-1];
                  prefixArr1[i]=sum;
                  prefixArr2[i]=sum1;
              }

              for(int i=1;i<n+1;i++){
                  long sub1=prefixArr1[n]-prefixArr1[i];
                  long sub2=prefixArr2[i-1];
                  long max=Math.max(sub1,sub2);
                  res=Math.min(max,res);
              }
              return res;
          }