Leetcode|leetcode-蜡烛之间的盘子(经典空换时) 算法|java|leetcode

https://leetcode-cn.com/problems/plates-between-candles/

文章图片

思路：（预处理+前缀和）

本题的思路是找到区间中的被两个蜡烛围起的盘子
最先的思路是：先获取前缀和，最后计算的过程，遍历去寻找下标最近的蜡烛-------->> 超时

前缀和的思想就是以空间换时间，下标最近的蜡烛可以通过记忆保存到数组的方式，获取最近的蜡烛
前缀和的获取：只需要迭代累加的方式，记录从起点到当前结点的 ‘*’ 的数量
【Leetcode|leetcode-蜡烛之间的盘子(经典空换时)】注意事项：
● 前几个 p q 为初始值时，说明没碰到 | 直接为默认值0 ,且必须保证左蜡烛小于右蜡烛
● 在记录离左右的蜡烛的距离时，同时也可同时遍历

public static int[] platesBetweenCandles(String s, int[][] qs) {char[] cs = s.toCharArray(); int n = cs.length, m = qs.length; int[] l = new int[n], r = new int[n]; int[] sum = new int[n + 1]; for (int i = 0, j = n - 1, p = -1, q = -1; i < n; i++, j--) { if (cs[i] == '|') p = i; if (cs[j] == '|') q = j; l[i] = p; r[j] = q; // 前缀和的presum数组保存到当前位置的* 记录前缀 sum[i + 1] = sum[i] + (cs[i] == '*' ? 1 : 0); } int[] ans = new int[m]; for (int i = 0; i < m; i++) { int a = qs[i][0], b = qs[i][1]; int c = r[a], d = l[b]; // 前几个 p q 为初始值时，说明没碰到 | 直接为默认值0 ,且必须保证左蜡烛小于右蜡烛 if (c != -1 && c <= d) ans[i] = sum[d + 1] - sum[c]; } return ans; }