刷题记录：一维前缀和 | leetcode-2559. 统计范围内的元音字符串数 2023/6/2

leetcode-2559. 统计范围内的元音字符串数

这道题的思路并不难找，一开始我有点看出是一维前缀和问题，但没有很确定，因此也就没有直接从这个思路走下去。还是想着先做暴力版本的吧！

这是暴力版本的代码：

class Solution {
    static String array = "aeiou";
    static int[] ret;

    static boolean judge(String str) {
        String head = str.charAt(0)+"";
        String rear = str.charAt(str.length()-1)+"";
        if(array.contains(head) && array.contains(rear)) {
            return true;
        }
        return false;
    }

    public static int[] vowelStrings(String[] words, int[][] queries) {
        ret = new int[queries.length];
        int i = 0;
        int k = 0;
        while(i < queries.length) {
            int count = 0;

            int l = queries[i][0];
            int r = queries[i][1];
            for(int j = l; j <= r; j++) {
                if(judge(words[j])) {
                    count++;
                }
            }
            ret[k++] = count;
            i++;
        }
        return ret;
    }
}

果不其然超时了😂卡在了92/93个用例。

我试图优化一下，粗暴地认为如果字符串的长度是1，那就是要找的一个答案。属于是做题做懵了（我不是在做回文串啊喂！只有一个b，b不是元音字母！），当然这个方法是不对的。

这时我做题过程中最大的问题出现了，我没有更换思路（比如自己去寻求前缀和的思路）寻求优化，而是看了看题解。不过当我看见题解的标题写着“前缀和”的时候，就没有再看下去了。

因为确定了是前缀和的思路，那我也能做出来。

思路非常简单：words数组中的元素是字符串，可以先将各个字符串按是否是元音字母首位的这一标准，映射到 a 数组。a数组就是原始数组。

初始化原始数组a后，再初始化前缀和数组s。有公式：

s[i] = s[i-1] + a[i]    //初始化s数组
a[l]加到a[r]的和 = s[r] - s[l-1]    //求前缀和

一位前缀和的公式很好推导。 按照上面这两步，很快就写好了。

这是我第一次提交的前缀和代码（注：并没有AC）。

class Solution {
    String s = "aeiou";
    int judge(String str) {
        String head = str.charAt(0)+"";
        String rear = str.charAt(str.length()-1)+"";
        if(s.contains(head) && s.contains(rear)) {
            return 1;
        }
        return 0;
    }

    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length; //words 原数组
        int[] a = new int[n+10];    //words数组映射成前缀和数组
        for(int i = 1; i <= n; i++) {
            a[i] = judge(words[i-1]);
        }

        int[] s = new int[n+10];    //前缀和数组
        //初始化前缀和数组
        for(int i = 1; i <= n; i++) {
            s[i] = s[i-1] + a[i];
        }

        //求前缀和
        int[] ret = new int[queries.length];
        int k = 0;
        int j = 0;
        while(k < queries.length) {
            int l = queries[k][0];
            int r = queries[k][1];
            ret[j++] = s[r] - s[l-1];    //注：此处有问题
            k++;

        }
        return ret;
    }
}

运行后，报了数组越界的问题，定位在ret[j++] = s[r] - s[l-1] 这一行。

当时由于时间比较晚了，再不回宿舍要门禁了。所以我收电脑从自习室跑了。不过心里大概有数了。第二天一早我就来自习室，开这个题，不到5分钟找出问题了。

因为我的a数组与s数组，为了操作方便，我令它们从下标1开始计数。但 l 和 r 是从0开始计数的。所以，这里要有一个转换。

ret[j++] = s[r+1] - s[l];

被减数和减数的下标都加一即可。下面是正确的代码： 

class Solution {
    String s = "aeiou";
    int judge(String str) {
        String head = str.charAt(0)+"";
        String rear = str.charAt(str.length()-1)+"";
        if(s.contains(head) && s.contains(rear)) {
            return 1;
        }
        return 0;
    }

    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length; //words 原数组
        int[] a = new int[n+10];    //words数组映射成前缀和数组
        for(int i = 1; i <= n; i++) {
            a[i] = judge(words[i-1]);
        }

        int[] s = new int[n+10];    //前缀和数组
        //初始化前缀和数组
        for(int i = 1; i <= n; i++) {
            s[i] = s[i-1] + a[i];
        }

        //求前缀和
        int[] ret = new int[queries.length];
        int k = 0;
        int j = 0;
        while(k < queries.length) {
            int l = queries[k][0];
            int r = queries[k][1];
            ret[j++] = s[r+1] - s[l];
            k++;

        }
        return ret;
    }
}

成功通过。头一次做到“不那么直白的”一维前缀和题目。还是很有收获的。 

 

记录一下 2023/6/2 晚上回宿舍的路。月亮其实是很好看的，可惜拍不出来。当时心情不错。