iii.run

128. Longest Consecutive Sequence

链接
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

方法一

unordered_map

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> used;
        for (auto i : nums) used[i] = false;
        int longest = 0;
        for (auto i : nums) {
            int length = 1;
            if (used[i]) continue;
            used[i] = true;
            for (int j = i + 1; used.find(j) != used.end(); j++) {
                used[j] = true;//用过了
                length++;
            }
            for (int j = i - 1; used.find(j) != used.end(); j--) {
                used[j] = true;
                length++;
            }
            longest = max(length, longest);
        }
        return longest;
    }
};

方法二

unordered_set

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int longest = 0;
        unordered_set<int> used(nums.begin(),nums.end());
        for (auto i : nums) {
            if (!used.count(i)) continue;
            used.erase(i);
            int pre = i - 1, next = i + 1;
            while (used.count(pre)) used.erase(pre--);
            while (used.count(next)) used.erase(next++);
            longest = max(longest, next - pre  - 1);
        }
        return longest;
    }
};

16. 3Sum Closest

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
``` cpp
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        double result = 1e9;
        double temp = 1e9;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        for (auto i = nums.begin(); i < last - 2; i++) {
            auto j = i + 1;
            if (i > nums.begin() && *i == *(i - 1)) i++;
            auto k = last - 1;
            while (j < k) {
                if (*i + *j + *k > target) {
                    if (abs(*i + *j + *k - target) < temp) {
                        temp = abs(*i + *j + *k - target);
                        result = *i + *j + *k;
                    }
                    --k;
                    while (j < k&& *k == *(k + 1)) --k;
                }
                else if(*i + *j + *k < target){
                    if (abs(*i + *j + *k - target) < temp) {
                        temp = abs(*i + *j + *k - target);
                        result = *i + *j + *k;
                    }
                    ++j;
                    while (j < k&& *j == *(j - 1)) ++j;
                }
                else {
                    return target;
                }
            }
        }
        return result;
    }
};

跟上个题思路一样，从两边开始往中间夹逼。

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if (nums.size() < 4) return result;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        for (auto a = nums.begin(); a < prev(last, 3); ++a) {
            for (auto b = next(a); b < prev(last, 2); ++b) {
                auto c = next(b);
                auto d = prev(last);
                while (c < d) {
                    if (*a + *b + *c + *d < target) {
                        ++c;
                    }
                    else if (*a + *b + *c + *d > target) {
                        --d;
                    }
                    else {
                        result.push_back({ *a, *b, *c, *d });
                        ++c;
                        --d;
                    }
                }
            }
        }
        sort(result.begin(), result.end());
        //result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};

注意消除重复元素

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,

"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

class Solution {
public:
    bool isPalindrome(string s) {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        auto left = s.begin(), right = prev(s.end());
        while (left < right) {
            if (!isalnum(*left)) left++;
            else if (!isalnum(*right)) right--;
            else if (*left != *right) return false;
            else left++, right--;
        }
        return true;
    }
};

28. 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:

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

Example 2:

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

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;

        int N = haystack.size() - needle.size() + 1;
        for (int i = 0; i < N; i++) {
            int k = i;//从i这一位开始对比
            int j = 0;
            while (k < haystack.size() && j < needle.size() && haystack[k] == needle[j]) {
                k++;
                j++;
            }
            if (j == needle.size()) return i;
        }
        return -1;
    }
};