LeetCode21-30

发表于 | 更新于: | 分类于 ， | | 阅读次数:
字数统计: 1.8k 字 | 阅读时长 ≈ 9 分钟

21、合并两个有序链表

两个有序链表的合并，本渣代码充分利用原有空间，没开辟新的内存存储新链。

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
/**
 * 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 *ans = (ListNode*)malloc(sizeof(ListNode)), *tmp = ans;
        ans->next = NULL;
        while( l1&&l2 ){
            if( l1->val > l2->val ){
                tmp->next = l2;
                l2 = l2->next;
            }
            else{
                tmp->next = l1;
                l1 = l1->next;
            }
            tmp = tmp->next;
            tmp->next = NULL;
        }
        if( l1 )
            tmp->next = l1;
        if( l2 )
            tmp->next = l2;
        return ans->next;
    }
};

22、括号生成

生成的种类数是个卡特兰数，因此 n 的值不会太大。卡特兰数在计算机中是个特别重要的数串，像：三角剖分、n个叶节点树的种类、n个数字的进出栈、括号匹配、矩阵链乘等等都有卡特兰数的应用。

卡特兰数的通项公式：
$$
h(n) = C_{2n}^n - C_{2n}^{n-1}
$$
递推公式为：
$$
h(n) = h(n-1)*\frac{4n-2}{n+1}
$$
其实，求组合数时，当 n 很大的时候，计算也是个问题，好在有 Lucas定理 可以解决这事，当然以上这些与解决本题没啥关系。

本题做法是直接递归一下即可，每次放左括号（第16行）或右括号（第17行），递归的退出条件是放了n个左括号和n个右括号（第9行），剪枝条件是放的右括号数量大于左括号数量了，明显会造成非法串，直接返回退出（第13行）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        func(ans, "", n, n);
        return ans;
    }
    void func(vector<string>& ans, string tmp_ans, int left, int right){
        if( left==0 && right==0 ){
            ans.push_back(tmp_ans);
            return;
        }
        if( right<left )  //相当于剪枝，2^n剪到katalan(n)
            return;
        if( left>0 )
            func( ans, tmp_ans+'(', left-1, right );
        func( ans, tmp_ans+')', left, right-1 );
    }
};

23、合并K个排序链表

合并的关键点在于如何快速找到当前最小值，最小堆可以帮我们快速实现这一点。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 struct cmp{
    bool operator()(ListNode* a, ListNode* b){
        return a->val > b->val;
    }
 };
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = new ListNode(0);
        ListNode *p = ans, *tmp;
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for(int i=0; i<lists.size(); i++){
           if(lists[i])
                pq.push(lists[i]);
        }
        while(pq.size()>1){
            tmp = pq.top();
            pq.pop();
            p->next = tmp;
            if(tmp->next)
                pq.push(tmp->next);
            p = p->next;
            p->next = NULL;
        }
        if(pq.size()==1)
            p->next = pq.top();
        return ans->next;
    }
};

24、两两交换链表中的节点

处理好两个指针之间的关系即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if( head==NULL || head->next==NULL )
            return head;
        ListNode *p1=head, *p2=head->next, *tmp;
        head = head->next;
        while( p1 && p2){
            tmp = p1;
            p1->next = p2->next==NULL? NULL:p2->next->next==NULL? p2->next:p2->next->next;
            p1 = p2->next;
            p2->next = tmp;
            p2 = p1==NULL? NULL:p1->next;
        }
        return head;
    }
};

25、k个一组翻转链表

采用一个大小为 k 的栈来实现翻转。

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:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len = 0;
        ListNode *tmp_head = head, *ans, *cur_ans;
        while(tmp_head){
            len++;
            tmp_head = tmp_head->next;
        }
        int num_roll = len / k;
        ans = new ListNode(-1);
        cur_ans = ans;
        stack<ListNode*> s;
        tmp_head = head;
        for(int i=0; i<num_roll; i++){
            for(int j=0; j<k; j++){
                s.push(tmp_head);
                tmp_head = tmp_head->next;
            }
            for(int j=0; j<k; j++){
                cur_ans->next = s.top();
                s.pop();
                cur_ans = cur_ans->next;
            }
        }
        cur_ans->next = tmp_head;
        return ans->next;
    }
};

26、删除排序数组中的重复项

直接使用 STL 中的 unique 函数即可，unique 函数的具体说明如下：

iterator unique(iterator it_1,iterator it_2);

两个参数表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。注意，unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置，而不是将重复的元素往后移动。

1
2
3
4
5
6
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return unique(nums.begin(), nums.end()) - nums.begin();
    }
};

27、移除元素

双指针，执行调换过程即可，注意，如果前后调换后，nums[pFront] 可能依然等于 val，通过第11行的 continue语句巧妙的解决该问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()==0)
            return 0;
        int pFront=0, pEnd = nums.size()-1;
        while(pEnd>pFront){
            if(nums[pFront]==val){
                swap(nums[pFront], nums[pEnd]);
                pEnd--;
                continue;
            }
            pFront++;
        }
        return nums[pFront]==val? pFront:pFront+1;
    }
};

28、实现strStr()

可以直接暴力，时间复杂度为$O(n^2)$。线性时间复杂度算法为 KMP 算法或 BM 算法。KMP 算法的关键是理解 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
class Solution {
private:
    int next[100000];
public:
    void solve_next(string needle){
        memset(next, -1, sizeof(next));
        int len = needle.size();
        int k = -1, j = 0;
        while(j<len-1){
            if( k==-1 || needle[j]==needle[k] )
                next[++j] = ++k;
            else
                k = next[k];
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0)
            return 0;
        solve_next(needle);
        int len_haystack = haystack.size();
        int len_needle = needle.size();
        int i = 0, j = 0;
        while( i<len_haystack && j<len_needle){
            if(j==-1 || haystack[i]==needle[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(j==len_needle)
            return i-j;
        return -1;
    }
};

29、两数相除

使用移位操作模拟乘法，用减法代替除法。

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:
    int divide(int dividend, int divisor) {
        if( dividend==INT_MIN && divisor==-1 )
            return INT_MAX;
        int flag1 = dividend>0? 1:-1;
        int flag2 = divisor>0? 1:-1;
        long long _dividend = abs((long long)dividend);
        long long _divisor = abs((long long)divisor);
        int n = 0;
        while(_divisor<<(n+1) <= _dividend && _divisor<<(n+1) >= 0)
            n++;
        long long ans = 0;
        for(int i=n; i>=0; i--){
            if( _dividend >= _divisor<<i ){
                ans += (long long)1<<i;
                _dividend -= _divisor<<i;
            }
        }
        if(flag1+flag2==0)
            return -ans>=INT_MAX? INT_MAX:int(-ans);
        return ans>=INT_MAX? INT_MAX:ans;
    }
};

30、串联所有单词的子串

words中单词长度固定，将s串按照固定长度切分保存进vector<string>中，之后使用两个map和滑动窗口实现匹配过程，详见代码：

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<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if(s.size()==0 || words.size()==0)
            return ans;
        unordered_map<string, int> mp1;
        for(auto str : words)
            mp1[str] = mp1.find(str)==mp1.end()? 1:mp1[str]+1;
        int str_len = words[0].length();
        for(int i=0; i<str_len; i++){
            vector<string> word_vec;
            int position = i;
            while( position + str_len <= s.length() ){
                word_vec.push_back(s.substr(position, str_len));
                position += str_len;
            }
            unordered_map<string, int> mp2;
            int left = 0;
            for(int j=0; j<word_vec.size(); j++){
                if(mp1.find(word_vec[j])==mp1.end()){
                    mp2.clear();
                    left = j+1;
                    continue;
                }
                mp2[word_vec[j]] = mp2.find(word_vec[j])==mp2.end()? 1:mp2[word_vec[j]]+1;
                while(mp2[word_vec[j]] > mp1[word_vec[j]])
                    mp2[word_vec[left++]] -= 1;
                if( j-left+1 == words.size() ){
                    ans.push_back(left*str_len+i);
                    mp2[word_vec[left]] -= 1;
                    if(mp2[word_vec[left]]==0)
                        mp2.erase(word_vec[left]);
                    left++;
                }
            }
        }
        return ans;
    }
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%