1.Two Sum

描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

题解

  • 用哈希表记录每个元素的位置,遍历时一边记录哈希表,一边查找target减当前值是否在哈希表中,是则返回
  • 时间复杂度:只需遍历一次,O(n)
  • 空间复杂度:每个元素存储一对key-value,O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Runtime: 20 ms, faster than 64.59% of C++ online submissions for Two Sum.
// Memory Usage: 10.1 MB, less than 42.21% of C++ online submissions for Two Sum.
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        for(int i=0;i<nums.size();++i){
            auto diff=m.find(target-nums[i]);
            if(diff!=m.end())
                return {diff->second,i};
            m[nums[i]]=i;
        }
        return {0,0};
    }
};

2. Add Two Numbers

描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题解

  • 同时遍历两个链表,并开辟第三个链表空间,用carry表示进位,sum表示新链表中该位存储的值。
  • 遍历时只需l1非空或l2非空或有进位,并在每次取节点val/next前检查节点是否为空,即可处理各种情形
  • 时间复杂度:只需在两个链表中同时推进指针,O(n)
  • 空间复杂度:开辟了新链表存储结果,O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// Runtime: 20 ms, faster than 98.45% of C++ online submissions for Add Two Numbers.
// Memory Usage: 70.2 MB, less than 43.01% of C++ online submissions for Add Two Numbers.
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy=new ListNode(0),*curr=dummy;
        int sum=0,carry=0;
        while(l1||l2||carry){
            sum=(l1?l1->val:0)+(l2?l2->val:0)+carry;
            carry=sum/10;
            sum=sum%10;
            curr->next=new ListNode(sum);
            curr=curr->next;
            l1=l1?(l1->next):nullptr;
            l2=l2?(l2->next):nullptr;
        }
        return dummy->next;
    }
};

3. Longest Substring Without Repeating Characters

描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题解

  • 使用l和r指定无重复子串的范围,哈希表m存储每个字符对应的位置(每次r右移时更新value,保证存储的位置是当前看到的最右的该字符的位置)
  • 对于当前r,若哈希表中的该字符对应位置在l的右侧,说明范围[l,r)中有字符r,即有重复字符,且能由哈希表得到该重复字符位置,将l变为该字符的位置+1即可跳过重复的区域
  • 时间复杂度:只需要扫描一次数组,O(n)
  • 空间复杂度:哈希表中key-value的数量取决于字符集的数量O(m)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Runtime: 36 ms, faster than 61.35% of C++ online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 8.7 MB, less than 43.29% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<int,int> m;
        int max_len=0,len=0;
        for(int l=0,r=0;r<s.length();++r){
            //范围[l,r)中有字符r
            if(m.find(s[r])!=m.end() && m[s[r]]>=l){
                max_len=(max_len>r-l)?max_len:r-l;
                l=m[s[r]]+1;
                len=r-l+1;
            }else{
                ++len;
                max_len=(max_len>len)?max_len:len;
            }
            m[s[r]]=r;
        }
        return max_len;
    }
};

4. Median of Two Sorted Arrays

描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题解

解法1:二分查找

  • 要求对数复杂度,使用二分查找
  • 求合并后大数组最中间的两个数,假设这两个数分别在两个数组中,且索引分别为i和j
  • 由于i和j处于合并后数组的最中间,必有:
    • 合并后这两元素左右的元素数量相等,故i+j=(m-i)+(n-j),即j=(m+n+1)/2-i,同时得到必须满足m<=n,否则j值产生负数。这里为什么+1没看懂
    • i左侧的元素必小于j对应元素,反之亦然,即A[i-1]<B[j]B[j-1]<A[i]
  • 根据i+j=(m-i)+(n-j)可在搜索i时同时搜索j
  • 根据A[i-1]<B[j]B[j-1]<A[i]可判断i是太大还是太小:
    • 若i太小,则j太大,j左侧的数可以大于i对应的数,即B[j-1]>A[i]
    • 若i太大,则j太小,i左侧的数可以大于j对应的数,即A[i-1]>B[j]
  • 当搜到准确的i和j时,先检查i和j是否为原数组的边界:
    • 若i是A的左边界,则合并后数组左侧的数全部由B提供,中间(偏左)的数是B[j-1],若合并后有偶数个则需计算另一个中间的数
    • 同理,若j是B的左边界,则合并后中间(偏左)的数是A[i-1]
    • 若i和j都不是A或B的左边界,则取max(A[i-1],B[j-1])为合并后数组中间(偏左)的数
  • 合并后数组长度的奇偶决定是否还要继续计算
    • 若合并后数组长度为奇数,则刚才算出的中间的数就是中位数
    • 若合并后数组长度为偶数,则还需算出另一个中间的数
  • 计算另一个中间的数时,需要讨论i和j是否为原数组的右边界:
    • 若i是A的右边界,则合并后数组右侧的数全部由B提供,中间(偏右)的数是B[j]
    • 同理,若j是B的右边界,则合并后数组中间(偏右)的数是A[i]
    • 若i和j都不是A或B的右边界,则取min(A[i],B[j])为合并后数组中间(偏右)的数
    • 由于合并后数组长度是偶数,故需将求得的中间偏左和中间偏右取平均
  • 时间复杂度:在数组A中二分查找,而A一定是较小的数组,故O(log(min{m,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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Runtime: 44 ms, faster than 84.90% of C++ online submissions for Median of Two Sorted Arrays.
// Memory Usage: 89.1 MB, less than 57.81% of C++ online submissions for Median of Two Sorted Arrays.
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(),n=nums2.size();
        if(m>n)
            return findMedianSortedArrays(nums2,nums1);
        int l=0,r=m;
        while(l<=r){
            int i=l+(r-l)/2,j=(m+n+1)/2-i;
            // i is too small
            if(i<r && nums2[j-1]>nums1[i])
                l=i+1;
            // i is too big
            else if(i>l && nums1[i-1]>nums2[j])
                r=i-1;
            // i is perfect
            else{
                int maxLeft=0,minRight=0;
                // i和j都确定了,求中间的数
                if(i==0)
                    maxLeft=nums2[j-1];
                else if(j==0)
                    maxLeft=nums1[i-1];
                else
                    maxLeft=max(nums1[i-1],nums2[j-1]);
                // 大数组为奇数则直接是中位数
                if((m+n)%2==1)
                    return maxLeft;
                // 大数组是偶数则需算出下一个数求平均
                if(i==m)
                    minRight=nums2[j];
                else if(j==n)
                    minRight=nums1[i];
                else
                    minRight=min(nums1[i],nums2[j]);
                return (maxLeft+minRight)/2.0;
            }
        }
        return 0;
    }
};

解法2:每次排除一半

  • 扩展为求合并后数组第k项的问题
  • 考虑A和B的前k/2个元素,若A[k/2]<B[k/2]则说明A左侧k/2的元素一定在合并后数组的第k项的左侧,故可以排除掉这k/2个元素。下一次搜索时从A的第k/2项开始查找,找合并后数组的第k-k/2项即可,以此类推。
  • 时间复杂度:取第k大的数时每次排除k/2,而k设置为(m+n)/2,故时间复杂度为O(log((m+n)/2))
  • 空间复杂度:未开辟新空间,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: 48 ms, faster than 75.80% of C++ online submissions for Median of Two Sorted Arrays.
// Memory Usage: 89 MB, less than 80.35% of C++ online submissions for Median of Two Sorted Arrays.
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    // i和j左侧都是已经被排除的元素,k是需查找的合并后数组的第k个元素
    int findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        // 若想取的值会导致越界,则将midVal置为int的最大值
        int midVal1 = (i+k/2-1 < nums1.size()) ? nums1[i+k/2-1] : INT_MAX;
        int midVal2 = (j+k/2-1 < nums2.size()) ? nums2[j+k/2-1] : INT_MAX;
        if (midVal1 < midVal2) {
            // 若A[k/2]<B[k/2]则可排除A左侧的k/2个元素
            // 下次直接从k/2开始搜索合并后数组里第k-k/2的元素
            return findKth(nums1, i+k/2, nums2, j, k-k/2);
        } else {
            return findKth(nums1, i, nums2, j+k/2, k-k/2);
        }
    }
};

5. Longest Palindromic Substring

描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

题解

  • 暴力搜索,在每个元素i处,以它为中心分两种情况搜索:
    • 搜索奇数长度的回环序列,该元素是正中心,左右边界是i-diff和i+diff
    • 搜索偶数长度的回环序列,该元素是偏左的中心,左右边界是i-diff和i+1+diff
  • 若搜索到的回环序列大于记录的结果,则将其记录
  • 时间复杂度:每遍历一个元素都向其左右两侧搜索,O(n^2)
  • 空间复杂度:未开辟新空间,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
// Runtime: 60 ms, faster than 74.97% of C++ online submissions for Longest Palindromic Substring.
// Memory Usage: 14.3 MB, less than 47.08% of C++ online submissions for Longest Palindromic Substring.
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        int l=0,r=0;
        for(int i=0;i<s.size();++i){
            int diff=0;
            while(i-diff>=0 && i+diff<s.size() && s[i-diff]==s[i+diff]){
                if(2*diff+1>res.size())
                    res=s.substr(i-diff,2*diff+1);
                ++diff;
            }
            diff=0;
            while(i-diff>=0 && i+1+diff && s[i-diff]==s[i+1+diff]){
                if(2*diff+2>res.size())
                    res=s.substr(i-diff,2*diff+2);
                ++diff;
            }
        }
        return res;
    }
};

6. ZigZag Conversion

描述

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows); Example 1:

1
2
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

1
2
3
4
5
6
7
8
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

题解

  • 逐行求出通项即可:
    • 第一行索引:2*k*(numRows-1)
    • 第row行索引:row+2*k*(numRows-1)row+2*k*(numRows-1)+2*(numRows-row-1)
    • 最后一行索引:numRows-1+2*k*(numRows-1)
  • 时间复杂度:每个元素计算一次索引,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
26
27
28
29
30
31
32
// Runtime: 24 ms, faster than 78.14% of C++ online submissions for ZigZag Conversion.
// Memory Usage: 8.1 MB, less than 69.38% of C++ online submissions for ZigZag Conversion.
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        string ans;
        // first line
        for(int k=0;k<s.size()/numRows+1;++k){
            int idx=2*k*(numRows-1);
            if(idx<s.size())
                ans.push_back(s[idx]);
        }
        for(int row=1;row<numRows-1;++row){
            for(int k=0;k<s.size()/numRows+1;++k){
                int idx1=row+2*k*(numRows-1);
                int idx2=idx1+2*(numRows-row-1);
                if(idx1<s.size())
                    ans.push_back(s[idx1]);
                if(idx2<s.size())
                    ans.push_back(s[idx2]);
            }
        }
        // last line
        for(int k=0;k<s.size()/numRows+1;++k){
            int idx=numRows-1+2*k*(numRows-1);
            if(idx<s.size())
                ans.push_back(s[idx]);
        }
        return ans;
    }
};

7. Reverse Integer

描述

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

题解

  • 使用普通的/10和%10即可,注意由于int溢出,要在中间使用long long
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// Runtime: 4 ms, faster than 56.23% of C++ online submissions for Reverse Integer.
// Memory Usage: 5.9 MB, less than 82.94% of C++ online submissions for Reverse Integer.
class Solution {
public:
    int reverse(int x) {
        long long copy=x,res=0;
        bool neg=(copy<0);
        if(neg)
            copy=-copy;
        while(copy){
            res=10*res+copy%10;
            copy/=10;
        }
        if(neg)
            res=-res;
        if(res>INT_MAX || res<INT_MIN)
            return 0;
        return res;
    }
};

8. String to Integer (atoi)

描述

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned. Example 1:

1
2
Input: "42"
Output: 42

Example 2:

1
2
3
4
Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

1
2
3
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

1
2
3
4
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

1
2
3
4
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

题解

  • 使用for和break跳过开头的空格
  • 若第一个有效字符是负号则记录,符号之外的部分单独处理
  • 由于数值会溢出,故用long long存储结果,若检测到超出int范围的值则返回int的极限
  • 时间复杂度:遍历一次,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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Runtime: 0 ms, faster than 100.00% of C++ online submissions for String to Integer (atoi).
// Memory Usage: 6.2 MB, less than 55.89% of C++ online submissions for String to Integer (atoi).
class Solution {
public:
int myAtoi(string str) {
    long long res=0;
    int i=0;
    for(i=0;i<str.size();++i)
        if(str[i]!=' ')
            break;
    char first=str[i];
    if(first=='+' || first=='-' || (first>='0' && first<='9')){
        string pure;
        pure.push_back(first);
        ++i;
        while(i<str.size() && str[i]>='0' && str[i]<='9'){
            pure.push_back(str[i]);
            ++i;
        }
        int sign=1;
        if(pure[0]=='-' || pure[0]=='+'){
            if(pure[0]=='-')
                sign=-1;
            pure=pure.substr(1,pure.size()-1);
        }
        for(int num:pure){
            res=10*res+num-'0';
            if(res>INT_MAX)
                break;
        }
        res*=sign;
        cout<<res;
        if(res>INT_MAX)
            return INT_MAX;
        if(res<INT_MIN)
            return INT_MIN;
        return res;
    }
    return 0;
}
};

9. Palindrome Number

描述

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

1
2
Input: 121
Output: true

Example 2:

1
2
3
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

题解

  • 将数值转为字符串,取一半入栈,另一半若更长则丢弃第一个元素
  • 一边出栈一边比较与剩下的关系
  • 时间复杂度:O(n)
  • 空间复杂度:开辟了string和stack,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
// Runtime: 28 ms, faster than 24.74% of C++ online submissions for Palindrome Number.
// Memory Usage: 15.4 MB, less than 5.05% of C++ online submissions for Palindrome Number.
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        string str=to_string(x);
        stack<int> sta;
        int half_size=str.size()/2;
        for(int i=0;i<half_size;++i){
            sta.push(str[i]);
        }
        str=str.substr(half_size);
        if(str.size()>half_size)
            str=str.substr(1);
        for(int i=0;i<half_size;++i){
            if(sta.top()!=str[i])
                return false;
            sta.pop();
        }
        return true;
    }
};

10. Regular Expression Matching

描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

1
2
3
4
5
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

1
2
3
4
5
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

1
2
3
4
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

题解

解法1:递归

  • 每次将string和pattern同步向前推进,检查完当前是否匹配,就将问题递归地变为求后面的字串是否匹配
    • 递归终止条件是pattern被检查完,此时若string也被检查完则匹配
    • 走到一个位置时,检查当前位置是否匹配的方法是判断当前pattern是否等于当前string或'.'
    • 当pattern当前位置的下一个位置的值是'*'时,分两种情况:
      • '*'可能代表0个当前字符,直接将pattern向前推进2步,跳过当前字符和'*'
      • '*'可能代表1个或多个当前字符,首先检查当前字符是否匹配,匹配则将string向前推进1步
    • 当pattern当前位置的下一个位置的值不是'*'时,直接检查当前字符是否匹配,并将string和pattern同步向前推进
  • 时间复杂度:O((m+n)*2^(m+n/2))
  • 空间复杂度:O((m+n)*2^(m+n/2))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Runtime: 748 ms, faster than 5.88% of C++ online submissions for Regular Expression Matching.
// Memory Usage: 13.3 MB, less than 15.64% of C++ online submissions for Regular Expression Matching.
class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.size()==0) return s.size()==0;
        bool first_match= (s.size()!=0 && (p[0]==s[0] || p[0]=='.'));
        if(p.size()>=2 && p[1]=='*')
            return isMatch(s,p.substr(2)) || (first_match && isMatch(s.substr(1),p));
        else
            return first_match && isMatch(s.substr(1),p.substr(1));
    }
};

解法2:DP

  • 递归的问题在于冗余计算太多:当前位置的下一个位置是'*'时,需递归调用两次,其中包含重复的计算
  • DP使用二维数组dp[i][j]来标记string[:i-1]和pattern[:j-1]是否匹配。对于每个dp[i][j]:
    • 若当前[j-1]的pattern值不是'*',则需要上一个位置匹配即dp[i-1][j-1]==1,同时比较当前位置是否有p[j-1]==s[i-1]或'.'
    • 若当前[j-1]的pattern值是'*',则只需下列之一满足:
      • '*'代替0个[j-2]处的字符,即dp[i][j-2]==1
      • '*'代替1个[j-2]处的字符,即dp[i][j-1]==1
      • '*'代替多个[j-2]处的字符,需要该pattern和上一个位置的srting匹配即dp[i-1][j]==1,同时string的当前位置s[i-1]也能被’*‘代替的字符p[i-2]匹配即p[j-2]==s[i-1]或'.'
  • 时间复杂度:两层循环填充矩阵,O(m*n)
  • 空间复杂度:取决于矩阵大小,O(m*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
// Runtime: 4 ms, faster than 96.81% of C++ online submissions for Regular Expression Matching.
// Memory Usage: 6.7 MB, less than 62.19% of C++ online submissions for Regular Expression Matching.
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.length(),n=p.length();
        vector<vector<bool>> dp=vector(m+1,vector(n+1,false));
        dp[0][0]=true;
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p[j-1]!='*'){
                    if(i>0 && dp[i-1][j-1] && (p[j-1]==s[i-1] || p[j-1]=='.'))
                        dp[i][j]=true;
                }
                else if(j>1){
                    if(dp[i][j-1] || dp[i][j-2])
                        dp[i][j]=true;
                    else if(i>0 && dp[i-1][j] && (p[j-2]==s[i-1] || p[j-2]=='.'))
                        dp[i][j]=true;
                }
            }
        }
        return dp[m][n];
    }
};

11. Container With Most Water

描述

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

LeetCode11

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

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

题解

  • 双指针,最初指向两端,若一边高度比另一边小则指针向另一边移动。
  • 这样做能work的理由是,计算面积以较短的高度为准,一边较短时应调整较短的边
  • 时间复杂度:双指针走完全程,O(n)
  • 空间复杂度:O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// Runtime: 24 ms, faster than 98.66% of C++ online submissions for Container With Most Water.
// Memory Usage: 14.3 MB, less than 54.99% of C++ online submissions for Container With Most Water.
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0,j=height.size()-1;
        int max_area=0;
        while(i<j){
            int area=min(height[i],height[j])*(j-i);
            if(area>max_area)
                max_area=area;
            if(height[i]>height[j])
                --j;
            else
                ++i;
        }
        return max_area;
    }
};

12. Integer to Roman

描述

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: 3
Output: "III"

Example 2:

1
2
Input: 4
Output: "IV"

Example 3:

1
2
Input: 9
Output: "IX"

Example 4:

1
2
3
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

1
2
3
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

题解

  • 根据题意,实际上罗马数字只有13种符号,分别对应13种面值,只需从大到小依次取商和模即可
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// Runtime: 16 ms, faster than 57.17% of C++ online submissions for Integer to Roman.
// Memory Usage: 8.7 MB, less than 27.85% of C++ online submissions for Integer to Roman.
class Solution {
public:
    string intToRoman(int num) {
        string res;
        for(int idx=12;idx>=0;--idx){
            int div=num/nums[idx];
            num=num%nums[idx];
            for(int i=0;i<div;++i)
                res+=symbs[idx];
        }
        return res;
    }
private:
    vector<int> nums={1,4,5,9,10,40,50,90,100,400,500,900,1000};
    vector<string> symbs={"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
};

13. Roman to Integer

描述

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: "III"
Output: 3

Example 2:

1
2
Input: "IV"
Output: 4

Example 3:

1
2
Input: "IX"
Output: 9

Example 4:

1
2
3
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

1
2
3
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

题解

  • 根据上一道题,罗马数字只有13个符号,依次检测即可
  • 看到I、X、C时需要讨论是否是双字符的符号
 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: 36 ms, faster than 25.94% of C++ online submissions for Roman to Integer.
// Memory Usage: 12.8 MB, less than 5.00% of C++ online submissions for Roman to Integer.
class Solution {
public:
    int romanToInt(string s) {
        int idx=0,sum=0;
        while(idx<s.size()){
            if(s[idx]=='I')
                move(s,idx,sum,'V','X');
            else if(s[idx]=='X')
                move(s,idx,sum,'L','C');
            else if(s[idx]=='C')
                move(s,idx,sum,'D','M');
            else
                sum+=map[s.substr(idx++,1)];
        }
        return sum;
    }
private:
    unordered_map<string,int> map={{"I",1},{"IV",4},{"V",5},{"IX",9},{"X",10},
                                   {"XL",40},{"L",50},{"XC",90},{"C",100},{"CD",400},
                                   {"D",500},{"CM",900},{"M",1000}};
    void move(string &s,int &i,int &sum,char next1,char next2){
        int step=(i+1<s.size() && (s[i+1]==next1 || s[i+1]==next2))?2:1;
        sum+=map[s.substr(i,step)];
        i+=step;
    }
};

14. Longest Common Prefix

描述

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
4
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

题解

  • 先找到这一组字符串的最小长度,该长度作为遍历的范围
  • 维护一个计数,当所有字符串的该位相等时就+1
  • 每次使用一个bool来判断一位是否相等,检测到不相等就置为false,发生false时程序应该结束并返回目前的最大长度
  • 注意遍历vector中的string时要用const auto &,否则会发生拷贝,很慢
 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: 4 ms, faster than 98.72% of C++ online submissions for Longest Common Prefix.
// Memory Usage: 9.1 MB, less than 90.63% of C++ online submissions for Longest Common Prefix.
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty())
            return "";
        int min_len=INT_MAX,cnt=0;
        for(const auto &str:strs)
            if(str.size()<min_len)
                min_len=str.size();
        for(int i=0;i<min_len;++i){
            bool equal=true;
            char first_char=strs[0][i];
            for(const auto &str:strs)
                if(str[i]!=first_char){
                    equal=false;
                    break;
                }
            if(equal)
                ++cnt;
            else
                break;
        }
        return strs[0].substr(0,cnt);
    }
};

15. 3Sum

描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题解

  • 首先排序,固定一个数i,然后用双指针l和r搜索i右侧区域。遍历i
  • 当i大于0时退出循环,因为3个正数之和一定不为0
  • 搜索l和r时,若当前和<0则l太小,将其增大。反之若当前和>0则r太大,将其减小
  • 考虑去重:
    • 当前i等于上一个i时跳出一轮循环
    • 找到一个三元组时,将l/r跳出其右侧/左侧相等的范围
  • 时间复杂度:排序O(nlogn),每个i处双指针是O(n),总复杂度O(n^2+nlogn)
  • 空间复杂度: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
// Runtime: 84 ms, faster than 88.40% of C++ online submissions for 3Sum.
// Memory Usage: 19.7 MB, less than 77.66% of C++ online submissions for 3Sum.
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3)
            return {};
        vector<vector<int>> ans;
        std::sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;++i){
            if(nums[i]>0) break;
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1,r=nums.size()-1;
            while(l<r){
                if(nums[i]+nums[l]+nums[r]==0){
                    ans.push_back(vector({nums[i],nums[l++],nums[r--]}));
                    while(l<r && nums[l]==nums[l-1]) ++l;
                    while(l<r && nums[r]==nums[r+1]) --r;
                }
                else if(nums[i]+nums[l]+nums[r]<0)
                    ++l;
                else
                    --r;
            }
        }
        return ans;
    }
};

16. 3Sum Closest

描述

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

1
2
3
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

题解

  • 首先排序,固定一个数i,然后用双指针l和r搜索i右侧区域。遍历i
  • 维护一个最小的差min_diff,每当当前求和和target之差的绝对值小于它时更新
  • 当前求和太大时减小r,当前求和太小时增大l,以调整求和使其接近target
  • 时间复杂度:排序O(nlogn),每个i处双指针是O(n),总复杂度O(n^2+nlogn)
  • 空间复杂度: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: 8 ms, faster than 99.60% of C++ online submissions for 3Sum Closest.
// Memory Usage: 9.9 MB, less than 60.00% of C++ online submissions for 3Sum Closest.
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size()<3)
            return {};
        std::sort(nums.begin(),nums.end());
        int res=0,min_diff=INT_MAX;
        for(int i=0;i<nums.size()-2;++i){
            int l=i+1,r=nums.size()-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==target)
                    return target;
                int diff=abs(sum-target);
                if(diff<min_diff){
                    min_diff=diff;
                    res=sum;
                }
                if(sum>target)
                    --r;
                else if(sum<target)
                    ++l;
            }
        }
        return res;
    }
};

17. Letter Combinations of a Phone Number

描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

LeetCode17

Example:

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

题解

  • 使用DFS和回溯法
    • DFS用于搜索结果
    • 每当搜索到终点(输入字符串尾)时记录结果
    • 每一次DFS结束之后都移除该节点之后的搜索结果(回溯),继续讨论下一种可能情形
 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: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
// Memory Usage: 6.6 MB, less than 59.32% of C++ online submissions for Letter Combinations of a Phone Number.
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        DFS(digits,0);
        return res;
    }
private:
    unordered_map<char,string> map={{'0'," "},{'1',""},{'2',"abc"},{'3',"def"},
                                    {'4',"ghi"},{'5',"jkl"},{'6',"mno"},
                                    {'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string> res;
    string tmp;
    void DFS(const string &nums,int pos){
        //记录结果
        if(pos==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(auto c:map[nums[pos]]){
            tmp.push_back(c);
            DFS(nums,pos+1);
            //回溯
            tmp.pop_back();
        }
    }
};

18. 4Sum

描述

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题解

  • 类似3sum,前两个数用两层循环搜索,后两个数用双指针搜索
  • 考虑到已经排序,故重复的情况仅限于相同的四元组,而不存在不同顺序。故使用集合去重即可
  • 时间复杂度:两层for循环是O(n^2),双指针搜索是O(n),故总时间是O(n^3)
  • 空间复杂度: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
// Runtime: 68 ms, faster than 64.22% of C++ online submissions for 4Sum.
// Memory Usage: 13.5 MB, less than 32.80% of C++ online submissions for 4Sum.
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        std::sort(nums.begin(),nums.end());
        int N=nums.size();
        set<vector<int>> res;
        for(int i=0;i<N-3;++i){
            for(int j=i+1;j<N-2;++j){
                //双指针搜索
                int l=j+1,r=N-1;
                while(l<r){
                    int sum=nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target)
                        res.insert({nums[i],nums[j],nums[l++],nums[r--]});
                    else if(sum>target)
                        --r;
                    else
                        ++l;
                }
            }
        }
        return vector(res.begin(),res.end());
    }
};

19. Remove Nth Node From End of List

描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

题解

  • 使用dummy节点作为头节点之前的节点,双指针记录两个位置
  • 右侧的指针先走n步,之后双指针一起走,直到右侧的指针为空时左侧指针的位置即是倒数第n个
  • 维护一个左侧指针的before用于删除左侧指针
  • 时间复杂度:只遍历了一次,O(n)
  • 空间复杂度:O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// Runtime: 4 ms, faster than 84.05% of C++ online submissions for Remove Nth Node From End of List.
// Memory Usage: 10.8 MB, less than 5.09% of C++ online submissions for Remove Nth Node From End of List.
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy=new ListNode(0,head);
        ListNode *before=dummy,*left=head,*right=head;
        for(int i=0;i<n;++i)
            right=right->next;
        while(right){
            before=before->next;
            left=left->next;
            right=right->next;
        }
        before->next=left->next;
        delete left;
        return dummy->next;
    }
};

20. Valid Parentheses

描述

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

题解

  • 使用哈希表存储括号的配对,key为右括号,value为左括号
  • 使用栈来判断匹配:
    • 当读到的字符是右括号,即在哈希表的key中时,则判断栈顶是否为对应的value即左括号,若匹配则弹出
    • 当读到的字符是左括号,入栈
    • 读完字符串后若栈为空,则匹配成功
  • 时间复杂度:遍历一次,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
// Runtime: 4 ms, faster than 41.40% of C++ online submissions for Valid Parentheses.
// Memory Usage: 6.5 MB, less than 9.27% of C++ online submissions for Valid Parentheses.
class Solution {
public:
    bool isValid(string s) {
        stack<char> sta;
        unordered_map<char,char> map={{')','('},{'}','{'},{']','['}};
        for(char c:s){
            if(map.find(c)!=map.end()){
                if(sta.empty() || sta.top()!=map[c])
                    return false;
                sta.pop();
            } else
                sta.push(c);
        }
        if(sta.empty())
            return true;
        else
            return false;
    }
};