LeetCode刷题151-170

LeetCode刷题
Word count: 10.3k   |   Reading time≈ 47 min

①49.字母异位词分组

2024.4.7 周日
题目：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路1：
字母异位词：所有字母拆开后再排序是相同的，可以用作 Map 的 key
Map< String ,List< String >>

97.89% 排序 HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> res = new HashMap<>();

        for(String str : strs){
            //排序后的字符串作为键
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);

            //值
            List<String> value = res.getOrDefault(key,new ArrayList());
            value.add(str);

            //更新map
            res.put(key,value);
        }

        return new ArrayList<List<String>>(res.values());
    }
}

思路2：
使用 stream流 来解决问题
Arrays.stream(str).collect(Collectors.groupingBy(str->{

})).values()

stream流 27%

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<List<String>>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str ->{
                //提供分类依据
                char[] array = str.toCharArray();
                Arrays.sort(array);
                return new String(array);
            })).values()
        );
    }
}

②79.单词搜索

2024.4.8 周一
题目：

思考：
需要单独一个方法 check ，从二维数组的某个点出发，是否可以找到该字符串 word 从第 k 个字符开始的后缀子串(从该点的四个方向开始找起)
(使用递归)
如果当前点满足，则往四周找，必须满足x、y不可以出界
且只找四周没有被访问过的一边，

在backtrack的过程中，我们需要回溯到上一步进行下一次尝试。当我们尝试完当前位置(i, j)的所有可能方向后，如果没有找到符合条件的路径，就需要将当前位置的visited状态重置为false，以便在下一次搜索中重新使用这个位置。这样可以确保每个位置都能被正确地访问和尝试。

*20% *

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        boolean[][] visited = new boolean[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(check(board,visited,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board,boolean visited[][],String word,int I,int J,int k){
        int m = board.length;
        int n = board[0].length;

        //起始点错误
        if(board[I][J] != word.charAt(k)){
            return false;
        }else if(k == word.length() - 1){
            //对应相等，且找的是最后一个字母
            return true;
        }

        visited[I][J] = true;

        //起始点找到了，且对比字母不是最后一个，就要向四周寻找了
        int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
        boolean result = false;

        for(int[] dir : direction){
            //产生新的x、y
            int newX = I + dir[0];
            int newY = J + dir[1];
            //不出界
            if(newX >= 0 && newX < m && newY >= 0 && newY < n){
                //且未访问过
                if(!visited[newX][newY]){
                    //下一个字母之后也满足条件
                    boolean flag = check(board,visited,word,newX,newY,k+1);
                    if(flag){
                        result = true;
                        break;
                    }
                }
            }
        }

        //四个方向都没有找到
        visited[I][J] = false;

        return result;
    }
}

③139.单词拆分

2024.4.9 周二
题目：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

思考：

j 1 2 3 ..

j = 1
i = 0
dp[1] = dp[0] && check(0,1)

j = 2
i = 1 0
dp[2] = dp[1] && check(1,2)
dp[2] = dp[0] && check(0,2)

j = 3
i = 2 1 0

3 2 + 2
3 1 + 1
3 0 + 0

dp，用于记录字符串s前i个字符能否拆分。数组长度为s.length()+1。
初始化dp[0]为true，表示空字符串可以被拆分。

dp[j] = dp[i] && check(i,j)
前 j 为能否被拆分取决于前 i 位能否被拆分，并且 i + 1 到 j 这一段是否是 wordDict 中的单词

遍历字符串s，外层循环从1到s.length()，内层循环从j-1到0。

最终返回 dp[s.length()]，即整个字符串 s 能否被拆分

方法：
check()
检查字符串 s 是否是 wordDict 中的单词
为了方便，将 wordDict 放在 map 中，默认是 true

动态规划 90%

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
33
34
class Solution {
    //将单词放map中方便判断某字符串是否在该单词列表中
    Map<String,Boolean> map = new HashMap<>();


    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];

        //将word放入map中
        for(String word : wordDict){
            map.put(word,true);
        }

        //初始
        dp[0] = true;

        //遍历
        for(int j = 1; j <= s.length(); j++){
            for(int i = j - 1; i >= 0; i--){
                dp[j] = dp[i] && check(s.substring(i,j));
                if(dp[j]) break;
            }
        }
        return dp[s.length()];
    }

    public boolean check(String s){
        return map.getOrDefault(s,false);
    }
}

//↓也可
//Map<String,Boolean> map = new HashMap<>();
//dp[j] = dp[i] && temp.contains(s.substring(i,j));

④179.最大数

2024.4.10 周三
题目：
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

思考：
需要自定义排序逻辑，根据两个数字相结合后谁最大谁就排列在前面

已经按照从大到小的顺序排列了，那么如果首字母还是’0’，就直接返回”0”即可

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
33
34
35
36
37
38
39
40
41
42
class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;

        String[] temp = new String[n];

        //将整数数组转化为字符串数组之后再进行排序
        for(int i = 0; i < n; i++){
            temp[i] = "" + nums[i];
        }

        //排序
        Arrays.sort(temp,(a,b)->{
            String sa = a + b;
            String sb = b + a;
            return sb.compareTo(sa);
        });

        //排序后进行字符串拼接
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < n; j++){
            sb.append(temp[j]);
        }

        //剔除特殊情况0
        if(sb.charAt(0) == '0'){
            return "0";
        }

        return sb.toString();
    }
}


//以下有些许多余
//剔除特殊情况0
int k = 0;
while(k < n - 1 && sb.charAt(k) == '0'){
    k++;
}

return sb.substring(k);

不使用StringBuilder拼接 使用String.join(“”, ss)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) ss[i] = String.valueOf(nums[i]);

        Arrays.sort(ss, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));

        String result = String.join("", ss);
        return result.charAt(0) == '0' ? "0" : result;
    }
}

⑤318.最大单词长度乘积

2024.4.11 周四
题目：
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。
如果不存在这样的两个单词，返回 0 。
words[i] 仅包含小写字母

重点：如何区分两个字符串里面有没有重复的字母
使用位运算、结合二进制数

通过在第二个for循环中使用for(int j = 0; j < i; j++)，我们可以确保只考虑不同字符串之间的组合，
避免重复计算相同的组合。这样可以提高算法的效率，并且符合问题的要求。

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

        //每个word用一个二进制数表示它的字母
        int[] temp = new int[n];

        //将word -> 二进制数
        for(int i = 0; i < n; i++){
            int binary = 0;
            for(int j = 0; j < words[i].length(); j++){
                int num = words[i].charAt(j) - 'a';
                //用1标记出现的字母
                binary |= (1 << num);
            }
            //放到对应temp的位置
            temp[i] = binary;
        }

        //遍历temp找到两者无重复位，且length乘积最大的值
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if((temp[i] & temp[j]) == 0){//无重复位数
                    result = Math.max(result,words[i].length() * words[j].length());
                }
            }
        }

        return result;

    }
}

⑥848. 字母移位

2024.4.12 周五
题目：
有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts 。
我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， ‘z’ 将会变成 ‘a’）。

例如，shift(‘a’) = ‘b’, shift(‘t’) = ‘u’, 以及 shift(‘z’) = ‘a’。

对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。
返回 将所有这些移位都应用到 s 后最终得到的字符串 。
提示：
s 由小写英文字母组成
shifts.length == s.length

思考：
注意是前 i 位一起移动

每个字母移动的次数 X ：
shifts[0] + shifts[1] + … + shifts[n-1]
shifts[1] + shifts[2] + … + shifts[n-1]
shifts[2] + shifts[3] + … + shifts[n-1]
…
shifts[n-1]

X = X - shifts[i]

先计算出最多需要移动多少次，后序字母依次减去 当前shifts[i]的次数，即为下一个字母移动次数
(将字母原有序号 + 移动位数) % 26 + 97 ——> 转化为新的字母

在每次迭代时，通过move = (move - shifts[i]) % 26更新 move 时，可能会出现负数的情况
※※※使用 Math.fioorMod(move - shifts[i], 26) 可以解决问题

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 String shiftingLetters(String s, int[] shifts) {
        int n = shifts.length; 

        //统计最多移动的位数
        int move = 0;
        for(int shift : shifts){
            move = (move + shift) % 26;
        }

        StringBuilder result = new StringBuilder();

        for(int i = 0; i < n; i++){
            //先得到当前字母在26字母表中的位置
            int index = s.charAt(i) - 'a';
            //在当前位置的基础上移动后的位置
            index = ((index + move) % 26);
            //转换成字母，拼接到答案上
            result.append((char) (index + 97));
            
            //更新下一字母移动的次数
            move = Math.floorMod(move - shifts[i], 26);
        }
        return result.toString();
    }
}

⑦522.最长特殊序列 Ⅱ

2024.4.13 周六
题目：
给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
例如，”abc” 是 “aebdc” 的子序列，因为您可以删除”aebdc”中的下划线字符来得到 “abc” 。”aebdc”的子序列还包括”aebdc”、 “aeb” 和 “” (空字符串)。
提示:

  • 2 <= strs.length <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] 只包含小写英文字母

思考：
最长的 字符串数组 中的 子序列 ，该 子序列 只能是其中一个字符串独有的

只需要对比，找到最大的长度

如果 sub 是 字符串 strs[i] 的一个独有子序列，那么 strs[i] 也是一个独有子序列，
因为 strs[i] 的整个字符串可以看成在独有子序列sub的基础上添加若干个字母组成，
所以只要找到 strs[i] 中最长的特殊的字符串即可。

使用双重循环比较当前字符串，是不是其他字符串的子序列

如何判断当前字符串是不是某一个字符串的子序列：
用双指针，起始时分别指向两个字符串的首字母，
如果相同就全部移动到下一个字母，
如果不相同就只挪动第二个指针 second 。

直到两指针某一个指到最后
如果是第一个指针 first 到最后那么 第一个 String 就是第二个是子序列，
如果是第二个指针 second 到最后，就不是子序列 

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
33
34
35
36
37
38
39
40
class Solution {
    public int findLUSlength(String[] strs) {
        int n = strs.length;
        int result = -1;

        for(int i = 0; i < n; i++){
            Boolean check = true;

            for(int j = 0; j < n; j++){
                //只将当前字符串和其他字符串比较即可
                if(i != j && isSub(strs[i], strs[j])){
                   //当前字符串已经是某个字符串的子序列了
                   check = false;
                   break;
                }
            }

            if(check){
                //当前不是子序列
                result = Math.max(strs[i].length(),result);
            }
        }

        return result;
    }

    public Boolean isSub(String word1,String word2){
        int first = 0;
        int second = 0;

        while(first < word1.length() && second < word2.length()){
            if(word1.charAt(first) == word2.charAt(second)){
                first ++;
            }
            second ++;
        }

        return first == word1.length();
    }
}

⑧524.通过删除字母匹配到字典里最长单词

2024.4.14 周日
题目：
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

思考：
判断一个字符串是不是由另一个字符串中的字母组成的：
两个字符串中的字母的先后顺序是一致的

当答案有多个时，如何返回字母序最小的字符串：
使用 compareTo() 方法进行比较

self 78%

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 String findLongestWord(String s, List<String> dictionary) {
        String res = "";

        for(String word : dictionary){
            if(isInWord(word,s)){
                if(word.length() > res.length() || (word.length() == res.length() && word.compareTo(res) < 0) ){
                    res = word;
                }
            }
        }
        return res;
    }

    //判断一个字符串是不是由另一个字符串中的字母组成的
    public Boolean isInWord(String word, String isIn){
        //两个字符串中的字母的先后顺序是一致的
        int i = 0;
        int j = 0;
        while(i < word.length() && j < isIn.length()){
            if(word.charAt(i) == isIn.charAt(j)){
                i++;
            }
            j++;
        }
        return i == word.length();
    }
}

⑨539.最小时间差

2024.4.15 周一
题目：
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
提示：
2 <= timePoints.length <= 2 * 104
timePoints[i] 格式为 “HH:MM”

思考1：
将 timePoints 中的字符串拆分成字符串数组，
计算每个 timePoints 中的字符串对应的时间的分钟数(包括今天的和明天的)
将每个字符串对应的两个时间，放在一个数组中，将数组排序，将相邻两个数求差，得到最小的差值

55% 排序

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
class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();

        int[] time = new int[2 * n];

        for(int i = 0,index = 0; i < n; i++, index += 2){
            String[] temp = timePoints.get(i).split(":");
            int h = Integer.parseInt(temp[0]);
            int m = Integer.parseInt(temp[1]);
            //将两个时间装到数组time中去
            time[index] = h * 60 + m;
            time[index + 1] = time[index] + 24 * 60;
        }

        Arrays.sort(time);

        int res = time[1] - time[0];

        for(int i = 0; i < 2 * n - 1; i++){
            res = Math.min(time[i+1] - time[i],res);
        }
        return res;
    }
}

思考2：
可以直接将 timePoints 用 Collections.sort() 排序，
最小时间差在相邻两个时间 or timePoints 排序后首位两个时间中

98% 排序 抽屉原理

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
class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();

        if (n > 1440) { //抽屉原理 可以减少时间复杂度
            return 0;
        }

        Collections.sort(timePoints);
        int res = Integer.MAX_VALUE;
        
        int pre = getMinutes(timePoints.get(0));

        for(int i = 1; i < n; i++){
            int cur = getMinutes(timePoints.get(i));
            res = Math.min(res,cur - pre);
            pre = cur;
        }

        //首位时间差
        res = Math.min(res,(getMinutes(timePoints.get(0)) + 24*60) - pre);
        return res;
    }

    //根据一个字符串得到分钟数
    public int getMinutes(String s){
        return (s.charAt(0)*10 + s.charAt(1)) * 60 + (s.charAt(3)*10 + s.charAt(4));
    }
}

⑩609.在系统中查找重复文件

2024.4.16 周二
题目：
给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。
一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下：
“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”
这意味着，在目录 root/d1/d2/…/dm 下，有 n 个文件 ( f1.txt, f2.txt … fn.txt ) 的
内容分别是 ( f1_content, f2_content … fn_content ) 。
注意：n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。
其中每个组由所有具有相同内容文件的文件路径组成。
文件路径是具有下列格式的字符串：
“directory_path/file_name.txt”

提示：
paths[i] 由英文字母、数字、字符 ‘/‘、’.’、’(‘、’)’ 和 ‘ ‘ 组成
你可以假设在同一目录中没有任何文件或目录共享相同的名称。
你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。

思考：
只需要得到文件路径即可，不用加内容、文件必须是重复文件，即需要两个及以上

使用 map
key - 文件内容
value - 文件路径

如何得到文件内容
拆分字符串： split
组合字符串：replace

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
32
33
34
35
36
37
class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String,List<String>> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();

        for(String path : paths){
            /**
            用空格拆分路径 得到
                root/a 
                1.txt(abcd) 
                2.txt(efgh)
             */
             String[] temp = path.split(" ");
             //从文件开始遍历该字符串数组
             for(int i = 1; i < temp.length; i++){
                //使用split("\\(")对文件进行拆分
                //1.txt   
                //abcd)
                String[] tempContent = temp[i].split("\\(");
                //去掉) 得到文件内容
                String content = tempContent[1].replace(")"," ");
                //得到并更新 map 中的 value 值
                List<String> an = map.getOrDefault(content,new ArrayList<String>());
                an.add(temp[0] + "/" + tempContent[0]);
                //更新 map
                map.put(content,an);
             }

        }
        for(String key : map.keySet()){
            if(map.get(key).size() > 1){
                res.add(map.get(key));
            }
        }
        return res;
    }
}

⑪648.单词替换

2024.4.17 周三
题目：
在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 继承词 (successor)。
例如，词根 help，跟随着 继承词 “ful”，可以形成新的单词 “helpful”。
现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
你需要将句子中的所有 继承词 用 词根 替换掉。如果 继承词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。
你需要输出替换之后的句子。

思考：
将句子中的单词，替换成词根

如何保证替换成的前缀是最短的？可以挨个找到句子中单词的前缀，看前缀字典中有没有该前缀，有就是最短的

哈希集合 20%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> set = new HashSet<>();
        for(String word : dictionary){
            set.add(word);
        }

        String[] words = sentence.split(" ");
        for(int i = 0; i < words.length; i++){
            String word = words[i];
            //从最短前缀开始找
            for(int j = 0; j < word.length(); j++){
                if(set.contains(word.substring(0,j+1))){
                    //替换
                    words[i] = word.substring(0,j+1);
                    break;
                }
            }
        }
        return String.join(" ",words);
    }
}

⑫720.词典中最长的单词

2024.4.18 周四
题目：
给出一个字符串数组 words 组成的一本英语词典。
返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

思考：
找到 words 中最长的一个单词
先找到最长的那个单词，再判断 words 中是否包含其所有前缀单词

self 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
32
33
34
35
36
37
38
39
40
41
class Solution {
    public String longestWord(String[] words) {
        String res = "";
        int n = words.length;
        //将 words 按照长度由大到小排序
        //长度相同时按照字典序由小到大排序
        Arrays.sort(words,new Comparator<String>(){
            @Override
            public int compare(String s1,String s2){
                if(s1.length() != s2.length()){
                return s2.length() - s1.length();
            }else{
                return s1.compareTo(s2);
            }
            }
        });

        for(int i = 0; i < n; i++){
            if(isContains(words[i], words)){
                res = words[i];
                break;
            }
        }
        return res;
    }

    //判断一个字符串数组中是否含有一个字符串的所有前缀
    public Boolean isContains(String word,String[] words){
        Set<String> temp = new HashSet<>();
        for(int i = 0; i < words.length; i++){
            temp.add(words[i]);
        }

        for(int k = 0; k < word.length(); k++){
            if(!temp.contains(word.substring(0,k+1))){
                return false;
            }
        }
        return true;
    }
}

⑬721.账户合并

2024.4.19 周五
题目：
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。
如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。
请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。
一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：
每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。
账户本身可以以 任意顺序 返回。

示例 1：
输入：
accounts =[
[“John”, “johnsmith@mail.com“, “john00@mail.com“],
[“John”, “johnnybravo@mail.com“],
[“John”, “johnsmith@mail.com“, “john_newyork@mail.com“],
[“Mary”, “mary@mail.com“]
]

输出：[
[“John”, ‘john00@mail.com‘, ‘john_newyork@mail.com‘, ‘johnsmith@mail.com‘],
[“John”, “johnnybravo@mail.com“],
[“Mary”, “mary@mail.com“]
]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com“。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。

思考：
只要是含有相同邮箱地址的人就是同一个人，否则就不是
是同一个人就需要将他的所有邮箱合并起来

Map
邮箱地址 - 名称
邮箱地址 - 编号

emailToIndex
邮箱 - 编号

emailToName
邮箱 - 名称

union
原来给到的：
名称下——将邮箱进行合并邮箱的 编号

indexToEmails Map<Integer, List<String>>
根节点 编号 - 该根节点下所有 邮箱
find
找到每个邮箱 编号 所属的并查集的 根节点
同一个 根节点 下的所有邮箱地址添加到 indexToEmails 中

并查集

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<String, Integer>();
        Map<String, String> emailToName = new HashMap<String, String>();
        int emailsCount = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                if (!emailToIndex.containsKey(email)) {
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }
        UnionFind uf = new UnionFind(emailsCount);
        //将每个账户中的邮箱地址进行合并
        //相同名称的邮箱地址在并查集中进行合并
        //原集合中给每个账户的地址合并起来，建立并查集
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                uf.union(firstIndex, nextIndex);
            }
        }

        //-------------------------------------------------------------------

        Map<Integer, List<String>> indexToEmails = new HashMap<Integer, List<String>>();
        for (String email : emailToIndex.keySet()) {
            //找到每个邮箱地址所属的并查集的根节点
            int indexG = uf.find(emailToIndex.get(email));
            //将同一个根节点下的所有邮箱地址添加到 indexToEmails 中
            List<String> account = indexToEmails.getOrDefault(indexG, new ArrayList<String>());
            account.add(email);
            indexToEmails.put(indexG, account);
        }

        List<List<String>> merged = new ArrayList<List<String>>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            account.add(name);
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }
}

class UnionFind{
    //并查集
    int[] parent;

    //初始化
    public UnionFind(int n){
        parent = new int [n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    //查找
    public int find(int index){
        if(parent[index] == index){
            return index;
        }else{
            parent[index] = find(parent[index]);
            return parent[index];
        }
    }
    //合并
    public void union(int index1, int index2){
        int p1 = find(index1); //找到index1的祖先
        int p2 = find(index2); //找到index2的祖先
        parent[p2] = p1; //index2的祖先指向index1的祖先
    }
}

⑭722.删除注释

2024.4.20 周六
题目：
给一个 C++ 程序，删除程序中的注释。
这个程序source是一个数组，其中source[i]表示第 i 行源码。
这表示每行源码由 ‘\n’ 分隔。

  1. 第一个有效注释优先于其他注释。
  2. 如果一行在删除注释之后变为空字符串，那么不要输出该行。
    即，答案列表中的每个字符串都是非空的。

样例中没有控制字符，单引号或双引号字符。

例子：

[
“/*Test program /“, ———
“int main()”,
“{ “,
“ // variable declaration “, ———
“int a, b, c;”,
“/ This is a test”, —–
“ multiline “, —-
“ comment for “, —
“ testing */“, —
“a = b + c;”,
“}”
]

输入: source = [“a/comment”, “line”, “more_comment/b”]
输出: [“ab”]

new_line 记录新的一行

每个字符有两种情况：
在一个注释内 or 不在注释内

假设此刻不在注释快内：

  • 遇到 /* 将状态改为在注释内，继续遍历第三个字符
  • 遇到 // 直接忽略掉该行后面的部分
  • 遇到其他字符，将该字符记录到 new_line 中
    假设在注释快内：
  • 遇到 * / 则将状态改为不在注释快内，继续遍历第三个字符

当遍历到每行的末尾时，如果不在注释快内并且 new_line 不为空，则将它放入答案中

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public List<String> removeComments(String[] source) {
        List<String> res = new ArrayList<>();
        StringBuilder newLine = new StringBuilder();

        //记录当前字符是否在注释快内
        Boolean inBlock = false;

        //遍历每行代码
        for(String line : source){
            for(int i = 0; i < line.length(); i++){

                if(inBlock){
                    //在注释快内，找 */
                    if(i + 1 < line.length() && line.charAt(i) == '*' && line.charAt(i+1) == '/'){
                        inBlock = false;
                        i++; //继续下一个字符
                    }
                }else{
                    //不在注释快内，找 //、/*
                    if(i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i+1) == '*'){
                        inBlock = true;
                        i++;
                    }else if(i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i+1) == '/'){
                        //直接忽略掉该行后面部分 换下一行
                        break;
                    }else{
                        //遇到普通字符 进行拼接
                        newLine.append(line.charAt(i));
                    }
                }

            }//当前行代码遍历结束
            //将拼接是字符串添加到 res 答案中
            //当字符拼接器不为空、且不在注释快内 即可添加到答案中
            //注意：清空 StringBuilder
            if(!inBlock && newLine.length() > 0){
                res.add(newLine.toString());
                //清空
                newLine.setLength(0);
            }

        }//双层for循环结束
        return res;
    }
}

⑮752.打开转盘锁

2024.4.21 周日
(最短路/最小步数)
(双向BFS)
题目：
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。
每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:
输入：deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。

思考：
每次旋转都只能转动一个数字

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
    String start;
    String target;

    Set<String> dead = new HashSet<>();

    public int openLock(String[] deadends, String t) {
        start = "0000";
        target = t;
        if (start.equals(t))
            return 0;

        for (String d : deadends) {
            dead.add(d);
        }
        if (dead.contains(t) || dead.contains("0000"))
            return -1;

        int res = bfs();
        return res;
    }

    public int bfs() {
        Deque<String> deque1 = new ArrayDeque<>();// 正向搜索 start 开始
        Deque<String> deque2 = new ArrayDeque<>();// 反向搜索 target 开始

        // 分别记录两个方向出现的状态是经过多少次转换而来的
        Map<String, Integer> state1 = new HashMap<>();
        Map<String, Integer> state2 = new HashMap<>();

        // 初始状态值
        deque1.addLast(start);
        state1.put(start, 0);
        deque2.addLast(target);
        state2.put(target, 0);

        while (!deque1.isEmpty() && !deque2.isEmpty()) {
            int res = -1;
            if (deque1.size() <= deque2.size()) {
                res = update(deque1, state1, state2);
            } else {
                res = update(deque2, state2, state1);
            }
            if (res != -1)
                return res;
        }
        return -1;
    }

    // 更新队列状态
    int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
        int size = deque.size();
        while (size-- > 0) {
            String poll = deque.pollFirst();
            char[] pollChar = poll.toCharArray();
            int step = cur.get(poll);
            // 枚举替换每个字符
            for (int i = 0; i < 4; i++) {
                // 可以正向or反向 直接枚举偏移量 [-1,1] 然后跳过 0
                for (int j = -1; j <= 1; j++) {
                    if (j == 0)
                        continue;

                    // 求得替换字符串
                    // 先将当前字符变成数字
                    int origin = pollChar[i] - '0';
                    int next = (origin + j) % 10;
                    if (next == -1) {
                        next = 9;
                    }

                    // 又替换成字符
                    char[] clonePoll = pollChar.clone();
                    clonePoll[i] = (char) (next + '0');
                    String str = String.valueOf(clonePoll);

                    if (dead.contains(str))
                        continue;
                    if (cur.containsKey(str))
                        continue;

                    // 如果在另一方向找到过，说明最短路径找到了，否则加入队列
                    if (other.containsKey(str)) {
                        return step + 1 + other.get(str);
                    } else {
                        deque.addLast(str);
                        cur.put(str, step + 1);
                    }
                }

            }
        }
        return -1;
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deads=new HashSet<>();
        for(String dead:deadends){
            deads.add(dead);
        }
        Queue<String> queue=new LinkedList<>();
        Set<String> visited=new HashSet<>();
        int step=0;
        queue.offer("0000");
        visited.add("0000");

        while(!queue.isEmpty()){
            int size=queue.size();

            for(int i=0;i<size;i++){
                String cur=queue.poll();

                if(deads.contains(cur)){
                    continue;
                }
                if(cur.equals(target)){//得到目标值
                    return step;
                }
                for(int j=0;j<4;j++){
                    //枚举替换每个字符
                    String up = plusOne(cur, j);
                    if(!visited.contains(up)){
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if(!visited.contains(down)){
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }

            step++;
        }

        return -1;
    }

    // 将 s[j] 向上拨动一次
    String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9')
            ch[j] = '0';
        else
            ch[j] += 1;
        return new String(ch);
    }

    // 将 s[i] 向下拨动一次
    String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0')
            ch[j] = '9';
        else
            ch[j] -= 1;
        return new String(ch);
    }
}

⑯792.匹配子序列的单词数

2024.4.22 周一
题目：
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
例如， “ace” 是 “abcde” 的子序列。
提示：
words[i]和 s 都只由小写字母组成。
1 <= s.length <= 5 * 104

思路1：
暴力枚举 words 中的每个字符串 word ，判断其是否为 s 的子序列

self 超出时间限制

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 int numMatchingSubseq(String s, String[] words) {
        int res = 0;
        for(String word : words){
            if(isSub(s,word)){
                res++;
            }
        }
        return res;
    }

    //判断word是不是s的子序列
    public Boolean isSub(String s, String word){
        if(word.length() > s.length()) return false;

        int first = 0;
        int second = 0;

        while(first < word.length() && second < s.length()){
            if(word.charAt(first) == s.charAt(second)){
                first++;
            }
            second++;
        }
        return first == word.length();
    }
}

思路2：分桶
将 words 中的 word 按照首字母分到26个桶中。

从 s 的第一个字母开始遍历
假设第一个字母是’a’：
从’a’桶中取出所有单词；
对于每个取出的单词，如果长度为1，则说明该单词已经匹配完毕，将res+1；
如果长度大于1，则将首字母去掉，放入下一个字母的桶中；
进行下一轮…

分桶 87%

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
33
34
35
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int res = 0;
        //26个桶的数组
        Deque<String> [] temp = new Deque[26];
        //创建好每个空桶
        for(int i = 0; i < 26; i++){
            temp[i] = new ArrayDeque<String>();
        }

        //将words中的单词分类装桶
        for(String word : words){
            temp[word.charAt(0) - 'a'].add(word);
        }

        //遍历s中的每个字母
        for(char c : s.toCharArray()){
            //找到c对应的桶
            var barrel = temp[c-'a'];
            //遍历该桶中的所有字符串
            for(int k = barrel.size(); k > 0; --k){ //注意：这里的for循环中的size是会改变的
                //依次取出每个元素
                String word = barrel.pollFirst(); //这里会改变桶的大小
                //判断是不是1
                if(word.length() == 1){
                    res++;
                }else{
                    //删除第一个字母，加入到新桶
                    temp[word.charAt(1) - 'a'].offer(word.substring(1));
                }
            }
        }
        return res;
    }
}

⑰809.情感丰富的文字

2024.4.23 周二
题目：
有时候人们会用重复写一些字母来表示额外的感受，比如 “hello” -> “heeellooo”, “hi” -> “hiii”。
我们将相邻字母都相同的一串字符定义为相同字母组，例如：”h”, “eee”, “ll”, “ooo”。
扩张 操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。
输入一组查询单词，输出其中可扩张的单词数量。
输入：
s = “heeellooo”
words = [“hello”, “hi”, “helo”]
输出：1
解释：
我们能通过扩张 “hello” 的 “e” 和 “o” 来得到 “heeellooo”。
我们不能通过扩张 “helo” 来得到 “heeellooo” 因为 “ll” 的长度小于 3 。

思考：
s 中相同字母达到3个及以上才可以对该字母进行扩张

遍历words中的每个单词，判断该单词可不可以扩张为s

只有当 i 和 j 同时超出边界时才是可扩张。
首字母必须相同，不相同 return false
当首字母相同时：
分别统计 s 和 word 从该首字母开始相同的字母的个数；
如果 counti < countj return false
如果 counti = countj 满足要求
如果 counti != countj 且 counti < 3 return false
最后判断 s 和 word 是否同时遍历完

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
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int expressiveWords(String s, String[] words) {
        int res = 0;
        for(String word : words){
            //判断s是不是当前单词的扩展
            if(isExpand(s,word)){
                res++;
            }
        }
        return res;
    }

    public Boolean isExpand(String s, String word){
        int i = 0;
        int j = 0;
        while(i < s.length() && j < word.length()){
            //如果两者都超过了length则说明两字符串同时完成遍历，word可以扩展成s
            if(s.charAt(i) != word.charAt(j)){
                return false;
            }

            //字母相同
            char same = s.charAt(i);
            int counti = 0; //统计该字母在s中出现的次数
            while(i < s.length() && s.charAt(i) == same){
                counti++;
                i++;
            }

            int countj = 0; //统计该字母在word中出现的次数
            while(j < word.length() && word.charAt(j) == same){
                countj++;
                j++;
            }

            if(counti < countj){
                return false;
            }
            if(counti != countj && counti < 3){
                return false;
            }
        }
        return i == s.length() && j == word.length();
    }
}

⑱811.子域名访问计数

2024.4.24 周三
题目：
网站域名 “discuss.leetcode.com” 由多个子域名组成。
顶级域名为 “com” ，二级域名为 “leetcode.com” ，最低一级为 “discuss.leetcode.com” 。
当访问域名 “discuss.leetcode.com” 时，同时也会隐式访问其父域名 “leetcode.com” 以及 “com” 。
计数配对域名 是遵循 “rep d1.d2.d3” 或 “rep d1.d2” 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

easy

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> subdomainVisits(String[] cpdomains) {
        List<String> res = new ArrayList<>();
        Map<String,Integer> counts = new HashMap<>();

        for(String cpdomain : cpdomains){
            int space = cpdomain.indexOf(' ');//空格
            int count = Integer.parseInt(cpdomain.substring(0,space));//次数
            String domain = cpdomain.substring(space + 1);//域名

            counts.put(domain,counts.getOrDefault(domain,0) + count);
            for(int i = 0; i < domain.length(); i++){
                if(domain.charAt(i) == '.'){
                    //得到子域名
                    String subdomain = domain.substring(i+1);
                    counts.put(subdomain,counts.getOrDefault(subdomain,0) + count);
                }
            }
        }
        for(Map.Entry<String,Integer> entry : counts.entrySet()){
            String subdomain = entry.getKey();
            int count = entry.getValue();
            res.add(count + " " + subdomain);
        }
        return res;

    }
}

⑲820.单词的压缩编码

2024.4.25 周四
题目：
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.length
助记字符串 s 以 ‘#’ 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 ‘#’ 字符结束（但不包括 ‘#’）的 子字符串 恰好与 words[i] 相等
给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
示例 1：
输入：words = [“time”, “me”, “bell”]
输出：10
解释：一组有效编码为 s = “time#bell#” 和 indices = [0, 2, 5] 。
words[0] = “time” ，s 开始于 indices[0] = 0 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
words[1] = “me” ，s 开始于 indices[1] = 2 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
words[2] = “bell” ，s 开始于 indices[2] = 5 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”

思考：
words = [“time”, “me”, “bell”]
s = “time#bell#” 和 indices = [0, 2, 5]
求 s 的最短长度

只有一个单词是另一个单词的后缀，才可以共用一个 #
将 words 中的字符串反转后再按照字典序排序
可以发现，前一个单词可能是后一个单词的前缀，如果是就可以共用一个 #

time -> emit
me -> em
bell -> lleb
排序
em
emit
lleb

翻转 + 排序 21%

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

        //翻转
        for(int i = 0; i < n; i++){
            String word = words[i];
            reverseWord[i] = new StringBuilder(word).reverse().toString();
        }
        //排序
        Arrays.sort(reverseWord);

        for(int i = 0; i < n; i++){
            //如果后一个以前一个开头，则可以共用一个字符串
            if(i + 1 < n && reverseWord[i+1].startsWith(reverseWord[i])){
                continue;
            }else{
                res += reverseWord[i].length() + 1;
            }
        }
        return res;
    }
}

思路2：
将所有 words 放在一个 set 中
在 set 中直接删除 words 中单词 word 的所有后缀单词

哈希表 68%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> set = new HashSet<>(Arrays.asList(words));
        int res = 0;

        for(String word : words){
            for(int i = 1; i < word.length(); i++){
                set.remove(word.substring(i));
            }
        }

        for(String word : set){
            res += word.length() + 1;
        }
        return res;
    }
}

⑳833.字符串中的查找与替换

2024.4.26 周五
(在指定的位置进行部分字符串精确替换)
题目：
你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。
替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。
要完成第 i 个替换操作:
检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
如果没有出现， 什么也不做 。
如果出现，则用 targets[i] 替换 该子字符串。
例如，如果 s = “abcd” ， indices[i] = 0 , sources[i] = “ab”， targets[i] = “eee” ，那么替换的结果将是 “eeecd” 。
所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
s、sources[i] 和 targets[i] 仅由小写英文字母组成

思考：
不能使用 s.indexOf(source) == index 进行判断是否进行替换操作，因为 source 第一次出现的位置不一定是 index
可以这样判断： s.startsWith(source,index)
注意：使用replace和replaceAll都不适合，需要自己写替换操作

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 String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int k = indices.length;
        int n = s.length();

        String[] replaceStr = new String[n]; //替换后的字符串
        int[] replaceLen = new int[n]; //被替换的长度
        Arrays.fill(replaceLen,1); //无需替换时 i += 1

        for(int i = 0; i < k; i++){
            String source = sources[i];
            int index = indices[i];
            if(s.startsWith(source,index)){
                //需要替换
                replaceStr[index] = targets[i];
                replaceLen[index] = source.length();
            }
        }

        //进行替换操作
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < n; i += replaceLen[i]){
            if(replaceStr[i] == null){
                ans.append(s.charAt(i));
            }else{
                ans.append(replaceStr[i]);
            }
        }
        return ans.toString();
    }
}
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:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信