LeetCode 696.カウントバイナリサブストリング(Count Binary Substrings)C C++
2032 ワード
タイトルリンク:https://leetcode-cn.com/problems/count-binary-substrings/description/
タイトル:
1つの文字列
重複するサブストリングが発生する回数を計算します
例1:
例2:
注意:
問題は、非空のサブ文字列が同じ要素で連続しなければならないことを要求するので、連続した同じ要素の最小個数、すなわち隣接する異なる要素と構成できるサブ列の個数を得ることができる.私は自分の言ったことに丸をつけられました.どう言いますか.例えば11000,'1';の個数は2,'0'の個数は3であるため,この一連の条件に合致するサブ列の個数は2であり,連続的で個数が等しい必要があるため,1と0の間は対称軸であり,それぞれ外に広がる.したがって、連続する同じ要素「圧縮」、すなわち、出現した個数を統計し、スタックに記録する必要があります.
Cコード:
C++ :
ありがとうございます.
タイトル:
1つの文字列
s
が与えられ、0と1の同じ数の非空(連続)サブ文字列の数が計算され、これらのサブ文字列のすべての0とすべての1が結合される.重複するサブストリングが発生する回数を計算します
例1:
: "00110011"
: 6
: 6 1 0:“0011”,“01”,“1100”,“10”,“0011” “01”。
, 。
,“00110011” , 0( 1) 。
例2:
: "10101"
: 4
: 4 :“10”,“01”,“10”,“01”, 1 0。
注意:
s.length
は1から50000の間にあります.s
には、「0」または「1」の文字のみが含まれます.問題は、非空のサブ文字列が同じ要素で連続しなければならないことを要求するので、連続した同じ要素の最小個数、すなわち隣接する異なる要素と構成できるサブ列の個数を得ることができる.私は自分の言ったことに丸をつけられました.どう言いますか.例えば11000,'1';の個数は2,'0'の個数は3であるため,この一連の条件に合致するサブ列の個数は2であり,連続的で個数が等しい必要があるため,1と0の間は対称軸であり,それぞれ外に広がる.したがって、連続する同じ要素「圧縮」、すなわち、出現した個数を統計し、スタックに記録する必要があります.
Cコード:
int countBinarySubstrings(char* s)
{
int total = 0,ct = 0;
int len = strlen(s);
int ar[50000] = {1};
for (int i = 0;i < len-1;i++)
{
if (s[i] != s[i+1])
{
ct++;
ar[ct] = 1;
}
else
ar[ct]++;
}
for (int j = 0;j < ct;j++)
total += (ar[j] < ar[j+1] ? ar[j] : ar[j+1]);
return total;
}
C++ :
class Solution {
public:
int countBinarySubstrings(string s) {
int* ar = new int[50000];
int count = 1;
int i = 0,j;
for (j = 1;j < s.size();j++)
{
if (s[j] == s[j-1])
count++;
else {
ar[i++] = count;
count = 1;
}
}
ar[i++] = count;
int sum = 0;
while (--i)
{
sum += min(ar[i],ar[i-1]);
}
delete []ar;
return sum;
}
};
ありがとうございます.