38.md

38. 外观数列

1.     1
2.     11
3.     21
4.     1211
5.     111221

思路

• 标签：栈（数组）
• 字符串：「外观数列」用字符串表示
• 借助栈：将相同元素加入栈，使用栈得到相同元素的长度（个数）。
• 时间复杂度：O(n^2)，双重循环
• 空间复杂度：O(1)，需要额外的空间 -- 栈。栈的长度始终为常数个？

  1           11          21         12    1211  
│   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
│   │ │   │ │   │ │   │ │   │ │   │ │   │ │   │
│   │ │   │ │   │ │ 1 │ │   │ │   │ │   │ │   │
│   │ │ 1 │ │   │ │ 1 │ │   │ │ 2 │ │ 1 │ │   │
└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘

代码

# Python3
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        res = "1"
        for i in range(1, n):
            newStr = ""
            stack = [] 
            for x in res:
                if stack == [] or stack[0] == x:
                    stack.append(x)
                else:
                    newStr = newStr + str(len(stack)) + stack[0]
                    stack = []
                    stack.append(x)
            newStr = newStr + str(len(stack)) + stack[0] # 当字符串遍历完成后，还需要计算一次栈，因为栈中此时可能还有值
            res = newStr
        return res

// Java
class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        String res = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder newStr = new StringBuilder();
            LinkedList<Character> stack = new LinkedList<>();
            for (char x : res.toCharArray()) {
                if (stack.size() == 0 || stack.peek() == x) {
                    stack.push(x);
                } else {
                    newStr.append(stack.size()).append(stack.peek());
                    stack = new LinkedList<>();
                    stack.push(x);
                }
            }
            newStr.append(stack.size()).append(stack.peek());
            res = newStr.toString();
        }
        return res;
    }
}

前期错误思路

• 通过循环比较，判断元素是否相同，使用 count 记录重复元素

// 代码未实现，因为需要考虑的条件太多
class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        if (n == 2) {
            return "11";
        }

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);

        for (int i = 2; i < n; i++) {
            int count = 1;
            List<Integer> newList = new ArrayList<>();
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j) == list.get(j + 1)) {
                    count++;
                    if (j == list.size() - 2) {
                        newList.add(count);
                        newList.add(list.get(j));
                        break;
                    }
                } else {
                    newList.add(count);
                    newList.add(list.get(j));
                }
            }
            list = newList;
        }
        return list.toString();
    }
}