Problem A

  • 题目链接:统计数组中峰和谷的数量
  • 题目分析:波峰和波谷出现,必然是有单调性,当出现波谷,那么必然之前存在单调递增的波峰。同理,当出现波峰,必然它前面出现波谷的。通过这个性质利用单调性,可以在O(n)的时间内求出答案。
  • 题目代码:
    • 
      	/**
      	 * @param {number[]} nums
      	 * @return {number}
      	 */
      	var countHillValley = function(nums) {
      	    let [pre, ans, flag] = [nums[0], 0, 0];
      	    for (let i = 0; i < nums.length; ++ i) {
      	        if (pre == nums[i])
      	            continue;
      
      	        if (nums[i] > pre) {
      	            // 之前是单调递减
      	            ans += (flag == -1);
      	            flag = 1;
      	        }
      
      	        if (nums[i] < pre) {
      	            // 之前是单调递增
      	            ans += (flag == 1);
      	            flag = -1;
      	        }
      	        pre = nums[i];
      	    }
      	    return ans;
      	};
      

Problem B

  • 题目链接:统计道路上的碰撞次数
  • 解题思路:对于 L 方向的汽车,只有在最左端,才不会出现碰撞。 对于 R 方向的汽车,只有在最右端,才不会出现碰撞。所以,对于 L 方向的汽车 左边出现 R 或 S 方向的汽车,那么必然会碰撞。对于 R 方向的汽车,右边出现 R 或 S 方向的汽车必然会碰撞。
  • 解题代码
    • 
      	/**
      	 * @param {string} directions
      	 * @return {number}
      	 */
      	var countCollisions = function(directions) {
      
      	    let [ans, flag] = [0, false];
            // 统计 L 方向的左边
      	    for (const c of directions) {
      	        if (c == 'R' || c == 'S') flag = true;
      	        else if (flag) ans ++;
      	    }
      
            // 统计 R 方向的右边
      	    flag =  false;
      	    for (let i = directions.length - 1; i >= 0; -- i) {
      	        let c = directions[i];
      	        if (c == 'L' || c == 'S') flag = true;
      	        else if (flag) ans ++;
      	    }
      
      	    return ans;
      	};
      

Problem C

  • 题目链接:射箭比赛中的最大得分
  • 解题思路:我们可以枚举bob的对所有区间的得分状态,那么一共有(1 << 12) 个状态。如果bob某一个区间得分,那么他只要在该区间的射箭数尾 aliceAllows[i] + 1. 如果还有剩余的箭,则随意放在哪个区间都可以。
  • 解题代码:
    • 
      	/**
      	 * @param {number} numArrows
      	 * @param {number[]} aliceArrows
      	 * @return {number[]}
      	 */
      	var maximumBobPoints = function(numArrows, aliceArrows) {
      	    const n = aliceArrows.length;
      	    let ans = 0, best = new Array(n).fill(0);
      
      	    // 二进制枚举 bob所有区间的得分状态
      	    for (let i = 0; i < (1 << n); ++ i) {
      	        let [tot, score] = [0, 0];
      
      	        for (let j = 0; j < n; ++ j)
      	            // 该位是1表示,bob在该区间要得分
      	            if (i >> j & 1) {
      	                tot += aliceArrows[j] + 1;
      	                score += j;
      	            }
      	        if (tot <= numArrows && score > ans) {
      	            ans = score;
      	            for (let j = 0; j < n; ++ j) {
      	                if (i >> j & 1)
      	                    best[j] = aliceArrows[j] + 1;
      	                else 
      	                    best[j] = 0;
      	            }
      	            // 将剩余的箭放在任意一个区间,不影响答案
      	            best[n - 1] += numArrows - tot;
      	        }
      	    }
      
      	    return best;
      
      	};
      

Problem D