leetCode周赛81解题报告

比赛地址
https://leetcode.com/contest/weekly-contest-81

 

821. Shortest Distance to a Character

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

 找出每个位置左边右边离C字母最近的距离，简单难度，两次遍历分别求出左边和右边最近距离即可。

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function(S, C) {
    var r = new Array(S.length).fill(99999);
    var pos = -1;
    for (var i = S.length - 1; i >= 0; i--) {
        if (S[i] == C) {
            pos = i;
        }
        if (pos >= 0) {
            r[i] = pos - i;
        }
    }
    pos = -1;
    for (var i = 0; i < S.length; i++) {
        if (S[i] == C) {
            pos = i;
        }
        if (pos >= 0) {
            r[i] = Math.min(r[i], i - pos);
        }
    }
    return r;
};

 

 

 

 

822. Card Flipping Game

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card. 

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good?  If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i. 

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

 

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3].
We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

一大片英文不大看得懂，纯属坑中国人的题，试错法试了四次看错误case猜题目意思、大致意思就是牌随便翻转，找出翻了之后最小的只有一张的牌。

 

/**
 * @param {number[]} fronts
 * @param {number[]} backs
 * @return {number}
 */
var flipgame = function(fronts, backs) {
    var f = new Array(2001).fill(false);
    for (var i = 0; i < fronts.length; i++) {
        if (fronts[i] == backs[i]) {
            f[fronts[i]] = true;
        }
    }
    var ans = 2001;
    for (var i = 0; i < fronts.length; i++) {
        if (fronts[i] !== backs[i]) {
            if (!f[fronts[i]]) {
                ans = Math.min(ans, fronts[i]);
            }
            if (!f[backs[i]]) {
                ans = Math.min(ans, backs[i]);
            }
        }
    } 
    return ans === 2001 ? 0 : ans;
};

 

 

 

 

820. Short Encoding of Words

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

 

题意是压缩所有单词到尽量短的一句话中，使得所有单词都可以用一个位置表示。

思路是后缀树。Js其实有一种很方便的树的实现例如本题单词time，生成这样一个后缀树结构：{e:{m:{i:{t:{}}}}}，当遇到下个单词如me时，从最外层开始找到{e:{m:{...}}}说明单词me已经被包含。具体代码如下：

 

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    words.sort((a,b)=>b.length-a.length);
    var ans = 0;
    var d = {};
    for (var i = 0; i < words.length; i++) {
        var find = true;
        var p = d;
        for (var j = words[i].length - 1; j >= 0; j--) {
            if (!p[words[i][j]]) {
                find = false;
                p[words[i][j]] = {};
            }
            p = p[words[i][j]];
        }
        if (!find) {
            ans += words[i].length + 1;
        }
    }
    return ans;
};

 

 

 

 

 

823. Binary Trees With Factors

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node's value should be equal to the product of the values of it's children.

How many binary trees can we make?  Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

题意是求满足这样规则的树的数量：非叶结点的值是两个孩子节点的乘积。

中等难度、就是计算结果要求对1000000007取模，马蛋又被坑了一次。

利用集合加速查找数字是否存在、键值对m记录中间结果。

/**
 * @param {number[]} A
 * @return {number}
 */
var numFactoredBinaryTrees = function(A) {
    var s = new Set(A);
    var m = {};
    var M = 1000000007;
    A.sort((a,b)=>a-b);
    for (var i = 0; i < A.length; i++) {
        var count = 1;
        for (var j = 0; j < i; j++) {
            if (A[i] % A[j] === 0) {
                var other = A[i] / A[j];
                if (s.has(other)) {
                    count = (count + (m[A[j]] % M) * (m[other] % M)) % M;
                }
            }
        }
        m[A[i]] = count;
    }
    var ans = 0;
    for (var k in m) {
        ans = (ans + m[k]) % M;
    }
    return ans;
};