最后一题是个模板题, 求割边
/**
* @param {string} text
* @return {number}
*/
var maxNumberOfBalloons = function (text) {
const m = { b: 0, a: 0, l: 0, o: 0, n: 0 };
let r = Number.MAX_SAFE_INTEGER;
for (const c of text) {
if ('balloon'.indexOf(c) !== -1) {
if (m[c])++m[c];
else m[c] = 1;
}
}
const keys = Object.keys(m);
for (const i of keys) {
r = Math.min(r, m[i]);
}
return Math.min(r, parseInt(m['l'] / 2), parseInt(m['o'] / 2));
};
/**
* @param {string} s
* @return {string}
*/
var reverseParentheses = function (s) {
s = s.split('');
const h = (s, j) => {
while (j >= 0) {
if (s[j] === '(') return j;
else --j;
}
}
for (const i in s) {
if (s[i] === ')') {
const j = h(s, i - 1);
s[i] = s[j] = '*';
s.splice(j + 1, i - j - 1, ...s.slice(j + 1, i).reverse());
}
}
let r = '';
for (const c of s) {
if (c !== '*') r += c;
}
return r;
};
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var kConcatenationMaxSum = function (arr, k) {
const h = arr => {
let max = Number.MIN_SAFE_INTEGER, sum = 0;
for (const a of arr) {
if (sum < 0) sum = a;
else sum += a;
if (sum > max) max = sum;
}
return max > 0 ? max : 0;
}
let r = 0;
const n1 = h(arr);
if (k === 1) return n1;
const n2 = h([...arr, ...arr]);
const n3 = h([...arr, ...arr, ...arr]);
if (n1 === 0) return 0;
if (n2 > 2 * n1 || n2 === n3) return n2;
if (n3 - n2 === n2 - n1) {
r = n1;
const d = n2 - n1;
for (let i = 1; i < k; i++) {
r += d;
r %= 10 ** 9 + 7;
}
return r;
}
for (let i = 0; i < k; i++) {
r += n1;
r %= 10 ** 9 + 7;
}
return r;
};
/**
* @param {number} n
* @param {number[][]} connections
* @return {number[][]}
* https://www.cnblogs.com/nullzx/p/7968110.html
*/
var criticalConnections = function (n, connections) {
let index = -1;
const dfn = new Array(n).fill(0);
const low = new Array(n).fill(0);
const v = new Array(n).fill(0);
const parent = new Array(n).fill(-1);
const tarjan = (i) => {
dfn[i] = low[i] = ++index;
v[i] = 1;
for (const j of g[i]) {
if (!v[j]) {
parent[j] = i;
tarjan(j);
if (low[j] < low[i]) low[i] = low[j];
if (low[j] > dfn[i]) r.push([i, j]);
} else if (j !== parent[i] && dfn[j] < low[i]) low[i] = dfn[j];
}
}
const g = new Array(n).fill(0).map(() => new Array());
const r = [];
for (const [f, t] of connections) {
g[f].push(t);
g[t].push(f);
}
for (let i = 0; i < n; i++)
if (!v[i])
tarjan(i);
return r;
};