LeetCode刷题91-110

LeetCode刷题
Word count: 6.9k   |   Reading time≈ 31 min

①面试题 10.05.稀疏数组搜索

2024.2.27 周二
题目：
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:
输入: words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,”dad”, “”, “”], s = “ta”
输出：-1
说明: 不存在返回-1

方法一：
注意题目给出的是排好序的字符串数组。
运用二分查找的思想，先排除空字符串。
compareTo()方法

100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findString(String[] words, String s) {
        int n = words.length;
        int left = 0;
        int right = n-1;
        while(left <= right){
            while(words[left].equals("")) left++;
            while(words[right].equals("")) right--;
            int mid = left + (right - left)/2;
            while(mid < n && words[mid].equals("")) mid++;
            if(words[mid].compareTo(s) == 0){
                return mid;
            }else if(words[mid].compareTo(s) > 0){
                right = mid-1;
            }else{
                left = mid +1;
            }
        }
        return -1;
    }
}

方法二：
比较字符串相等要用equals()方法
30.56% self

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findString(String[] words, String s) {
        int res = -1;
        int n = words.length;
        for(int i = 0; i < n; i++){
            if(words[i].equals(s)){
                res = i;
                break;
            }
        }
        return res;
    }
}

②LCR 034.验证外星语词典

2024.2.28 周三
26个字母
题目：
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

思路1：
用哈希表存储order中每个字母对应的索引值，比较索引值大小即可

哈希表 HashMap 43.60%

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
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        //哈希表
        //记录每个单词对应的顺序优先级
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < order.length(); i++){
            map.put(order.charAt(i),i);
        }
        //遍历字符串数组
        for(int j = 0; j < words.length -1; j++){
            //比较当前字符串and下一个字符串的顺序
            String cur = words[j];
            String next = words[j+1];
            int n1 = cur.length();
            int n2 = next.length();
            //遍历字符串，比较对应位置的字母
            for(int k = 0; k < Math.max(n1,n2); k++){
                //得到对应位置的字母(注意有可能长度不同)
                int index1 = k < n1? map.get(cur.charAt(k)) : -1;
                int index2 = k < n2? map.get(next.charAt(k)) : -1;
                if(index1 > index2){
                    return false;
                }
                if(index1 < index2){
                    break;
                }
            }
        }
        return true;
    }
}

思路2：
用数组记录每个字母的存储顺序

数组 100%

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
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        //用数组记录每个单词对应的顺序优先级
        int[] index = new int[26];
        for(int i = 0; i < 26; i++){
            index[order.charAt(i) - 'a'] = i;
        }


        //遍历字符串数组
        for(int j = 0; j < words.length -1; j++){
            //比较当前字符串and下一个字符串的顺序
            String cur = words[j];
            String next = words[j+1];
            int n1 = cur.length();
            int n2 = next.length();
            //遍历字符串，比较对应位置的字母
            for(int k = 0; k < Math.max(n1,n2); k++){
                //得到对应位置的字母(注意有可能长度不同)
                int index1 = k < n1 ? index[cur.charAt(k) - 'a']  : -1;
                int index2 = k < n2 ? index[next.charAt(k) - 'a'] : -1;
                if(index1 > index2){
                    return false;
                }
                if(index1 < index2){
                    break;
                }
            }
        }
        return true;
    }
}

③LCP 66.最小展台数量

2024.2.29 周四
题目：
力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。 已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型， demand[i][j] 表示第 i 天展览时第 j 个展台的类型。 在满足每一天展台需求的基础上，请返回后勤部需要准备的 最小 展台数量。
注意：
同一展台在不同天中可以重复使用。
示例：
输入：demand = [“acd”,”bed”,”accd”]
输出：6
解释： 第 0 天需要展台 a、c、d； 第 1 天需要展台 b、e、d； 第 2 天需要展台 a、c、c、d；
因此，后勤部准备 abccde 的展台，可以满足每天的展览需求;

思考：
同一天展台中重复需要额外的加
统计不同字母类型对应的最大数量，将最大数量相加即可
需要先统计每一天需要的字母及其对应的最大数；
后期将字母最大数相加即可。

统计字母出现的次数：哈希表/数组

哈希表 23.48%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minNumBooths(String[] demand) {
        //汇总
        Map<Character,Integer> map = new HashMap<>();
        int res = 0;
        for(String word : demand){
            //记录当前字符串中出现的字母及其个数
            Map<Character,Integer> curMap = new HashMap<>();
            //遍历当前字符串中的每个字母
            for(char c : word.toCharArray()){
                int count = curMap.getOrDefault(c,0) + 1; //更新次数
                //更新当前字符串表
                curMap.put(c,count);
                //更新汇总表
                map.put(c,Math.max(count,map.getOrDefault(c,0)));
            }
        }
        //相加得到和
        for(int key : map.values()){
            res += key;
        }
        return res;
    }
}

数组 88.70%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minNumBooths(String[] demand) {
        int[] ans = new int[26];
        int result = 0;
        for(String word : demand){
            int[] res = new int[26]; //当前单词的次数
            for(char c : word.toCharArray()){
                res[c - 'a']++;
            }
            for(int i = 0; i < 26; i++){
                if(res[i] > ans[i]){
                    ans[i] = res[i];
                }
            }
        }
        for(int i = 0; i < 26; i++){
            result += ans[i];
        }
        return result;
    }
}

④3042.统计前后缀下标对Ⅰ

2024.3.1 周五
题目：
给你一个下标从 0 开始的字符串数组 words 。
定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：
当 str1 同时是 str2 的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。
例如，isPrefixAndSuffix(“aba”, “ababa”) 返回 true，因为 “aba” 既是 “ababa” 的前缀，也是 “ababa” 的后缀，
但是 isPrefixAndSuffix(“abc”, “abcd”) 返回 false。
以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

n1 = 3
0 1 2

3 4 5

n2 = 6
0 1 2 3 4 5

self 100%

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
class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int res = 0;
        int n = words.length;
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(isPrefixAndSuffix(words[i],words[j])){
                    res++;
                }
            }
        }
        return res;
    }

    public boolean isPrefixAndSuffix(String word1,String word2){
        int n1 = word1.length();
        int n2 = word2.length();
        if(n1 > n2) return false;
        for(int k = 0; k < n1; k++){
            if(word1.charAt(k) != word2.charAt(k) || word1.charAt(k) != word2.charAt(n2 - n1 + k)) return false;
            
        }
        return true;
    }

    //↓可替换成startsWith，startsWith用法
    public boolean isPrefixAndSuffix(String word1,String word2){
        return word2.startsWith(word1) && word2.startsWith(word1);
    }
}

⑤2942.查找包含给定字符的单词

2024.3.2 周六
题目：
给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。
请你返回一个 下标数组 ，表示下标在数组中对应的单词包含字符 x 。
注意 ，返回的数组可以是 任意 顺序。

方法一：

42.47% self

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < words.length; i++){
            for(char c : words[i].toCharArray()){
                if(c == x){
                    res.add(i);
                    break;
                }
            }
        }
        return res;
    }
}
  1. indexOf(String str)：返回指定子字符串/字符在字符串中第一次出现的位置(如果没有出现就返回-1)。

方法二：

100%

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < words.length; i++){
            if(words[i].indexOf(x) != -1){
                res.add(i);
            }
        }
        return res;
    }
}

⑥2900.最长相邻不相等子序列Ⅰ

2024.3.3 周日
题目：
给你一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的 二进制 数组 groups ，两个数组长度都是 n 。

你需要从 words 中选出 最长子序列。如果对于序列中的任何两个连续串，二进制数组 groups 中它们的对应元素不同，则 words 的子序列是不同的。

正式来说，你需要从下标 [0, 1, …, n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, …, ik - 1] ，对于所有满足 0 <= j < k - 1 的 j 都有 groups[ij] != groups[ij + 1] 。

请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回 任意 一个。

注意：words 中的元素是不同的 。

示例 ：
输入：words = [“e”,”a”,”b”], groups = [0,0,1]
输出：[“e”,”b”]
解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。
所以一个可行的答案是 [words[0],words[2]] = [“e”,”b”] 。
另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。
得到答案为 [words[1],words[2]] = [“a”,”b”] 。
这也是一个可行的答案。
符合题意的最长子序列的长度为 2 。

题目难读懂，实际不难

思考：
需要找到groups中相邻二进制数不同，对应到下标words中的字符串

100%

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public List<String> getLongestSubsequence(String[] words, int[] groups) {
        int n = words.length;
        List<String> res = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if( i == n-1 || groups[i] != groups[i+1]){
                res.add(words[i]);
            }
        }
        return res;
    }
}

⑦2899.上一个遍历的整数

2024.3.4 周一
题目：
给你一个下标从 0 开始的字符串数组 words ，其中 words[i] 要么是一个字符串形式的正整数，要么是字符串 “prev” 。
我们从数组的开头开始遍历，对于 words 中的每个 “prev” 字符串，找到 words 中的 上一个遍历的整数 ，定义如下：
k 表示到当前位置为止的连续 “prev” 字符串数目（包含当前字符串），令下标从 0 开始的 整数 数组 nums 表示目前为止遍历过的所有整数，
同时用 nums_reverse 表示 nums 反转得到的数组，那么当前 “prev” 对应的 上一个遍历的整数 是 nums_reverse 数组中下标为 (k - 1) 的整数。
如果 k 比目前为止遍历过的整数数目 更多 ，那么上一个遍历的整数为 -1 。
请你返回一个整数数组，包含所有上一个遍历的整数。

分析：
words = [“1”,”2”,”prev”,”prev”,”prev”]
k = 0 0 1 2 3
nums = [1 2 -1 -1 -1]所有遍历过的整数(已知)
temp = [1 2]
nums_reverse = [2 1]
结果：[2,1,-1]上一个遍历过的整数

需要得到连续prev的数目，即-1的个数

99.05%

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
class Solution {
    public List<Integer> lastVisitedIntegers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        //记录出现的非-1的正整数
        List<Integer> temp = new ArrayList<>();
        int k = 0;
        int size = 0;

        for(int num : nums){
            if(num == -1){
                k++;
                if(k <= size){
                    res.add(temp.get(size - k));
                }else{
                    res.add(-1);
                }
            }else{
                //正整数
                temp.add(num);
                size++;
                k = 0;
            }
        }
        return res;
    }
}

⑧2828.判别首字母缩略词

2024.3.5 周二
题目：
给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。
如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。
例如，”ab” 可以由 [“apple”, “banana”] 形成，但是无法从 [“bear”, “aardvark”] 形成。
如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

self 100%

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isAcronym(List<String> words, String s) {
        StringBuilder sb = new StringBuilder();
        for(String word : words){
            sb.append(word.charAt(0));
        }
        return s.equals(sb.toString());

    }
}

⑨2788.按分隔符拆分字符串

2024.3.6 周三
题目：

思路1：
使用split方法进行字符串分割(需要运用正则表达式)
self思路

21.41%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new ArrayList<>();

        for(String word : words){
            for(String ans : word.split("\\"+separator)){
                if(!ans.isEmpty()){
                    res.add(ans);
                }
            }
        }
        return res;
    }
}

思路2：
一个字符一个字符地判断

82.30%

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
class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new ArrayList<>();

        for(String word : words){
            int n = word.length();
            StringBuilder sb = new StringBuilder();

            for(int i = 0; i < n; i++){
                if(word.charAt(i) == separator){
                    //遇到拆分字符了
                    if(sb.length() > 0){
                        res.add(sb.toString()); //添加到结果中
                        sb.setLength(0); //字符串拼接器清零
                    }
                }else{
                    //非拆分字符
                    sb.append(word.charAt(i));
                }
            }
            //最后一个字符不是分割字符的情况，还要再判断一次
            if(sb.length() > 0){
                res.add(sb.toString());
            }
        }
        return res;
    }
}

思路3：
一个过时了的分词器
StringTokenizer()

36.66%

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new ArrayList<>();
        String split = String.valueOf(separator);
        StringTokenizer stringTokenizer = new StringTokenizer(String.join(split, words), split);
        while (stringTokenizer.hasMoreTokens()) {
            res.add(stringTokenizer.nextToken());
        }
        return res;
    }
}

⑩2744.最大字符串配对数目

2024.3.7 周四
题目：
给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。
如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：
字符串 words[i] 等于 words[j] 的反转字符串。
0 <= i < j < words.length
请你返回数组 words 中的 最大 匹配数目。
注意，每个字符串最多匹配一次。

self 通用 43.72%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int n = words.length;
        int res = 0;
        for(int i = 0; i < n-1; i++){
            //得到反转字符串
            StringBuilder temp = new StringBuilder(words[i]).reverse();
            for(int j = i+1; j < n; j++){
                if(temp.toString().equals(words[j])){
                    res++;
                }
            }
        }
        return res;
    }
}

只考虑每个字符串只有两个字符

99.69%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int n = words.length;
        int res = 0;
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(words[i].charAt(0) == words[j].charAt(1) && words[i].charAt(1) == words[j].charAt(0)){
                    res++;
                }
            }
        }
        return res;
    }
}

⑪2678.老人的数目

2024.3.8 周五
题目：
给你一个下标从 0 开始的字符串 details 。details 中每个元素都是一位乘客的信息，信息用长度为 15 的字符串表示，表示方式如下：
前十个字符是乘客的手机号码。
接下来的一个字符是乘客的性别。
接下来两个字符是乘客的年龄。
最后两个字符是乘客的座位号。
请你返回乘客中年龄 严格大于 60 岁 的人数。

取第12.13位的数字
Integer.parseInt(people.substring(11,13));

71.39% self

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int countSeniors(String[] details) {
        int res = 0;
        for(String people:details){
            int age = Integer.parseInt(people.substring(11,13));
            if(age > 60){
                res++;
            }
        }
        return res;
    }
}

⑫2586.统计范围内的元音字符串数

2024.3.9 周六
题目：(easy)
给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。
如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 ‘a’、’e’、’i’、’o’、’u’ 。
返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

方法一：
也可以使用：
List yyzm = new ArrayList<>(Arrays.asList(‘a’,’e’,’i’,’o’,’u’));

41.88% self

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int vowelStrings(String[] words, int left, int right) {
        int res = 0;
        Set<Character> vowel = new HashSet<>();
        char[] array = {'a','e','i','o','u'};
        for(char c : array){
            vowel.add(c);
        }

        for(int i = left; i <= right; i++){
            int n = words[i].length();
            if(vowel.contains(words[i].charAt(0)) && vowel.contains(words[i].charAt(n-1))){
                res++;
            }
        }
        return res;
    }
}

方法二：
单独摘出来判断

99.75%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int vowelStrings(String[] words, int left, int right) {
        int res = 0;

        for(int i = left; i <= right; i++){
            int n = words[i].length();
            if(isTrue(words[i].charAt(0)) && isTrue(words[i].charAt(n-1))){
                res++;
            }
        }
        return res;
    }

    public boolean isTrue(char c){
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
        return false;
    }
}

⑬2515.到目标字符串的最短距离

2024.3.10 周日
题目：
给你一个下标从 0 开始的 环形 字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。
形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。
从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。
返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。

100% 一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        int res = Integer.MAX_VALUE;
        
        //一次遍历
        for(int i = startIndex; i < startIndex + n; i++){
            if(words[i % n].equals(target)){
                int rmin = i - startIndex;
                int lmin = startIndex - i + n;
                res = Math.min(res,Math.min(rmin,lmin));
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

⑭2506.统计相似字符串对的数目

2024.3.11 周一(今天是我们在一起的第520天)
题目：
给你一个下标从 0 开始的字符串数组 words 。
如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。
例如，”abca” 和 “cba” 相似，因为它们都由字符 ‘a’、’b’、’c’ 组成。
然而，”abacba” 和 “bcfd” 不相似，因为它们不是相同字符组成的。
请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，
其中 0 <= i < j <= words.length - 1 。

思考：
需要遍历每个字符串，统计他们其中由相同字符构成的字符串的个数。
将每个字符对应的位置上的比特位设置为 1 的意思是利用整数的二进制表示方式来表示字符的集合。
在代码中，通过 tmp |= 1 << (c[i]-'a') 的操作，实际上是在一个整数 tmp 中的不同比特位上设置为 1，每个字符对应整数的不同比特位。这样做的目的是为了将字符集合转换为一个整数，方便进行比较和处理。

举个例子，假设字符集合为 {‘a’, ‘b’, ‘c’}，则对应的整数表示为：

  • ‘a’ 对应整数的第 0 位，即 000…0001
  • ‘b’ 对应整数的第 1 位，即 000…0010
  • ‘c’ 对应整数的第 2 位，即 000…0100

将这些整数按位或操作后，得到的整数就能表示字符集合 {‘a’, ‘b’, ‘c’}，可以方便地比较不同字符串的字符集合是否相似。

位运算 HashMap (得到重复的对数再计算) 77.95%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int similarPairs(String[] words) {
        int res = 0;

        Map<Integer,Integer> map = new HashMap<>();

        for(String word : words){
            char[] c = word.toCharArray();
            int temp = 0;
            for(int i = 0; i < word.length(); i++){
                temp |= 1 << (c[i] - 'a');  //这里直接temp |= 1 << c[i];也可以且更高效
            }
            map.put(temp,map.getOrDefault(temp,0)+1);
        }

        for(Integer value:map.values()){
            res += value * (value - 1)/2;
        }
        return res;
    }
}

思路2：
对每个字符串提取特征值，并存储在一个数组中，后遍历该数组得到对数(将其转化为相同的特征值存放在数组中，无需计算直接遍历即可)

100%

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
class Solution {
    public int similarPairs(String[] words) {
        int res = 0;
        int n = words.length;

        //对字符串提取特征值
        int[] temp = new int[n];

        for(int i = 0; i < n; i++){
            //得到每个字符串
            for(char c: words[i].toCharArray()){
                //将字符集合化为2进制特征值
                temp[i] = temp[i] | (1 << c); //此处的c-'a'皆可
            }
        }

        //统计对数
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(temp[i] == temp[j]){
                    res++;
                }
            }
        }

        return res;
    }
}

⑮2496.数组中字符串的最大值

2024.3.12 周二
题目：
一个由字母和数字组成的字符串的 值 定义如下：
如果字符串 只 包含数字，那么值为该字符串在 10 进制下的所表示的数字。
否则，值为字符串的 长度 。
给你一个字符串数组 strs ，每个字符串都只由字母和数字组成，请你返回 strs 中字符串的 最大值 。

self matches(正则表达式) 14.93%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximumValue(String[] strs) {
        int resMax = 0;
        int n = strs.length;
        //使用一个数组存储每个字符串的值
        int[] values = new int[n];
        for(int i = 0; i < n; i++){
            if(strs[i].matches("^\\d+$")){
                //字符串中只含有数字
                values[i] = Integer.parseInt(strs[i]);
            }else{
                values[i] = strs[i].length();
            }
            //寻找最大值
            resMax = Math.max(resMax,values[i]);
        }
        return resMax;
    }
}

思路2：
用ASCII码值，一个字母一个字母地更新
value = value * 10 + (int)(str - ‘0’);

ASCII码值 100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximumValue(String[] strs) {
        int resMax = 0;
        int n = strs.length;

        for(int i = 0; i < n; i++){
            //得到每一个字符串对应的值
            int value = 0;
            for(char str : strs[i].toCharArray()){
                if(str >= '0' && str <= '9'){
                    value = value*10 + (int)(str - '0');
                }else{
                    value = strs[i].length();
                    break;
                }
            }
            if(value > resMax){
                resMax = value;
            }
        }
        return resMax;
    }
}

⑯2451.差值数组不同的字符串

2024.3.13 周三
题目：
给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] ，
其中对于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] - words[i][j] 。
注意两个字母的差值定义为它们在字母表中 位置 之差，也就是说 ‘a’ 的位置是 0 ，’b’ 的位置是 1 ，’z’ 的位置是 25 。
比方说，字符串 “acb” 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1] 。
words 中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。
请你返回 words中 差值整数数组 不同的字符串。

思路:
单独写一个得到一个字符串的差值整数数组的方法，
如果前两字符串的差值整数数组不同，则只需要和第三个相比较即可；如果前两个不相同，则需要遍历后面的字符串得到不相同的那一个。

遍历 100%

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
class Solution {
    public String oddString(String[] words) {
        int[] temp1 = getInt(words[0]);
        int[] temp2 = getInt(words[1]);

        //如果前两个相同则需要判断后面的
        if(Arrays.equals(temp1,temp2)){
            for(int i = 2; i < words.length; i++){
                if(!Arrays.equals(getInt(words[i]),temp1)){
                    return words[i];
                }
            }
        }
        return Arrays.equals(temp1,getInt(words[2])) ? words[1] : words[0];
    }


    //得到差值整数数组
    public int[] getInt(String word){
        int[] temp = new int[word.length() - 1];

        for(int i = 0; i < word.length() - 1; i++){
            temp[i] = word.charAt(i+1) - word.charAt(i);
        }
        return temp;
    }
}

⑰2446.判断两个事件是否存在冲突

2024.3.14 周四
题目：
给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：
event1 = [startTime1, endTime1] 且
event2 = [startTime2, endTime2]
事件的时间为有效的 24 小时制且按 HH:MM 格式给出。
当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现 冲突 。
如果两个事件之间存在冲突，返回 true ；否则，返回 false 。
输入：event1 = [“01:15”,”02:00”], event2 = [“02:00”,”03:00”]
输出：true
解释：两个事件在 2:00 出现交集。

思路：
直接使用 compareTo 方法比较，找出不冲突的条件

100%

1
2
3
4
5
class Solution {
    public boolean haveConflict(String[] event1, String[] event2) {
        return !(event1[1].compareTo(event2[0]) < 0 || event2[1].compareTo(event1[0]) < 0);
    }
}

⑱2418.按身高排序

2024.3.15 周五
题目：
给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。
对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。
请按身高 降序 顺序返回对应的名字数组 names 。

思路1：
使用一个二维数组，记录 heights 和排序之前的下标，
得到根据 heights 排序后的二维数组，遍历第二位即可得到names的顺序

75.42%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        String[] res = new String[n];

        int[][] temp = new int[n][2];
        for(int i = 0; i < n; i++){
            temp[i] = new int[]{heights[i],i};
        }

        Arrays.sort(temp,(a,b) -> b[0] - a[0]);
        for(int i = 0; i < n; i++){
            res[i] = names[temp[i][1]];
        }
        return res;
    }
}

⑲2399.检查相同字母间的距离

2024.3.16 周六
题目：
给你一个下标从 0 开始的字符串 s ，该字符串仅由小写英文字母组成，s 中的每个字母都 恰好 出现 两次 。另给你一个下标从 0 开始、长度为 26 的的整数数组 distance 。
字母表中的每个字母按从 0 到 25 依次编号（即，’a’ -> 0, ‘b’ -> 1, ‘c’ -> 2, … , ‘z’ -> 25）。
在一个 匀整 字符串中，第 i 个字母的两次出现之间的字母数量是 distance[i] 。如果第 i 个字母没有在 s 中出现，那么 distance[i] 可以 忽略 。
如果 s 是一个 匀整 字符串，返回 true ；否则，返回 false 。
输入：s = “abaccb”, distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：true
解释：

  • ‘a’ 在下标 0 和下标 2 处出现，所以满足 distance[0] = 1 。
  • ‘b’ 在下标 1 和下标 5 处出现，所以满足 distance[1] = 3 。
  • ‘c’ 在下标 3 和下标 4 处出现，所以满足 distance[2] = 0 。
    注意 distance[3] = 5 ，但是由于 ‘d’ 没有在 s 中出现，可以忽略。
    因为 s 是一个匀整字符串，返回 true 。

思路：
遍历该字符串，当找到两个相同的字符时，且不满足 distance 中的间时，返回false

60.44% 枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int n = s.length();
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if(s.charAt(i) == s.charAt(j) && distance[s.charAt(i) - 'a'] != j - i - 1){
                    return false;
                }
            }
        }
        return true;
    }
}

⑳2273.移除字母异位词后的结果数组

2024.3.17 周日
题目：
给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。
在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：
0 < i < words.length
words[i - 1] 和 words[i] 是 字母异位词 。
只要可以选出满足条件的下标，就一直执行这个操作。
在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，”dacb” 是 “abdc” 的一个字母异位词。

思考：
字母异位词：给字母重新排序后相同

89.29%

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
class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> res = new ArrayList<>();
        int n = words.length;
        if(words == null || n == 0){
            return res;
        }

        //需要将当前遍历到的字符串和上一个字符串相比较
        char[] pre = words[0].toCharArray();
        Arrays.sort(pre);
        res.add(words[0]);


        for(int i = 1; i < n; i++){
            char[] cur = words[i].toCharArray();
            Arrays.sort(cur);

            if(!Arrays.equals(cur,pre)){
                res.add(words[i]);
                pre = cur;
            }
        }
        return res;
    }
}

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信