来刷题啊 2.21

LeetCode

easy

696. Count Binary Substrings

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of "0" or "1" characters.

【思路】
签到题。求0和1成团粘一起的子串个数，一串里面0和1的数目要相同。
用 s0 存一团里面 0 的个数， s1 存 1 的个数，因为数目要相同，所以每一团里面的可行子串数取较小的那个就好了。

【代码】

int countBinarySubstrings(char* s) {
    int count = 0;
    int len = strlen(s);
    int s0 = 0, s1 = 0;
    bool flag = 0;
    for(int i = 0; i < len; i++)
    {
        if(s[i]-'0' == 0)
        {
            if(flag == 0) s0++;
            else
            {
                count += min(s0,s1);
                flag = 0;
                s0 = 1;
            }
        }
        else
        {
            if(flag == 1) s1++;
            else
            {
                count += min(s0,s1);
                flag = 1;
                s1 = 1;
            }
        }
    }    
    return count + min(s0,s1);
}

686. Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

打模拟打崩了呀qaq...中间跑去刷了一趟空间回来就过了一个小时了（不x），然后来码了一下打崩掉的思路，突然发现卧槽我打智障了，然后重打十分钟a了...

【思路】
拿 B 的首元素去跟 A 元素一个个比对，如果遇到一个相同的，那说明有希望，就从这里开始往后看能不能一串都匹配上，但是因为可能有多解，所以再继续从 A 的刚刚那里往后找看能不能再遇到一个能匹配上 B 的首元素的，最后取个最小。

【代码】

int repeatedStringMatch(char* A, char* B) {
    int lenA = strlen(A);
    int lenB = strlen(B);
    int res = 10001;
    for(int i = 0; i < lenA; i++)
    {
        if(B[0] == A[i]) 
        {
            bool flag = true;
            int count = 1;
            int beginA = i+1;
            for(int j = 1; j < lenB; j++)
            {
                if(beginA >= lenA)
                {
                    beginA = 0;
                    count++;
                }
                if(B[j] != A[beginA++]) 
                {
                    flag = false;
                    break;
                }
            }
            if(flag == true) res = min(res,count);
        }
    }
    return res == 10001 ? -1 : res;
}

680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

【思路】
模拟咯。如果头尾不一样，那就看看如果扔头能匹配上就扔头，扔尾能匹配就扔尾。结果wa掉了扔头扔尾都可以匹配上的情况- -...比如“cuqucu”，所以还要特判一下这种情况，因为这种情况默认是扔头，那就用b1、e1存这时候如果扔尾的始末端，如果扔头失败，那就最后再重判一下扔尾的情况。

【代码】

bool validPalindrome(char* s) {
    int len = strlen(s);
    bool flag = true;
    int count = 0;
    int begin = 0, end = len-1;
    int b1 = 0,e1 = 0;
    while(begin < end)
    {
        if(s[begin] != s[end])
        {
            count++;
            if(count >= 2) 
            {
                flag = false;
                break;
            }
            if(s[begin+1] == s[end] && s[begin] == s[end-1])
            {
                b1 = begin;
                e1 = end-1;
            }
            if(s[begin+1] == s[end]) begin++;
            else if(s[begin] == s[end-1]) end--;
            else flag = false;
        }
        begin++;
        end--;
    }   
    if(b1 < e1 && flag == false)
    {
        while(b1 < e1) if(s[b1++] != s[e1--]) return false; 
        flag = true;
    }
    return flag;
}

【看到的一个优美的递归写法】

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--)
            if (s[i] != s[j]) return isp(s, i + 1, j) || isp(s, i, j - 1);
        return true;
    }
private:
    bool isp(string s, int l, int r) {
        for (int i = l, j = r; i < j; i++, j--)
            if (s[i] != s[j]) return false;
        return true;
    }
};

medium

767. Reorganize String

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Note:

S will consist of lowercase letters and have length in range [1, 500].

因为要用优先队列不得不用了C++（真tm好用...抱着C语言流下了委屈的泪水）

【思路】
题目要输出字符交换后相同元素不相邻的串。那就要看同个字符的一大串被别的插空能不能插满，只有当某个元素个数太多的时候会出事，比如aaab，里面最多个数的元素 a，最多最多只能跟后面其他的多一个，不然间隔就会插不满（tmp <= len-tmp+1）。
于是先 count 一下每个字母的个数然后全部扔进优先队列，每次取最多的那个来输出，这样一直输 len 个，一旦发现取出来最多的那个不满足之前说的条件（ 2*tmp.first > len+1）就GG了，返回空。这里漏考虑的一个点是，未必最多的那个元素扣掉一个之后就会比其他的少，这时候每次取最多就会出事。所以记录一下前一个刚输出的元素 now，如果这次取到的元素前面刚好输的就是它，那就再取下一个次多的来插空（如aaabc）。

【代码】

string reorganizeString(string S) {
    int count[26];
    memset(count,0,sizeof(count));
    int len = S.length();
    priority_queue< pair<int, char> > que;
    string ans = "";
    for(int i = 0; i < len; i++)
        count[S[i]-'a']++;
    for(int i = 0; i < 26; i++)
        if(count[i] != 0) que.push({count[i],i+'a'});
    char now = '0';
    while(!que.empty())
    {
        pair<int,char> tmp = que.top();
        que.pop();
        if(2*tmp.first > len+1) return "";
        if(tmp.second == now)
        {
            pair<int,char> tmp2 = que.top();
            que.pop();
            now = tmp2.second;
            ans += tmp2.second;
            tmp2.first--;
            len--;
            if(tmp2.first != 0) que.push(tmp2);
            que.push(tmp);
        }
        else
        {
            now = tmp.second;
            ans += tmp.second;
            tmp.first--;
            len--;
            if(tmp.first != 0) que.push(tmp);
        }
    }
    return ans; 
}

hard

761. Special Binary String

Special binary strings are binary strings with the following two properties:

The number of 0's is equal to the number of 1's.
Every prefix of the binary string has at least as many 1's as 0's.

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

Example 1:

Input: S = "11011000"
Output: "11100100"
Explanation:
The strings "10" [occuring at S1] and "1100" [at S3] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Note:

S has length at most 50.
S is guaranteed to be a special binary string as defined above.

题意有点懵...英语是真的菜，（没懂为什么example里的 S 会是special..）

直接贴discuss惹：Easy and Concise Solution with Explanation [C++/Java/Python]
可以直接看discuss，讲的很清楚，样例中的 S 在这个解法中会被拆成 1 10 1100 0