algorithms/leetcode/2055-PlatesBetweenCandles.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package main

// 2055. Plates Between Candles
// There is a long table with a line of plates and candles arranged on top of it.
// You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

// You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive).
// For each query, you need to find the number of plates between candles that are in the substring.
// A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
//     For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|".
//     The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

// Return an integer array answer where answer[i] is the answer to the ith query.

// Example 1:
// <img src="https://assets.leetcode.com/uploads/2021/10/04/ex-1.png" />
// Input: s = "**|**|***|", queries = [[2,5],[5,9]]
// Output: [2,3]
// Explanation:
// - queries[0] has two plates between candles.
// - queries[1] has three plates between candles.

// Example 2:
// <img src="https://assets.leetcode.com/uploads/2021/10/04/ex-2.png" />
// Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
// Output: [9,0,0,0,0]
// Explanation:
// - queries[0] has nine plates between candles.
// - The other queries have zero plates between candles.

// Constraints:
//     3 <= s.length <= 10^5
//     s consists of '*' and '|' characters.
//     1 <= queries.length <= 10^5
//     queries[i].length == 2
//     0 <= lefti <= righti < s.length

import "fmt"

func platesBetweenCandles(s string, queries [][]int) []int {
    prefixPlates := make([]int, len(s)+1)
    prefixPlates[0] = 0
    candles := make([]int, 0, len(s))
    for i := 1; i < len(prefixPlates); i++ {
        prefixPlates[i] = prefixPlates[i-1]
        if s[i-1] == '*' {
            prefixPlates[i]++
        } else {
            candles = append(candles, i-1)
        }
    }
    lessOrEqual := func(candles []int, idx int) int {
        if len(candles) == 0 { return -1 }
        l, r := 0, len(candles)-1
        for l+1 < r {
            mid := l + (r-l)/2
            if candles[mid] < idx {
                l = mid
            } else {
                r = mid
            }
        }
        if candles[r] <= idx { return candles[r] }
        if candles[l] <= idx { return candles[l] }
        return -1
    }
    upperOrEqual := func(candles []int, idx int) int {
        if len(candles) == 0 { return -1 }
        l, r := 0, len(candles)-1
        for l+1 < r {
            mid := l + (r-l)/2
            if candles[mid] <= idx {
                l = mid
            } else {
                r = mid
            }
        }
        if candles[l] >= idx { return candles[l] }
        if candles[r] >= idx { return candles[r] }
        return -1
    }
    res := make([]int, 0, len(queries))
    for _, query := range queries {
        left, right := upperOrEqual(candles, query[0]), lessOrEqual(candles, query[1])
        if right == -1 || left == -1 || right <= left {
            res = append(res, 0)
        } else {
            res = append(res, prefixPlates[right] - prefixPlates[left])
        }
    }
    return res
}

func platesBetweenCandles1(s string, queries [][]int) []int {
    res := make([]int,len(queries))
    sum, left, right := make([]int,len(s)+1), make([]int,len(s)), make([]int,len(s))
    p :=-1
    for i, c := range s {
        sum[i+1] = sum[i]
        if c == '|' {
            p = i
        } else {
            sum[i+1]++
        }
        left[i]=p
    }
    for i, p :=len(s)-1, len(s); i >= 0; i-- {
        if s[i]=='|' {
            p = i
        }
        right[i]=p
    }
    for i, q := range queries {
        l, r := right[q[0]], left[q[1]]
        if l < r {
            res[i] = sum[r] - sum[l]
        }
    }
    return res
}

func main() {
    // Example 1:
    // <img src="https://assets.leetcode.com/uploads/2021/10/04/ex-1.png" />
    // Input: s = "**|**|***|", queries = [[2,5],[5,9]]
    // Output: [2,3]
    // Explanation:
    // - queries[0] has two plates between candles.
    // - queries[1] has three plates between candles.
    fmt.Println(platesBetweenCandles("**|**|***|", [][]int{{2,5},{5,9}})) // [2,3]
    // Example 2:
    // <img src="https://assets.leetcode.com/uploads/2021/10/04/ex-2.png" />
    // Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
    // Output: [9,0,0,0,0]
    // Explanation:
    // - queries[0] has nine plates between candles.
    // - The other queries have zero plates between candles.
    fmt.Println(platesBetweenCandles("***|**|*****|**||**|*", [][]int{{1,17},{4,5},{14,17},{5,11},{15,16}})) // [9,0,0,0,0]

    fmt.Println(platesBetweenCandles1("**|**|***|", [][]int{{2,5},{5,9}})) // [2,3]
    fmt.Println(platesBetweenCandles1("***|**|*****|**||**|*", [][]int{{1,17},{4,5},{14,17},{5,11},{15,16}})) // [9,0,0,0,0]
}