发表于 | 分类于

Can Place Flowers

题目描述：

给定一个数组，数组中1表示该位置栽花；0则代表没有。则要求返回该数组是否能种n株花，在花的栽种间隔为1的情况下。

例子：

具体描述看LeetCode605

解题思路：

本题中的主要难点有两个(1)0的个数和栽种花的数量的关系(2)如何处理好数组头部和尾部的情况和全0的情况。代码中先设置的c=1是为了处理开头为0的情况；在循环的外部是为了处理尾部结尾为0的情况。因为在开头为0和结尾为0的情况，0的个数和栽花数量的关系较为特殊。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int c = 1;
        int m = 0;
        for (auto i : flowerbed){
            if (i == 0){
                c++;
            }else{
                m += (c - 1) / 2;
                c = 0;
            }
        }
        c++;
        m += (c - 1) / 2;
        return m >= n;
    }
};

发表于 | 分类于

Basic Calculator

题目描述：

具体描述可以看LeetCode227

解题思路：

代码如下：

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
class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        char sign = '+';
        int tmp = 0;
        int res = 0;
        for (int i = 0; i < s.size(); i++){
            if (isdigit(s[i]))
                tmp = tmp * 10 + s[i] - '0';
            if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size() - 1){
                if (sign == '+')
                    stk.push(tmp);
                else if (sign == '-')
                    stk.push(-tmp);
                else{
                    int num;
                    if (sign == '*')
                        num = stk.top() * tmp;
                    else
                        num = stk.top() / tmp;
                    stk.pop();
                    stk.push(num);
                }
                sign = s[i];
                tmp = 0;
            }
        }
        while(!stk.empty()){
            res += stk.top();
            stk.pop();
        }  
        return res;
        
    }
};

发表于 | 分类于

Reverse Words in a String

题目描述：

给定一个字符串，其中包含着单词和空格；要求原地逆序字符串中的每个单词。

例子：

具体描述看LeetCode557

解题思路：

解题的想法很直接，我们定义一个函数用于逆序字符串中的单词，在主函数中找到需要逆序的字符起始位置和结束位置即可。

代码如下：

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
class Solution {
public:
    string reverseWords(string s) {
        int cur = 0;
        int start = 0;
        while(cur < s.size()){
            while(cur < s.size() && s[cur] == ' ')cur++;
            start = cur;
            //找到非空字符的起始位置
            while(cur < s.size() && s[cur] != ' ')cur++;
            //非空的结束位置
            reverseword(s, start, cur - 1);
            //逆序函数
        }
        return s;
        
    }
    void reverseword(string& s, int start, int end){
    //逆序字符串中的一部分字符
        while(start < end){
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }
};

发表于 | 分类于

Permutation In String

题目描述：

给定两个字符串s1和s2要求判断s2中是否包含着s1的排列组合子串。

例子：

具体描述见LeetCode567

解题思路：

本题中主要的思路是如何判断其存在排列组合的子串。这边主要利用了数组来保存字符串的信息。在遍历s2的子串过程中不断判断和s1的数组信息是否相同即可。需要注意的是在遍历s2的时候我们需要删除被遗弃的字符的信息，增加遍历字符的信息。

代码如下：

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:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size())
            return false;
            //如果s1要长于s2即不可能存在
        vector<int> v1(26, 0);
        vector<int> v2(26, 0);
        //用两个数组保存信息
        for (int i = 0; i < s1.size(); i++){
            v1[s1[i] - 'a']++;
        }
        //保存s1的信息
        for (int j = 0; j < s1.size(); j++){
            v2[s2[j] - 'a']++;
        }
        //遍历和s1相同长度的子串信息
        if (v1 == v2) return true;
        //相同的情况下直接返回
        for (int i = s1.size(); i < s2.size(); i++){
            v2[s2[i] - 'a']++;
            v2[s2[i - s1.size()] - 'a']--;
            //移位改变当前数组中的信息
            if (v1 == v2)
                return true;
            //判断是否相等
        }
        return false;
        
    }
};

发表于 | 分类于

In The Same Line

题目描述：

给定一组字符串，判断每个字符串中的字符是否在键盘上的同一行。

例子：

具体描述看LeetCode500

解题思路：

构建每一行键盘的哈希表，然后对每个字符串中的字符分别进行判断即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> res;
        set<char> hash1 = {'q','w','e','r','t','y','u','i','o','p','Q','W','E','R','T','Y','U','I','O','P'};
        set<char> hash2 = {'a','s','d','f','g','h','j','k','l','A','S','D','F','G','H','J','K','L'};
        set<char> hash3 = {'z','x','c','v','b','n','m','Z','X','C','V','B','N','M'};
        for (int i = 0; i < words.size(); i++){
            if (allIn(hash1, words[i]) || allIn(hash2, words[i]) ||allIn(hash3, words[i]))
                res.push_back(words[i]);
        }
        return res;
        
    }
    bool allIn(set<char>hash, string str){
        for(int i = 0; i < str.size(); i++){
            if (hash.find(str[i]) == hash.end())
                return false;
        }
        return true;
    }
};

发表于 | 分类于

Is Subsuquence

题目描述：

给定两个字符串，判断字符串之间是否存在子串关系

例子：

具体描述见LeetCode392

解题思路：

遍历源字符串的每个位置判断与目标字符串字符的关系；相同的情况位置加1，如果不相等的情况则不断循环到下一次字符相同的位置。需要注意的是在循环的过程中如果已经到达源字符串的末尾则直接返回false。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0;
        
        for (int j = 0; j < s.size(); j++){
            while(i < t.size() && t[i] != s[j]){
                i++;
            }
            if (i == t.size()) return false;
            i++;
        }
        return true;
        
    }
};

发表于 | 分类于

Intersection Of Array

题目描述：

给定两个数组，找到两个数组中数字的交集

例子：

见LeetCode349

解题思路：

我们首先对第一个数组进行构建哈希表，然后遍历第二个数组，如果数字在哈希表中，将其保存到结果中，并将该值从哈希表中删除即可

代码如下：

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<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> hash;
        vector<int> res;
        for (int i = 0; i < nums1.size(); i++){
            if (hash.find(nums1[i]) == hash.end()){
                hash.insert({nums1[i]});
                //对第一个数组构建哈希表
            }
        }
        for (int j = 0; j < nums2.size(); j++){
            if (hash.find(nums2[j]) != hash.end()){
                hash.erase(nums2[j]);
                res.push_back(nums2[j]);
                //遍历第二个数组中的数
            }
        }
        return res;
    }
};

发表于 | 分类于

Reverse Vowels

题目描述：

逆序给定字符串中的元音字母

例子：

具体描述看LeetCode345

解题思路：

我们利用vector保存下字符串中是元音的字符的对应位置。然后对字符串中的这些字符进行逆序即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string reverseVowels(string s) {
        set<char> hash = {'a','e','i','o','u','A','E','I','O','U'};
        //记录元音字符集合
        vector<int> vec = {};
        //保存下元音字符的位置
        for (int i = 0; i < s.size(); i++){
            if (hash.find(s[i]) != hash.end()){
                vec.push_back(i);
            }
        }
        for (int j = 0; j < vec.size() / 2; j++){
            swap(s[vec[j]], s[vec[vec.size() - j - 1]]);
        }
        return s;
    }
};

发表于 | 分类于

Reverse String

题目描述：

给定字符串返回其逆序后的结果

例子：

具体描述看LeetCode344

解题思路：

利用swap函数交换对应位置上的字符即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string reverseString(string s) {
        string res = s;
        int length = s.size();
        for (int i = 0; i < length / 2; i++){
            swap(res[i], res[length - i - 1]);
        }
        return res;
    }
};

发表于 | 分类于

Is Isomorphic

题目描述：

给定两个字符串，判断这两个字符对应位置是否有一一对应关系。我们认为egg和add是一一对应的关系;foo和bar就不是。

例子：

具体描述看LeetCode205

解题思路：

我们利用哈希表来保存字符串之间的对应关系，在遍历过程中判断字符是否已经出现在哈希表中，如果和已知的对应关系不匹配即返回false。需要注意的是字符串如果长度不一致即直接返回false;另外一一对应的关系是相互的，所以我们需要判断(t,s)和(s,t)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        return judge(s, t) && judge(t, s);
    }
    bool judge(string s, string t){
        map<char, char> hash;
        if (s.size() != t.size())
            return false;
            //如果两个字符串长度不相等直接返回false
        for (int i = 0; i < s.size(); i++){
            if (hash.find(s[i]) == hash.end()){
                hash.insert({s[i], t[i]});
                //保存对应的字符对应关系
            }else if (hash[s[i]] != t[i]){
                return false;
            }
        }
        return true;
    }
};