美团1面

  1. 初级版本字符串压缩
    原题链接:
    https://leetcode.cn/problems/compress-string-lcci/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String compressString(String S) {
        StringBuilder res = new StringBuilder() ;
        char [] cs = S.toCharArray();
        int i = 0;
        int n = cs.length;
        while (i < n){
            int count = 1;
            int j = i + 1;
            while (j < n && cs[i] == cs[j]){
                count++;
                j++;
            }
            res.append(cs[i] + "" + count);
            i = j;
        }

        return res.length() >= n ?  S : res.toString() ;
    }
}

  1. 中级版字符串压缩

原题链接:
https://leetcode.cn/problems/string-compression/description/

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
class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        // i j 分别指向 当前处理位置 和 答案待插入的位置
        int i = 0, j = 0;

        while(i < n){
            int idx = i;
            while(idx < n && chars[i] == chars[idx]){
                idx++;
            }      

            // 先赋值字母 如果有大于1的重复出现那么进行压缩
            chars[j++] = chars[i];

            // 统计有多少相同的元素
            int count = idx - i ;

            // count >  1 则开始压缩、
            // count = 1 不压缩 否则 1变成2 就变成增长了 
            if(count > 1){  
                int start = j, end = start;
                while(count != 0){
                    chars[end++]  = (char)((count % 10)+ '0');
                    count /= 10;
                }
                reverse(start,end - 1,chars);
                j = end;
            }
            i = idx;
        } 

        // j为答案待插入的位置
        // j - 1 即为答案的位置 由于数组从0开始 故返回j
        return j;
    }

    private void reverse(int start, int end,char[] cs) {
        while (start < end) {
            char t = cs[start];
            cs[start] = cs[end];
            cs[end] = t;
            start++; end--;
        }
    }

}

  1. 高级版字符串压缩
    原题链接:
    https://leetcode.cn/problems/string-compression-ii/description/