暑期前端训练day6

好多天没有更新了，一直在熟悉项目和做需求，下班以后也是累了，直接开摆。
今天来更一下，水几个力扣每日一题，用ts写的，以后每天都打卡一道困难，除了周末。

题1： 力扣困难题，记忆化搜索。

• 链接：
  题目传送门
• 先上代码：

function earliestAndLatest(n: number, firstPlayer: number, secondPlayer: number): number[] {
    let c1 = firstPlayer - 1, c2 = n - secondPlayer;
    const dp = new Map<number, [number, number]>();
    const min = (x1: number, x2: number) => Math.min(x1, x2);
    const max = (x1: number, x2: number) => Math.max(x1, x2);

    const f = (x: number): [number, number] => {
        if(dp.has(x)) return dp.get(x) 
        const tmp: Array<number> = [] 
        let c1 = -1, c2 = -1, curIdx = 0 
        for(let i = 0; i < n; ++ i) { 
            if(x >> i & 1) {
                if(i + 1 === firstPlayer) c1 = curIdx
                else if(i + 1 === secondPlayer) c2 = curIdx  
                tmp.push(i + 1)
                curIdx ++ 
            }
        }

        if(c1 === tmp.length - 1- c2) {
            dp.set(x, [1, 1])
            return [1, 1] 
        }

        const m = tmp.length 
        const md2 = Math.floor(m / 2) 
        
        const nk = 1 << md2  
        let rs1 = n + 1, rs2 = 0 
        for(let i = 0; i < nk; ++ i ) {
            let flag = 1, sta = x 
            
            for(let j = 0; j < md2; ++ j ) {
                let l = tmp[j], r = tmp[tmp.length - 1 - j]
                if(i >> j & 1) {
                    if(r === firstPlayer || r === secondPlayer) {
                        flag = 0 
                        break 
                    }
                    sta -= (1 << r - 1) 
                }
                else {
                    if(l === firstPlayer || l === secondPlayer) {
                        flag = 0 
                        break 
                    }
                    sta -= (1 << l - 1)  
                }
            }
            if(!flag) continue 
            const [v1, v2] = f(sta)
            rs1 = min(rs1, v1 + 1) 
            rs2 = max(rs2, v2 + 1) 
        }

        dp.set(x, [rs1, rs2]) 
        return [rs1, rs2] 
    };
    const res = f((1 << n) - 1);
    return res 
}

• 总结：

  • 其实就是一道记忆化搜索，其实我对他的时间复杂度还是很感兴趣的，我们来探究一下他的时间复杂度，我们考虑最坏情况，当n = 28的时候, $2^{n/2}\ast n/2\ast 2^{n/4}\ast n/4\ast ....=2^{n/2+n/4+....}\ast (n/2\ast .n/4\ast ....\ast n/8)$，感觉在超时的边缘，但是不知道为什么过了…

  • 并且我在debug的时候吃了一个大亏，写多了C++，C++的除法默认都是取整，因为有int类型。但是js的每次都会算成一个小数，如果要取整，需要用Math.floor处理一下。

还有一些其他的题，太简单了，懒得写题解，已经熟悉用ts去实现这些东西。

题2:

题目传送门

code:

function maxFreeTime(eventTime: number, startTime: number[], endTime: number[]): number {
    const max: (m1: number, m2: number) => number = (m1, m2) => {
        if(m1 >= m2) m2 = m1 
        return m2  
    }

    const fn: () => number = () => {
        const timeRangeList: Array<any> = new Array()
        for(let i = 0; i < startTime.length; ++ i ) {
            let l, r 
            if(!i) {
                if(startTime[i] === 0) {
                    timeRangeList.push([0, 0, i])
                    continue 
                } 
                l = 0 
                r = startTime[i] 
            }
            else {
                l = endTime[i - 1] 
                r = startTime[i] 
            }
            if(l < r) {
                timeRangeList.push([l, r, i]) 
            }
            else {
                timeRangeList.push([startTime[i],startTime[i],i]) 
            }
        }
        if(endTime[endTime.length - 1] < eventTime) {
            let l = endTime[endTime.length - 1], r = eventTime 
            timeRangeList.push([l, r, undefined]) 
        }
        else {
            timeRangeList.push([eventTime, eventTime, undefined])
        }
        let n: number = timeRangeList.length 
        let ans = 0
        const ma = new Array(n).fill(0).
        map((item, idx) => {
            const u = timeRangeList[idx][1] - timeRangeList[idx][0]
            ans = max(ans, u) 
            return u 
        }) 

        const fa = new Array(n).fill(0).
        map((item, idx) => timeRangeList[idx][1] - timeRangeList[idx][0]) 

        for(let i = n - 2; i >= 0; -- i) ma[i] = max(ma[i], ma[i + 1]) 
        for(let i = 1; i < n; ++ i ) fa[i] = max(fa[i], fa[i - 1])             
        
        for(let i = 0; i < n - 1; ++ i ) {
            const [l, r, ix] = timeRangeList[i] 
            const va = -timeRangeList[i][0] + timeRangeList[i+1][1]
            const cur = -startTime[ix]+endTime[ix]
            if((i + 2 < n && ma[i + 2] >= cur) || 
            (i - 1 >= 0 && fa[i - 1] >= cur)) {
                // console.log("debug")
                ans = max(ans, va)
            } 
            // console.log(va, cur)
            ans = max(ans, 
                va - cur 
            )

        }

        return ans 
    }

    return fn() 
    
};

题3:

题目传送门

code:

function countDays(days: number, meetings: number[][]): number {
    const n: number = meetings.length
    meetings.sort(
        (a, b) => {
            if(a[0] === b[0] && a[1] === b[1]) return 0; 
            if(a[0] != b[0]) {
                if(a[0] < b[0]) return -1; 
                else return 1 
            }
            if(a[1] < b[1]) return -1; 
            return 1 
        }
    )
    let ans: number = days 
    for(let i = 0; i < n; ++ i ) {
        let j = i 
        let [l, r] = meetings[i]
        while(j + 1 < n && meetings[j + 1][0] <= r) {
            j ++ 
            r = Math.max(r, meetings[j][1] as number) 
        }
        ans -= (r - l + 1) 
        i = j
    }
    return ans 
};