OJ每日练习（10）

Posted on | In

题目名称

  1. Valid Palindrome(Leetcode #125)
  2. Implement strStr(Leetcode #28)
  3. String to Integer(Leetcode #8)
  4. Add Binary(Leetcode #67)
  5. Longest Palindrome(Leetcode #409)
  6. 二叉搜索树的后续遍历序列（剑指offer #33）
  7. 二叉树中和为某一值的路径（剑指offer #34）
  8. 复杂链表的复制（剑指offer #35)
  9. 二叉搜索树与双向链表（剑指offer #36)
  10. 字符串的排列（剑指offer #37)

Valid Palindrome(Leetcode #125)

题目描述

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

解题思路

双指针解题，避开所有无效字符后对二者进行比对。若匹配则执行下一轮，否则退出。这里注意isalnum的使用。

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isPalindrome(string s) {
        for(int i=0,j=s.size()-1;i<j;++i,--j){
            while (isalnum(s[i]) == false && i < j) i++;
		    while (isalnum(s[j]) == false && i < j) j--;
		    if (toupper(s[i]) != toupper(s[j])) return false;
        }
        return true;
    }
};

Implement strStr(Leetcode #28)

题目描述

Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example :

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

解题思路

本身使用暴力是很容易的，我们在暴力的基础上升级为KMP算法。

解题方案

暴力(不匹配则回退，i-j为返回值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty())
            return 0;
        int n=haystack.size(),m=needle.size();
        int i=0,j=0;
        while(i!=n && j!=m){
            if(haystack[i]==needle[j])
                ++i,++j;
            else
                i-=j-1,j=0;
        }
        return (i-j>n-m)?-1:i-j;
    }
};

KMP(非常好记忆，是模式串的自匹配，只是在字符类型较多时效率未必高）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0 ) 
            return 0;
        if(needle.size()>haystack.size()) 
            return -1;
        vector<int> next=nextTable(needle);
        int i=0,n=haystack.size();
        int j=0,m=needle.size();
        while(i<n && j<m ){
            if(j<0 || haystack[i]==needle[j]) 
                ++i,++j;
            else 
                j=next[j];
        }
        return (i-j>n-m)?-1:i-j;
    }
private:
    vector<int> nextTable(string needle){
        int j=0,m=needle.size();
        int t=-1;
        vector<int> next(m,-1);
        next[0]=-1;
        while(j<m-1){
            if(t<0 || needle[j]==needle[t]){
                ++j,++t;
                next[j]=(needle[j]!=needle[t])?t:next[t];
            }
            else
                t=next[t];
        }
        return next;
    }
};

String to Integer(Leetcode #8)

题目描述

Implement atoi which converts a string to an integer.

解题思路

利用find_first_of找到第一个不为空的字符，然后判断其是否为+-，若是则设定正负。然后遍历字符串，利用isDigit作为while退出条件。若退出时字符串尚未结束则说明当前存在非法字符。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int StrToInt(string str) {
        int base=0,sign=1;
        int i = str.find_first_not_of(" ");
        if(i==-1)
            return 0;
        if(str[i]=='+'||str[i]=='-')
            sign=str[i++]=='+'?1:-1;
        while(i!=str.size() && isdigit(str[i])){
            base=base*10+str[i++]-'0';
        }
        if(i!=str.size()) return 0;
        else return base*sign;
    }
};

Add Binary(Leetcode #67)

题目描述

Given two binary strings, return their sum (also a binary string).The input strings are both non-empty and contains only characters 1 or 0.
Example 1:

1
2
Input: a = "11", b = "1"
Output: "100"

Example 2:
1
2
Input: a = "1010", b = "1011"
Output: "10101"

解题思路

非常类似于之前做的高精度加法或者链表求和,与链表不同的是，我们这里利用str的operator+，将每一次的结果添加于res之后，最终翻转res。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string addBinary(string a, string b) {
        int m = a.size(), n = b.size();
        int i = m - 1, j = n - 1, carry = 0;
        string res;
        while (i >= 0 && j >= 0) {
            char sum = (a[i--] - '0') + (b[j--] - '0') + c;
            res += ('0' + (sum % 2));
            carry = (sum >= 2) ? 1 : 0;
        }
        while (i >= 0) {
            char sum = (a[i--] - '0') + c;
            res += ('0' + (sum % 2));
            carry = (sum >= 2) ? 1 : 0;
        }
        while (j >= 0) {
            char sum = (b[j--] - '0') + c;
            res += ('0' + (sum % 2));
            carry = (sum >= 2) ? 1 : 0;
        }
        if (carry)
            res += '1';
        reverse(res.begin(), res.end());
        return res;
    }
};

Longest Palindrome(Leetcode #409)

题目描述

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.This is case sensitive, for example “Aa” is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:

1
2
3
4
5
6
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

解题思路

若某个字母存在奇数次，则我们可以认为最大长度必须要减1，否则不必减1。我们将针对每一个字符遍历依次字符串，尽管遍历需要O（n)的时间，但由于字符种类已知，总开销依然是O（n）。此外，如果存在奇数，返回的结果是size-odds+1，原因在于单独的那一个可以放在最中间。

解题方案

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int longestPalindrome(string s) {
        int odds=0;
        for(char c='A';c<='z';++c)
            odds+=count(s.cbegin(),s.cend(),c)&1;
        return s.size()-odds+(odds>0);
    }
};

扩展（Longest Palindromic Subsequence）

题目描述

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example:

1
2
3
4
5
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

解题思路

这题与上一题不同的地方在于规定了必须是subsequence。本题使用动态规划求解较为方便。设dp[i][j]为字符str[i]、str[j]之间形成的子串所能构建的最长回文串，那么对于dp，存在状态转移方程为：

1
2
3
if str[i]==str[j] dp[i][j]=dp[i+1][j-1]+2;
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
dp[i][i]=1;

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int> > dp(s.size());
        for(auto& v:dp)
            v.resize(s.size());
        for(int i =s.size()-1;i!=-1;--i){
            dp[i][i]=1;
            for(int j=i+1;j!=s.size();++j){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][s.size()-1];
    }
    
};

扩展（Longest Palindromic Substring）

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
1
2
Input: "cbbd"
Output: "bb"

解题思路

两种做法。

  1. 若str存在n个元素，那么应当有2n-1个作为回文字符串中点的位置。我们遍历这些中点，求解这些中点所能形成的回文子串的最大长度。最后得到最终的中点及最大长度，使用substr。
  2. 动态规划，dp[i][j]表示str[i]到str[j]形成的子串是否为回文串。有状态转移方程为
    1
    2
    if(j==i+1 && str[i]==str[j]) dp[i][j]=1;
    while(j>i+1) dp[i][j]=(str[i]==str[j] && dp[i+1][j-1])

解题方案

扩张法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string longestPalindrome(string s) {
        //Expand around center
        int start = 0, maxlen=0;
        for (int i = 0; i != s.size(); ++i) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = max(len1, len2);
            if (len > maxlen) {
                start = i - (len - 1)/2;
                maxlen = len;
            }
        }
        return s.substr(start,maxlen);
    }
private:
    int expandAroundCenter(const string&s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left, ++right;
        }
        return right - left - 1;
    }
};

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string longestPalindrome(string s) {
        //use DP
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        int maxlen = 1, start = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < s.size(); ++j) {
                if (s[i] == s[j]) {
                    if (dp[i][j] =(j==i+1)?1: dp[i + 1][j - 1]) {
                        if (j - i + 1 > maxlen) {
                            start = i;
                            maxlen = j - i + 1;
                        }
                    }
                }
                else dp[i][j] = 0;
            }
        }
        return s.substr(start, maxlen);
    }
};

二叉搜索树的后序遍历序列

解题思路

递归式求解。首先找到数组的末尾元素，其必为根节点。然后向前找到第一个不大于根的元素，其必为左子树根节点。若左子树中存在大于根节点的元素则返回false，否则再次判断左右子树是否具备二叉搜索性质。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> v) {
        if(v.empty())
            return false;
        return aux(v,0,v.size()-1);
    }
private:
    bool aux(const vector<int> &v,int b,int e){
        if(b>=e)
            return true;
        int lr=e-1;
        while(lr>=b && v[lr]>v[e]) lr--;
        for(int i = b;i<=lr;++i)
            if(v[i]>v[e]) return false;
        return aux(v,b,lr) && aux(v,lr+1,e-1);
    }
};

二叉树中和为某一值的路径

解题思路

朴素深搜,值得注意的是某个节点检查完毕后需要pop_back。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int sum) {
        vector<vector<int> > res;
        vector<int> cur;
        aux(root,sum,cur,res);
        return res;
    }
private:
    void aux(TreeNode* root,int gap,vector<int> &cur,vector<vector<int> >& res){
        if(!root)
            return;
        cur.push_back(root->val);
        if(!root->left && !root->right)
            if(root->val==gap)
                res.push_back(cur);
        aux(root->left,gap-root->val,cur,res);
        aux(root->right,gap-root->val,cur,res);
        cur.pop_back();
    }
};

复杂链表的复制（剑指offer #35)

（在OJ exercise8中已经介绍）

二叉搜索树与双向链表（剑指offer #36)

解题思路

递归式地连接。先将左子树构造为双链表，然后连接左子与根节点，然后再将右子树构造为双链表。最终连接完毕，返回根节点，一路向左找到头即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    TreeNode* Convert(TreeNode* root){
        if(!root)
            return root;
        TreeNode* pre = nullptr;
        aux(root,pre);
        TreeNode* res = root;
        while(res->left)
            res=res->left;
        return res;
    }
private:
    void aux(TreeNode* cur,TreeNode* &pre){
        if(!cur)
            return;
        aux(cur->left,pre);
        cur->left=pre;
        if(pre)
            pre->right=cur;
        pre=cur;
        aux(cur->right,pre);
    }
};

字符串的排列

解题思路

递归式的解法，需要注意的式aux的string参数并非引用，因此每一次都需要复制，如果采用引用，则需要在aux的最后一行将str复原。（本解法针对重复元素亦有效）

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        sort(str.begin(),str.end());
        aux(str,0,res);
        return res;
    }
private:
    void aux(string str,int beg,vector<string>& res){
        if(beg>=str.size()-1){
            res.push_back(str);
            return;
        }
        for(int i=beg;i!=str.size();++i){
            if(i>beg && str[beg]==str[i]) continue;
            swap(str[i],str[beg]);
            aux(str,beg+1,res);
        }
    }
};