93. Restore IP Addresses

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

这道题要求我们从字符串中恢复出所有的标准IP,对于这种要求返回所有可能结果的题目,我们通常优先采用递归和回溯算法来解决。

我们可以从头到尾遍历字符串,观察每个字符是否符合我们的要求,至于什么样的字符能够被定义为符合要求,我们稍后讨论。每次取三个字符进行判断,判断其是否有效。

为什么每次取三个?稍有些网络基本常识的人就会知道,IPv4的IP地址由32个二进制数表示,共四部分,每部分由8位组成。所以最大也就是255。所以每次取三位进行判断。

在取字符的过程中,如果该字符符合条件,那么我们向后移动一位,以后一位为起点进行递归。否则,直接后移。

这个思路我们之前在Subsets问题中已经用过了,稍加改动即可。

下面我们讨论如何判断地址有效性的问题:

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()){
                string ipAddr=ipNum[0];
                for(int i=1;i<4;i++)
                    ipAddr+=("."+ipNum[i]);
                ipComb.push_back(ipAddr);
            }
            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> restoreIpAddresses(string s) {
        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

这是一道在leetcode上有较大争议的一道题,原因在于它的描述方式确实不够准确,以至于我在开始读这道题时不知所云。

此外,这道题的generate the nth sequence.也造成了一定的困惑,这个n到底是从哪里开始算的呢?

实际上,这道题的题意是,最初有一个字符串"1",我们将其读作“one 1”,也就是”一个1”的意思。对于“11”,当然就是“两个1”啦,以此类推就可以得出n取其他值时应该由我们的函数生成的字符串了。

很显然,这是一个不断迭代的过程,我们只需要从第一个数字开始不断计数,如果之后的数字等于第一个数字,那么计数变量应该+1,否则,就应该将统计结果转换为字符串,使之成为结果的一部分,并且,在下一轮计数开始之前,切记将计数变量初始化为0.

迭代版的代码如下:

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;
    }
};

关于n的计数问题,根据题目的意思,n==1时应该返回“1”,而不是“11”.

另外,也可以通过递归来解决这个问题。

最后,附上leetcode讨论区中关于此题的说明。

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,是同一个版本。

所以,如果我们想当然地认为浮点数2.2大于2.15,所以在版本号系统中亦如此,那就大错特错了。

所以要对版本号进行比较的话,我们需要对两个字符串进行遍历,之后以’.’为界限,计算两个’.’之间的数值,每分割出一个这样的子串并计算出其整型值之后,可以立刻进行比较。

之所以要立刻进行比较,是因为,以13.28.3513.30.36做比较,当我们比较到中间的两位数字2830之后,实际上已经分出了新旧版本关系,完全不必去比较3536的关系。

给出如下代码,看完代码思路应该会很清楚。

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;
    }
};

67. Add Binary

Description

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

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

Analysis

这道题和之前做过的Add two number在题意上有很多相似之处,都是将两个二进制数进行加法运算,但这道题的难点在于,字符串有可能是不等长的,一旦出现了不等长,就很有可能会因为空指针的问题导致程序出现问题。

最开始我的思路比较直接,就是将字符串转换为二进制数后再进行加法运算,看似很简单的方法往往其中会暗藏很多陷阱,导致我卡在这道题上很长时间。

参阅了Discuss区之后,我获得了一种比较好的思路,既然之前程序出问题都是因为字符串不等长,那么我们只需要将短一些的字符串用0补齐不就解决了吗?

这种放法的思路是,从右到左按位取出字符串中的每一位,对于较短的字符串则用0来补位。对两个数进行加法运算,同时维护一个carry变量用于进位即可,代码如下:

如果运算到最高位发现还需要进位,那就在字符串开头插一个0即可。

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

这道题是一道比较容易的字符串操作题,只要找到其中的规律其实就没有什么难度了。

我们可以用一个vector<string>来保存我们的答案,这是因为,我们需要先将一个字符串转换为nRows个字符串。之后,我们每次用一个指针指向字符串起始位置,同时设置计数变量row来标记其在vector<string>中的位置即可。

下面对循环及逻辑判断的条件进行讨论,当我们的计数变量row小于nRows-1的值时,说明vector<string>没有构造完成,我们应该让字符串上的指针继续向前,同时计数变量row继续前进,也就是说进入下一行继续构造vector<string>

若两值相等,则说明我们该让计数变量row回退一下,即退回上一行继续构造vector<string>

厘清思路后,代码就很容易看明白了

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
*/