发表于 | 分类于

Multiply Strings

题目描述：

给定两个数字字符串，要求计算其数字乘积后的结果。

例子：

具体描述见LeetCode43

解题思路：

首先如果字符串中有一个是0的情况直接返回0；其次，因为我们是从低位算起，所以我们需要逆序原有的字符串；然后需要定义几个变量:(1)进位变量carry(2)表示当前第一个乘数的遍历位置step(3)position表示第一位乘数中取一位和第二个乘数进行计算过程中所在位的位置；在每次从第一个数取一位和第二个乘数进行乘积计算完成时；需要判断是否进位；注意在计算字符乘积的过程中进位需要每次相乘结果上加上。

代码如下：

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
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int carry =0;
        int step = 0;
        string res = "";
        for (int i = 0; i < num1.size(); i++){
            int position = step;
            for (int j = 0; j < num2.size(); j++){
                int num = (num1[i] - '0') * (num2[j] - '0') + carry;
                if (position < res.size()){
                    num += res[position] - '0';
                    res[position] = num % 10 + '0';
                }else{
                    res.append(1, (num % 10) + '0');
                }//以上这一步非常重要
                carry = num / 10;
                position++;
            }
            if (carry > 0){
                res.append(1, carry + '0');
            }
            step++;
            carry = 0;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

发表于 | 分类于

Reconstruct Original Digits from English

题目描述：

给定一个字符串，其中包含着0~9的英文字符，要求返回其原始的数字字符串。

例子：

具体描述见LeetCode423

解题思路：

主要的思路是在于不同的数字的对应的英文字符串中有各自特殊的字符，比如zero中z字符在其他数字中都不存在。利用这个特点我们可以一一找到各自的数字。思路是我们构建26个字符的统计表；各个数字对应的英文字符串；各个数字以及各个数字对应的特殊的英文字符。然后遍历每个数字，将数字对应的英文字符串的所有字符在统计表中减去；然后根据对应特殊字符的数量来将字符加到结果字符串中即可。

代码如下：

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 originalDigits(string s) {
        vector<string> word = {"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
        vector<char> alpha = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> nums = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        vector<int> counts(26, 0);
        string res;
        for (int i = 0; i < s.size(); i++) counts[s[i] - 'a']++;
        for(int i = 0; i < 10; i++){
            int count = counts[alpha[i] - 'a'];
            for(int j = 0; j < word[i].size(); j++){
                counts[word[i][j] - 'a'] -= count;
            }
            while(count > 0){
                res += to_string(nums[i]);
                count--;
            }
        }
        sort(res.begin(), res.end());
        return res;
        
    }
};

发表于 | 分类于

Longest Palindrome

题目描述：

给定一个字符串，要求得到利用这个字符串的所有字符能够构成的最长的回文字符串的长度。

例子：

具体描述看LeetCode409

解题思路：

我们可以构建这个字符串的哈希表，然后根据每个字符数量的奇偶数来得到回文字符的长度。其中需要注意的地方是，如果有奇数个的字符的情况下，我们需要再回文字符的最终长度上加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
25
26
27
28
29
30
class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> hash;
        int res = 0;
        int odd = 0;
        for (int i = 0; i < s.size(); i++){
            if (hash.find(s[i]) == hash.end()){
                hash.insert({s[i], 1});
            }else{
                hash[s[i]]++;
            }
        }//构建字符串的哈希表
        map<char, int>:: iterator it = hash.begin();
        while(it != hash.end()){
            if (it->second % 2 == 0){
                res += it->second;
                it++;
                //偶数的情况下直接将长度加到结果上
            }else{
                res += it->second - 1;
                odd++;
                it++;
                //奇数的情况下，加上减一后的偶数个，并将标志是否有奇数个字符的标志加1
            }
        }
        return (odd > 0) ? res + 1 : res;
        //最终长度加1
    }
};

发表于 | 分类于

Valid Triangle Number

题目描述：

给定一个数组，要求找到数组中所有组合能够构成三角形的边的组合的个数。

例子：

具体描述看LeetCode611

解题思路：

一开始的思路是想要用回溯的方式找到所有的组合然后判断每个组合的合法性来计算所有的组合；但是TLE。后面发现其实我们可以将数组排序后利用排序的性质来找到所有合法的三角形边。主要的方法是外面设置两个循环找到三角形的两条边，寻找第三条边的时候，我们从第二条边的下一个数开始遍历，找到第一个大于等于前两条边和的位置和第二条边的下一个数的位置之间的所有数都满足构成三角形的情况。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res = 0;
        if (nums.size() < 3) return res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i++){
            if (nums[i] == 0) continue;
            for (int j = i + 1; j < nums.size() - 1; j++){
                int temp = nums[i] + nums[j];
                int flag = j + 1;
                while(flag < nums.size() && nums[flag] < temp){
                    flag++;
                }//找到大于等于前两条边和的第一个位置。
                res += (flag - (j + 1));
            }
        }
        return res;
    }
};

发表于 | 分类于

String Iterator

题目描述：

要求设计一个字符串迭代类，能够实现next和hasNext两个函数的功能。

例子：

具体描述看LeetCode604

解题思路：

本题中主要用到的函数是istringstream。我们通过将字符串变成字符串流；然后根据>>char>>count这样可以从字符串中读取到字符和对应出现的次数。然后根据题目要求可以很快的实现hasNext和next函数。

代码如下：

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
class StringIterator {
    istringstream iss;
    int count = 0;
    char c = 0;
public:
    StringIterator(string compressedString) {
        iss = istringstream(compressedString);
    }
    
    char next() {
        if (hasNext()){
            count--;
            return c;
        }else{
            return ' ';
        }
    }
    
    bool hasNext() {
        if (count == 0)
            iss >> c >> count;
        return count > 0;
    }
};
/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator obj = new StringIterator(compressedString);
 * char param_1 = obj.next();
 * bool param_2 = obj.hasNext();
 */

发表于 | 分类于

Merge Two Binary Trees

题目描述：

给定两棵二叉树的头节点，要求将两个树整合后返回新树的头结点。

例子：

具体描述见LeetCode617

解题思路：

本题的思路非常的直接，使用递归的方式来解决问题。其中需要判断是否有空节点的情况和都是非空节点的情况分类处理即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1 || !t2) return !t1 ? t2 : t1;
        else if (t1 && t2){
            t1->val += t2->val;
            t1->left = mergeTrees(t1->left, t2->left);
            t1->right = mergeTrees(t1->right, t2->right);
            return t1;
        }
        
    }
};

发表于 | 分类于

Multiply Strings

题目描述：

给定两个代表数字的字符串，要求计算其乘积的结果，返回其字符串形式。

例子：

具体描述见LeetCode43

解题思路：

代码如下：

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
36
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        //如果乘数中有任意一个是0的情况下直接返回0即可
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //逆序字符串从低位开始处理
        int carry =0;
        int step = 0;
        string res = "";
        for (int i = 0; i < num1.size(); i++){
            int position = step;
            for (int j = 0; j < num2.size(); j++){
                int num = (num1[i] - '0') * (num2[j] - '0') + carry;
                if (position < res.size()){
                    num += res[position] - '0';
                    res[position] = num % 10 + '0';
                }else{
                    res.append(1, (num % 10) + '0');
                }
                carry = num / 10;
                position++;
            }
            if (carry > 0){
                res.append(1, carry + '0');
            }
            step++;
            carry = 0;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

发表于 | 分类于

Letter Combinations

题目描述：

给定手机键盘上的数字字符的字符串，要求输出所有可能由该数字字符串得到英文字符串。

例子：

具体描述看LeetCode17

解题思路：

主要的思路是递归的方式。我们针对每一位的数字字符进行遍历，然后不断递归到下一层得到字符串的组合。其中需要注意的是我们每次加上字符后需要回溯一步。

代码如下：

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
36
37
38
39
40
41
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string str;
        vector<string> res;
        map<char, vector<char>> hash;
        if (digits == "") return res;
        hash.insert({'2',{'a', 'b', 'c'}});
        hash.insert({'3',{'d', 'e', 'f'}});
        hash.insert({'4',{'g', 'h', 'i'}});
        hash.insert({'5',{'j', 'k', 'l'}});
        hash.insert({'6',{'m', 'n', 'o'}});
        hash.insert({'7',{'p', 'q', 'r', 's'}});
        hash.insert({'8',{'t', 'u', 'v'}});
        hash.insert({'9',{'w', 'x', 'y', 'z'}});
        hash.insert({'0',{' '}});
        //构建各个数字对应字符的哈希表
        permutation(res, str, hash, 0, digits.size(), digits);
        //调用递归函数来得到所有的组合
        //其中res是保存组合结果；str是当前的组合结果；
        //begin和end表示要找到源字符begin到end的位置的所有组合字符
        return res;
        
    }
    void permutation(vector<string>& res, string& str, map<char, vector<char>>& hash, int begin, int end, string digits){
        if (begin >= end){
            res.push_back(str);
            return;
            //begin大于等于end的情况说明到达尾部，将结果保存即可
        }
        for (int i = 0; i < hash[digits[begin]].size(); i++){
        //对当前的begin位置的所有可能进行遍历
            str = str + hash[digits[begin]][i];
            //将每种可能加到str字符串上
            permutation(res, str, hash, begin + 1, end, digits);
            //进行下一层的遍历，注意此时的begin加1
            str.pop_back();
            //另外需要回溯一步
        }
    }
};

发表于 | 分类于

Longest Common Prefix

题目描述：

给定一组字符串，找到这组字符串中最长的公共前缀。

例子：

具体描述可以看LeetCode14

解题思路：

首先最长公共前缀肯定是小于等于所有字符串中的最短长度的；所以先找到字符串数组中的最短长度；然后是一个一个的判断在这个长度范围内是否所有的字符串都是以该字符为前缀即可。

代码如下：

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
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        //如果是空字符串数组直接返回空
        string res = "";
        int min_length = INT_MAX;
        for (auto &s : strs){
            min_length = min(min_length, (int)s.size());
        }//找到所有字符串中最短的长度
        for (int i = 0; i < min_length; i++){
            char prefix = strs[0][i];
            bool flag = true;
            //提取第i位的字符
            for (auto &s : strs){
                if (s[i] != prefix){
                    flag = false;
                    break;
                }
            }//判断所有的字符串是否都含有该字符
            if (flag == false) 
                return res;
                //标签为false的情况直接返回
            else {
                res = res + prefix;
                //否则加上该位字符
            }
        }
        return res;
    }
};

发表于 | 分类于

Construct String from Binary Tree

题目描述：

给定一棵树的头节点按照规则重建该树的字符串形式。

例子：

具体描述可以看LeetCode606

解题思路：

主要的解题想法是递归。当然在本题中需要注意的是，左子树是空的情况和右子树是空的情况需要不同的处理。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        if (!t) return "";
        string root = to_string(t->val);
        string left = tree2str(t->left);
        string right = tree2str(t->right);
        
        if (left == "" && right == "") return root;
        else if (right == "") return root + "(" + left + ")";
        else return root + "(" + left + ")" + "(" + right + ")";
        
    }
};