richardlaiis_not_found

just some ASCII texts

發表於

用來測試程式碼 highlight 的文章 ><。

Approach

紀錄每個連續的 substring 長度，把它加到答案中。但這樣會多算，因為每個可能多打的片段，都有算到”原本字串”的可能性，因此需要扣掉連續字元 substring 的數目減掉 1，此即為正確答案。

Complexity

$$O(n)$$

Code (C++)

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 possibleStringCount(string word) {
        int ret = 0;
        int seqcnt = 0;
        int cur = 1;
        char prev = word[0];
        int n = word.size();
        for (int i = 1; i < n; i++) {
            if (word[i] == prev) {
                ++cur;
            } else {
                if (cur > 1) {
                    ret += cur;
                    seqcnt++;
                }
                cur = 1;
                prev = word[i];
            }
        }
        if (cur > 1) {
            ret += cur-1;
        }
        if (ret == 0) return 1;
        ret -= seqcnt-1;
        return ret;
    }
};

發表於

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

0%