记一下最近刷题的一些小想法

事情的起因还是要从我昨天上班赚（mo）钱（yu）开始说起，最近项目比较闲，于是我在intelij上面装了一个leetcode插件，每天日常刷一刷leetcode题。就在昨天，我刷到了这样一题

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

0 <= len(big) <= 1000
0 <= len(smalls[i]) <= 1000
smalls的总字符数不会超过 100000。
你可以认为smalls中没有重复字符串。
所有出现的字符均为英文小写字母。

解法：

看到判断字符串在母串的位置，很容易让人想到indexOf(str)，我们可以记录indexOf(str)返回值，但smalls中特定位的字符在big出现的次数是未知数x，所以可以用一个可变数组List来存储这个字符在big中出现的次数。而indexOf(str)默认返回的是str在母串中第一次的索引值，String还提供了indexOf(str,index)来记录从第一个开始的索引值，因此可以采用indexOf(str,index+1)来避免记录重复值。
所以解法就很简单，先用indexOf获取索引值，然后存储在一个长度可变的数组List中，接着讲List再转成固定长度数组，返回给result[i]。

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        int [][] result = new int [smalls.length][];
        for (int i = 0; i < smalls.length ; i++) {
            if("".equals(big)){
                result[i] = new int[0];
                continue;
            }
            else if(!smalls[i].equals("")){
                int index = big.indexOf(smalls[i]);
                List<Integer> list = new ArrayList<>();
                while (index>=0){
                    list.add(index);
                    index = big.indexOf(smalls[i],index+1);
                }
                result[i] = parseList2Array(list);
            }else {
                result[i] = new int[0];
            }
        }
        return result;
    }

    private int[] parseList2Array(List<Integer> list){
        int [] index = new int[list.size()];
        for (int i = 0; i < list.size() ; i++) {
            index[i] = list.get(i);
        }
        return index;
    }
}

题很简答，但是我越刷(mo yu)越开心，又刷到了这样一题。

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:

1 2	输入: J = "aA", S = "aAAbbbb" 输出: 3

示例 2:

1 2	输入: J = "z", S = "ZZ" 输出: 0

注意:

S 和 J 最多含有50个字母。
J 中的字符不重复。

我直接一波惯性思维，想到了indexOf真香(主要简单)，把J拆成char[],那每个char[i],不就相当于上一题里面的small[i]吗，这样一想，其实还是在母串里找每个字符出现的次数。

public int numJewelsInStones(String J, String S) {
    int result = 0;
    char[] charArray = J.toCharArray();
    for (char item: charArray) {
        int index = S.indexOf(item);
        while (index>=0){
            result++;
            index = S.indexOf(item,index+1);
        }
    }
    return result;
}

解答出来之后，我就开始思考有没有其他方法可以更简单或者更快的解决这个题目。还是从刚刚这个思路切入，把J切成char[]，因为S中的char[i]可能是多个，所以还需要像上一题这样多次搜索，但是J中的元素是不会重复的，如果把S拆成char[]，那么对应可以直接在J中进行一次搜索，而且因为不需要取索引值，所以可以直接用J.contains(char[i])，看返回的布尔值，实现计数。

public int numJewelsInStones(String J, String S) {
    int result = 0;
    char[] charArray = S.toCharArray();
    for (char item: charArray) {
        if(J.contains(item+"")){
            result++;
        }
    }
    return result;
}

进一步思考，既然J的每个元素都不相同，那么我们可以采用元素都不重复的集合Set来存储J的每一个元素。不过这样需要对两个字符串都转数组，虽然简单但是感觉不如上述代码简洁。。。

    public int numJewelsInStones(String J, String S) {
    int result = 0;
    HashSet<Character> set = new HashSet<>();
    char[] chars = J.toCharArray();
    for (char item: chars) {
        set.add(item);
    }
    for (int i = 0; i < S.length(); i++) {
        if(set.contains(S.charAt(i)))
            result++;
    }
    return result;
}

写完这些，是不是突然发现，既然是用J中的每一个字符去挨个遍历S中的每一个字符。那么最粗暴的方法当然是双重for循环。

public int numJewelsInStones(String J, String S) {
    int result = 0;
    for(char Jitem : J.toCharArray()){
        for(char Sitem : S.toCharArray()){
            if(Jitem == Sitem){
                result++;
            }
        }
    }
    return result;
}

上述方法虽然简单，但是这样效率极低极低，这样的写法相当于是把整个J和整个S都遍历了一遍，相当于执行了J.length*S.length次。因为这里J的每一个字符都是唯一不重复的。那么我们可以用S去匹配J,找到自己break当前小循环直接进入下一次大循环，就会少一些遍历J中剩下的字符次数，相对而言就会少执行很多次循环体。

public int numJewelsInStones(String J, String S) {
        int result = 0;
        for(char Sitem : S.toCharArray()){
            for(char Jitem : J.toCharArray()){
                if(Jitem == Sitem){
                    result++;
                    break;
                }
            }
        }
        return result;
    }

快乐的上班(mo yu)时光总是很短暂，下班啦~~~~

...

00:00

记一下最近刷题的一些小想法

刷leetcode时遇到的一些小想法

...

标签

其他常用