C++刷题实战（Warm UP）

Sock Merchant

思路：把匹配的袜子挑出来放到新的vector中，每次配对袜子避开那些已经匹配了的

其他思路：用不可重复的容器如set，不断尝试将新的袜子放入若以重复表示匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sockMerchant(int n, vector<int> ar) {
    vector<int> selected;
    int count=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(find(selected.begin(),selected.end(),j)==selected.end())&&
            !(find(selected.begin(),selected.end(),i)!=selected.end())
            &&ar[i]==ar[j]){
                count++;
                selected.push_back(j);
                break;
            }
        }
        selected.push_back(i);
    }
    return count;

}

push_back

find(selected.begin(),selected.end(),j)!=selected.end()用来找寻元素。这个表示找到了。

Counting Valleys

思路：用一个int表示之前状态（在山上，水平面，峡谷里），一个int表示当前状态，只有从山上或水平面，下到峡谷才经过一个峡谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int countingValleys(int n, string s) {
    int state=0;
    int statePrevious;
    int valley=0;
    for(int i=0;i<n;i++){
        if(state==0){
            statePrevious=0;
        }else if(state>0){
            statePrevious=1;
        }else{
            statePrevious=-1;
        }
        
        if(s[i]=='U'){
            state++;
        }else if(s[i]=='D'){
            state--;
        }
        if(statePrevious>=0&&state<0){
            valley++;
        }
    }
    return valley;
}

Jumping on the Clouds

思路：只要向后两个是能站的云就站上去，否则就只向前一步，注意：需要判断结束条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int jumpingOnClouds(vector<int> c) {
    int steps=0;
    auto player=c.begin();
    while(player!=c.end()){
        if(next(player,2)==--c.end()||next(player,1)==--c.end())
        {
            steps++;
            break;
        }
        if(*next(player,2)==1){
            player=next(player,1);
        }else{
            player=next(player,2);
        }
        steps++;
    }
    return steps;

}

iterator的end指向的是最后一个元素之后的位置，所以为了获得最后一个元素要–操作

iterator是指针，要获得原object要*操作取消引用

关于next，advance的区别：next是advance带返回值的版本

Repeated String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long repeatedString(string s, long n) {
    int length=s.length();
    int aNum=0;
    for(int i=0;i<length;++i){
        if(s[i]=='a'){
            aNum++;
        }
    }
    long repeteTimes=n/length*aNum;
    long leftLetters=n%length;
    for(long i=0;i<leftLetters;++i){
        if(s[i]=='a'){
            repeteTimes++;
        }
    }
    return repeteTimes;
}

思路：a在s中出现频率*s重复次数+最后用于补全的句子中a重复次数，s重复次数=n/s长度。注意：用long

获取字符串长度用length()