这次生病了拖了这么久才做完这次的题
/**
* @param {number[][]} coordinates
* @return {boolean}
*/
var checkStraightLine = function (coordinates) {
const n = coordinates.length;
if (n === 2) return true;
const a = coordinates[0][0] - coordinates[1][0], b = coordinates[0][1] - coordinates[1][1];
for (let i = 2; i < n; i++) if ((coordinates[i][0] - coordinates[i - 1][0]) * b !== (coordinates[i][1] - coordinates[i - 1][1]) * a) return false;
return true;
};
/**
* @param {string[]} folder
* @return {string[]}
*/
function T(bool, val) {
this.val = val;
this.end = bool;
this.children = [];
}
var removeSubfolders = function (folder) {
const m = new T(false, '/');
function h(arr, val) {
for (const i in arr) if (arr[i].val === val) return i;
return -1;
}
for (const f of folder) {
const fArr = f.split('/');
if (fArr[0] === '') fArr.shift();
if (fArr.length === 0) continue;
let t = m;
for (let i = 0; i < fArr.length; i++) {
const index = h(t.children, fArr[i]);
if (index !== -1) {
if (t.end || t.children[index].end) break;
if (i === fArr.length - 1) t.children[index].end = true;
t = t.children[index];
} else {
if (i === fArr.length - 1) t.children.push(new T(true, fArr[i]));
else t.children.push(new T(false, fArr[i]));
t = t.children[t.children.length - 1];
}
}
}
let s = '';
const r = [];
function dfs(root) {
if (root.children && root.children.length > 0) {
for (const a of root.children) {
const ttt = s;
s += '/' + a.val;
if (a.end) {
r.push(s);
s = ttt;
continue;
}
dfs(a);
s = ttt;
}
}
}
dfs(m)
return r;
};
// 滑动窗口的常规做法, 使窗口外的字母符合题目中的条件, 符合之后往后移动窗口, 找到符合条件的最小的窗口.
/**
* @param {string} s
* @return {number}
*/
var balancedString = function (s) {
const n = s.length, nn = n / 4, m = { Q: 0, W: 0, E: 0, R: 0 };
let l = 0, r = 0, min = n;
for (const c of s)++m[c];
while (r <= n) {
if (m['Q'] > nn || m['W'] > nn || m['E'] > nn || m['R'] > nn)--m[s[r++]];
else {
if (r - l < min) min = r - l;
if (min === 0) break;
++m[s[l++]];
}
}
return min;
};
// dp问题, dp[i] = 结束时间为 i 获得的最大利润,
// dp[i] = 结束时间为i的任务的开始时间j之前可以获得的最大利润
/**
* @param {number[]} startTime
* @param {number[]} endTime
* @param {number[]} profit
* @return {number}
*/
var jobScheduling = function (startTime, endTime, profit) {
const lowerBound = function (arr2, val) {
let f = 0, arr = arr2[0], l = arr.length;
if (val > arr[l - 1]) return l - 1;
if (val < arr[0]) return 0;
let m;
while (f < l) {
m = f + parseInt((l - f) / 2);
if (arr[m] < val) f = m + 1;
else if (arr[m] === val) return m;
else l = m;
}
return f - 1;
}
const n = startTime.length, dp = [[0], [0]], jobs = [];
for (let i = 0; i < n; i++) jobs[i] = [startTime[i], endTime[i], profit[i]];
jobs.sort((a, b) => a[1] - b[1]);
for (const [s, e, p] of jobs) {
const cur = dp[1][lowerBound(dp, s)] + p;
if (cur > dp[1][dp[1].length - 1]) { dp[0].push(e); dp[1].push(cur); }
}
return dp[1][dp[1].length - 1];
};