发表于 | 分类于

Reverse Words in a String

题目描述：

给定一个字符串，要求逆序字符串中的单词。

例子：

具体描述见LeetCode151

解题思路：

主要的思路是我们将字符串中的每个单词都逆序，然后整体全部逆序，这样就可以得到逆序单词的字符串序列了。需要注意的地方是我们需要判断边界和需要resize字符串的长度。

代码如下：

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:
    void reverseWords(string &s) {
        int i = 0;
        int j = 0;//用来记录字符串中非空的长度
        int l = 0;
        int length = s.size();
        int wordcount = 0;
        while(true){
            while(i < length && s[i] == ' ')i++;
            //过滤掉空格
            if (i == length) break;
            //如果已经到达末尾
            if (wordcount) s[j++] = ' ';
            l = j;
            while(i < length && s[i] != ' '){
                s[j] = s[i];
                i++;
                j++;
            }//l用来记录单词的起始位置
            reverseword(s, l, j - 1);
            //逆序单词
            wordcount++;
        }
        s.resize(j);
        reverseword(s, 0, j - 1);
    }
    //逆序函数用于逆序函数中从start到end位置的字符
    void reverseword(string& s, int start, int end){
        while(start < end){
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }
};

发表于 | 分类于

4Sum II

题目描述：

给定4个数字数组，要求分别从4个数组中各取一个数的组合中和为0的情况有多少种。

例子：

具体描述见[LeetCode454]

解题思路：

主要的思路是利用哈希表；我们取其中两个数组，然后利用其和为key，出现的次数为value构建哈希表；对剩下的两个数组也进行相同的操作；然后遍历第一个哈希表，在第二个哈希表中找到是否能够构成0的值；如果存在则对其次数进行乘积操作加到结果上。

代码如下：

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
class Solution {
public:
    void fillMap(vector<int> &A, vector<int> &B, map<int, int> &m){
        for (int i = 0; i < A.size(); i++){
            for (int j = 0; j < B.size(); j++){
                m[A[i] + B[j]]++;
            }
        }//和为key;出现次数为value
    }
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        map<int, int> m1;
        map<int, int> m2;
        
        fillMap(A, B, m1);
        fillMap(C, D, m2);
        int res = 0;
        
        for (auto it1 = m1.begin(); it1 != m1.end(); it1++){
            
            auto it2 = m2.find(-it1->first);
            //此处注意负号，即要求和为0
            if (it2 != m2.end()){
                res += it1->second * it2->second;
                //出现的次数的乘积
            }
        }
        return res;
    }
};

发表于 | 分类于

Repeated Substring Pattern

题目描述：

给定一个字符串，要求判断这个字符串能否由其子串的整数倍连接而成。

例子：

具体描述见LeetCode459

解题思路：

根据题意我们可以知道子串的长度最少是1，最大是字符串的1/2。所以我们从1开始遍历到总长度的1/2；然后判断每个长度是否是符合条件即可。

代码如下：

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 repeatedSubstringPattern(string s) {
        
        for (int i = 1; i <= s.size() / 2; i++){
            if (check(s.substr(0, i), s))
                return true;//取出开头的前i个字符作为pattern来判断
        }
        return false;
    }
    bool check(string pattern, string target){
        int size = pattern.size();
        int cur = 0;
        while(cur < target.size()){
            if (target.substr(cur, size) != pattern)
                return false;
            else
                cur = cur + size;
        }
        return true;
    }
};

发表于 | 分类于

Task Scheduler

题目描述：

给定一个计算机执行任务的数组(用’A’-‘Z’表示，且不必按照字母序执行)，和一个执行相同任务的间隔n,表示执行相同两个任务之间最少需要有n个时间间隔，一个时间间隔内只能执行一个任务。

例子：

具体描述见LeetCode621

解题思路：

这边的思路主要是逆序的思维；我们找到所有字符任务中出现最多次数的字符，假设为A有7个；我们对6个A进行任务排序的情况下，不管其他字符是什么情况，我们最少需要的间隔是6 * n个字符；而后将剩下的最后一个A进行排序，因为其他的字符可能也是7个，所以需要找到剩下字符也是7个的字符个数将其加到最后结果中即可。这边需要注意的是，如果间隔是0的情况下：举个例子[“A”,”A”,”A”,”B”,”B”,”B”]，间隔为0，根据以上计算过程得到的4；但是实际上需要的是6个，即再怎么排序得到的结果不会少于所有任务数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int count = 0;
        unordered_map<char, int> hash;
        for (auto e: tasks){
            hash[e]++;
            count = max(count, hash[e]);
        }//找到出现最多的任务数和得到哈希表
        int res = (count - 1) * (n + 1);
        //对前count-1个字符进行排列
        for (auto i : hash){
            if (i.second == count) res++;
        }//找到出现字符数也是count的字符
        return max((int)tasks.size(), res);
    }
};

发表于 | 分类于

Reverse String II

题目描述：

给定一个字符串和数字k，要求逆序字符串中每2k字符的前k个，如果末尾剩下的字符超过k个，只逆序前k个；如果小于k个，则将其全部逆序。

例子：

具体描述见LeetCode541

解题思路：

本题的主要需要注意的地方在于如何判断当前是否到2k字符的末尾和如何处理剩下的字符。这边主要使用了cur作为遍历的index；遍历之间判断加上2k是否会超过字符的范围；然后在到达末尾的时候，判断末尾字符串的长度；根据不同的情况对字符进行逆序操作。其中定义了一个逆序函数用于每一步的逆序。

代码如下：

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
class Solution {
public:
    string reverseStr(string s, int k) {
        int cur = 0;
        while(cur + 2 * k <= s.size()){
            reverse(s, cur, cur + k - 1);
            cur += 2 * k; 
        }
        int left = s.size() - cur;
        //判断剩余字符的长度
        if (left < k) reverse(s, cur, s.size() - 1);
        //小于k个的情况
        if (left >= k) reverse(s, cur, cur + k - 1);
        //如果大于k个小于2k个
        return s;
    }
    void reverse(string& s, int start, int end){
        while(start < end){
            swap(s[start], s[end]);//交换函数
            start++;
            end--;
        }
    }
    
};

发表于 | 分类于

Minimum Time Difference

题目描述：

给定一个数组中包含时间的字符串，要求找到字符串中时间差最短的差值。

例子：

具体描述见LeetCode539

解题思路：

首先我们需要将字符串中的时间转化为分钟数；主要用到了substr和stoi函数；然后对转化后的数组进行排序；其中需要注意的地方是我们需要考虑数组中的最小值和最大值之间的差值，因为00:00和23:59之间的差值反而小；所以需要特别注意这两个数之间的差值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> res;
        
        for (int i = 0; i < timePoints.size(); i++){
            int t = stoi(timePoints[i].substr(0, 2)) * 60 + stoi(timePoints[i].substr(3, 2));
            res.push_back(t);
        }//转化为数字
        sort(res.begin(), res.end());
        //排序
        int mindiff = res[0] + 24 * 60 - res[res.size() - 1];
        //头和尾的差值
        for (int i = 1; i < res.size(); i++){
            int diff = res[i] - res[i - 1];
            if (diff < mindiff)
                mindiff = diff;
        }//找到最小值
        return mindiff;
    }
};

发表于 | 分类于

Add One Row to Tree

题目描述：

给定一棵树的头结点，和插入行的深度depth和值value；要求在深度为depth的位置插入一行值为value的节点。

例子：

具体描述见LeetCode623

解题思路：

第一种想法是非递归的思路：我们可以通过按行遍历树的节点；然后找到需要插入节点的那一行的所有节点；然后遍历这些节点，不断增加新的节点和改变指针的指向即可。

代码如下：

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
42
43
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            TreeNode* res = new TreeNode(v);
            res->left = root;
            return res;
        }//当深度为1的情况直接新增一个节点，然后将根节点连接到新节点的左子指针
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(root);
        while(!q1.empty() && d != 2){
            while(!q1.empty()){
                if (q1.front()->left){
                    q2.push(q1.front()->left);
                }
                if (q1.front()->right){
                    q2.push(q1.front()->right);
                }
                q1.pop();
            }
            queue<TreeNode*> tmp;
            tmp = q2;
            q2 = q1;
            q1 = tmp;
            d--;
        }//以上通过两个队列找到需要插入节点的那一行
        while(!q1.empty()){
            TreeNode* node = q1.front();
            TreeNode* left = node->left;
            TreeNode* right = node->right;
            TreeNode* new_left = new TreeNode(v);
            TreeNode* new_right = new TreeNode(v);
            node->left = new_left;
            new_left->left = left;
            node->right = new_right;
            new_right->right = right;
            q1.pop();
        }//遍历这一行中的所有节点，不断增加新的节点和改变指针的指向即可
        return root;
        
    }
};

递归思路：

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
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            TreeNode* res = new TreeNode(v);
            res->left = root;
            return res;
        }
        TreeNode* res = helper(root, v, d);
        return res;
    }
    TreeNode* helper(TreeNode* root, int value, int depth){
        if (!root) return NULL;
        if (depth == 2){
            TreeNode* new_left = new TreeNode(value);
            TreeNode* new_right = new TreeNode(value);
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            root->left = new_left;
            new_left->left = left;
            root->right = new_right;
            new_right->right = right;
            return root;
        }//如果深度是2，直接增加节点然后改变指针指向
        else{
            root->left = helper(root->left, value, depth - 1);
            root->right = helper(root->right, value, depth - 1);
            //如果是深度是非目标行，继续往下一层遍历，记得记录指针的指向和深度的改变
            return root;
        }
    }
};

发表于 | 分类于

Find All Anagrams in a String

题目描述：

给定一个源字符串s,和一个目标字符串t,要求找到s中所有的片段包含t的起始位置。

例子：

具体描述见LeetCode438

解题思路：

定义源和目标字符串的哈希表，因为只包含26个字母可以直接使用vector来保存字符和对应的数量；起始代码直接判断2个字符串的长度；然后遍历较短字符，保存下字符和对应的数量；这边需要注意如果开头就想同需要把0push；然后遍历长字符的字符，每增加一个字符，需要删除上一个字符对应的数量；然后进行判断是否相等。这边其实是维持了一个窗口，记录窗口中的字符的数量，是字符串中的常见做法，需要谨记！。

代码如下：

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:
    vector<int> findAnagrams(string s, string p) {
        vector<int> sv(26, 0);
        vector<int> pv(26, 0);
        vector<int> res;
        if (p.size() > s.size())
            return res;
        
        for (int i = 0; i < p.size(); i++){
            sv[s[i] - 'a']++;
            pv[p[i] - 'a']++;
        }//遍历较短字符串
        if (sv == pv)
            res.push_back(0);
        //起始位置
        for (int i = p.size(); i < s.size(); i++){
            sv[s[i] - 'a']++;
            sv[s[i - p.size()] - 'a']--;
            //遍历新的位置
            if (sv == pv)
                res.push_back(i - p.size() + 1);
        }
        return res;
        
    }
};

发表于 | 分类于

Count Prime

题目描述：

例子：

具体描述见LeetCode204

解题思路：

主要的思路是我们构建一个bool型的数组，假设全为true。在遍历到第i个数的时候，我们先判断这个数是否是小于sqrt(n)的结果，是的情况下，我们对这个找到的素数的整数倍位置都置为false；如果是true的情况下，在先前的数中已经判断过了所以无需再次判断。

代码如下：

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:
    int countPrimes(int n) {
    vector<bool> isPrime(n, true);
    
    int primeCount = 0;
    int upperBound = sqrt(n);
    
    for (int i = 2; i < n; i++) {  //Start from 2 since 1 * j == j, all the following numbers will be affected
        if (isPrime[i-1]) {
            primeCount++;
            
            //When i > upper, i(bigger) * j(smaller) has already been checked, where i(bigger) == j(old) and i(smaller) == j(new)
            //Eg. n == 11, 2 * 5 == 10 has been checked when i == 2 and j == 5, so when i == 5 > 3, no need to check 5 * 2 where i == 5 and j == 2.
            if (i > upperBound)
                continue;
                
            for (int j = i; i * j < n; j++) {   //j >= i, so that i(bigger) * j(smaller) has already been checked in previous loops
                isPrime[i*j - 1] = false;
            }
        }
    }
    
    return primeCount;
    }
};

发表于 | 分类于

Number of Segments in a String

题目描述：

给定一个字符串，要求返回该字符串中的单词的个数。

例子：

具体描述见LeetCode434

解题思路：

本题主要的思路是如何抓住说一个单词的确定情况，我们这边的想法是如果当前字符是空格，切前一个字符非空即为一个单词。但是对于末尾的单词而言；我们无法使用这个规则，所以取巧的方法是，我们在字符串的末尾加上一个空格，这样整个字符串的所有单词都可以使用这个规则来判断了。

代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        s.push_back(' ');
        for(int i = 1; i < s.size(); ++i)
          if(s[i] == ' ' && s[i-1] != ' ') ++res;
        return res;
    }
};