牛客-剑指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;
}
};