在这里做出处理，让下标从1开始，询问的区间两端也+1
我们开两个数组： nearL 以及 nearR
nearL[i] 表示：在i 位置离着最近的左边的 ∣符号是在哪一个下标
nearR[i] 表示：在i 位置离着最近的右边的 ∣符号是在哪一个下标
如果说 s[i] == '|' 那么说 nearL[i]=i 并且 nearR[i]=i
让左区间等于离着当前位置最近的右边的 |
让右区间等于离着当前位置最近的左边的 |
然后就可以直接开始 前缀和 了
Code:
class Solution { public: vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) { const int N = s.size(); int cnt2[N+7]; vector<int> ans; s = "#" + s; int tot = queries.size(); for(vector<int> &v:queries) { v[0] += 1; v[1] += 1; } int nearL[N+7], nearR[N+7]; memset(nearL,0,sizeof nearL); memset(nearR,0,sizeof nearR); cnt2[0] = 0; for (int i = 1;i <= N;i ++) { if(s[i] == '|') { cnt2[i] = cnt2[i-1]; nearL[i] = i; } else { cnt2[i] = cnt2[i-1] + 1; nearL[i] = nearL[i-1]; } } for(int i=N;i>=1;i--) { if(s[i] == '|') nearR[i] = i; else nearR[i] = nearR[i+1]; } for(vector<int> v : queries) { int l = v[0], r = v[1]; if(l == r) { ans.push_back(0); continue; } int tl,tr; tl = nearR[l]; tr = nearL[r]; if(tl >= tr) ans.push_back(0); else ans.push_back(cnt2[tr] - cnt2[tl-1]); } return ans; } };
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成8256 人正在系统学习中
