LeetCode汇总21-40

21. Merge Two Sorted Lists

链接：https://leetcode.com/problems/merge-two-sorted-lists/

描述

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2


Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

题解

遍历两个链表时将它们合并（根据两个链表节点的最小值来决定谁是当前节点的next）
使用dummy节点避免特殊处理头节点，使用curr指针指代当前节点
使用两个指针分别遍历两个小链表，都没遍历完时比较两个节点的大小，将较小者指定为curr的next，并向前推进
遍历完一个链表时，若另一个链表还没走完，直接放在末尾
时间复杂度：每个链表遍历一次，O(n)
空间复杂度：原位构建，仅移动了指针，O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// Runtime: 8 ms, faster than 78.28% of C++ online submissions for Merge Two Sorted Lists.
// Memory Usage: 14.4 MB, less than 73.15% of C++ online submissions for Merge Two Sorted Lists.
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2)
            return (!l1)?l2:l1;
        ListNode *dummy=new ListNode,*cur=dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next=l1;
                l1=l1->next;
            } else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        if(l1 || l2)
            cur->next=l1?l1:l2;
        return dummy->next;
    }
};

22. Generate Parentheses

链接：https://leetcode.com/problems/generate-parentheses/

描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example,

1
2
3
4
5
6
7
8
9


given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题解

使用DFS结合回溯，每次DFS的参数是剩下的左括号数l_n和右括号数r_n
当构建完成字符串，即字符串长度为2n时，搜索到一个结果
每次决定放置一个字符时，对左右括号的处理不同：
- 对于左括号，只要还剩下有没放入字符串的，就可放入
- 对于右括号，由于需要匹配，故需要已经构建的字符串当中左括号多于右括号，即剩下的部分中左括号少于右括号，才可放右括号
每次添加一个字符后，回溯讨论其他可能

 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


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Generate Parentheses.
// Memory Usage: 11.7 MB, less than 76.33% of C++ online submissions for Generate Parentheses.
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        N=n;
        DFS(n,n);
        return res;
    }
private:
    int N;
    string tmp;
    vector<string> res;
    void DFS(int l_n,int r_n){
        if(tmp.size()==2*N)
            res.push_back(tmp);
        if(l_n>0){
            tmp.push_back('(');
            DFS(l_n-1,r_n);
            tmp.pop_back();
        }
        if(r_n>0 && r_n>l_n){
            tmp.push_back(')');
            DFS(l_n,r_n-1);
            tmp.pop_back();
        }
    }
};

23. Merge k Sorted Lists

链接：https://leetcode.com/problems/merge-k-sorted-lists/

描述

Given an array of linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked-lists into one sort linked-list and return it.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

1
2


Input: lists = []
Output: []

Example 3:

1
2


Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won’t exceed 10^4.

题解

使用优先队列存储每一个链表中未被看过的第一个节点，从中取最小者即是所有链表中未看过的最小节点
为优先队列自定义序，一是要处理节点大小比较，二是优先队列默认大的在前，需要逆转序
每从优先队列中取一个节点，就将它放在排序好的部分的末尾（因为它大于看过的所有元素，小于没看过的所有元素），并将其next放入优先队列，保证原来每个队列未看过部分的第一个节点都在队列中
当队列为空说明所有链表的所有节点都被看过了，排序完成
时间复杂度：每个节点只看一次，O(n)
空间复杂度：未使用新空间，O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// Runtime: 32 ms, faster than 83.23% of C++ online submissions for Merge k Sorted Lists.
// Memory Usage: 12 MB, less than 74.85% of C++ online submissions for Merge k Sorted Lists.
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *dummy=new ListNode,*curr=dummy;
        auto order=[](ListNode *lhs,ListNode *rhs){return lhs->val > rhs->val;};
        priority_queue<ListNode *,vector<ListNode *>,decltype(order)> q(order);
        for(auto node:lists)
            if(node)
                q.push(node);
        while(!q.empty()){
            curr->next=q.top();
            q.pop();
            curr=curr->next;
            if(curr->next)
                q.push(curr->next);
        }
        return dummy->next;
    }
};

24. Swap Nodes in Pairs

链接：https://leetcode.com/problems/swap-nodes-in-pairs/

描述

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1

Given 1->2->3->4, you should return the list as 2->1->4->3.

题解

使用三个指针：left和right保存需交换的两节点，before保存left的前驱
dummy节点处理头部节点交换的边界情形
每一次交换后，若交换后的left（即原来的right）的next为空则说明整个链表处理完成
时间复杂度：遍历一次，O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Swap Nodes in Pairs.
// Memory Usage: 7.6 MB, less than 14.61% of C++ online submissions for Swap Nodes in Pairs.
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !(head->next)) return head;
        ListNode *dummy=new ListNode(0,head);
        ListNode *before=dummy,*left=before->next,*right=left->next;
        while(left && right){
            before->next=right;
            left->next=right->next;
            right->next=left;
            if(left->next){
                before=left;
                left=left->next;
                right=left->next;
            }else
                break;
            
        }
        return dummy->next;
    }
};

25. Reverse Nodes in k-Group

链接：https://leetcode.com/problems/reverse-nodes-in-k-group/

描述

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

1
2
3
4
5


Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.

题解

使用三个指针：left和right是要反转的一段的左右端点，before是left的前驱
将left和right界定的一段进行反转时，使用递归方式：
- 每次将left右移即left->next输入内层函数，将left到right这一段的反转归结于left->next到right这一段的反转
- 递归终点是left和right重合，此时认为left到right已逆转，直接return
- 每当left->next到right这一段已逆转时，只需要left->next->next=left就可使left到right这一段也是逆转的
- 每次递归时可顺手使left（即逆转后的尾节点）的next为空，对此题影响不大，但正经反转链表时尾节点的next应该是空
每次逆转一段之后，修改三个指针使它们指向下一段即可
时间复杂度：只遍历两次链表（一次是right前进，另一次是每一段逆转），故O(n)
空间复杂度：递归深度取决于一段的长度，即O(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


// Runtime: 12 ms, faster than 96.87% of C++ online submissions for Reverse Nodes in k-Group.
// Memory Usage: 10.2 MB, less than 49.33% of C++ online submissions for Reverse Nodes in k-Group.
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy=new ListNode(0,head);
        ListNode *before=dummy,*left=before->next,*right=before;
        while(right){
            for(int i=0;i<k;++i){
                if(right->next)
                    right=right->next;
                else
                    return dummy->next;
            }
            ListNode *tmp=right->next;
            reverseSegment(left,right);
            before->next=right;
            left->next=tmp;
            before=left;
            right=left;
            left=tmp;
        }
        return dummy->next;
    }
private:
    void reverseSegment(ListNode *left,ListNode *right){
        if(left!=right){
            reverseSegment(left->next,right);
            left->next->next=left;
            left->next=nullptr;
        }
    }
};

26. Remove Duplicates from Sorted Array

链接：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

描述

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5


Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5


Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8


// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题解

法1：使用unique函数

直接调用stl的unique函数去重

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// Runtime: 12 ms, faster than 99.51% of C++ online submissions for Remove Duplicates from Sorted Array.
// Memory Usage: 13.9 MB, less than 44.24% of C++ online submissions for Remove Duplicates from Sorted Array.
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto end_unique=std::unique(nums.begin(),nums.end());
        nums.erase(end_unique,nums.end());
        return std::distance(nums.begin(),end_unique);
    }
};

法2：手写

维护两个指针i和j：
- i是已去重部分的末尾
- j在i后，向右移动
  - j和i处的值相等时，j向右移动直到不相等或碰到数组边界
  - j和i处的值不相等时，说明看到新值，将其插入i右边，并使i和j同时右移
时间复杂度：只遍历一次，O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Runtime: 20 ms, faster than 76.52% of C++ online submissions for Remove Duplicates from Sorted Array.
// Memory Usage: 13.8 MB, less than 70.70% of C++ online submissions for Remove Duplicates from Sorted Array.
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2)
            return nums.size();
        int i=0,j=1;
        while(j<nums.size()){
            if(nums[j]==nums[i]){
                ++j;
            else
                nums[++i]=nums[j++];
        }
        nums.erase(nums.begin()+i+1,nums.end());
        return i+1;
    }
};

27. Remove Element

链接：https://leetcode.com/problems/remove-element/

描述

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5


Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7


Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8


// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题解

维护两个指针i和j：
- i是已处理区域的末尾
- j从i开始，向右移动
  - j的值为target时只需++j跳过
  - j的值不为target时将其写入已处理区域，随后i和j同时右移
注意该问题与去重不一样，该问题要考虑数组第一个元素即是target的情形
时间复杂度：只遍历一次，O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Remove Element.
// Memory Usage: 9 MB, less than 45.26% of C++ online submissions for Remove Element.
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0,j=0;
        while(j<nums.size()){
            if(nums[j]==val)
                ++j;
            else
                nums[i++]=nums[j++];
        }
        return i;
    }
};

28. Implement strStr()

链接：https://leetcode.com/problems/implement-strstr/

描述

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2


Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2


Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Constraints:

haystack and needle consist only of lowercase English characters.

题解

使用KMP算法，关键是求next数组，参见另一篇文章
时间复杂度：假设原字符串长m，模式字符串长n，则O(m+n)
空间复杂度：next数组和模式字符串等长，为O(n)

 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


// Runtime: 4 ms, faster than 99.00% of C++ online submissions for Implement strStr().
// Memory Usage: 7.3 MB, less than 11.26% of C++ online submissions for Implement strStr().
class Solution {
public:
    int strStr(string str,string pat){
        if(pat=="") return 0;
        vector<int> next=get_next(pat);
        int j=-1;
        for(int i=0;i<str.size();++i){
            while(j>-1 && pat[j+1]!=str[i])
                j=next[j];
            if(pat[j+1]==str[i])
                ++j;
            if(j==pat.size()-1)
               return i-pat.size()+1;
        }
        return -1;
    }
private:
    vector<int> get_next(string pat){
        vector<int> next(pat.size(),-1);
        int j=-1;
        for(int i=1;i<pat.size();++i){
            while(j>-1 && pat[j+1]!=pat[i])
                j=next[j];
            if(pat[j+1]==pat[i])
                ++j;
            next[i]=j;
        }
        return next;
    }
};

29. Divide Two Integers

链接：https://leetcode.com/problems/divide-two-integers/

描述

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

1
2
3


Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

1
2
3


Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

题解

为处理正负数，先将两数全转为正数，得到商后再根据输入的两数符号是否相反（异或逻辑）来决定商是否要取反
使用右移实现x2操作。先预设商为1，每次商和除数都x2，直到除数再x2就比被除数大，此时得到的商是2的幂，即是最终商的二进制形式中最高位的1，这个2的幂乘上除数后刚好小于被除数。用被除数减去这个商与被除数的乘积，再递归调用该函数，即可得到最终商的二进制形式中其他位的1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Runtime: 8 ms, faster than 20.71% of C++ online submissions for Divide Two Integers.
// Memory Usage: 5.9 MB, less than 91.14% of C++ online submissions for Divide Two Integers.
class Solution {
public:
    int divide(int dividend, int divisor) {
        long long m=labs(dividend),n=labs(divisor),res=1;
        if(m<n)
            return 0;
        while(m > (n<<1)){
            n<<=1;
            res<<=1;
        }
        res+=divide(m-n,abs(divisor));
        if(dividend<0 ^ divisor<0)
            res=-res;
        return res>INT_MAX ? INT_MAX : res;
    }
};

30. Substring with Concatenation of All Words

链接：https://leetcode.com/problems/substring-with-concatenation-of-all-words/

描述

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

1
2
3
4


Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

1
2


Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

1
2


Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 104
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

题解

记vector中的小字符串长为m，vector中有n个小字符串。
在原字符串上使用m*n的滑动窗口，判断滑动窗口中的内容是否是vector中小字符串的组合，滑动窗口每次右移一位
- 对于vector，建立字典cnt来表示每个小字符串应该出现的次数
- 在滑动窗口中，建立字典cnt_str来表示窗口中n个小字符串实际出现的次数
- 若cnt_str中出现vector中没有的key，或者每次滑动窗口构建的cnt_str和vector的cnt不完全相同，则该窗口不是vector中小字符串的组合，反之是
时间复杂度：每个滑动窗口中需要遍历一次来构建字典并比较字典，滑动窗口要遍历整个字符串，故O(n^2)
空间复杂度：构建了两个字典，每个字典的大小取决于vector的尺寸，故O(n)

 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


// Runtime: 380 ms, faster than 76.55% of C++ online submissions for Substring with Concatenation of All Words.
// Memory Usage: 22.5 MB, less than 76.01% of C++ online submissions for Substring with Concatenation of All Words.
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int m=words[0].size(),n=words.size();
        if(s.size()<m*n)
            return {};
        //统计vector各个小字符串的个数，即应该具有的频率
        unordered_map<string,int> cnt;
        for(const auto &word:words)
            ++cnt[word];
        for(int i=0;i<=s.size()-m*n;++i){
            //窗口的第一个小字符串不在vector中，则窗口直接右移
            if(cnt.find(s.substr(i,m))==cnt.end())
                continue;
            //统计窗口中小字符串实际的出现次数
            unordered_map<string,int> cnt_str;
            for(int j=i;j<i+m*n;j+=m)
                ++cnt_str[s.substr(j,m)];
            bool match=true;
            //将两个字典进行比较，发现不一样就将match置为false
            for(const auto &word:words){
                auto word_find=cnt_str.find(word);
                if(word_find!=cnt_str.end() && word_find->second==cnt[word]);
                else{
                    match=false;
                    break;
                }
            }
            //match为true表示窗口中内容是vector中小字符串的组合
            if(match)
                res.push_back(i);
        }
        return res;
    }
};

31. Next Permutation

链接：https://leetcode.com/problems/next-permutation/

描述

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3


1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

本题最难的是理解next permutation是在做什么，也即字典序的含义
假设P是1~n的全排列，即P=p1p2……pn=p1p2……pj-1pjpj+1……pk-1pkpk+1……pn
- 假设尾部是降序排列，j是降序子序列的边界，即j=max{i|pi<pi+1}
- 假设pk是尾部降序子序列中刚好比pj大的元素，即pk=min{pi|pi>pj}，由于降序，也即k=max{i|pi>pj}
- 操作步骤：
  - 若j>=0，即整个序列并非全部递减，即不是全排列的最后一个，就交换pj和pk，随后将j之后的部分翻转
  - 若j<0，即整个序列全部递减，即是全排列的最后一个，就将整个序列翻转
时间复杂度：查找j和k需从后往前扫描两次，O(n)
空间复杂度：O(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


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Next Permutation.
// Memory Usage: 12.2 MB, less than 45.99% of C++ online submissions for Next Permutation.
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int j=-1;
        for(int i=nums.size()-1;i>0;--i){
            if(nums[i-1]<nums[i]){
                j=i-1;
                break;
            }
        }
        if(j>=0){
            int k=-1;
            for(int i=nums.size()-1;i>j;--i){
                if(nums[i]>nums[j]){
                    k=i;
                    break;
                }
            }
            std::swap(nums[j],nums[k]);
        }
        std::reverse(nums.begin()+j+1,nums.end());
    }
};

32. Longest Valid Parentheses

链接：https://leetcode.com/problems/longest-valid-parentheses/

描述

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3


Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3


Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

题解

使用dp，数组dp[i]代表以第i个字符为结尾的有效字串的最大长度
若第i个字符为(，不可能为有效子串的结尾，则dp[i]为0
若第i个字符为)，则需讨论：
- 形如(())，dp[i-1]=2，而dp[i-1]代表的子串左侧是(，可以和i处的)匹配，故dp[i]=dp[i-1]+2
- 形如()(())，i处的)不仅能和dp[i-1]代表的子串左侧的(匹配，有效的长度还要加上最左边的()，故dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
时间复杂度：扫描一遍，O(n)
空间复杂度：一维dp数组，O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// Runtime: 4 ms, faster than 99.55% of C++ online submissions for Longest Valid Parentheses.
// Memory Usage: 7.3 MB, less than 49.10% of C++ online submissions for Longest Valid Parentheses.
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        vector<int> dp(s.size(),0);
        for(int i=1;i<s.size();++i){
            int j=i-dp[i-1]-2;
            if(s[i]=='(')
                dp[i]=0;
            else{
                if(j+1>=0 && s[j+1]=='(')
                    dp[i]=(j>=0)?(dp[i-1]+2+dp[j]):(dp[i-1]+2);
                else
                    dp[i]=0;
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

33. Search in Rotated Sorted Array

链接：https://leetcode.com/problems/search-in-rotated-sorted-array/

描述

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

1
2


Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2


Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

1
2


Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
-10^4 <= target <= 10^4

题解

使用二分法，边界l和r
取中间位置m，若中间的数大于最右边的数，则说明左边一半是升序的，比较l处和m处的值与target的关系即可确定target在左侧还是在右侧，可收缩边界。若中间的数小于最右边的数同理
时间复杂度：每次排除一半，是二分，O(logn)
空间复杂度：O(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


// Runtime: 8 ms, faster than 69.28% of C++ online submissions for Search in Rotated Sorted Array.
// Memory Usage: 11.3 MB, less than 23.54% of C++ online submissions for Search in Rotated Sorted Array.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]==target)
                return m;
            if(nums[m]>nums[r]){
                if(nums[l]<=target && nums[m]>=target)
                    r=m-1;
                else
                    l=m+1;
            }else{
                if(nums[m]<=target && nums[r]>=target)
                    l=m+1;
                else
                    r=m-1;
            }
        }
        return -1;
    }
};

34. Find First and Last Position of Element in Sorted Array

链接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

描述

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2


Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2


Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is a non decreasing array.
-10^9 <= target <= 10^9

题解

使用两次二分查找，第一次找左边界，第二次找右边界
使用l和r表示左闭右开区间，两次二分的终止条件是l==r
第一次搜索左边界
- 初始l为0，r为尾后
- 当nums[m]<target时左边界变为m+1（+1是因为已经排除了这个值，且左边界为闭）
- 其他情形（m>=target）时右边界变为m（不+1是因为已经排除了这个值，但右边界为开）
- 终止时l=r=左边界，即最左边的target
第二次搜索右边界
- 初始l为上次搜索到的左边界，r为尾后
- 当nums[m]<=target时左边界变为m+1（+1是因为已经排除了这个值，且左边界为闭）
- 其他情形（m>target）时右边界变为m（不+1是因为已经排除了这个值，但右边界为开）
- 终止时l=r=右边界的后一个位置，即最右边的target之后
时间复杂度：二分查找，O(logn)
空间复杂度：O(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


// Runtime: 16 ms, faster than 91.71% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
// Memory Usage: 13.7 MB, less than 91.92% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res={-1,-1};
        int l=0,r=nums.size();
        while(l<r){
            int m=l+(r-l)/2;
            if(nums[m]<target)
                l=m+1;
            else
                r=m;
        }
        if(r==nums.size() || nums[r]!=target)
            return res;
        res[0]=r;
        r=nums.size();
        while(l<r){
            int m=l+(r-l)/2;
            if(nums[m]<=target)
                l=m+1;
            else
                r=m;
        }
        res[1]=r-1;
        return res;
    }
};

35. Search Insert Position

链接：https://leetcode.com/problems/search-insert-position/

描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2


Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2


Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2


Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2


Input: [1,3,5,6], 0
Output: 0

题解

二分查找，使用l和r作为左闭右开区间的边界，终止条件是找到target或l==r
若找到target直接返回，否则收缩区间。由于左闭右开，收缩时是l=m+1，r=m
若最后还没找到target就l==r，则该值是大于target的第一个值
时间复杂度：二分查找，O(logn)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Runtime: 8 ms, faster than 92.94% of C++ online submissions for Search Insert Position.
// Memory Usage: 9.7 MB, less than 56.64% of C++ online submissions for Search Insert Position.
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l=0,r=nums.size();
        while(l<r){
            int m=l+(r-l)/2;
            if(nums[m]==target)
                return m;
            else if(nums[m]<target)
                l=m+1;
            else
                r=m;
        }
        return l;
    }
};

36. Valid Sudoku

链接：https://leetcode.com/problems/valid-sudoku/

描述

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

LeetCode36

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character ‘.’.
The given board size is always 9x9.

题解

使用字符串来描述一个位置及其所处的值：
- x<j>[<val>]代表第j列中含有数字val
- y<i>[<val>]代表第i行中含有数字val
- c<i/3><j/3>[<val>]代表第(i/3,j/3)个3x3小方块中含有数字val
将这些字符串都存入一个集合中，看到一个位置时先检查集合中是否有重复项，有则false，无则放入集合。最终一直没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


// Runtime: 56 ms, faster than 26.16% of C++ online submissions for Valid Sudoku.
// Memory Usage: 20.3 MB, less than 14.43% of C++ online submissions for Valid Sudoku.
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> seen;
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                if(board[i][j]=='.')
                    continue;
                // encoding
                string val="["+to_string(board[i][j])+"]";
                string x="x"+to_string(j)+val;
                string y="y"+to_string(i)+val;
                string c="c"+to_string(i/3)+to_string(j/3)+val;
                if(seen.count(x) || seen.count(y) || seen.count(c))
                    return false;
                seen.insert(x);
                seen.insert(y);
                seen.insert(c);
            }
        }
        return true;
    }
};

37. Sudoku Solver

链接：https://leetcode.com/problems/sudoku-solver/

描述

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.’.

LeetCode37_1 LeetCode37_2

Note:

The given board contain only digits 1-9 and the character ‘.’.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

题解

使用DFS实现回溯
使用辅助函数isValid来判断在(i,j)放置某值是否导致无效
每次DFS前都要检验一个’.‘处的值是否能被替换为数字，若替换合法则执行替换并进入下一层DFS，不合法则continue尝试下一个数字。
若内层DFS返回true则说明找到了一个解，直接return即可。若内层DFS返回false说明这个位置放置这个值会导致无解，将这个位置的值回溯为’.‘并尝试下一个值
时间复杂度：每次判断isValid是O(n)，DFS的复杂度是O(n^3)，故总复杂度是O(n^4)
空间复杂度：取决于DFS的深度即’.‘的数量，O(n^2)

 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


// Runtime: 24 ms, faster than 65.84% of C++ online submissions for Sudoku Solver.
// Memory Usage: 6.5 MB, less than 70.38% of C++ online submissions for Sudoku Solver.
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        DFS(board);
    }
private:
    bool DFS(vector<vector<char>>& board){
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                if(board[i][j]!='.')
                    continue;
                for(char c='1';c<='9';++c){
                    if(isValid(board,i,j,c))
                        board[i][j]=c;
                    else
                        continue;
                    if(DFS(board))
                        return true;
                    else
                        board[i][j]='.';
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(const vector<vector<char>> &board,int i,int j,char c){
        for(int k=0;k<9;++k){
            if(board[i][k]==c)
                return false;
            if(board[k][j]==c)
                return false;
            int y=i/3*3+k/3,x=j/3*3+k%3;
            if(board[y][x]==c)
                return false;
        }
        return true;
    }
};

38. Count and Say

链接：https://leetcode.com/problems/count-and-say/

描述

The count-and-say sequence is the sequence of integers with the first five terms as following:

1
2
3
4
5


1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

1
2
3


Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:

1
2
3


Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

题解

按照字符重复出现的次数读出，只需数每个字符连续出现的次数即可
时间复杂度：扫描一次，O(n)
空间复杂度：构造了临时字符串，O(n)

 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


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Count and Say.
// Memory Usage: 6.7 MB, less than 34.35% of C++ online submissions for Count and Say.
class Solution {
public:
    string countAndSay(int n) {
        string seq="1";
        for(int i=0;i<n-1;++i){
            string tmp=next(seq);
            seq=tmp;
        }
        return seq;
    }
private:
    string next(string seq){
        string tmp;
        int sz=seq.size();
        for(int i=0;i<sz;){
            int j=i;
            while(seq[j]==seq[i])
                ++j;
            tmp.push_back('0'+j-i);
            tmp.push_back(seq[i]);
            i=j;
        }
        return tmp;
    }
};

39. Combination Sum

链接：https://leetcode.com/problems/combination-sum/

描述

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

1
2
3
4
5
6


Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

1
2


Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

1
2


Input: candidates = [2], target = 1
Output: []

Example 4:

1
2


Input: candidates = [1], target = 1
Output: [[1]]

Example 5:

1
2


Input: candidates = [1], target = 2
Output: [[1,1]]

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

题解

使用DFS结合回溯，搜索所有可能出现的序列。递归终点是：和为target则向结果中添加该序列并返回，和大于target则直接返回
为了去重，使用集合维护最终结果。
为了剪枝：
- 将输入序列排序并去重
- 每次搜索时只搜现在和未来不搜过去。例如{2,3,4,5}，以2开始时搜索{2,3,4,5}，以3开始时搜索{3,4,5}，以4开始时搜索{4,5}。这样做的好处还有保证不会搜到之前搜过的序列，同时起到去重作用。

 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


// Runtime: 12 ms, faster than 67.57% of C++ online submissions for Combination Sum.
// Memory Usage: 11.4 MB, less than 52.29% of C++ online submissions for Combination Sum.
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        can=candidates;
        t=target;
        //减小原数组，减小搜索空间
        std::sort(can.begin(),can.end());
        unique(can.begin(),can.end());
        dfs(0,0);
        return vector(res.begin(),res.end());
    }
private:
    set<vector<int>> res;
    vector<int> can,tmp;
    int t;
    void dfs(int order,int sum){
        if(sum>=t){
            if(sum==t)
                res.insert(tmp);
            return;
        }
        //只搜现在和未来，不搜过去，剪枝并去重
        for(int i=order;i<can.size();++i){
            tmp.push_back(can[i]);
            dfs(i,sum+can[i]);
            tmp.pop_back();
        }
    }
};

40. Combination Sum II

链接：https://leetcode.com/problems/combination-sum-ii/

描述

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8


Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

1
2
3
4
5
6


Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

题解

使用DFS结合回溯，搜索所有可能出现的序列。递归终点是：和为target则向结果中添加该序列并返回，和大于target则直接返回
与上一题的去重/剪枝手段相同，区别是每个数只在结果序列中出现一次，因此：
- 不能对原序列做unique
- 只能搜未来，不能搜过去和现在

 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


// Runtime: 44 ms, faster than 30.44% of C++ online submissions for Combination Sum II.
// Memory Usage: 10.9 MB, less than 59.26% of C++ online submissions for Combination Sum II.
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        can=candidates;
        t=target;
        std::sort(can.begin(),can.end());
        dfs(0,0);
        return vector(res.begin(),res.end());
    }
private:
    set<vector<int>> res;
    vector<int> can,tmp;
    int t;
    void dfs(int order,int sum){
        if(sum>=t){
            if(sum==t)
                res.insert(tmp);
            return;
        }
        //搜索现在和未来
        for(int i=order;i<can.size();++i){
            tmp.push_back(can[i]);
            //跳过现在
            dfs(i+1,sum+can[i]);
            tmp.pop_back();
        }
    }
};

文章目录

21. Merge Two Sorted Lists

描述

题解

22. Generate Parentheses

描述

题解

23. Merge k Sorted Lists

描述

题解

24. Swap Nodes in Pairs

描述

题解

25. Reverse Nodes in k-Group

描述

题解

26. Remove Duplicates from Sorted Array

描述

题解

法1：使用unique函数

法2：手写

27. Remove Element

描述

题解

28. Implement strStr()

描述

题解

29. Divide Two Integers

描述

题解

30. Substring with Concatenation of All Words

描述

题解

31. Next Permutation

描述

题解

32. Longest Valid Parentheses

描述

题解

33. Search in Rotated Sorted Array

描述

题解

34. Find First and Last Position of Element in Sorted Array

描述

题解

35. Search Insert Position

描述

题解

36. Valid Sudoku

描述

题解

37. Sudoku Solver

描述

题解

38. Count and Say

描述

题解

39. Combination Sum

描述

题解

40. Combination Sum II

描述

题解