Ascendlogo

Posted on Edited on In

392.Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

1
2
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

1
2
Input: s = "axc", t = "ahbgdc"
Output: false

双指针：

时间复杂度：O(n+m)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == n;
    }
};

动态规划：

时间复杂度：O(m*S+n)，S为字符集大小

空间复杂度：O(m*s)

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
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();

        vector<vector<int> > f(m + 1, vector<int>(26, 0));
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t[i] == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s[i] - 'a'] == m) {
                return false;
            }
            add = f[add][s[i] - 'a'] + 1;
        }
        return true;
    }
};

Posted on Edited on In

389.Find the Difference

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

1
2
3
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

1
2
Input: s = "", t = "y"
Output: "y"

哈希表：

时间复杂度：O(n)

空间复杂度：O(S)，S表示字符集大小。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char,int> set;
        for (char ch : s)set[ch]++;
        for (char ch : t) {
            if (set[ch])set[ch]--;
            else return ch;
        }
        return ' ';
    }
};

求和：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for (char ch: s) {
            as += ch;
        }
        for (char ch: t) {
            at += ch;
        }
        return at - as;
    }
};

位运算：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int ret = 0;
        for (char ch: s) {
            ret ^= ch;
        }
        for (char ch: t) {
            ret ^= ch;
        }
        return ret;
    }
};

Posted on Edited on In

387.First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

1
2
Input: s = "leetcode"
Output: 0

Example 2:

1
2
Input: s = "loveleetcode"
Output: 2

Example 3:

1
2
Input: s = "aabb"
Output: -1

哈希表存储频数：

时间复杂度：O(n)

空间复杂度：O(S)，S为字符集大小，本题中S不大于26。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> frequency;
        for (char ch: s) {
            ++frequency[ch];
        }
        for (int i = 0; i < s.size(); ++i) {
            if (frequency[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};

哈希表存储索引：

时间复杂度：O(n)

空间复杂度：O(S)，S为字符集大小，本题中S不大于26。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> position;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (position.count(s[i])) {
                position[s[i]] = -1;
            }
            else {
                position[s[i]] = i;
            }
        }
        int first = n;
        for (auto [_, pos]: position) {
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        if (first == n) {
            first = -1;
        }
        return first;
    }
};

队列：

时间复杂度：O(n)

空间复杂度：O(S)，S为字符集大小，本题中S不大于26。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            }
            else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

Posted on Edited on In

383.Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

1
2
Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

1
2
Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

1
2
Input: ransomNote = "aa", magazine = "aab"
Output: true

时间复杂度：O(m+n)
空间复杂度：O(S)，S为字符集大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        vector<int> cnt(26);
        for (auto & c : magazine) {
            cnt[c - 'a']++;
        }
        for (auto & c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

Posted on Edited on In

374.Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

  • -1: Your guess is higher than the number I picked (i.e. num > pick).
  • 1: Your guess is lower than the number I picked (i.e. num < pick).
  • 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:

1
2
Input: n = 10, pick = 6
Output: 6

Example 2:

1
2
Input: n = 1, pick = 1
Output: 1

Example 3:

1
2
Input: n = 2, pick = 1
Output: 1

二分法：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int guessNumber(int n) {
        int left = 0;
        int right = n;
        while(1) {
            int mid = left + (right - left)/2;
            if(guess(mid) == 1)left = mid + 1;
            else if(guess(mid) == -1) right = mid;
            else return mid;
        }

    }
};

Posted on Edited on In

367.Valid Perfect Square

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Example 1:

1
2
3
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

1
2
3
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

暴力法：

时间复杂度：O(√n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isPerfectSquare(int num) {
        long n = 1;
        while(n*n<=num) {
            if(n*n == num)return true;
            n++;
        }
        return false;
    }
};

内置函数法：

1
2
3
4
5
6
7
class Solution {
public:
    bool isPerfectSquare(int num) {
        int x = (int) sqrt(num);
        return x * x == num;
    }
};

二分法：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            long square = (long) mid * mid;
            if (square < num) {
                left = mid + 1;
            } else if (square > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

牛顿迭代法：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
};

Posted on Edited on In

350.Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

1
2
3
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

双指针：

时间复杂度：O(mlogm+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
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        int index1 = 0, index2 = 0;
        vector<int> intersection;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                intersection.push_back(num1);
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return intersection;
    }
};

哈希表：

时间复杂度：O(m+n)

空间复杂度：O(min(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
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        unordered_map <int, int> m;
        for (int num : nums1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};

Posted on Edited on In

349.Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

1
2
3
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

哈希表：

时间复杂度：O(n+m)

空间复杂度：O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        unordered_set<int> set1;
        unordered_set<int> set2;
        for (int num : nums1)set1.insert(num);
        for (int num : nums2)set2.insert(num);
        if (set1.size() > set2.size())swap(set1, set2);
        for (int num : set1) {
            if (set2.count(num))ans.push_back(num);
        }
        return ans;
    }
};

双指针：

时间复杂度：O(nlogn+mlogm)

空间复杂度：O(nlogn+mlogm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        int index1 = 0, index2 = 0;
        vector<int> intersection;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (!intersection.size() || num1 != intersection.back()) {
                    intersection.push_back(num1);
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return intersection;
    }
};

Posted on Edited on In

345.Reverse Vowels of a String

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

1
2
Input: s = "hello"
Output: "holle"

Example 2:

1
2
Input: s = "leetcode"
Output: "leotcede"

双指针：

时间复杂度：O(n)

空间复杂度：O(10)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<int> set = { 'a','e','i','o','u','A','E','I','O','U' };
        for (int left = 0, right = s.size() - 1; 
             left < right; left++, right--) {
            while(!set.count(s[left])&&(left < right))left++;
            while(!set.count(s[right])&&(left < right))right--;
            swap(s[left], s[right]);
        }
        return s;
    }
};

Posted on Edited on In

344.Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

1
2
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

时间复杂度：O(n/2)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reverseString(vector<char>& s) {
        int s_size = s.size();
        for (int i = 0; i < s_size / 2; i++) {
            swap(s[i], s[s_size - i - 1]);
        }
    }
};