暑期前端训练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 = curIdxelse 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 = 0const 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.lengthmeetings.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 
};