三色球问题_三色球问题 rgb分别代表红色,绿色,蓝色球。 输入 给定一串字符串

三色球问题

RGB分别代表红色，绿色，蓝色球。

输入 给定一串字符串 如“RRRRGGGGGGBGGBBBB”

返回 G 5 6 7 8 9 10

     R 1 2 3 4

     B  14 15 16 17

     G 12 13
1
2
3
4
5

解释：第一行 先输出 颜色相同 连续的 最长球串，如上述字符串中 显然G那段最长，从第5个开始，到第10个结束，所以第一行输出 G 5 6 7 8 9 10

       第二行，在第一行奖G输出之后，就要从字符串中删除G，原来的字符串被分为两个 “RRRR”和“BGGBBBB”但是仍然要保持在原来串中的先后次序。此时最长的就是RRRR和BBBB，规则：碰到多段等长的球串 输出最左边的 因此 输出 R 1 2 3 4

      第三行，同理 删除第二行输出的R，原串变成 BGGBBBB，此时最长显然为B那段 因此输出 B 14 15 16 17，为什么不是B 4 5 6 7 呢，

      规则：虽然前面删除了已经输出的串，但是不管删多少后面输出时，仍然按照 球在原来字符串中位置信息输出。
1
2
3
4
5

就是这样。

package other;

import java.util.HashMap;

/**
 * @author lzm
 * @create 2020- 04- 06- 15:56
 * 题目：给一个字符串 由RGB（红绿蓝）3种字母组成
 * 1.找出串中最长的相同子串，输出字母以及所在位置，然后剔除（如有多个相同拿最左的子串）
 * 2.将剩余部分按序连接，如果只有一个字母则结束游戏，否则返回第一步
 * 注意每次输出的位置为原始串中的位置
 * 例：
 * RBBGGR
 * B 2 3
 * G 4 5
 * R 1 6
 */
public class Test2 {
    public static void main(String[] args) {
        Test2 test2=new Test2();
        String s="RRGGGBGG";
        test2.RGB(s);
    }

        public void RGB(String s)
        {
            int rlength=0,glength=0,blength=0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)=='R') rlength++;
                if (s.charAt(i)=='G') glength++;
                if (s.charAt(i)=='B') blength++;
            }
            //存储R G  B各个位置
            int[] red=new int[rlength];
            int[] green=new int[glength];
            int[] blue=new int[blength];
            int r=0,g=0,b=0;
            String copy=new String(s);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)=='R')
                {
                    red[r]=i;
                    r++;
                }
                if (s.charAt(i)=='G')
                {
                    green[g]=i;
                    g++;
                }
                if (s.charAt(i)=='B')
                {
                    blue[b]=i;
                    b++;
                }
            }
            while (s.length()>0)
            {
                //找出单轮的最大连续个数
                int max=1;
                int start=0,end=0;
                for (int i = 0; i < s.length()-1; i++) {
                    int count = 1;
                    int p=i;
                    while ( p<s.length()-1&&s.charAt(p) == s.charAt(p + 1) ) {
                        count++;
                        p++;
                    }
                    if (count > max) {
                        start = i;
                        max=count;
                        end=start+max-1;
                    }
                }
                    char c = s.charAt(start);
                //a是前面有几个和自己相同的字符
              int a= findCharNumBeforeStart(start,c, s);
                System.out.print(c);
                    for (int j = 0; j <max ; j++) {
                        int location=out(j,a,c,red,green,blue)+1;
                        System.out.print(location);
                    }
                String substring = s.substring(0, start);
                String substring1 = s.substring(end+1, s.length());
                s=substring+substring1;
            }
        }

        //a是删减的字符串s中最大连续字符的位置，c是返回的R，G，B字符，count是前面被删除的个数
    private int out(int j,int a, char c, int[] red, int[] green, int[] blue) {
        int count=0;
        if (c=='R'){
            while (red[a+j+count]==-1) {
                count++;
            }
            int location=red[a+j+count];
            red[a+j+count]=-1;
            return location;
        }
        if (c=='G'){
            while (green[a+j+count]==-1) {
                count++;
            }
            int location=green[a+j+count];
            green[a+j+count]=-1;
            return location;
        }
        if (c=='B'){
            while (blue[a+j+count]==-1) {
                count++;
            }
            int location=blue[a+j+count];
            blue[a+j+count]=-1;
            return location;
        }
        return -1;
    }


    //查找前面有几个和自己相同的字符
    private int findCharNumBeforeStart(int start,char c,String s) {
        int count=0;
        for (int i = 0; i < start; i++) {
            if (s.charAt(i)==c)
            {
                count++;
            }
        }
        return count;
    }


}

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

当s=“RRRRGGGGGGBGGBBBB”时

这道题我感觉还是还是有难度的，考虑的条件有点多，代码应该没啥问题，就是时间复杂度度会差点，就只有这水平了

优化下代码

主要是排序排出来，考虑好边界就行

res = res.stream().sorted(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                if (o1.get(0).equals(o2.get(0))) {
                    //count相同  起始位置单调递增
                    return o1.get(1) - o2.get(1);
                } else {
                    //单调递减
                    return o2.get(0) - o1.get(0);
                }
            }
        }).collect(Collectors.toList());
1
2
3
4
5
6
7
8
9
10
11
12

package com.lzm.Group3;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Description: TODO
 * @author: lzm
 * @date: 2021年09月06日 16:00
 */
public class Test5 {
    public static void main(String[] args) {
        Test5 test5 = new Test5();
        String s = "RRRRGGGGGGBGGBBBB";
        List<String> res = test5.getRgb(s);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

    private List<String> getRgb(String s) {
        if (s.length() == 0) {
            return new ArrayList<>();
        }
        //定义一个数组记录是否已使用
        boolean[] isUse = new boolean[s.length()];
        //定义一个list[4] 0:count  1:start 2:end 3:颜色 0:R 1:G 2:B
        Character[] color = {'R', 'G', 'B'};
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int start = 0;
        int end = 0;
        int length = s.length();
        List<Integer> list = new ArrayList<>();
        Character character = new Character(s.charAt(0));
        while (end < length) {
            if (s.charAt(end) == character) {
                end++;
            } else {
                //遍历数组将大小 start end 颜色注入res
                list.add(end - start + 1);
                list.add(start);
                list.add(end);
                int index = getColorIndex(character);
                list.add(index);
                res.add(list);
                //重新写start
                start = end;
                end = start;
                character = s.charAt(end);
                list = new ArrayList<>();
            }
        }


        list.add(end - start);
        list.add(start);
        list.add(end);
        int index = getColorIndex(character);
        list.add(index);
        res.add(list);

        res = res.stream().sorted(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                if (o1.get(0).equals(o2.get(0))) {
                    //count相同  起始位置单调递增
                    return o1.get(1) - o2.get(1);
                } else {
                    //单调递减
                    return o2.get(0) - o1.get(0);
                }
            }
        }).collect(Collectors.toList());

        //数组队列
        List<String> rgbString = new ArrayList<>();
        for (int i = 0; i < res.size(); i++) {
            List<Integer> colorList = res.get(i);
            //得到颜色
            Integer integer = colorList.get(3);
            Character colorCharacter = color[integer];
            //开始 结束位置
            Integer begin = colorList.get(1);
            Integer end1 = colorList.get(2);
            //输出颜色字符串
            StringBuilder outColorString = new StringBuilder();
            outColorString.append(colorCharacter).append(" ");
            for (int j = begin+1; j <= end1; j++) {
                outColorString.append(j).append(" ");
            }
            rgbString.add(outColorString.toString());
        }
        return rgbString;
    }

    private int getColorIndex(Character character) {
        Character[] color = {'R', 'G', 'B'};
        for (int i = 0; i < color.length; i++) {
            if (color[i].equals(character)) {
                return i;
            }
        }
        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
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
96
97
98
99
100
101
102
103
104
105
106
107
108