Binary Search

14. Longest Common Prefix

这一题有好多解法, 比较精彩的两种是二分查找和分治法

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

二分查找:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int max_len = INT_MAX;
        string res;
        if (strs.size() == 0) return res;
        for (auto str : strs) if (max_len > str.size()) max_len = str.size();

        int start = 1;
        int end = max_len;
        int common_len = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (isCommonPrefix(strs, mid)) {
                common_len = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return strs[0].substr(0, common_len);

    }

    bool isCommonPrefix(vector<string>& strs, int len) {
        if (len < 0) return false;
        string target = strs[0].substr(0, len);
        for (auto str : strs) {
            if (str.substr(0, len) != target) return false;
        }
        return true;
    }
};

29. Divide Two Integers

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;

        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;

        long dvd = labs(dividend);
        long dvs = labs(divisor);
        int res = 0;

        while (dvd >= dvs) {
            long tmp = dvs;
            long multipule = 1;
            while (dvd >= (tmp << 1)) {
                tmp <<= 1;
                multipule <<= 1;
            }

            dvd -= tmp;
            res += multipule;
        }

        return sign == 1 ? res : -res;
    }
};

33. Search in Rotated Sorted Array

先找到 Rotate 的地方, 然后在进行常规的二分.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        if (!len) return -1;
        int start = 0;
        int end = len - 1;
        int ret = start;
        while (start <= end && nums[start] > nums[end]) {
            int mid = start + (end - start) / 2;
            if (nums[start] > nums[mid]) {
                end = mid - 1;
                ret = mid;
            } else {
                start = mid + 1;
                ret = start;
            }
        }

        int rot = ret;
        ret = 0;
        start = 0;
        end = len - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int real_mid = (mid + rot) % len;
            if (nums[real_mid] >= target) {
                ret = real_mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (nums[ret] == target) return ret;
        return -1;
    }
};

50. Pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;

        int sign = n > 0;
        n = abs(n);
        if (sign) return absPow(x, n);
        else return (1/absPow(x, n));
    }

    double absPow(double x, int n) {
        if (n==0) return 1;

        double res = absPow(x, n/2);
        res *= res;
        if (n&1) res *= x;
        return res;
    }
};

69. Sqrt(x)

class Solution {
public:
    int mySqrt(int x) {
        if (x < 0) return 0;

        int start = 0;
        int end = x;
        int pos = -1;
        while (start <= end) {
            long long mid = start + (end - start) / 2;
            if (mid * mid <= static_cast<long long>(x)) {
                pos = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
                pos = end;
            }
        }

        return pos;
    }
};

154. Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why? Suppose a sorted array 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).

Find the minimum element.

The array may contain duplicates.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        if (!len) return -1;
        int start = 0;
        int end = len - 1;
        while (start < end && nums[start] >= nums[end]) {
            int mid = start + (end - start) / 2;
            if (nums[start] > nums[mid]) {
                end = mid;
            } else if (nums[mid] > nums[end]) {
                start = mid + 1;
            } else {
                ++start;
            }
        }

        return nums[start];
    }
};

275. H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

class Solution {
public:
    int hIndex(vector<int>& citations) {
         int len = citations.size();
         if (!len) return 0;

         int start = 0;
         int end = len - 1;
         int res = start;
         while (start <= end) {
             int mid = start + (end - start) / 2;
             if (len - mid <= citations[mid]) {
                 res = len - mid;
                 end = mid - 1;
             } else {
                 start = mid + 1;
             }
         }

         return res;
    }
};

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() < 2) return -1;
        int len = nums.size();
        int start = 1;
        int end = nums.size() - 1;
        int target = 0;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            int count = 0;
            for (int i = 0; i < len; ++i) {
                if (nums[i] <= mid) count++;
            }

            if (count > mid) {
                end = mid - 1;
                target = mid;
            } else {
                start = mid + 1;
            }
        }

        return target;
    }
};

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> sequence;
        for (auto num : nums) {
            auto it = lower_bound(sequence.begin(), sequence.end(), num);
            if (it == sequence.end()) sequence.push_back(num);
            else *it = num;
        }
        return sequence.size();
    }
};

334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples: Given [1, 2, 3, 4, 5], r>eturn true.

Given [5, 4, 3, 2, 1], return false.

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int c1 = INT_MAX, c2 = INT_MAX;
        for (auto num : nums) {
            if (num <= c1) c1 = num;
            else if (num <= c2) c2 = num;
            else return true;
        }
        return false;
    }
};

302 Smallest Rectangle Enclosing Black Pixels

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
  "0010",
  "0110",
  "0100"
]

and x = 0, y = 2, Return 6.

class Solution_v2 {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int height = image.size();
        if (!height) return 0;
        int width = image[0].size();
        if (!width) return 0;

        int left = find_lowerbound(image, 0, y, this->hasBlackPixelinCol);
        int right = find_upperbound(image, y, width-1, hasBlackPixelinCol);
        int top = find_lowerbound(image, 0, x, hasBlackPixelinRow);
        int bottom = find_upperbound(image, x, height-1, hasBlackPixelinRow);
        // cout << "left: " << left << ", right" << right << ", top:" << top << ", bottom: " << bottom << endl;
        return (right - left + 1) * (bottom - top + 1);
    }

    static bool hasBlackPixelinRow(vector<vector<char>>& image, int row) {
        for (size_t i = 0; i < image[row].size(); ++i) {
            if (image[row][i] == '1') return true;
        }
        return false;
    }

    static bool hasBlackPixelinCol(vector<vector<char>>& image, int col) {
        for (size_t i = 0; i < image.size(); ++i) {
            if (image[i][col] == '1') return true;
        }

        return false;
    }

    int find_lowerbound(vector<vector<char>>& image, int start, int end, function<bool(vector<vector<char>>& image, int x)> cmp) {
        int ret = end;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (cmp(image, mid)) {
                ret = mid;
                // cout << "ret: " << ret << endl;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        // cout <<"return ret: " << ret << endl;
        return ret;
    }

    int find_upperbound(vector<vector<char>>& image, int start, int end, function<bool(vector<vector<char>>& image, int x)> cmp) {
        int ret = start;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (cmp(image, mid)) {
                ret = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ret;
    }
};

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Return the array [2, 1, 1, 0].

struct BSTreeNode {
    BSTreeNode* left = nullptr;
    BSTreeNode* right = nullptr;
    int val = 0;
    int cnt = 0;

    BSTreeNode(int val, int cnt) : val(val), cnt(cnt) {}
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        size_t len = nums.size();
        vector<int> res(len);
        if (!len) return res;
        BSTreeNode* root = nullptr;
        for (size_t i = len; i != 0; --i) {
            root = insert(root, nums[i-1], res, i-1, 0);
        }

        return res;
    }

    BSTreeNode* insert(BSTreeNode* root, int val, vector<int>& res, size_t index, int preSum) {
        if (!root) {
            root = new BSTreeNode(val, 0);
            res[index] = preSum;
        } else if (val < root->val) {
            root->cnt++;
            root->left = insert(root->left, val, res, index, preSum);
        } else {
            int sum  = root->val == val ? preSum + root->cnt : preSum + root->cnt + 1;
            root->right = insert(root->right, val, res, index, sum);
        }
        return root;
    }
};

354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example: Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](pair<int, int>&a, pair<int, int>&b){
            return a.first == b.first ? a.second > b.second : a.first < b.first;
        });
        vector<int> heights;
        size_t i = 0;
        while (i < envelopes.size()) {
            int cur = envelopes[i].second;
            heights.push_back(cur);
            ++i;
        }
        vector<int> res;
        for (auto h : heights) {
            auto it = lower_bound(res.begin(), res.end(), h);
            if (it == res.end()) {
                res.push_back(h);
            } else {
                *it = h;
            }
        }
        return res.size();
    }
};

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

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

Example 1:

 s = "abc", t = "ahbgdc"

Return true.

Example 2:

 s = "axc", t = "ahbgdc"

Return false.

Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

class Solution {
public:
    bool isSubsequence(string s, string t) {
        unordered_map<char, set<size_t>> ch_idx;
        for (size_t i = 0; i < t.size(); ++i) {
            ch_idx[t[i]].insert(i);
        }

        int idx = 0;
        for (auto c : s) {
            if (ch_idx.find(c) == ch_idx.end()) return false;
            auto it = ch_idx[c].lower_bound(idx);
            if (it == ch_idx[c].end()) return -1;
            idx = (*it) + 1;
        }
        return true;
    }
};