## Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

## Analysis

1.第一种情况:长度大于3，必然是无效地址，返回false

2.第二种情况:首位为0，但其长度大于1,比如001。

3.第三种情况:大于255

class Solution {
bool isValidNum(string num){
if(num.size()>3||num[0]=='0'&&num.size()>1||num.empty()||stoi(num)>255)
return false;
return true;
}
void Dfs(string & str,int index,vector<string> & ipNum,vector<string> & ipComb){
if(ipNum.size()==4){
if(index==str.size()){
for(int i=1;i<4;i++)
}
return;
}
string curNum;
for(int i=index;i<str.size()&&i<index+3;i++){
curNum.push_back(str[i]);
if(isValidNum(curNum)){
ipNum.push_back(curNum);
Dfs(str,i+1,ipNum,ipComb);
ipNum.pop_back();
}
}
}
public:
vector<string> ipNum;
vector<string> ipComb;
Dfs(s,0,ipNum,ipComb);
return ipComb;
}
};


# 38. Count and Say

## Description

The count-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2 then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

## Analysis

class Solution {
public:
string countAndSay(int n) {
if(n==1)
return "1";
string res="1";
int count=0;
while(--n){
string tmp="";
for(int i=0;i<res.size();++i){
int count=1;
while(i+1<res.size()&&res[i]==res[i+1]){
++i;
++count;
}
tmp+=to_string(count)+res[i];
}
res=tmp;
}
return res;
}
};


https://discuss.leetcode.com/topic/2068/how-to-proof-the-count-is-always-less-than-10

https://discuss.leetcode.com/topic/2264/examples-of-nth-sequence


# 165. Compare Version Numbers

## Description

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37


## Analysis

1.对于2.152.2，前者相对后者属于更新的版本，因为前者指第二阶段第十五个版本，而后者是第五个。

2.对于1.01，是同一个版本。

## Code

class Solution {
public:
int compareVersion(string version1, string version2) {
int v1_size=version1.size();
int v2_size=version2.size();
int sum1=0,sum2=0;
int i=0,j=0;
for(i=0,j=0;i<v1_size||j<v2_size;++i,++j){
sum1=0;
while(i<v1_size&&version1[i]!='.'){
sum1=sum1*10+version1[i]-'0';
++i;
}
sum2=0;
while(j<v2_size&&version2[j]!='.'){
sum2=sum2*10+version2[j]-'0';
++j;
}
if(sum1>sum2)
return 1;
else if(sum1<sum2)
return -1;
}
return 0;
}
};


## Description

Given two binary strings, return their sum (also a binary string).

For example, a = "11" b = "1" Return "100".

## Analysis

class Solution {
public:
string addBinary(string a, string b) {
int str_size=max(a.size(),b.size());
string res;
int carry=0;
for(int i=0;i<str_size;i++){
int tmpA=i<a.size()?(a[a.size()-1-i]-'0'):0;
int tmpB=i<b.size()?(b[b.size()-1-i]-'0'):0;
res.insert(0,to_string((tmpA+tmpB+carry)%2));
carry=(tmpA+tmpB+carry)>1?1:0;
}
if(carry==1)
res.insert(0,"1");
return res;
}
};


# 6. ZigZag Conversion

## Description

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R


And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);


convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

## Analysis

class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1||numRows>s.size()||numRows==s.size())
return s;
vector<string> str(numRows);
int step=1,row=0;
for(int i=0;i<s.size();++i){
str[row].push_back(s[i]);
if(row==0)
step=1;
else if(row==numRows-1)
step=-1;
row+=step;
}
s.clear();
for(int j=0;j<str.size();++j)
s.append(str[j]);
return s;
}
};


P.S 如果你对ZigZag Pattern的理解有疑惑的话，请记住这道题是这样定义ZigZag Pattern的。

/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/