1189-1192.md

最后一题是个模板题, 求割边

/**
 * @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;
};