Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Between the candles on the plate

Subject address: leetcode-cn.com/problems/pl…

Title description:

Here’s a long table with plates and candles in a row. Give you a string s subscript starting from 0, it contains only characters’ and ‘|’, ‘said of a plate,’ | ‘said a candle.

Queries [I] = [lefti, righti] represents the substring s[lefti…righti] (contains characters for left and right endpoints). For each query, you need to find the number of plates in the substring between the two candles. If a plate has at least one candle to both the left and right of the substring, the plate satisfies between two candles.

For example, s = “| | | | |”, the query [3, 8], said is the substring “| | | * *”. The number of plates in the substring between two candles is 2, and the two plates on the right of the substring have at least one candle to their left and right. Return an integer array answer, where answer[I] is the answer to the ith query.

The sample

Enter: s ="| | | * * * * * * *", queries = [[2.5], [5.9] output: [2.3] -queries [0There are two plates between the candles. - queries[1[There are three plates between the candles.Copy the code

Enter: s ="* * * | | | * * * * * * * * * | | | * * *", queries = [[1.17], [4.5], [14.17], [5.11], [15.16] output: [9.0.0.0.0] -queries [0]9A plate was between the candles. - Another query has no plates between the candles.Copy the code

Subject analysis

In fact, the difficulty of this problem lies entirely in the complexity of the algorithm. At first, I wrote the code with O(n^2) time complexity and failed the test case (the test case was too long). Then I looked at the solution and found that there were prefixes and this way to solve the problem.

PS: Here I first say the wrong code

To get the correct number of plates in the truncated substring, you must truncate first, and since the argument is a truncated two-dimensional array, you must have a for loop.

Here I define a countNums method to handle the truncated string fragment. In this method, first obtain ‘|’ first and last index, and then through the way of or so on both ends of the pointer, gradually to the judge ‘*’ in the number of plates

function countNums(str) {
    let arr = str.split(""), count = 0, first = str.indexOf('|'), last = str.lastIndexOf('|');
    if (first == last || first + 1 == last) return 0;
    let i = first + 1, j = last - 1;
    while(i < j + 1) {
        if (i == j && arr[i] == The '*') {
            count++;
        } else {
            if (arr[i] == The '*') { count++; }
            if (arr[j] == The '*') { count++; }
        }
        i++; j--;
    }
    return count;
}
// current result array
let currentAns = [];
for(let item of queries) { 
    currentAns.push( countNums(s.slice(item[0], item[1] + 1)))}Copy the code

But this will need to use two cycles to judge, very time-consuming. So although the final result can be obtained, but does not meet the time requirements.

Prefixes and methods: Turn strings into arrays and create a new array of plate counts. The plate in the array, each element is in front of all the plate number, if it is a ‘|’. So we have the same number of plates as we had in the previous grid. So you don’t need another loop

code

var platesBetweenCandles = function(s, queries) {
    let currentAns = [];
    // Preprocessing creates an array of plates that displays the total number of plates in the current location
    let plateArr = [], sArr = s.split(' '), pNums = 0;
    for(let i of sArr) {
        if (i == The '*') {
            pNums++;
        }
        plateArr.push(pNums)
    }
    
    for(let item of queries) {
        let str = s.slice(item[0], item[1] + 1);
        let first = str.indexOf('|'), last = str.lastIndexOf('|');
        if (first == -1) {
            currentAns.push(0)}else {
            currentAns.push( plateArr[item[0] + last] - plateArr[item[0] + first] ); }}return currentAns;
};
Copy the code