leetCode周赛83 JavaScript解题报告829.Consecutive Numbers Sum 828.Unique Letter String

比赛地址

https://leetcode.com/contest/weekly-contest-83 

 

830. Positions of Large Groups

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".

Call a group large if it has 3 or more characters.  We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

 

Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting  3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

 

Note:  1 <= S.length <= 1000

 

题意：找出连续重复字母3次及以上的位置。简单难度

/**
 * @param {string} S
 * @return {number[][]}
 */
var largeGroupPositions = function(S) {
    if (!S || S.length == 0) {
        return [];
    }
    var ans = []; 
    var pos = 0;
    var count = 1;
    S += "_";
    for (var i = 1; i < S.length; i++) {
        if (S[i] === S[pos]) {
            count++;
        }
        else {
            if (count >= 3) {
                ans.push([pos, i - 1]);
            }
            pos = i;
            count = 1;
        }
    }
    return ans;
};

 

 

 

 

831. Masking Personal Information

We are given a personal information string S, which may represent either an email address or a phone number.

We would like to mask this personal information according to the following rules:

1. Email address:

We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.

An email address starts with a name, followed by the symbol '@', followed by a name, followed by the dot '.' and followed by a name. 

All email addresses are guaranteed to be valid and in the format of "[e-mail]3".

To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks '*'.

2. Phone number:

A phone number is a string consisting of only the digits 0-9 or the characters from the set {'+', '-', '(', ')', ' '}. You may assume a phone number contains 10 to 13 digits.

The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.

The local number should be formatted and masked as "***-***-1111", where 1 represents the exposed digits.

To mask a phone number with country code like "[phone]", we write it in the form "+***-***-***-1111".  The '+' sign and the first '-' sign before the local number should only exist if there is a country code.  For example, a 12 digit phone number mask should start with "+**-".

Note that extraneous characters like "(", ")", " ", as well as extra dashes or plus signs not part of the above formatting scheme should be removed.

 

Return the correct "mask" of the information provided.

 

Example 1:

Input: "[e-mail]"
Output: "l*****[e-mail]"
Explanation: All names are converted to lowercase, and the letters between the
             first and last letter of the first name is replaced by 5 asterisks.
             Therefore, "leetcode" -> "l*****e".

Example 2:

Input: "[e-mail]"
Output: "a*****[e-mail]"
Explanation: There must be 5 asterisks between the first and last letter 
             of the first name "ab". Therefore, "ab" -> "a*****b".

Example 3:

Input: "1(234)567-890"
Output: "***-***-7890"
Explanation: 10 digits in the phone number, which means all digits make up the local number.

Example 4:

Input: "86-(10)12345678"
Output: "+**-***-***-5678"
Explanation: 12 digits, 2 digits for country code and 10 digits for local number. 

Notes:

1. S.length <= 40.
2. Emails have length at least 8.
3. Phone numbers have length at least 10.

题意：将有关信息打码，例如邮箱名字只保留首末两个字母，中间5个星号代替；电话只保留末尾四位，具体还分10位号码和更多的号码，星号数量和数字一致。标注难度中等、看懂题意就比较简单：

/**
 * @param {string} S
 * @return {string}
 */
var maskPII = function(S) {
    if (S.indexOf("@") >= 0) {
        var s = S.toLowerCase().split("@");
        return s[0][0] + "*****" + s[0][s[0].length - 1] + "@" + s[1];
    }
    else {
        var d = [];
        for (var i = 0; i < S.length; i++) {
            if (S[i] != " " && !isNaN(S[i])) {
                d.push(parseInt(S[i]));
            }
        }
        if (d.length <= 10) {
            return "***-***-" + d.slice(-4).join("");
        }
        else {
            var pre = "+";
            for (var i = 0; i < d.length - 10; i++) {
                pre += "*";
            }
            return pre + "-***-***-" + d.slice(-4).join("");
        }
    }
};

 

 

 

 

829. Consecutive Numbers Sum

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

 

题意是给定一个数字、求出连续数字只和等于这个数的方案总数。总体思路是遍历查找所有数字数量，如2个数字能否组成、3个数字能否组成等等。这题用到了一个数学公式：等差数列只和等于中位数乘以数量。解题过程中因为两个细节错了两次：需要m>=i/2判断第一个数是正数、如果数量是奇数则中位数应该是个整数、如果数量是偶数则中位数应该是*.5，中等难度需要细心。

/**
 * @param {number} N
 * @return {number}
 */
var consecutiveNumbersSum = function(N) {
    var ans = 1;
    var n = Math.ceil(N / 2);
    for (var i = 2; i <= n; i++) {
        var m = N / i;
        if (m >= i / 2) { //根据中位数判断第一个数是正数
            if (i % 2 == 1 && m % 1 == 0 || i % 2 == 0 && m % 1 == 0.5) {
                ans++;
            }
        }
    }
    return ans;
};

 赛后改进：循环的终止条件由N/2改为N*2的平方根，不仅省去了上面m>=i/2的判断，而且将时间复杂度由原来的o(N)降低至o(logN)，一举两得。奇偶分别两次循环也可以省去不必要的判断。

/**
 * @param {number} N
 * @return {number}
 */
var consecutiveNumbersSum = function(N) {
    var n = Math.sqrt(N * 2);
    var ans = 0;
    for (var i = 2; i <= n; i += 2) {
        if (N / i % 1 == 0.5){
            ans++;
        }
    }
    for (var i = 1; i <= n; i += 2) {
        if (N / i % 1 == 0){
            ans++;
        }
    }
    return ans;
};

 

 

 

 

 

828. Unique Letter String

A character is unique in string S if it occurs exactly once in it.

For example, in string S = "LETTER", the only unique characters are "L" and "R".

Let's define UNIQ(S) as the number of unique characters in string S.

For example, UNIQ("LETTER") =  2.

Given a string S, calculate the sum of UNIQ(substring) over all non-empty substrings of S.

If there are two or more equal substrings at different positions in S, we consider them different.

Since the answer can be very large, retrun the answer modulo 10 ^ 9 + 7.

 

Example 1:

Input: "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:

Input: "ABA"
Output: 8
Explanation: The same as example 1, except uni("ABA") = 1.

 

Note: 0 <= S.length <= 10000.

 

题意：给定一串字母。找出所有的子串、并计算子串不重复字母的数量之和，计算过程对1000000007取模。

为了提高速度、用到位运算知识，例如二进制最低位记录是否含有A、第二位记录B、第三位记录C等等。cur变量记录当前所含有的字母，每新增一个字母，将cur与其字母掩码异或即可，sames记录重复两次以上的字母。

难度困难

/**
 * @param {string} S
 * @return {number}
 */
var uniqueLetterString = function(S) {
    var n = S.length;
    var ms = [];
    var a = "A".charCodeAt(0);
    for (var i = 0; i < n; i++) {
        ms.push(1 << (S.charCodeAt(i) - a));
    }
    var ans = 0;
    for (var i = 0; i < n; i++) {
        var cur = 0;
        var sames = 0;
        var count = 0;
        for (var j = i; j < n; j++) {
            if ((cur & ms[j]) == 0) {
                cur |= ms[j];
                count++;
            }
            else if ((sames & ms[j]) == 0) { //第一次重复
                sames |= ms[j]; //记录重复两次以上的
                count--; //第一次要减去之前加上的
            }
            ans = (ans + count) % 1000000007;
        }
    }
    return ans;
};

 以上解法耗时o(n^2)，看了题解最后解法的思路比较精妙：先记录每个字母所有出现的位置、每个字母单独出现的次数单独计算，耗时o(n)。例如“abc”，对于字母a单独出现的字符串有：a、ab、abc，对于字母b则有ab、b、bc、abc，对于字母c则有c、bc、abc，总计为10.

/**
 * @param {string} S
 * @return {number}
 */
var uniqueLetterString = function(S) {
    var poss = {};
    for (var i = 0; i < S.length; i++) {
        if (!poss[S[i]]) {
            poss[S[i]] = [];
        }
        poss[S[i]].push(i);
    }
    var ans = 0;
    for (var c in poss) {
        var pre = -1;
        for (var i = 0; i < poss[c].length; i++) {
            var cur = poss[c][i];
            var next = poss[c][i + 1] || S.length;
            ans += (cur - pre) * (next - cur);
            pre = cur;
        }
    }
    return ans % 1000000007;
};