剑指offer-搜索算法

1.数字在升序数组中出现的次数

实现函数lower_bound和upper_bound

    int GetNumberOfK(vector<int> nums ,int k) {
        if (nums.empty()) return 0;
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < k) l = mid + 1;
            else r = mid;
        }
        int idx1 = l;
        if (nums[l] != k) return 0;
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > k) r = mid - 1;
            else l = mid;
        }
        int idx2 = l;
        return idx2 - idx1 + 1;
    }

2.二维数组中的查找

    bool Find(int target, vector<vector<int> > array) {
        if (array.empty()) return false;
        int m = array.size(), n = array[0].size();
        int i = 0, j = n - 1;
        while (i < m and j >= 0) {
            if (target == array[i][j]) return true;
            else if (target < array[i][j]) --j;
            else ++i;
        }
        return false;
    }

3.旋转数组的最小数字

    int minNumberInRotateArray(vector<int> rotateArray) {
        int l = 0, r = rotateArray.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (rotateArray[mid] < rotateArray[r]) r = mid;
            else if (rotateArray[mid] > rotateArray[r]) l = mid + 1;
            else --r;
        }
        return rotateArray[l];
    }

4.字符串排列

class Solution {
    set<string> res;
    void dfs(int idx, string& str) {
        if (idx == str.size() - 1) {
            res.insert(str);
            return;
        }
        for (int i = idx; i < str.size(); ++i) {
            swap(str[idx], str[i]);
            dfs(idx + 1, str);
            swap(str[idx], str[i]);
        }
    }
public:
    vector<string> Permutation(string str) {
        dfs(0, str);
        return vector<string>(res.begin(), res.end());
    }
};

5.数字序列中的某一位数字

挺难的...

    int findNthDigit(int n) {
        //只有一位，一位数有9个，一位的基数是1,n是剩余的位数
        long long i = 1, s = 9, base = 1;
        while (n > i * s) {
            n -= i * s;
            ++i;
            s *= 10;
            base *= 10;
        }
        int num = base + (n + i - 1) / i - 1;
        int rest = n % i ? n % i : i;
        for (int j = 0; j < i - rest; ++j) {
            num /= 10;
        }
        return num % 10;
    }