发表于 | 分类于

Find Repeated DNA Sequences

题目描述：

定义长度为10的DNA片段，找到给定字符串中所有出现超过1次的DNA字符串片段。

例子：

具体描述可以看LeetCode187

解题思路：

我们用一个哈希表保存该字符串是否出现，用一个哈希表来表示是否已经保存到结果中即可。

代码如下：

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> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() <= 10) return res;
        set<string> hash;
        //保存该字符串是否已经出现
        set<string> table;
        //保存该字符串是否已经保存到结果res中
        for (int i = 0; i <= s.size() - 10; i++){
            if (hash.find(s.substr(i, 10)) == hash.end()){
                hash.insert(s.substr(i, 10));
            }else{
                if (table.find(s.substr(i, 10)) == table.end()){
                    table.insert(s.substr(i, 10));
                    res.push_back(s.substr(i, 10));
                }
            }
        }
        return res;
    }
};

发表于 | 分类于

Simplify Path

题目描述：

以字符串形式给定一个计算机中的路径，利用计算机中路径的知识将其简化。其中主要的规则有:
..表示进行上层目录
.表示当前目录

例子：

见LeetCode71

解题思路：

主要的难点在于我们如何将字符串按照特定字符隔开。这边使用的是stringstream来将字符串分隔。其中需要对..和.这两种情况进行讨论。只有当保存路径的vector非空并且分隔的字符串不是..的情况我们才将分隔的字符串保存到vector。然后我们将vector中字符串用’/‘连接即可。最后需要注意的是我们如果得到的vector是空的情况下，直接返回’/‘即可。

代码如下：

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 simplifyPath(string path) {
        string res;
        string tmp;
        vector<string> vec;
        stringstream ss(path);
        //字符串流
        while(getline(ss, tmp, '/')){
        //根据'/'来对字符串进行分割
            if (tmp == "" || tmp == ".")continue;
            if (tmp == ".." && !vec.empty()){
                vec.pop_back();
                //表示进入上一层
            }
            else if (tmp != "..") vec.push_back(tmp);
        }
        for (auto i : vec)
            res += "/" + i;
            //连接
        return vec.empty() ?  "/" : res;
    }
};

发表于 | 分类于

Last Word Length

题目描述：

给定一个字符串，找到字符串中最后一个单词的长度。

例子：

具体描述见LeetCode58

解题思路：

本题主要的难点在于各种边界条件的判断。首先是字符串是空的情况；其次字符串结尾是空格的情况；找到非空格字符后我们需要判断是不是已经到达字符的首位；最后是找到结尾单词的起始位置。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLastWord(string s) {
        if (s.size() == 0 || s == " ") return 0;
        //字符串为空的情况
        int end = s.size() - 1;
        while(end >= 0 && s[end] == ' ') end--;
        //先找到结尾开始的非空字符
        if (end == -1) return 0; 
        //如果整个字符为空返回0
        int left = end;
        while(end >= 0 &&s[end] != ' ') end--;
        //找到单词的另外一侧
        return left - end;
        
    }
};

发表于 | 分类于

Group String

题目描述：

给定一组字符串序列，将含有相同字符的字符串进行分组。我们以”eat”和”ate”是同一组字符串

例子：

见LeetCode49

解题思路：

我们通过对vector中字符串进行构建哈希表，利用该哈希表作为key，字符串作为value来进行查找和匹配；而后对最终哈希表中的所有value进行保存即为分组的结果。

代码如下：

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<map<char, int>, vector<string>> hash;
        vector<vector<string>> res;
        map<char, int> str_map;
        for (int i = 0; i < strs.size(); i++){
            str_map = generate(strs[i]);
            //对每个字符串产生哈希表
            if (hash.find(str_map) == hash.end()){
                vector<string> tmp = {strs[i]};
                hash.insert({str_map, tmp});
                //如果结果哈希表中还未出现
            }else{
                hash[str_map].push_back(strs[i]);
                //如果已经出现
            }
        }
        map<map<char, int>, vector<string>> :: iterator it = hash.begin();
        while(it != hash.end()){
            res.push_back(it->second);
            it++;
            //将结果哈希表中的value进行保存即为分组结果
        }
        return res;
    }
    map<char, int> generate(string str){
    //对字符串进行构建哈希表操作
        map<char, int> hash;
        for (int i = 0; i < str.size(); i++){
            if (hash.find(str[i]) == hash.end()){
                hash.insert({str[i], 1});
            }else{
                hash[str[i]]++;
            }
        }
        return hash;
    }
};

发表于 | 分类于

Count And Say

题目描述：

给定一个数字n,找到按照如下规律的第n个字符串。
1: 11 即1个1
2: 21 即2个1
3: 1211 即1个2两个1
4: 111221 即1个1，1个2，2个1

例子：

具体描述看LeetCode38

解题思路：

通过观察规律我们知道，我们需要定义一个函数，输入为上一轮的结果，输出为当前轮的结果。然后将当前轮的结果作为下一轮的输入不断循环即可。

代码如下：

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:
    string countAndSay(int n) {
        string start = to_string(1);
        if (n == 1) return start;
        string result;
        while(n > 1){
            result = helper(start);
            //得到当前轮的结果
            start = result;
            //将结果作为下一轮的输入
            n--;
        }
        return result;
        
    }
    string helper(string s){
    //用来产生下一轮的字符串
        string res;
        int index = 0;
        while(index < s.size()){
            int count = 1;
            while(index + 1 < s.size() && s[index + 1] == s[index]){
                index++;
                count++;
            }
            //这个循环找到有多少个相同的字符
            string tmp = to_string(count) + s[index];
            index++;
            res += tmp;
            //将字符串连接
        }
        return res;
    }
};

发表于 | 分类于

Find First Subsequence

题目描述：

给定一个源字符串和目标字符串，找到源字符串中第一次出现目标字符串出现的位置。

例子：

具体描述见LeetCode28

解题思路：

主要的想法在于我们在遍历字符串的过程中如何判断当前位置是否出现目标字符串。这边用的是substr函数将字符串中的和目标字符串相同长度的子串剪切用于判断是否相同即可。另外需要注意的是边界条件的判断。空串以及字符串长度的判断。

代码如下：

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 (haystack == needle) return 0;
        if (haystack == "") return -1;
        if (haystack.size() < needle.size()) return -1;
        //以上三种情况直接返回即可
        for (int i = 0; i <= haystack.size() - needle.size(); i++){
            if (haystack.substr(i, needle.size()) == needle)
            //遍历过程中对每个位置目标子串长度进行判断
                return i;
        }
        return -1;
    }
    
};

发表于 | 分类于

Merge Lists

题目描述1：

给定两个有序链表的头节点，要求返回将这两个链表合并后的头结点。

例子：

具体描述看LeetCode21

解题思路：

代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head1 = l1;
        ListNode* head2 = l2;
        if(head1 == NULL || head2 == NULL)
            return head1 == NULL ? head2 : head1;
        // 只要一个为空就返回非空的那个链表
        ListNode* head = head1->val <= head2->val ? head1 : head2;
        //定义头结点中较小的那个为头
        ListNode* cur1 = head == head1 ? head1 : head2;
        ListNode* cur2 = head == head1 ? head2 : head1;
        //定义遍历的两个链表头节点，其中cur1代表较小的那个
        ListNode* pre = NULL;
        ListNode* next = NULL;
        while(cur1 != NULL && cur2 != NULL){
            if (cur1->val <= cur2->val){
                pre = cur1;
                cur1 = cur1->next;
            }
            else{
                next = cur2->next;
                pre->next = cur2;
                cur2->next = cur1;
                pre = cur2;
                cur2 = next;
                //重新连接链表
            }
        }
        pre->next = cur1 == NULL ? cur2 : cur1;
        //pre的下一个节点连接到非空的那个剩余链表上
        return head;
    }
};

发表于 | 分类于

Relocate List By Odd Or Even

题目描述：

给定链表的头节点，然后要求根据链表节点所处的位置的奇偶性重新排列链表。

例子：

具体描述可以看LeetCode328

解题思路：

本题的解题思路是将原始链表中的奇数位置节点连接成奇数链表，偶数位置连接成偶数链表；然后重新连接这两个链表即可。主要需要注意的是：在遍历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
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        // 单个节点或者空链表直接返回
        ListNode* odd = head;
        ListNode* even = head->next;
        // 定义奇偶链表的头节点
        ListNode* even_head = even;
        ListNode* odd_head = odd;
        // 保存奇偶链表的头节点用于最后的连接
        while(odd->next && even->next){
            if (even->next){
                odd->next = even->next;
                odd = odd->next;
                // 连接奇数链表
            }
            if (odd->next){
                even->next = odd->next;
                even = even->next;
                //连接偶数链表
            }
        }
        even->next = NULL;
        odd->next = NULL;
        // 定义链表尾部节点
        odd->next = even_head;
        return odd_head;
    }
};

发表于 | 分类于

Reverse Part List

题目描述：

给定一个链表的头结点，然后指定起始位置m和终止位置n；要求逆序链表中从第m个节点到n个节点的部分。

例子：

详细描述可以看LeetCode92。

解题思路：

链表的题目需要注意的是关于头节点的处理。我们定义了一个虚拟头节点用来处理这种情况；另外需要注意的是关于链表被逆序后的重新连接的问题，我们在开始部分需要找到需要逆序部分的上一个节点和下一个节点用来将逆序结果重新连接到链表中。

代码如下：

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
44
45
46
47
48
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || (m == n)) return head;
        # 如果是空链表或者起始位置和终止位置相同，则直接返回
        ListNode* dummy = new ListNode(-1);
        # 定义虚拟头结点
        dummy->next = head;
        ListNode* pre = dummy;
        # 定义前节点
        ListNode* back = head;
        # 定义后节点
        while(m - 1 > 0){
            pre = pre->next;
            m--;
        }
        # 找到待逆序节点的前一个位置
        ListNode* front = pre->next;
        # 逆序部分的第一个节点
        while(n - 1 > 0){
            back = back->next;
            n--;
        }
        # 逆序部分的尾节点
        ListNode* next = back->next;
        # 逆序部分尾部的下一个节点
        
        ListNode* left = front;
        ListNode* right = front->next;
        # 定义逆序部分的前后节点
        left->next = NULL;
        # 前节点next指针改变
        while(right != next){
            ListNode* tmp = right->next;
            # 保存好下一个指针
            right->next = left;
            # 逆序前后位置
            left = right;
            # 前指针前进一个位置
            right = tmp;
            # 后指针前进一个位置
        }
        pre->next = left;
        front->next = next;
        # 重新连接链表的头和尾
        return dummy->next;     
    }
};

发表于 | 分类于

Reorder List

题目描述：

给定一个链表的头节点，然后将原来链表顺序为L1->L2->L3…..->Ln-1->Ln的链表重现排序为L1->Ln->L2->Ln-1….

例子：

具体描述可以看LeetCode143

解题思路：

本题的思路很简单，主要是过程中涉及到链表的多种操作需要认真学习。首先是我们找到链表的中间节点主要利用的是快慢指针的方式，这个过程中需要注意在while部分我们需要考虑fast和fast->next;然后找到后半段链表后，将其逆序;这个过程中主要是定义pre=NULL的方式能帮助代码简洁一些;最后是两个链表的重新连接;主要是保存当前指针的下一个节点用于遍历即可。

代码如下：

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
44
45
46
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        //空链表的情况直接返回
        ListNode* fast = head->next;
        ListNode* slow = head;
        //快慢指针找到链表的中间节点
        while(fast && fast->next){
        // 注意判断fast和fast->next
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* pre = NULL;
        //逆序常用技巧定义pre=NULL
        ListNode* mid = slow->next;
        slow->next = NULL;
        while(mid){
            ListNode* tmp = mid->next;
            mid->next = pre;
            pre = mid;
            mid = tmp;
        }
        //通过找到的中间节点将后半部分链表逆序
        ListNode* right = pre;
        ListNode* left = head;
        while(left && right){
            ListNode* tmp1 = left->next;
            ListNode* tmp2 = right->next;
            //同时保存下一个节点的信息
            left->next = right;
            right->next = tmp1;
            left = tmp1;
            right = tmp2;
        }
        // 重现连接两个链表       
    }
};