周赛271

第一题：环和杆

题目描述

思路

存储每个位置出现的颜色值的集合，统计集合的大小等于3的位置个数，返回即可。

代码

var countPoints = function(rings) {
    let len =rings.length;
    let dp =new Array(10).fill(0).map(v=>new Set());// 表示第i个位置上集齐的颜色
    for(let i =0 ;i < len;i += 2){
        dp[+rings[i+1]].add(rings[i]);
    }
    let res=0;
    for(let i =0 ;i < 10;i++){
        if(dp[i].size == 3)res++;
    }
    return res;
};

第二题：子数组的范围和

描述

思路

遍历每个区间，求出最大值和最小值，然后累加最大值和最小值的差值，最后返回累加结果。
使用双重循环遍历区间，其中外循环遍历i作为区间的开始位置，内循环遍历j作为区间的结束位置。
遍历过程中满足dp[i,j] = max(max[i, j-1], nuns[j] ); 其中dp[i,j]表示区间[i,j]中的最大值。
区间最小值同理。

代码

var subArrayRanges = function(nums) {
    const n =nums.length;
    let sum = 0;
    let min,max;
    for(let i =0 ;i < n;i++){
        min = nums[i];
        max = nums[i];
        for(let j = i + 1 ;j < n; j++){
            min = nums[j] < min? nums[j]:min;
            max = nums[j] > max? nums[j]:max;
            sum += max - min;
        }
    }
    return sum;
};

第三题：给植物浇水 II

描述

思路

双指针两边向中间夹，直接模拟。

代码

var minimumRefill = function(plants, capacityA, capacityB) {
    const n=plants.length;
    let l=0, r = n-1;
    let a = capacityA, b = capacityB;
    let cnt=0;
    while(l < r){
        if(a >= plants[l]){
            a -= plants[l];
        }else{
            a = capacityA - plants[l];
            cnt++;
        }
        l++;
        if(b >= plants[r]){
            b -= plants[r];
        }else{
            b = capacityB - plants[r];
            cnt++;
        }
        r--;
    }
    if(l == r && ( a >= plants[l] || b >= plants[l]))return cnt;
    else if(l == r)return cnt+1;
    return cnt;
};

第四题：摘水果

描述

思路

先求出 前缀和，然后遍历可行的区间，得出各个可行区间和，得出最大的区间和即可。
注意： 只要是区间和问题，一律先求出前缀和

代码

var maxTotalFruits = function(fs, start, k) {  // 只要是区间和，就一定要求 前缀和
    const n = fs.length;
    const pre = [];                             //求出前缀和 ,
    const pos =  fs[n-1][0];
    for(let i = 0, j=0; i <= pos;  i++){
        if( i==0 && fs[j][0]==0 ){
            pre[0] = fs[j++][1];
        }else if(i == 0){
            pre[0] = 0;
        }else if(fs[j][0] == i){
            pre[i] = pre[i-1] + fs[j][1];            
            j++;
        }else{
            pre[i] = pre[i-1];
        }
    }
    if(k == 0){
        if(start > pos) return 0;
        if(start == 0) return pre[0];
        return pre[start] - pre[start-1];
    }
    let res = Math.max(get(k, 0), get(0,k));
    for(let i= k ; i > 0; i--){
        let left =  get(    i, k - 2*i);
        let right = get(k-2*i,      i);
        res=_.max([res,left,right]);
    }
    return res;
    function get( l, r){  // 返回区间l 到 r之间的区间和
        if(r < 0) r = 0;
        if(l < 0) l = 0;
        if(start - l - 1 < 0 && start + r > pos){
            return pre[pos];
        }else if(start-l-1 < 0){
            return pre[start+r]
        }
        else if(start+r > pos) {
            return pre[pos] -  pre[start-l-1];   
        }
        return pre[start+r] - pre[start-l-1];
    }
};