Leetcode第111次周赛解题报告

速度刷完了前三题，然后第四题被卡住，还是动态规划=_=

941. 有效的山脉数组

模拟，维护一个状态机，给其编码
0(没有上升)、1(上升中)、2(下降)
状态只能按照 0(没有上升)->1(上升中)->2(下降) 发展，且遍历完数组后状态必须在2

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int state = 0;
        int size = arr.size();
        for(int i = 1; i < size;i++){
            int now = arr[i];
            int last = arr[i-1];
            if(now < last) {
                if(state==0) return false;
                else if(state == 1) state = 2;
            }else if(now > last){
                if(state==0) state = 1;
                else if(state==2) return false;
            }else{
                return false;
            }
        }
        return state==2;
    }
};

944. 删列造序

简单题，相当于把字符串转置下，然后统计非递增串的个数（其实不用再赋值，直接遍历即可）

/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
        const len = strs.length
        const lenX = strs[0].length
        const arr = []
        for(let i = 0;i < lenX;i++) {
            const r = []
            for(let j = 0;j < len;j++){
                r.push(strs[j][i])
            }
            arr.push(r)
        }
        let cnt = 0
        const ok = (x)=>{
            for(let i = 1;i < x.length;i++) {
                if(x[i]<x[i-1]) return false
            }
            return true
        }
        arr.forEach(x=>{
            if(!ok(x)) cnt++
        })
        return cnt
};

942.增减字符串匹配

归纳：
维护一个右侧值R，维护一个左侧值L，因为R必大于L，所以每次

• 遇到D时从R侧取一个，因为当前取的是能够取到的最大的，下次取必然比本次小
• 遇到I时从L侧取一个，因为当前取的是能够取到的最小的，下次取必然比本次大

/**
 * @param {string} s
 * @return {number[]}
 */
var diStringMatch = function(s) {
    let [l,r] = [0,s.length]
    const ans = []
    for(let i = 0;i < s.length;i++){
        if(s[i]==="I") {
            ans.push(l++)
        }else{
            ans.push(r--)
        }
    }
    ans.push(l++)
    return ans
};

943. 最短超级串

又是DP，对于这种字符串+生成+动态规划+状压把buff叠起来的问题确实不会，学习下