leetCodeの週間試合106の問題解決報告書javascript

7505 ワード

アルゴリズム考え方

競技の住所:
https://leetcode-cn.com/contest/weekly-contest-106
922.パリティ配列II
922.Sort Aray By Party II
非負の整数配列を指定します. A、Aの中の半分の整数は奇数で、半分の整数は偶数です.
配列を並べ替えて、お弁当にします. A[i] 奇数の場合、i 奇数です質に入れる A[i] 偶数の場合、 i 偶数です
上記の条件を満たす任意の配列を答えとして返すことができます.

例:

  ：[4,2,5,7]
  ：[4,5,2,7]
  ：[4,7,2,5]，[2,5,4,7]，[2,7,4,5]      。

ヒント:

2 <= A.length <= 20000

A.length % 2 == 0

0 <= A[i] <= 1000

最初に偶数を前半に並べてから、順番に中間に交換します.例えば、配列の8つの数字、位置14、35はそれぞれ交換します.

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function(A) {
    A.sort((a,b)=>a%2-b%2);
    for (var i = A.length / 2, j = 1; j < i; i++, j += 2) {
        var temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    return A;
};

921.括弧を最も有効にする追加
921.Minimm Add to Make Partheses Valid
与えられた '(' 和 ')' 括弧からなる文字列 S、最小の括弧を追加する必要があります. '(' または ')'は、得られた括弧文字列を有効にするために、任意の位置においてもよい.
形式的には、次の点の一つを満たすだけで、括弧文字列は有効です.

は空の文字列です.または

です.

は書き上げられます. AB (A を選択します B 接続する A 和 B すべて有効文字列です.または

です.

それは書くことができます. (A) A は有効文字列です.

括弧文字列を指定します.結果文字列を有効にするために追加しなければならない最低括弧数を返します.

例1:

  ："())"
  ：1

例2:

  ："((("
  ：3

例3:

  ："()"
  ：0

例4:

  ："()))(("
  ：4

ヒント:

S.length <= 1000

S のみを含む '(' 和 ')' 文字

現在の左括弧の数を変数一つで記録してから、右括弧に合わせたら一つ減らします.

/**
 * @param {string} S
 * @return {number}
 */
var minAddToMakeValid = function(S) {
    var leftCount = 0;
    var ans = 0;
    for (var i = 0; i < S.length; i++) {
        if (S[i] === ")") {
            if (leftCount === 0) {
                ans++;
            }
            else {
                leftCount--;
            }
        }
        else {
            leftCount++;
        }
    }
    ans += leftCount;
    return ans;
};

923.三数の和の様々な可能性
923.3 Sum With Multility
整数配列を指定します. A、および整数 target 目標値として満足を返します. i < j < k 且 A[i] + A[j] + A[k] == target の元グループ i, j, k の数です
結果が非常に大きいので、引き返してください. 10^9 + 7
例1:

  ：A = [1,1,2,2,3,3,4,4,5,5], target = 8
  ：20
  ：
    （A[i]，A[j]，A[k]）：
(1, 2, 5)    8  ；
(1, 3, 4)    8  ；
(2, 2, 4)    2  ；
(2, 3, 3)    2  。

例2:

  ：A = [1,1,2,2,2,2], target = 5
  ：12
  ：
A[i] = 1，A[j] = A[k] = 2    12  ：
    [1,1]       1，  2    ，
  [2,2,2,2]       2，  6    。

ヒント:

3 <= A.length <= 3000

0 <= A[i] <= 100

0 <= target <= 300

解析:観察データ量A[i]は100以下の整数であるため、各位置を遍歴した数をnとし、更に0~100の各数字mを見て前に出現する回数に、ターゲットt-m-nを乗じて後に出現する回数を積算すれば答えとなるという考えがある.二つの配列が現在位置の前後0～100の数字の出現回数を記録する必要があります.詳細はコードを参照してください.

/**
 * @param {number[]} A
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(A, target) {
    var maxNum = 100;
    var pre = new Array(maxNum + 1).fill(0);
    pre[A[0]]++;
    var ps = new Array(maxNum + 1).fill(0);
    for (var i = 1; i < A.length; i++) {
        ps[A[i]]++;
    }
    var m = 1e9 + 7;
    var ans = 0;
    for (var i = 1; i < A.length - 1; i++) {
        ps[A[i]]--;
        for (var j = Math.max(0, target - A[i] - maxNum); j <= maxNum && j <= target - A[i]; j++) {
            ans = (ans + pre[j] * ps[target - A[i] - j]) % m;
        }
        pre[A[i]]++;
    }
    return ans;
};

924.悪意のあるソフトウェアの普及をできるだけ減らす.
924.Minimize Malware Spread
ノードネットワークでは、当 graph[i][j] = 1 を選択すると、各ノード i 直接に他のノードに接続することができます. j一部のノード initial 最初は悪意のソフトに感染されました.2つのノードが直接接続され、少なくとも1つのノードが悪意のあるソフトウェアに感染すると、両方のノードが悪意のあるソフトウェアに感染する.この悪意のあるソフトウェアの普及は、より多くのノードがこのような方法で感染することができるまで継続されるだろう.
仮説 M(initial) 悪意のあるソフトウェアが伝播を停止した後、ネットワーク全体に悪意のあるソフトウェアに感染する最終ノード数です.
初期リストからノードを削除できます.このノードを削除すると最小化されます. M(initial)、このノードに戻ります.複数のノードが条件を満たすと、インデックスが一番小さいノードに戻ります.
あるノードが感染ノードのリストからすでに initial から削除されても、悪意のあるソフトが普及して感染する可能性があります.

例1:

  ：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
  ：0

例2:

  ：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
  ：0

例3:

  ：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
  ：1

ヒント:

1 < graph.length = graph[0].length <= 300

0 <= graph[i][j] == graph[j][i] <= 1

graph[i][i] = 1

1 <= initial.length < graph.length

0 <= initial[i] < graph.length

一つの配列で各ノードの感染回数を記録し、まずvisitはそれぞれの初期感染点を広げ、感染したノードを順次削除し、calCountは感染したノードの数を計算し、最小値のノードは答えとする.

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
    initial.sort((a,b)=>a-b)
    var n = graph.length;
    var gCount = new Array(n).fill(0);
    var calCount = function() {
        var count = 0;
        for (var i = 0; i < gCount.length; i++) {
            if (gCount[i] > 0) {
                count++;
            }
        }
        return count;
    }
    var visit = function(index, added, flags) {
        flags[index] = 1;
        gCount[index] += added;
        for (var j = 0; j < n; j++) {
            if (graph[index][j] === 1 && flags[j] === 0) {
                visit(j, added, flags);
            }
        }
    }
    for (var i = 0; i < initial.length; i++) {
        visit(initial[i], 1, new Array(n).fill(0));
    }
    var ans = initial[0];
    var minm = n + 1;
    for (var i = 0; i < initial.length; i++) {
        visit(initial[i], -1, new Array(n).fill(0));
        var m = calCount();
        if (minm > m) {
            minm = m;
            ans = initial[i];
        }
        visit(initial[i], 1, new Array(n).fill(0));
    }
    return ans;
};

Vue.js非同期アップデートおよびnextTick