牛客-剑指offer题解第一阶段

考察点汇总

数组，贪心，二分，归并排序，动态规划

二维数组中的查找

题目

考察点：思路

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0)
            return false;
        if(array[0].size()==0)
            return false;
        int n=array.size();
        int m=array[0].size();
        for(int i=0,j=m-1;i<n&&j>=0;)
        {
            if(target>array[i][j])
                i++;
            else if(target<array[i][j])
                j--;
            else
                return true;
        }
        return false;
    }
};

旋转数组的最小数字

题目

考察点：二分

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left=0,right=rotateArray.size()-1;
        while(left<right)
        {
            int mid=(left+right)/2;
            if(rotateArray[mid]>rotateArray[right])
                left=mid+1;
            else if(rotateArray[mid]<rotateArray[right])
                right=mid;
            else
                right--;
        }
        return rotateArray[left];
    }
};

调整数组顺序使奇数位于偶数前面

题目

考察点：思路

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        int n=array.size();
        vector<int> array1(n);
        int odd=0;
        for(int i=0;i<n;i++)
            if(array[i]%2)
                odd++;
        int index1=0,index2=odd;
        for(int i=0;i<n;i++)
        {
            if(array[i]%2)
                array1[index1++]=array[i];
            else
                array1[index2++]=array[i];
        }
        return array1;
    }
};

顺时针打印矩阵

题目

考察点：思路

class Solution {
  public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if (matrix.size() == 0)
            return res;
        int up = 0;
        int down = matrix.size() - 1;
        int left = 0;
        int right = matrix[0].size() - 1;
        while (up <= down && left <= right) {
            for (int i = left; i <= right; i++)
                res.push_back(matrix[up][i]);
            up++;
            if (up > down)
                break;

            for (int i = up; i <= down; i++)
                res.push_back(matrix[i][right]);
            right--;
            if (left > right)
                break;

            for (int i = right; i >= left; i--)
                res.push_back(matrix[down][i]);
            down--;
            if (up > down)
                break;

            for (int i = down; i >= up; i--)
                res.push_back(matrix[i][left]);
            left++;
            if (left > right)
                break;
        }
        return res;
    }
};

数组中出现次数超过一半的数

题目

考察点：哈希，思路

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n=numbers.size();
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++)
        {
            mp[numbers[i]]++;
            if(mp[numbers[i]]>n/2)
                return numbers[i];
        }
        return 0;
    }
};

连续子数组的最大和

题目

考察点：动态规划，贪心

class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        vector<int> dp(n, 0);
        dp[0] = array[0];
        int maxn=dp[0];
        for (int i = 1; i < n; i++)
        {
            dp[i]=max(dp[i-1]+array[i],array[i]);
            maxn=max(maxn,dp[i]);
        }
        return maxn;
    }
};

把数组排成最小的数

题目

考察点：贪心，排序

class Solution {
public:
    static bool cmp(string a,string b){
        return a+b<b+a;
    }
    //C++11的话直接用to_string(int n)
    static string toString(int n){
        if(n==0)
            return "0";
        string str="";
        int m;
        while(n){
            m=n%10;
            n/=10;
            str+=('0'+m);
        }
        reverse(str.begin(),str.end());
        return str;
    }
    string PrintMinNumber(vector<int> numbers) {
        string res="";
        vector<string> strs;
        for(int i=0;i<numbers.size();i++)
            strs.push_back(toString(numbers[i]));
        sort(strs.begin(),strs.end(),cmp);
        for(int i=0;i<strs.size();i++)
            res+=strs[i];
        return res;
    }
};

数组中的逆序对

题目

考察点：归并排序

class Solution {
  public:
    int mod = 1000000007;
    int merge(int left, int right, vector<int>& data, vector<int>& temp) {
        //终止条件
        if (left >= right)
            return 0;
        //为防止left+right超出整形范围可以这样写left+(right-left)/2
        int mid = (left + right) / 2;
        int res = merge(left, mid, data, temp) + merge(mid + 1, right, data, temp);
        res %= mod;
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++)
            temp[k] = data[k];
        for (int k = left; k <= right; k++) {
            if (i == mid + 1)
                data[k] = temp[j++];
            else if (j == right + 1 || temp[i] < temp[j])
                data[k] = temp[i++];
            else{
                data[k] = temp[j++];
                res += mid + 1 - i;
            }
        }
        return res%mod;
    }
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> temp(n);
        return merge(0, n - 1, data, temp);
    }
};

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

题目

考察点：二分

class Solution {
public:
    int find(vector<int>& data,double k){
        int left=0;
        int right=data.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(data[mid]>k)
                right=mid-1;
            else
                left=mid+1;
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        return find(data,k+0.5)-find(data,k-0.5);
    }
};

数组中只出现过一次的两个数字

题目

考察点：位运算，哈希

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        unordered_map<int,int> mp;
        vector<int> res;
        for(int i=0;i<array.size();i++)
            mp[array[i]]++;
        for(int i=0;i<array.size();i++)
            if(mp[array[i]]==1)
                res.push_back(array[i]);
        if(res[0]<res[1])
            return res;
        return {res[1],res[0]};
    }
};

数组中的重复数字

题目

考察点：思路

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        set<int> res;
        for(int i=0;i<numbers.size();i++)
            if(!res.insert(numbers[i]).second) return numbers[i];
        return -1;
    }
};

构建乘积数组

题目

考察点：思路

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(),1);
        //前缀和
        for(int i=1;i<A.size();i++)
            res[i]=res[i-1]*A[i-1];

        //后缀和
        int ans=1;
        for(int i=A.size()-1;i>=0;i--){
            res[i]*=ans;
            ans*=A[i];
        }
        return res;
    }
};